Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
201--209
Opis fizyczny
bibliogr. 7 poz.
Twórcy
autor
- Fachbereich mathematik und Informatik, Universität Bremen, 28334 Bremen, Germany, det@informatik.uni-bremen.de
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS1-0003-0025