Access Restriction

Author Diekert, Volker ♦ Kufleitner, Manfred ♦ Reinhardt, Klaus ♦ Walter, Tobias
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Church-Rosser system ♦ Local divisor ♦ Regular language ♦ Semigroup ♦ String rewriting
Abstract This article shows a general result about finite monoids and weight reducing string rewriting systems. As a consequence it proves a long standing conjecture in formal language theory: All regular languages are Church-Rosser congruential. The class of Church-Rosser congruential languages was introduced by McNaughton, Narendran, and Otto in 1988. A language $\textit{L}$ is Church-Rosser congruential if there exists a finite, confluent, and length-reducing semi-Thue system $\textit{S}$ such that $\textit{L}$ is a finite union of congruence classes modulo $\textit{S}.$ It was known that there are deterministic linear context-free languages which are not Church-Rosser congruential, but the conjecture was that all regular languages are of this form. The article offers a stronger statement: A language is regular if and only if it is strongly Church-Rosser congruential. It is the journal version of the conference abstract which was presented at ICALP 2012.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-11-02
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 62
Issue Number 5
Page Count 20
Starting Page 1
Ending Page 20

Open content in new tab

   Open content in new tab
Source: ACM Digital Library