Hierarchy among Automata on Linear Orderings
Bruyère , Véronique
Carton , Olivier
- Publisher: Springer Verlag
[ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
acm: TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES | ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
arxiv: Computer Science::Formal Languages and Automata Theory
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.