Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Tytuł pozycji:

Termination of graph rewriting is undecidable

Szczegóły
Abstrakt

Tytuł:: Termination of graph rewriting is undecidable
Autorzy:: Plump, D.
Data publikacji:: 1998
Słowa kluczowe:: graph rewriting
termination
Post Correspondence Problem
Język:: angielski
Dostawca treści:: BazTech
: Artykuł

Przejdź do źródła

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.

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies

Informacja

Termination of graph rewriting is undecidable