2004 | OriginalPaper | Buchkapitel
Complementation of Rational Sets on Scattered Linear Orderings of Finite Rank
verfasst von : Olivier Carton, Chloé Rispal
Erschienen in: LATIN 2004: Theoretical Informatics
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 a preceding paper (Bruyère and Carton, automata on linear orderings, MFCS’01), automata have been introduced for words indexed by linear orderings. These automata are a generalization of automata for finite, infinite, bi-infinite and even transfinite words studied by Büchi. Kleene’s theorem has been generalized to these words. We show that deterministic automata do not have the same expressive power. Despite this negative result, we prove that rational sets of words of finite ranks are closed under complementation.