Provando que um idioma (árvore) não é reconhecível pelo Buchi

7

Estou revendo algumas anotações sobre autômatos de árvores e estou tentando concluir uma prova de que o professor deixou incompleto. A afirmação é:

Deixei A={a,b} e T={tTAωevery path in t contains a finite number of a}. Prove queT Buchi não é reconhecível.

Agora podemos definir os seguintes subconjuntos de árvores tnT Onde ttn tem um a nas posições: ϵ,1m10,1m101m20,,1m101m201mn0 com mi>0.

Agora assuma que A=(Q,A,Δ,q0,F) é o autômato Buchi que reconhece T com |Q|=n+1 e q0aparece apenas na raiz de seus cálculos. Deixeittn e r ser uma corrida bem sucedida de A em t.

Afirmação: There exists uv<w such that r(u)=r(w)=sF and t(v)=a.

Obviamente, se mostrarmos que a afirmação é verdadeira, podemos provar a afirmação inicial: pegue a subárvore tv e obter um ttn+1 substituindo a subárvore tw com tv. Temos que existe uma corridar que é idêntico ao r até a posição de w e seguirá a mesma sequência de estados em w como fez em ve, portanto, está aceitando. Repita o processo e você obterá um ramo com infinitoas que é aceito por A. (Essa é apenas a idéia aproximada, requer um pouco de formalismo, mas não é o ponto da questão.)

Minha pergunta é: como faço para provar a reivindicação?

Eu posso mostrar que existe uma tt2n com essa propriedade (que é realmente boa o suficiente para o restante da prova), mas não com um determinado valor tn a declaração vale para qualquer execução bem-sucedida.

Minha ideia é simplesmente: dado que r está aceitando deve existir um sF repetidas vezes infinitas em um caminho que passa 1m101m201mn0. Então pegue uma árvorettn+1que é idêntico a até a posição que nesse caminho e adicione um abaixo dessa posição. Agora, essa árvore ainda é aceita pelo autômato e existe uma execução de aceitação idêntica a até a posição , mas então não pode reutilizar para aceitar o mesmo caminho (caso contrário, encontramos os três estados da reivindicação) e, portanto, deve usar um estado diferente . Repita para todos os estados finais e você tem que deve ter uma execução com essa propriedade.tnxr(x)=sarrxrsst2n

Existe alguma maneira de aplicar esse tipo de raciocínio a , etc, para obter o resultado para ? Parece que, no máximo, posso provar que existe um com uma execução com essa propriedade, enquanto a reivindicação é mais forte. Ou estou indo na direção errada?tn1tn2tn ttn

Bakuriu
fonte

Respostas:

3

A idéia é brincar com os 's, como segue.mi

Considere uma árvore , que tem no , e em nenhum outro lugar. Veja o caminho - uma execução de aceitação nele tem infinitos estados de aceitação. Aguardar até que um estado de aceitação foi atingido, e só então colocar em , em que é grande o suficiente.t1aϵ1ωa1m10m1

Agora observe o caminho , novamente, ele possui um estado de aceitação eventualmente, denote o comprimento até , coloque em e veja em . Até agora você tem quase o que queria - dois estados aceitantes com um entre eles (falando informalmente). Mas você ainda não tem garantia de que ambos os estados aceitantes sejam iguais. Para impor esse último, repetimos o processo por vezes, esgotando assim o número de estados aceitantes e, pelo princípio do pigeonhole, dois estados aceitantes devem ser iguais.1m101ωm2a1m101m201m101m201ωan

Shaull
fonte
Você nem precisa considerar o número de estados - observe que essa abordagem fornece (para qualquer autômato ) uma sequência infinita modo que para cada , atinja um estado de aceitação vezes , e, portanto, o limite de será aceito apesar de ter um número infinito de s. Am1,m2,kAk1m101m201mk01m101m200
Klaus Draeger
Certo, mas o OP queria especificamente vincular o número de 's por , para o qual você precisa do número de estados. min+1
Shaull 28/02
Isso é mais ou menos o que eu estava pensando, mas prova algo um pouco mais fraco do que a afirmação. Com isso, você provar que e prazo bem sucedida de em tal que <alegação>. Enquanto na prova como afirma o professor que você tem e prazo bem sucedida de sobre ti detém <alegação>. O problema é que se você tem fixo você realmente não pode jogar com aqueles é como desejar. Agora, me pergunto se a afirmação declarada pelo professor é realmente verdadeira ou se é o melhor que podemos alcançar. ttnrAtttnrAttmi
Bakuriu 28/02
11
Para cada execução bem - sucedida, a afirmação é claramente falsa, pois o autômato pode ter um componente que adivinha um ponto a partir do qual nunca é encontrado novamente. Claramente todos os terá pelo menos um tal prazo aceitar ...attn
Shaull