|Abstract of Paper|
Unambiguous automata on bi-infinite words
by Olivier Carton
In this paper, we address the problem of ambiguity for automata accepting bi-infinite words. We introduce unambiguous automata where each accepted word is the label of exactly one accepting path. We show that any automaton on bi-infinite words is equivalent to an unambiguous one. We actually prove two results, a specific one for rational sets that are shift invariant and one for all rational sets. The former one holds for automata with a simple and natural acceptance mode which is only suitable for shift invariant sets. The latter one holds for automata with a more powerful acceptance mode suited to all rational sets. This result is also stronger because it states the existence of automata that are unambiguous and complete. There was no counterpart of McNaughton's result for automata on bi-infinite words. Our result fills this gap.