Logic in Computer Science (LICS 1996)

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

Authors: Yuri Matiyasevich Géraud Senizergues

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{MatiyasevichSenizer-DecisionProblemsfor,
    author = 	 {Yuri Matiyasevich and Géraud Senizergues},
    title = 	 {Decision Problems for Semi-Thue Systems with a Few Rules},
    booktitle =  {Proceedings of the Eleventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1996},
    year =	 1996,
    editor =	 {Edmund M. Clarke},
    month =	 {July}, 
    pages =      {523-531},
    location =   {New Brunswick, NJ, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }