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 tak, że wszystkie uruchomienia na wszystkich wejściach kończą się i odwiedzają co najwyżej każdą komórkę taśmy 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.