Os autômatos de empilhamento alternativo unidirecional (1APDA) podem reconhecer qualquer idioma em (Alternação de Chandra, Kozen e Stockmeyer, 1981) . Ao substituir um armazenamento pushdown de um 1APDA por um contador, podemos obter um autômato alternativo unidirecional por um contador (1ACA). Minha pergunta é sobre 1ACAs em idiomas unários.
Os 1ACAs podem reconhecer alguns idiomas não regulares unários ?
Observe que os autômatos de empilhamento não determinísticos unidirecionais podem reconhecer apenas idiomas regulares unários.
automata-theory
counter-automata
unary-languages
Abuzer Yakaryilmaz
fonte
fonte