Lics

IEEE Symposium on Logic in Computer Science

Paper: Decision Problems for Semi-Thue Systems with a Few Rules (at LICS 1996)

Abstract

For several decision problems about semi-Thue systems , we try to locate the frontier between the decidable and the undecidable from the point of view of the number of rules. We show that the the Termination Problem, the U-Termination Problem, the Accessibility Problem and the Common-Descendant Problem are undecidable for 3 rules semi-Thue systems . As a corollary we obtain the undecidability of the Post-Correspondence Problem for 7 pairs of words.

BibTeX

 @InProceedings{Snizergues-DecisionProblemsfor,
 author = 	 {Yuri Matiyasevich and Géraud Sénizergues},
 title = 	 {Decision Problems for Semi-Thue Systems with a Few Rules},
 booktitle = {Proceedings of the Eleventh Annual IEEE Symposium on Logic in Computer Science (LICS 1996)},
 year =	 {1996},
 month =	 {July}, 
 pages = {523--531},
 location = {New Brunswick, NJ, USA}, 
 publisher =	 {IEEE Computer Society Press}
 }