Back to Search
Start Over
Remarks on Jurdzinski and Lorys' proof that palindromes are not a Church-Rosser language
- Publication Year :
- 2007
-
Abstract
- In 2002 Jurdzinski and Lorys settled a long-standing conjecture that palindromes are not a Church-Rosser language. Their proof required a sophisticated theory about computation graphs of 2-stack automata. We present their proof in terms of 1-tape Turing machines.We also provide an alternative proof of Buntrock and Otto's result that the set of non-square bitstrings, which is context-free, is not Church-Rosser.<br />Comment: 15 pages
- Subjects :
- Computer Science - Logic in Computer Science
F.4.2
F.4.3
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.0710.4499
- Document Type :
- Working Paper