2002 | OriginalPaper | Buchkapitel
Partially-Ordered Two-Way Automata: A New Characterization of DA
verfasst von : Thomas Schwentick, Denis Thérien, Heribert Vollmer
Erschienen in: Developments in Language Theory
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper,we consider finite automata with the restriction that whenever the automaton leaves a state it never returns to it. Equivalently we may assume that the states set is partially ordered and the automaton may never move “backwards” to a smaller state. p] We show that different types of partially-ordered automata characterize different language classes between level 1 and 3/2 of the Straubing-Thérien-Hierarchy. p] In particular, we prove that partially-ordered 2-way DFAs recognize exactly the class UL of unambiguous languages introduced by Schützenberger in 1976. As shown by Schützenberger, this class coincides with the class of those languages whose syntactic monoid is in the variety DA, a specific subclass of all “groupfree” (or “aperiodic”) semigroups.DA has turned out to possess a lot of appealing characterizations. Our result adds one more to these: partially-ordered two-way automata recognize exactly those languages whose syntactic monoid is in DA.