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. $DTIME(2^{O(n)})$

Czy 1ACA mogą rozpoznać niektóre niekonwencjonalne języki?

Zauważ, że jednokierunkowe niedeterministyczne automaty wypychające mogą rozpoznawać tylko jednoargumentowe zwykłe języki.

automata-theory counter-automata unary-languages

— Abuzer Yakaryilmaz
źródło

$L = \{ a^n \mid n = 2^s, s \geq 0 \}$ $L$ $m$ $2 m$ $m$ $L$ $1$

$n = k_1^{s_1} \ldots k_r^{s_r}$ $k_1, \ldots, k_r$ $s_1, \ldots, s_r$

— dd1
źródło

Dziękuję za Twoją odpowiedź. Taką samą odpowiedź otrzymałem od Pavola Durisa (za pośrednictwem prywatnej komunikacji), która wkrótce pojawi się w artykule. Chciałem opublikować odpowiedź po ukazaniu się artykułu w Internecie. (Mogą być jeszcze mocniejsze wyniki.) W każdym razie twoja odpowiedź jest z pewnością zaakceptowana !

— Abuzer Yakaryilmaz