Quotient complexity of regular languages

Janusz Brzozowski

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