## Quotient complexity of regular languages

David R. Cheriton School of Computer Science

University of Waterloo

Thursday, 9 June 2011, 14:00

Cybernetica Bldg (Akadeemia tee 21), room B101

Slides from the talk [pdf]

**Abstract**: The quotient complexity of a regular language
*L* is the number of left quotients of *L*. The state
complexity of *L* is the number of states in the minimal
deterministic finite automaton recognizing *L*. While these two
numbers are the same for any language, there are some advantages to
using quotients.

The quotient complexity of a binary operation *f* in a
subclass *C* of regular languages is the maximal quotient
complexity of the language * taken as a function of the
quotient complexities of **K* and *L*, as
*K* and *L* range over all the languages in *C*. For
most operations one can find a formula for the typical quotient of
*f(K,L)* in terms of the quotients of *K* and *L*. To
obtain an upper bound on the number of quotients of *f(K,L)* all
one has to do is count how many such quotients are possible.

These ideas will be illustrated with several examples, and a
survey of the recent results on the complexity of union, intersection,
difference, symmetric difference, concatenation, star, and reversal
for many classes of regular languages will be given. The classes
include finite languages; prefix-, suffix-, bifix-, factor-, and
subword-free languages; prefix-, suffix-, factor-, and subword-closed
languages; left, right, two-sided, and all-sided ideals; 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