Quantos DFAs aceitam duas seqüências de caracteres fornecidas?

28

Corrija um número inteiro n e alfabeto Σ={0,1} . Defina DFA(n) como a coleção de todos os autômatos de estados finitos em n estados com o estado inicial 1. Estamos considerando todos os DFAs (não apenas os conectados, mínimos ou não degenerados); assim, |DFA(n)|=n2n2n .

Agora, considere duas cordas x,yΣ e definir K(x,y) para ser o número de elementos de DFA(n) que aceitar ambos x e y .

Pergunta: Qual é a complexidade da computação K(x,y) ?

Esta questão tem implicações para o aprendizado de máquina .

Edit: Agora que há uma recompensa sobre esta questão, suponho que um pouco mais de precisão na formulação esteja em ordem. Para , seja D F A ( n ) a coleção de n 2 n 2 n autômatos, conforme definido acima. Para x , y { 0 , 1 } * , definir K N ( x , y ) para ser o número de autómatos em D F A ( n ) que aceitar tanton1DFA(n)n2n2nx,y{0,1}Kn(x,y)DFA(n) x ey . Pergunta:Kn(x,y) ser calculado no tempopoly(n,|x|,|y|) ?

Aryeh
fonte
2
Se você corrige um DFA sem fixar os estados finais, ele mapeia xey para o mesmo estado; nesse caso, a única restrição é que o estado precisa ser final ou mapeia-os para dois estados diferentes, nesse caso a única restrição é que ambos precisam ser finais. Assim, eu reformularia seu problema como "quantos DFAs mapeiam xey para estados diferentes?".
a3nm
3
Aryeh, você pode explicar a contagem ? Não consigo obter o fator 2 n . Adicionado: Opa, esqueci de especificar os estados finais. Enfim, para o bem dos outros, aqui está como a contagem vai. Para cada estado, especifique para onde ir nas entradas 0 e 1 ; isso representa n 2 n . Especifique o conjunto de estados finais; isso é 2 n . n2n2n2n01n2n2n
Srivatsan Narayanan
2
Na verdade, eu não me importo o que acontece com outros do que cordas e y . Eu acho que é preciso uma certa quantidade de pontos para começar uma recompensa? xy
Aryeh
4
O menor autômato que aceita e y tem um único estado, então eu não acho que é terrivelmente informativo ...xy
Aryeh
3
Aqui está uma idéia: nós só precisamos saber o número de DFAs -Estado que acabam no mesmo estado em x e y . Seja esse número m e M seja o número total de DFAs, ou seja, M = n 2 n 2 n . Então a resposta é 1nxymMM=n2n2n, isso dá limites. Para calcularmoutra idéia é que podemos esquecer o segmento inicial compartilhada dexey, e também assumir que WLOGx=0aeb=1b. Contamos apenas o número de DAGs binários comlestados e altura nomáximo{a,b}queeterminam no mesmo local e, a partir disso, é fácil calcular. 12m+14(Mm)mxyx=0ab=1blmax{a,b}1 b m0a1bm
Kaveh

Respostas:

1

Portanto, a pergunta é bem breve, mas muito interessante. Suponho que a entrada seja em unário e e em binário (ou temos problemas, como apontado pela resposta de Kai).x ynxy

Antes de tudo, se você estiver interessado em conhecer aproximadamente, poderá gerar alguns DFA aleatórios e isso fornecerá a você (whp) uma boa aproximação. (Gostaria de saber se essa classe de complexidade tem um nome.)K(x,y)

Então, conhecer parece exatamente um problema difícil. Como fora apontado nos comentários por a3_nm e Kaveh, a questão é equivalente a determinação do número de autômatos para o qual e ir para o mesmo estado. Denotarei a probabilidade de que eles cheguem ao mesmo estado na .x y pK(x,y)xyp

Atualização: Algumas das coisas que escrevi aqui não eram verdadeiras, agora as corrigi.

É fácil ver que . Temos igualdade, se é todos os 0 e é zero, exceto seu último bit, que é um 1. Existem outros casos? Eu não sei. Se, por exemplo, for a sequência vazia e , então .x y x y = 00 p = n + 1p1/nxyxy=00p=n+1(n1)n

Para simplificar o problema, eu mesmo comecei a pensar sobre o que acontece se e são unário. Se ambos são pelo menos e sua diferença é divisível por, então . Existe uma fórmula simples para a versão unária?y n n ! p = 1xynn!p=1

domotorp
fonte
Esclareci o problema - um algoritmo é desejado (ou uma redução de algum problema grave conhecido). A aproximação de amostragem é empregada no papel onde este kernel é introduzido: portal.acm.org/citation.cfm?id=1577108poly(n,|x|,|y|)
Aryeh
2
Quanto à versão unária: existem apenas polinomialmente muitos autômatos unários do estado , então eu apostaria que existe um algoritmo de politempo para calcular K n ( x , y ) para este caso. nKn(x,y)
Aryeh 30/07
Na verdade, você está absolutamente certo de que a versão unária é computável. Ainda me pergunto o quão simples é a fórmula para um dado x e y.
Domotorp 30/07
A redução que você usou é de buggy: x e y podem ser aceitos pelo mesmo autômato e terminar em estados completamente diferentes; na verdade, eles podem compartilhar apenas o estado inicial em seus caminhos, o que é verdadeiro para todas as cadeias.
Amnn 26/07/2015
@ amnn: Já se passaram três anos desde que escrevi isso, mas o terceiro parágrafo da minha resposta não explica por que trato apenas de terminar no mesmo estado?
domotorp 26/07/2015
0

Talvez eu esteja perdendo o objetivo, mas você declarou que é fixo, portanto todos os DFAs desse tamanho podem ser considerados pré-computados e armazenados em um formato facilmente simulável. Calcule K da seguinte maneira:nK

Na entrada , y onde x , y Σ xyx,yΣ

  1. armazenar e yxy
  2. inicialize o contador para 0c0
  3. para cada um dos seus DFAsn2n2n
  4. uma. simule-o em ambas as palavras (esta etapa é )O(|xy|)

    b. incremento se ambas as execuções de simulação estiverem aceitandoc

  5. saída c

Ao todo, a computação tem complexidade linear. A resposta é bem diferente para .K(n,x,y)

Kai
fonte
3
Claramente, tentar todas as máquinas funcionará. Aryeh quer saber se existe, talvez, um algoritmo de tempo polinomial ou algum resultado de dureza.
Lev Reyzin
A rigor, esse é o tempo polinomial da entrada, se n não fizer parte da entrada, era o que Kai estava dizendo. Mas a questão é claramente diferente.
Domotorp 30/07/11
4
n
1
Certo, obrigado por apontar a brecha, Kai. Foi consertado :) #
30611 Aryeh