David R. Cheriton School of Computer Science
University of Waterloo
Monday, 13 June 2011, 14:00 (note the unusual weekday)
Cybernetica Bldg (Akadeemia tee 21), room B101
Slides from the talk [pdf]
Abstract: The state complexity of a regular language L is the number of states in the minimal deterministic finite automaton A accepting L. The syntactic complexity of L is the cardinality of its syntactic semigroup, and it is the same as the cardinality of the transformation semigroup of A. The syntactic complexity of a subclass C of regular languages is the worst-case syntactic complexity taken as a function of the state complexity of languages in C.
A survey of the recent results on syntactic complexity will be presented. The classes studied include prefix-, suffix-, and bifix-free languages; prefix-, suffix-, and factor-closed languages (which are the same as left, right, and two-sided ideals, respectively); and star-free languages.
Janusz Brzozowski's visit to Tallinn and Tartu is supported by the ETF under grant no. 7520.