Os autômatos XOR (NXA) para idiomas finitos se beneficiam de ciclos?

Um autômato Xor não determinístico (NXA) é sintaticamente um NFA, mas uma palavra é aceita pelo NXA se ele tiver um número ímpar de caminhos de aceitação (em vez de pelo menos um caminho de aceitação no caso de NFA).

É fácil ver que, para um idioma regular finito , existe um NFA mínimo que não contém nenhum ciclo (se um ciclo foi alcançável desde o estado inicial e você passou para um estado de aceitação - seu idioma não é finito).$L$

Este não é necessariamente o caso dos NXAs.

Denote por a complexidade xor-state de uma linguagem ,$xsc(L)$$L$

e por a complexidade acíclica do estado xor de (ou seja, o tamanho de um menor NXA acíclico que aceita ).L$axsc(L)$$L$$L$

É verdade que para toda linguagem finita : a x s c ( L ) = x s c ( L ) ?$L$

$$axsc(L)=xsc(L)\ ?$$

Eu acho que a resposta é afirmativa. Talvez haja uma prova mais simples, mas aqui está um esboço de uma prova que usa álgebra linear.

Como domotorp, veremos uma configuração de um autômato XOR de estado n como um vetor em V = GF (2) ⁿ .

Seja L um idioma finito sobre um alfabeto Σ = {1,…, k } e considere um autômato XOR para L com o número mínimo de estados. Seja n o número de estados. Supomos que os estados sejam rotulados como 1,…, n e o estado 1 seja o estado inicial.

Primeiro, configuramos a notação. Deixe v ₀ = (1, 0, ..., 0) ^t ∈ V ser o vector elementar correspondente ao estado inicial, e deixe s ser o vector da linha cujo i th entrada é 1, se e apenas se o estado i é um estado de aceitação. O subespaço R = { v : s v = 0} de V corresponde aos vetores de configuração que são rejeitados.

Para cada um ∈Σ, deixar Um _um ser o n x n matriz sobre GF (2), o qual representa a transição provocada pela letra um . Por exemplo, o vetor de configuração após a leitura da sequência de entrada a b é A _b A _a v ₀ . Para uma sequência σ = a ₁ … a _t , denotamos o produto A _{a t} … A _{a 1} por M ( σ ). Seja S = { A ₁,…, A _k }.

Um subespaço W de V é dito para ser S - invariante quando Um W ⊆ W para cada um ∈ S . Em nosso contexto, isso significa que, uma vez que o vetor de configuração entra em W , não há como sair de W lendo mais letras.

Como esse autômato XOR possui o número mínimo de estados, temos as seguintes propriedades.

• O único subespaço de V com variação S que contém v ₀ é o próprio V. Isso ocorre porque, se W é um subespaço de inversão S adequado, contendo v ₀ , então podemos usar W no lugar de V , contradizendo a minimalidade.
• O único subespaço com variação S contido em R é {0}. Isso ocorre porque se W é um subespaço não trivial de inversão S contido em R , então podemos usar o espaço vetorial quociente V / W no lugar de V , contradizendo novamente a minima.

Uma vez que L é finito, deixe m ser um número inteiro maior do que o comprimento de qualquer cadeia em L .

Lema 1 . Para qualquer string σ de comprimento pelo menos m , temos esse M ( σ ) = 0.

Prova. Primeiro, provamos que, para qualquer string σ de comprimento pelo menos m , temos que M ( σ ) v ₀ = 0. Seja W o subespaço de V estendido por { M ( σ ) v ₀ : σ é uma cadeia de comprimento pelo menos m }. Por definição, W é S- variável. Porque o autómato XOR em questão rejeita estas cordas σ , W está contido em R . Portanto, W = {0}, o que significa queM ( σ ) v ₀ = 0 para todas essas cadeias σ .

Agora, considere qualquer vector v ∈ V . Uma vez que a única S subespaço -invariant de V que contém v ₀ é V si, v pode ser escrito como uma combinação linear de vectores da forma H ( τ ) v ₀ para algumas cadeias τ . Porque M ( σ ) M ( τ ) v ₀ = M ( τ σ ) v ₀= 0 (a última igualdade segue o parágrafo anterior porque o comprimento de τ σ é pelo menos m ), sustenta que M ( σ ) v = 0. ■

Precisamos de mais um fato da álgebra linear.

Lema 2 . Deixe Um ₁ , ..., A _k ser n × n matrizes sobre um campo, e definir M ( σ ) como acima. Se houver m ≥0 tal que M ( σ ) = 0 para cada string σ de comprimento pelo menos m , as matrizes A ₁ ,…, A _k são simultaneamente semelhantes às matrizes triangulares estritamente inferiores (ou seja, existe um n × n matriz não singular P tal que as matrizes P ⁻¹ A₁ P ,…, P ⁻¹ A _k P são estritamente triangulares inferiores).

O caso de k = 1 é uma caracterização bem conhecida de matrizes nilpotentes, e o lema 2 pode ser provado da mesma maneira.

Agora considere o autômato n- state XOR no qual a matriz de transição correspondente ao símbolo a é dada por P- ¹ A _a P , o vetor de configuração inicial é dado por P- ¹ v ₀ e o vetor característico (linha) de os estados de aceitação é dado por s P . Por construção, esse autômato XOR aceita o mesmo idioma L. Como as matrizes de transição são estritamente triangulares mais baixas, todas as arestas de transição neste autômato XOR passam de um estado com um índice menor para um estado com um índice maior e, portanto, esse autômato XOR é acíclico. Embora o vetor de configuração inicial possa ter mais de um 1s, é fácil converter esse autômato XOR em um autômato XOR comum com um único estado inicial para o mesmo idioma sem aumentar o número de estados ou arruinar a aciclicidade.

Acho que posso provar que os ciclos não ajudam sobre o alfabeto unário.

$M$$F_2$$v_n$$F_2$$\mod 2$$n$$v_n=M^nv_0$$v_0=(1,0,..,0)$$t$$s\cdot v=0$$s$$M^n$$s\cdot v_n=0$