## Syntactic complexity of regular languages

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.

Tarmo Uustalu

Last update 13.6.2011