Les automates pushdown alternatifs unidirectionnels (1APDA) peuvent reconnaître n'importe quelle langue en (Alternation par Chandra, Kozen et Stockmeyer, 1981) . En remplaçant un stockage pushdown d'un 1APDA par un compteur, nous pouvons obtenir un automate alternatif unidirectionnel avec un compteur (1ACA). Ma question concerne 1ACA sur les langues unaires.
1ACA peut-il reconnaître certaines langues unaires non régulières ?
Notez que les automates de refoulement non déterministes unidirectionnels ne peuvent reconnaître que les langues régulières unaires.
la source