hide
Free keywords:
-
Abstract:
By reduction from the halting problem for Minsky's two-register
machines we prove that there is no algorithm capable of deciding the
EAAA-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
EA...A-theory of one step rewriting (strong
undecidability). This improves over all previously known results of
the same kind.