Undecidability of ground reducibility for word rewriting systems with variables. (English) Zbl 0998.68529


68Q42 Grammars and rewriting systems
Full Text: DOI


[1] Book, R.V., Thue systems as rewriting systems, J. symbolic comput., 3, 1&2, 39-68, (1987) · Zbl 0638.68091
[2] Jiang, T.; Salomaa, A.; Salomaa, K.; Yu, S., Inclusion is undecidable for pattern languages, (), 301-312 · Zbl 1422.68152
[3] Kapur, D.; Narendran, P.; Rosenkrantz, D.; Zhang, H., Sufficient-completeness, quasi-reducibility and their complexity, () · Zbl 0721.68032
[4] Kapur, D.; Narendran, P.; Zhang, H., On sufficient completeness and related properties of term rewriting systems, Acta inform., 24, 395-415, (1987) · Zbl 0594.68035
[5] Marchenko, S.S., Undecidability of the positive ∀∃-theory of a free semigroup, Sibirskii matematicheskii zhurnal, 23, 1, 196-198, (1982), in Russian · Zbl 0578.03024
[6] Minsky, M.L., Recursive unsolvability of Post’s problem of “tag” and other topics in theory of Turing machines, Ann. of math., 74, 3, 437-455, (1961) · Zbl 0105.00802
[7] Plaisted, D., Semantic confluence tests and completion methods, Inform. and control, 65, 182-215, (1985) · Zbl 0598.68058
[8] Salomaa, A., Pattern languages: problems of decidability and generation, (), 121-132 · Zbl 0794.68089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.