Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

1 Fundamenta Informaticae

1 2017

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: universal semi-Thue system

Sortuj według:

Ogranicz wyniki do:

Small Semi-Thue System Universal with Respect to the Termination Problem

100%

Halava V. , Matiyasevich Y. , Niskanen R.

Fundamenta Informaticae

2017

tom Vol. 154, nr 1/4

177--184

The termination problem for semi-Thue systems asks whether all derivations for a given word in a given semi-Thue system are finite, i.e., all derivations terminate after finite number of steps. This problem is known to be undecidable, there is a standard reduction of the halting problem of the Turing machines into termination problem; moreover, one can fix a semi-Thue system and still have the undecidability. In 1996 Sénizergues and the second author gave a construction for a 3-rule semi-Thue system with undecidable termination problem. However, in their construction the words of one of the rules are very long. Using some ideas of Tseijtin we give a construction for a semi-Thue system with low number of short rules having undecidable termination problem. Namely, we construct a semi-Thue system with 24 rules over 8 letter alphabet with rule words of length at most 5, and the termination problem for this semi-Thue system is undecidable. Moreover, this system is universal, that is, it can simulate any semi-Thue system.