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

Authors: Yuri Matiyasevich Géraud Sénizergues

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}
  }