Termination of graph rewriting is undecidable

• Autorzy: Plump D.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph rewriting; termination; Post Correspondence Problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1998
• Tom: Vol. 33, nr 2
• Strony: 201--209
• Opis fizyczny: bibliogr. 7 poz.

Twórcy

autor

Plump D.

• Fachbereich mathematik und Informatik, Universität Bremen, 28334 Bremen, Germany,