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
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.