Article ID Journal Published Year Pages File Type
10334381 Theoretical Computer Science 2005 25 Pages PDF
Abstract
We show that the accessibility problem, the common descendant problem, the termination problem and the uniform termination problem are undecidable for 3-rules semi-Thue systems. As a corollary we obtain the undecidability of the Post correspondence problem for 7 rules.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Decision problems for semi-Thue systems with a few rules
Authors
, ,