Name
Abstract | ||
|---|---|---|
This paper proves a long standing conjecture in formal language theory. It shows that 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 L is Church-Rosser congruential if there exists a finite, confluent, and length-reducing semi-Thue system S such that L is a finite union of congruence classes modulo S. It was known that there are deterministic linear context-free languages which are not Church-Rosser congruential, but on the other hand it was strongly believed that all regular languages are of this form. This paper solves the conjecture affirmatively by actually proving a more general result. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2808227 | Journal of the ACM (JACM) |
Keywords | DocType | Volume |
church-rosser congruential,language l,church-rosser congruential language,formal language theory,congruence class,deterministic linear context-free language,long standing conjecture,finite union,conjecture affirmatively,regular language | Conference | 62 |
Issue | ISSN | Citations |
5 | 0004-5411 | 4 |
PageRank | References | Authors |
0.55 | 9 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Volker Diekert | 1 | 702 | 67.46 |
| Manfred Kufleitner | 2 | 171 | 21.00 |
| Klaus Reinhardt | 3 | 136 | 9.74 |
| Tobias Walter | 4 | 117 | 10.92 |