Thursday, 10 May 2007, 14:00

Cybernetica Bldg (Akadeemia tee 21), room B101

Slides from the talk [pdf]

**Abstract**: In automata theory, problems related to
descriptional complexity issues have been of interest for decades. For
example, it is long and well known that the deterministic state
complexity, that is, the number of states of the minimal deterministic
finite automaton (DFA) for a given language, can be exponentially
larger than the nondeterministic state complexity -- the number of
states in a minimal nondeterministic finite automaton (NFA). But
obviously, there are many cases where the maximal blow-up of size when
converting an NFA to DFA does not occur.

It has been shown earlier that every bideterministic automaton -- which is any deterministic automaton such that its reversal automaton is also deterministic -- is the unique state-minimal NFA accepting its language. Since a bideterministic automaton was also known to be the minimal DFA, it was thus established that for any language accepted by a bideterministic automaton, the deterministic and nondeterministic state complexities coincide.

While the state-minimal DFA is also minimal with respect to the number of transitions, this is not necessarily the case with NFAs. Vice versa, even allowing one more state in an NFA can produce a considerable reduction in the number of transitions. Therefore, the number of transitions may be even a better measure for the size of an NFA than the number of states. Furthermore, it is well known that by allowing ε-transitions in an NFA (called ε-NFA) it is possible to construct automata with even less transitions than NFAs.

In this talk, we present some transition complexity results for bideterministic automata, in addition to the earlier state complexity result. First, we show that a bideterministic automaton is a transition-minimal NFA. However, as this transition minimality is not necessarily unique, we also present the necessary and sufficient conditions for a bideterministic automaton to be uniquely transition-minimal among NFAs. These results are derived using a canonical automaton, called universal automaton of a regular language.

And second, we show that a bideterministic automaton is a transition-minimal ε-NFA. This more general result is obtained by applying the theory for finding transition-minimal ε-NFAs developed by S. John, to bideterministic automata.

This talk is based on a paper to be presented at the conference of Developments in Language Theory (DLT 2007), Turku, July 2007.

Tarmo Uustalu

Last update 6.5.2007