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

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?

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

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 I ≠ y $N$$HAL$$L$$i$$x_i$$\$$$y_i$$x_i \ne y_i$. (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:

$D$$HAL$$x$$x$$D$$HAL$$L$$PDA$

$x$$x_1$$x_2$$x_1\$x_1$$x_2\$x_1$

ktoś widzi natychmiastowy dowód przypuszczenia?