Hierarchy Among Automata on Linear Orderings
Véronique Bruyère, Olivier Carton · 2002
In a preceding paper, automata and rational expressions have been introduced for words indexed by linear orderings, together with a Kleene-like theorem. We here pursue this work by proposing a hierarchy among the rational sets. Each class of the hierarchy is defined by a subset of the rational operations that can be used. We then characterize any class by an appropriate class of automata, leading to a Kleene theorem inside the class. A characterization by particular classes of orderings is also given. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.