Anzeige
Erschienen in:
01.05.2015
Omega-Rational Expressions with Bounded Synchronization Delay
Erschienen in: Theory of Computing Systems | Ausgabe 4/2015
EinloggenAktivieren 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
Abstract
In 1965 Schützenberger published his famous result that star-free languages (\(\operatorname{SF}\)) and aperiodic languages (\(\operatorname{AP}\)) coincide over finite words, often written as \(\operatorname{SF}= \operatorname {AP}\). Perrin generalized \(\operatorname{SF} = \operatorname{AP}\) to infinite words in the mid 1980s. In 1973 Schützenberger presented another (and less known) characterization of aperiodic languages in terms of rational expressions where the use of the star operation is restricted to prefix codes with bounded synchronization delay and no complementation is used. We denote this class of languages by \(\operatorname{SD}\). In this paper, we present a generalization of \(\operatorname{SD}= \operatorname{AP}\) to infinite words. This became possible via a substantial simplification of the proof for the corresponding result for finite words. Moreover, we show that \(\operatorname{SD}= \operatorname{AP}\) can be viewed as more fundamental than \(\operatorname{SF}= \operatorname{AP}\) in the sense that the classical 1965 result of Schützenberger and its 1980s extension to infinite words by Perrin are immediate consequences of \(\operatorname{SD}= \operatorname{AP}\).