DocumentCode
2741712
Title
Decision problems for semi-Thue systems with a few rules
Author
Matiyasevich, Yuri ; Sénizergues, Géraud
Author_Institution
Steklov Math. Inst., Acad. of Sci., St. Petersburg, Russia
fYear
1996
fDate
27-30 Jul 1996
Firstpage
523
Lastpage
531
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
Keywords
decidability; grammars; program verification; rewriting systems; U-termination problem; accessibility problem; common-descendant problem; decidable; decision problems; post-correspondence problem; semi-Thue systems; termination problem; undecidable; Mathematics; Radio access networks;
fLanguage
English
Publisher
ieee
Conference_Titel
Logic in Computer Science, 1996. LICS '96. Proceedings., Eleventh Annual IEEE Symposium on
Conference_Location
New Brunswick, NJ
ISSN
1043-6871
Print_ISBN
0-8186-7463-6
Type
conf
DOI
10.1109/LICS.1996.561469
Filename
561469
Link To Document