O número de estados de autômatos locais

10

Um autômato determinístico é chamado -local para se para cada o conjunto contém no máximo um elemento. Intuitivamente, isso significa que se uma palavra de comprimento leva a um estado, então esse estado é único ou dito diferentemente de uma palavra arbitrária de comprimento os últimos símbolos determinam o estado ao qual ele leva.k k > 0 w X k { δ ( q , w ) : q Q } w k > k kA=(X,Q,q0,F,δ)kk>0wXk{δ(q,w):qQ}wk>kk

Agora, se um autômato é , ele não precisa ser -local para alguns , mas deve ser -local para causar os últimos símbolos de alguma palavra determina o estado, se houver, exclusivamente.k k < k k k > k | w | > kkkk<kkk>k|w|>k

Agora, tento conectar o número de estados e a localização- de um autômato. Eu conjecturo:k

Lema: Seja seja -local, se | Q | < k , o autômato também é | Q | -local.kA=(X,Q,q0,F,δ)k|Q|<k|Q|

Mas não consegui provar, alguma sugestão ou idéia?

Espero por este lema a algo derive sobre o número de estados de um autômato que não é -local para todo k N dado um fixo N > 0 , mas k -local por algum k > N .kkNN>0kk>N

StefanH
fonte

Respostas:

7

Como você diz que deve ter no máximo um elemento, presumo que você use a versão do DFA em que δ pode ser parcial. Então este é um contra-exemplo: X = { a , b } , Q = { 0 , 1 , 2 , 3 , 4 } , δ ( q , a ) =Tw:={δ(q,w):qQ}δ para q < 4 , e δ ( 1 , b ) = 2 , δ ( 2 , b ) = 3 , δ ( 4 , b ) = 0 . F e q 0 obviamente não importam para esta pergunta.X={a,b},Q={0,1,2,3,4},δ(q,a)=q+1q<4δ(1,b)=2,δ(2,b)=3,δ(4,b)=0Fq0

O autômato é -local, mas não 5 -local, pois T a b a a b = { 0 , 3 } .65Tabaab={0,3}

Edit: este contra-exemplo não funciona, vou mantê-lo para que os comentários façam sentido. O seguinte, no entanto.

Tome , com transições 0 1 ( a ) , 1 2 ( a ) , 2 3 ( a ) , 2 0 ( b ) , 3 2 ( b ) . Esse autômato é 5X={a,b},Q={0,1,2,3}01(a),12(a),23(a),20(b),32(b)5-local, mas não -local: para a a b a , obtemos os caminhos 0 1 2 0 1 e 1 2 3 2 3 , ou seja, T a a b a = { 1 , 3 } .4aaba0120112323Taaba={1,3}

Klaus Draeger
fonte
algo está errado com seus autômatos, você esqueceu certas transições? A palavra leva a nenhum estado, independentemente de onde eu começo ...abaab
StefanH
Eu acho que deveria ser correto - afirmou um pouco diferente, as transições são: e 4 0 ( b ) . Então os caminhos que você obtém para a b a a b são 0 1 2 01(a),12(a,b),23(a,b),34(a),40 0(b)umabumaumab e 3 4 0 1 2 3 . 0 01 12340 0340 01 123
Klaus Draeger
desculpe, você está certo!
precisa saber é
Oh, na verdade não sou, mas por um motivo diferente. Você obtém esses caminhos, mas pode repetir indefinidamente - esse autômato não é k -local para nenhum k . umabumaumabkk
Klaus Draeger
é claro que, em geral, um autômato não poderia ser local se existir dois e uma palavra w distintos , tais que δ ( p , w ) = p e δ ( q , w ) = q . p,qWδ(p,W)=pδ(q,W)=q
precisa saber é o seguinte
8

Uma resposta tardia, mas o limite do atraso de sincronização foi estudado para várias classes de autômatos: veja, por exemplo, Autômatos inequívocos; Béal et al. MCS'08 .

Em particular; existe uma família de autômatos determinísticos que possuem atraso como mostrado em No limite do atraso de sincronização de um autômato local; Béal et al. TCS'98 , que corresponde a um limite superior O ( | Q | 2 ) correspondente .Ω(|Q|2)O(|Q|2)

PS, o atraso de sincronização definido no artigo é o mínimo para o qual o autômato local determinístico é k- local .kk

Joseph Stack
fonte
você parece estar implicando que o atraso da sincronização é equivalente ao k-local ....?
vzn
11
No artigo do TCS'08, cito, para os DFAs locais "o atraso de sincronização é 1 ou mais o comprimento de uma sequência não sincronizada mais longa", onde uma sequência não sincronizada é uma palavra que pode levar a dois estados diferentes. Para mim, esse é, por definição, o menor para o qual o autômato é k-local . Você acha que eu estou enganado? kk
Joseph Stack
uma boa resposta não deixará de fora os principais detalhes. é possível que eles sejam (quase? exatamente?) equivalentes, mas isso seria um "bridge thm" novo, não em um papel ou em uma conexão publicada ...? se por isso precisa ser concretizados em mais detalhes em algum lugar ...
vzn
11
Está bem. Eu editei a resposta para enfatizar o ponto. Eu não acho que nenhuma ponte seja necessária além de verificar a definição.
31520 Joseph
sugerem que ambos os padrões sejam declarados exatamente e depois provados equivalentes. thx para esclarecimentos até agora.
vzn