Pytania otagowane jako unary-languages

1
Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny?
Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny? Problem pustki dla modelu obliczeniowego (np. Automat skończony, automat przemienny, automat kwantowy z ograniczeniem błędu z licznikiem, deterministyczny LBA itp.) Polega na ustaleniu, czy dla danej takiej maszyny język rozpoznawany / definiowany przez tę maszynę jest pusty. Tutaj opis …
1
Czy jednokierunkowe przemienne automaty z jednym licznikiem rozpoznają niektóre jednoargumentowe nieregularne języki?
Jednokierunkowe naprzemienne automaty wypychające (1APDA) mogą rozpoznać dowolny język w (Alternacja autorstwa Chandra, Kozen i Stockmeyer, 1981) . Zastępując przechowywanie w dół 1APDA przez licznik, możemy uzyskać jednokierunkowy automat na przemian z jednym licznikiem (1ACA). Moje pytanie dotyczy 1ACA w językach jednoargumentowych.D T.jaM.mi( 2O ( n ))reT.jaM.mi(2)O(n)) DTIME(2^{O(n)}) Czy 1ACA …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.