Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki?

9

Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki?

Przez niedeterministyczny automat związany liniowo (nLBA) mam na myśli niedeterministyczną maszynę Turinga z pojedynczą taśmą, w której dane wejściowe są „wyściełane” znakami końcowymi na obu końcach, których nigdy nie można nadpisać, a więc głowa nigdy nie może wyjść z obszaru wejściowego, „poza” znacznikami końcowymi.

LBA jest ograniczona, jeśli istnieje numer ktak, że wszystkie uruchomienia na wszystkich wejściach kończą się i odwiedzają co najwyżej każdą komórkę taśmyk czasy.

Czy taka maszyna rozpoznaje tylko zwykłe języki? Wydaje się, że wynik Henniego mówi to tylko w przypadku maszyn deterministycznych, jeśli dobrze go czytam. Czy wynik odnosi się również do niedeterministycznych maszyn? Jeśli tak, referencje będą mile widziane.

Prateek
źródło

Odpowiedzi:

7

Trochę przesada, ale: ten artykuł pokazuje (między innymi dobre rzeczy), że niedeterministyczne przetworniki Hennie realizują dokładnie klasę niedeterministycznych transdukcji definiowanych przez MSO. Te ostatnie mają zwykłe domeny.

Boson
źródło