Termination of Graph Rewriting is Undecidable

Article type: Research Article

Authors: Plump, Detlef

Affiliations: Fachbereich Mathematik und Informatik, Universität Bremen, 28334 Bremen, Germany. det@informatik.uni-bremen.de

Abstract: It is shown that it is undecidable in general whether a graph rewriting system (in the “double pushout approach”) is terminating. The proof is by a reduction of the Post Correspondence Problem. It is also argued that there is no straightforward reduction of the halting problem for Turing machines or of the termination problem for string rewriting systems to the present problem.

Keywords: graph rewriting, termination, Post Correspondence Problem

DOI: 10.3233/FI-1998-33204

Journal: Fundamenta Informaticae, vol. 33, no. 2, pp. 201-209, 1998