Remarks on Jurdzinski and Lorys' proof that palindromes are not a Church-Rosser language
| dc.creator | Dunlaing, Colm O. | |
| dc.creator | Schluter, Natalie | |
| dc.date | 2007-10-24 | |
| dc.date | 2007-10-25 | |
| dc.date.accessioned | 2026-07-07T08:38:26Z | |
| dc.date.available | 2026-07-07T08:38:26Z | |
| dc.description | 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. | |
| dc.description | 15 pages | |
| dc.identifier | https://arxiv.org/abs/0710.4499 | |
| dc.identifier | http://arxiv.org/abs/0710.4499 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/140728 | |
| dc.subject | Logic in Computer Science | |
| dc.subject | F.4.2; F.4.3 | |
| dc.title | Remarks on Jurdzinski and Lorys' proof that palindromes are not a Church-Rosser language | |
| dc.type | text |