Parikh-reducing Church-Rosser representations for some classes of regular languages

DOI10.1016/j.tcs.2017.08.009zbMath1385.68021arXiv1703.10056OpenAlexW2605126582MaRDI QIDQ1676318

Tobias Walter

Publication date: 6 November 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.10056

zbMATH Keywords

regular languagerewriting systemsyntactic monoidlocal divisorChurch-Rossercongruential languageParikh-reducing

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35) Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Star-free languages are Church-Rosser congruential
• A survey on the local divisor technique
• On the irreducibility of pseudovarieties of semigroups.
• On varieties of rational languages and variable length codes. II
• The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
• Church-Rosser Thue systems and formal languages
• Characterizing Classes of Regular Languages Using Prefix Codes of Bounded Synchronization Delay
• Uniqueness Theorems for Periodic Functions
• Regular Languages Are Church-Rosser Congruential

This page was built for publication: Parikh-reducing Church-Rosser representations for some classes of regular languages