2008 | OriginalPaper | Buchkapitel
Well Quasi-orders in Formal Language Theory
verfasst von : Flavio D’Alessandro, Stefano Varricchio
Erschienen in: Developments in Language Theory
Verlag: Springer Berlin Heidelberg
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
The concept of well quasi-order is a generalization of the classical notion of well order and plays a role in the studying of several problems of Mathematics and Theoretical Computer Science. This paper concerns some applications of well quasi-orders to Formal Language Theory. In particular, we present a survey of classical and recent results, based upon such structures, concerning context-free and regular languages. We also focus our attention to some application of well quasi-orders in the studying of languages obtained by using the operators of shuffle and iterated shuffle of finite languages.