2024-03-28T22:03:21Z
https://nagoya.repo.nii.ac.jp/oai
oai:nagoya.repo.nii.ac.jp:00007649
2023-01-16T05:02:57Z
312:313:314
Confluence of Length Preserving String Rewriting Systems is Undecidable
WANG, Yi
SAKAI, Masahiko
NISHIDA, Naoki
SAKABE, Toshiki
KUSAKARI, Keiichirou
open access
Post's correspondence Problem
This paper shows the undecidability of confluence for length preserving string rewriting systems. It is proven by reducing the Post's correspondence problem(PCP), which is known to be undecidable, to confluence problem for length preserving string rewriting systems. More precisely, we designed a reduction algorithm having the property that the existence of a solution for a given instance of PCP concides with the non-confluence of the string rewriting system obtained from the reduction algorithm.
京都大学数理解析研究所
2007-05
eng
departmental bulletin paper
VoR
http://hdl.handle.net/2237/9353
https://nagoya.repo.nii.ac.jp/records/7649
1880-2818
数理解析研究所講究録
1554
171
177
https://nagoya.repo.nii.ac.jp/record/7649/files/1554_171-177.pdf
application/pdf
348.6 kB
2018-02-19