CIAA2003

START ConferenceManager

Bideterministic automata and minimal representations of regular languages

Hellis Tamm and Esko Ukkonen

Presented at Eighth International Conference on Implementation and Application of Automata (CIAA 2003), July 16-18, 2003 Santa Barbara, CA, USA

Abstract

Bideterministic automata are deterministic automata with the property of their reversal automata also being deterministic. It has been known that a bideterministic automaton is the minimal deterministic automaton accepting its language. This paper shows that any bideterministic automaton is the unique minimal automaton among all (including nondeterministic) automata accepting the same language. We also present a more general result that shows that under a certain condition a minimal deterministic automaton accepting some language or the reversal of the minimal deterministic automaton of the reversal language is a minimal automaton representation of the language. This condition can be checked in polynomial time.