The undecidability of the first-order theories of one step rewriting in linear canonical systems
By reduction from the halting problem for Minsky's two-register machine we prove that there is no algorithm capable of deciding the There ExistsFor AllFor AllFor All-theory of one step rewriting of an arbitrary finite linear confluent finitely terminating term rewriting system (weak undecidability), We also present a fixed such system with undecidable There ExistsFor All*-theory of one step rewriting (strong undecidability), This improves over all previously known results of the same kind. (C) 2002 Elsevier Science (USA).
decidability first-order theory of one step rewriting linearity termination term rewriting system confluence quantifier prefix classes