On transition minimality of bideterministic automata

Hellis Tamm

Institute of Cybernetics

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