MPI-I-98-2-009. May 1998, 59 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry
Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:
To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |
---|---|
449 KBytes | |
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |