Moc obliczeniowa deterministycznych versus niedeterministycznych automatów typu min-heap

15

To jest kolejne pytanie tego .

W poprzednim pytaniu dotyczącym egzotycznych automatów stanowych Alex ten Brink i Raphael odnieśli się do możliwości obliczeniowych szczególnego rodzaju automatu stanowego: automatów typu min-heap. Udało im się wykazać, że zestaw języków akceptowanych przez takie maszyny ( ) nie jest ani podzbiorem, ani nadzbiorem zestawu języków bezkontekstowych. Biorąc pod uwagę skuteczne rozstrzygnięcie i pozorne zainteresowanie tym pytaniem, przystępuję do zadawania kolejnych pytań.HAL

Wiadomo, że deterministyczne i niedeterministyczne automaty skończone mają równoważne możliwości obliczeniowe, podobnie jak deterministyczne i niedeterministyczne maszyny Turinga. Jednak możliwości obliczeniowe deterministycznych automatów odpychających są mniejsze niż zdolności niedeterministycznych automatów odpychających.

Czy możliwości obliczeniowe deterministycznych automatów mini-stosu są mniejsze niż, czy są one równe, zdolności niedeterministycznych automatów mini-stosu?

Patrick87
źródło

Odpowiedzi:

3

Wydaje się, że w tym modelu maszyny niedeterministyczne nie są równoważne z maszynami deterministycznymi, z tego samego powodu, dla którego deterministyczne PDA nie są równoważne z maszynami niedeterministycznymi.

Rozważ język

L=x$y|x|=|y|xy
(gdzie jest specjalny znak nie zawarty w X i Y ).$xy

Zastrzeżenia patentowe że nie deterministyczny urządzenie - H L może zdecydować tego języka Wykonuje się takie same, jak dla PDA L . Standardowe rozwiązanie PDA używa stosu tylko do zliczania przesunięć: nieeterministycznie zgaduje przesunięcie i , zapamiętuje wartość x i (dodając symbol do stosu na każdym etapie), następnie PDA ignoruje dane wejściowe, dopóki nie znajdzie $ , i następnie wyrzuca symbole ze stosu, aż będzie puste. Na tym etapie jesteśmy dokładnie w y ja i on PDA może sprawdzić, czy x Iy INHALL.jaxja$yjaxjayja. (jeśli coś pójdzie nie tak w środku, PDA „umiera”). Ponieważ alfabet stosu jest jednoargumentowy, można go symulować za pomocą maszyny z minimalną hałdą. Właściwie: każdy który jest akceptowany przez PDA z jednoargumentowym alfabetem, może zostać zaakceptowany przez maszynę z minimalną hałdą. (Być może ignoruję inny znak specjalny dodany w celu zidentyfikowania pustego stosu, ale do stosu można dodać równoważny znak)L.

W innym kierunku nie mam formalnego dowodu, ale oto moje przemyślenia:

reH.ZAL.xxreH.ZAL.L.P.reZA

xx1x2)x1$x1x2)$x1

ktoś widzi natychmiastowy dowód przypuszczenia?

Ran G.
źródło
x
Jakiej definicji minimalnych hałd używasz: mojej oryginalnej, czy bardziej naturalnej zaproponowanej przez Raphaela? W obu przypadkach, czy możesz być bardziej jasny o tym, w jaki sposób niedeterministyczna maszyna zaakceptowałaby język, który dajesz ... co on wkłada i zdejmuje ze stosu i kiedy?
Patrick87,
nn