Affordable Access

Hierarchy among Automata on Linear Orderings

Authors
Publication Date
Source
Hal-Diderot
Keywords
  • [Info.Info-Ds] Computer Science [Cs]/Data Structures And Algorithms [Cs.Ds]
External links

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments