Regular Languages Are Church-Rosser Congruential

DOI10.1145/2808227zbMath1426.68142arXiv1202.1148OpenAlexW2175851206MaRDI QIDQ5895070

Manfred Kufleitner, Tobias Walter, Volker Diekert, Klaus Reinhardt

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

semigroupregular languagestring rewritingChurch-Rosser systemlocal divisor

Mathematics Subject Classification ID

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

Related Items (1)

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

This page was built for publication: Regular Languages Are Church-Rosser Congruential