{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T15:43:17Z","timestamp":1785512597346,"version":"3.56.0"},"reference-count":0,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[1998,2]]},"abstract":"<jats:p>It is shown that it is undecidable in general whether a graph rewriting system (in the \u201cdouble pushout approach\u201d) 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.<\/jats:p>","DOI":"10.3233\/fi-1998-33204","type":"journal-article","created":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T21:23:48Z","timestamp":1575321828000},"page":"201-209","source":"Crossref","is-referenced-by-count":39,"title":["Termination of Graph Rewriting is Undecidable"],"prefix":"10.1177","volume":"33","author":[{"given":"Detlef","family":"Plump","sequence":"first","affiliation":[{"name":"Fachbereich Mathematik und Informatik, Universit\u00e4t Bremen, 28334 Bremen, Germany. det@informatik.uni-bremen.de"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[1998,1,1]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-1998-33204","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-1998-33204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:34:20Z","timestamp":1777444460000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-1998-33204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1,1]]},"references-count":0,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,2]]}},"alternative-id":["10.3233\/FI-1998-33204"],"URL":"https:\/\/doi.org\/10.3233\/fi-1998-33204","relation":{"is-cited-by":[{"id-type":"doi","id":"10.1007\/978-3-319-75396-6_13","asserted-by":"object"}]},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1,1]]}}}