Abstract of Paper

Unambiguous automata on bi-infinite words
by Olivier Carton

Abstract:

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.