Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
On Regularity-Preservation by String-Rewriting Systems
verfasst von : Peter Leupold
Erschienen in: Language and Automata Theory and Applications
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
When using string-rewriting systems in the context of formal languages, one of the most common questions is whether they preserve regularity. A class of string-rewriting systems that has received attention lately are idempotency relations. They were mainly used to generate languages starting from a single word.
Here we apply these relations to entire languages and investigate whether they preserve regularity. For this, it turns out to be convenient to define two more general classes of string-rewriting systems, the
k
-period expanding and the
k
-period reducing ones. We show that both preserve regularity. This implies regularity preservation for many classes of idempotency relations.