Os autômatos alternativos unidirecionais com o contador único podem reconhecer alguns idiomas não regulares unários?

11

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.DTIME(2O(n))

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.

Abuzer Yakaryilmaz
fonte

Respostas:

6

L={ann=2s,s0}Lm2mmL1

n=k1s1krsrk1,,krs1,,sr

dd1
fonte
1
Obrigado pela resposta. Eu recebi a mesma resposta de Pavol Duris (via comunicação privada) que aparecerá em um artigo em breve. Eu estava planejando postar a resposta depois que o documento aparecer on-line. (Pode haver resultados ainda mais fortes.) De qualquer forma, sua resposta certamente é aceita !
Abuzer Yakaryilmaz 28/02