Epsilon Automata on Linear Orderings
摘要
Automata on linear orderings are a form of finite-state automata introduced by Bruyère and Carton, that generalize the concepts of finite-word, infinite-word, and transfinite-word automata. They recognize words indexed by linear orderings, defined as mappings from the elements of such orderings to a finite alphabet. Some theoretical developments involving automata on linear orderings are hindered by the fact that their definition does not allow epsilon transitions, i.e., transitions with an empty label. In this paper, we define a variant of automata on linear orderings that allows such transitions in their transition relation, and show that this extension does not modify the expressive power of the automata. We motivate the usefulness of epsilon automata on linear orderings by using them for correcting an erroneous construction in the original proof of equivalence between automata on linear orderings and the corresponding notion of regular expressions.