Relação quadrática entre espaço não determinístico e determinístico?

16

O teorema de Savitch mostra que para todas as funções suficientemente grandes , e provar que isso é restrito tem sido um problema aberto por décadas .fNSPUMACE(f(n))DSPUMACE(f(n)2)f

Suponha que abordemos o problema do outro lado. Para simplificar, assuma o alfabeto booleano. A quantidade de espaço usada por uma TM para decidir uma linguagem computável geralmente está intimamente relacionada ao logaritmo do número de estados usados ​​pelo autômato que simula a TM para cada fatia regular de um idioma. Isso motiva a seguinte pergunta.

Seja o número de sintaticamente distintos com n estados e N_n seja o número de NFAs distintos com n estados. É simples mostrar que \ lg N_n está próximo de (\ lg D_n) ^ 2 . n N n n lg N n ( lg D n ) 2DnnNnnlgNn(lgDn)2

Além disso, seja Dn o número de idiomas regulares distintos que podem ser reconhecidos por um DFA com n estados e Nn seja o número reconhecido por um NFA.

Sabe-se se lgNn está próximo de (lgDn)2 ?

Não está claro para mim como Dn e Dn , ou Nn e Nn , estão relacionados entre si ou com que proximidade. Se tudo isso estiver relacionado a uma questão bem conhecida na teoria dos autômatos, uma dica ou ponteiro seria apreciado. A mesma pergunta também é relevante para os autômatos bidirecionais, devido ao mesmo raciocínio, e estou especialmente interessado nesta versão.

András Salamon
fonte
Veja também a pergunta relacionada cstheory.stackexchange.com/q/7913/109
András Salamon

Respostas:

18

No meu artigo com Domaratzki e Kisman, "Sobre o número de línguas distintas aceitas por autômatos finitos com n estados" publicado em J. Automata, Languages ​​e Combinatorics 7 (2002), provamos que se é o número de distintas idiomas aceitos pelos NFAs com estados sobre um alfabeto de letras , e é similarmente o número de idiomas distintos aceitos pelos DFAs, depois para fixoGk(n)nkgk(n)k2

(i) é, em termos de ordem menor, assintoticamenteregistrogk(n)knregistron

(ii) é, em termos de ordem menor, assintoticamente entre e .registroGk(n)(k-1 1)n2kn2

Jeffrey Shallit
fonte