Does XOR automata (NXA) for finite languages benefit from cycles?

Question

A non-deterministic Xor automata (NXA) is syntactically an NFA, but a word is said to be accepted by NXA if it has an odd number of accepting paths (instead of at least one accepting path in the NFA case).

It is easy to see that for a finite regular language $L$, there exists a minimal NFA which doesn't contain any cycles (if a cycle was both reachable from the initial state and you get from it to an accepting state - your language is not finite).

This is not necessarily the case for NXAs.

Denote by $xsc(L)$ the xor-state complexity of a language $L$,

and by $axsc(L)$ the acyclic xor state complexity of $L$ (i.e. the size of a smallest acyclic NXA which accepts $L$).

Is it true that for every finite language $L$: $$axsc(L)=xsc(L)\ ?$$

Answer 1

I think that the answer is the affirmative. Maybe there is a simpler proof, but here is a sketch of a proof which uses linear algebra.

Like domotorp, we will view a configuration of an n-state XOR automaton as a vector in V=GF(2)ⁿ.

Let L be a finite language over an alphabet Σ={1, …, k}, and consider an XOR automaton for L with the minimum number of states. Let n be the number of states. We assume that the states are labeled 1, …, n, and state 1 is the initial state.

First we set up the notation. Let v₀ = (1, 0, …, 0)^T ∈ V be the elementary vector corresponding to the initial state, and let s be the row vector whose ith entry is 1 if and only if state i is an accepting state. The subspace R = {v: sv=0} of V corresponds to the configuration vectors that are rejected.

For each a∈Σ, let A_a be the n×n matrix over GF(2) which represents the transition caused by letter a. For example, the configuration vector after reading the input string ab is A_bA_av₀. For a string σ=a₁…a_t, we denote the product A_at…A_a1 by M(σ). Let S = {A₁, …, A_k}.

A subspace W of V is said to be S-invariant when AW ⊆ W for every A∈S. In our context, this means that once the configuration vector goes in W, there is no way out of W by reading more letters.

Because this XOR automaton has the minimum number of states, we have the following properties.

• The only S-invariant subspace of V that contains v₀ is V itself. This is because if W is a proper S-invariant subspace containing v₀, then we can use W in place of V, contradicting the minimality.
• The only S-invariant subspace contained in R is {0}. This is because if W is a nontrivial S-invariant subspace contained in R, then we can use the quotient vector space V/W in place of V, again contradicting the minimality.

Because L is finite, let m be an integer larger than the length of any string in L.

Lemma 1. For any string σ of length at least m, we have that M(σ)=0.

Proof. First we prove that for any string σ of length at least m, we have that M(σ)v₀=0. Let W be the subspace of V spanned by {M(σ)v₀: σ is a string of length at least m}. By definition, W is S-invariant. Because the XOR automaton in question rejects these strings σ, W is contained in R. Therefore W={0}, which means that M(σ)v₀=0 for all such strings σ.

Now consider any vector v∈V. Because the only S-invariant subspace of V that contains v₀ is V itself, v can be written as a linear combination of vectors of the form M(τ)v₀ for some strings τ. Because M(σ)M(τ)v₀ = M(τσ)v₀ = 0 (the latter equality follows from the previous paragraph because the length of τσ is at least m), it holds that M(σ)v=0. ■

We need one more fact from linear algebra.

Lemma 2. Let A₁, …, A_k be n×n matrices over a field, and define M(σ) as above. If there is m≥0 such that M(σ)=0 for every string σ of length at least m, then the matrices A₁, …, A_k are simultaneously similar to strictly lower triangular matrices (that is, there exists an n×n nonsingular matrix P such that the matrices P⁻¹A₁P, …, P⁻¹A_kP are strictly lower triangular).

The case of k=1 is a well-known characterization of nilpotent matrices, and Lemma 2 can be proved in the same way.

Now consider the n-state XOR automaton in which the transition matrix corresponding to symbol a∈Σ is given by P⁻¹A_aP, the initial configuration vector is given by P⁻¹v₀, and the characteristic (row) vector of the accepting states is given by sP. By construction, this XOR automaton accepts the same language L. Because the transition matrices are strictly lower triangular, every transition edge in this XOR automaton goes from a state with a smaller index to a state with a larger index, and therefore this XOR automaton is acyclic. Although the initial configuration vector may have more than one 1s, it is easy to convert this XOR automaton to a usual XOR automaton with a single initial state for the same language without increasing the number of states or ruining the acyclicity.

Answer 2

I think I can prove that cycles do not help over the unary alphabet.

Consider the matrix $M$ over $F_2$ describing from which state into which state we can get in one step and the vector $v_n$ over $F_2$ describing the possible states of the automaton $\mod 2$ after $n$ steps, so $v_n=M^nv_0$, where $v_0=(1,0,..,0)$ describes the starting state. If we know that after some finite $t$ steps $s\cdot v=0$ (where $s$ is the characteristic vector of the accepting states), that means that we are in a certain subspace. The dimension of $M^n$ is strictly monotone descreasing for a while, then constant. This means that we must reach the subsapce $s\cdot v_n=0$ after at most as many steps, as many states the automaton has. But then there is a cycle-free automaton that just counts the length of the word.