Does XOR automata (NXA) for finite languages benefit from cycles? 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)\ ?$$
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)n.

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 v0 = (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 Aa 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 AbAav0.  For a string σ=a1…at, we denote the product Aat…Aa1 by M(σ).  Let S = {A1, …, Ak}.

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 v0 is V itself.  This is because if W is a proper S-invariant subspace containing v0, 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(σ)v0=0.  Let W be the subspace of V spanned by {M(σ)v0: σ 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(σ)v0=0 for all such strings σ.

Now consider any vector v∈V.  Because the only S-invariant subspace of V that contains v0 is V itself, v can be written as a linear combination of vectors of the form M(τ)v0 for some strings τ.  Because M(σ)M(τ)v0 = M(τσ)v0 = 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 A1, …, Ak 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 A1, …, Ak are simultaneously similar to strictly lower triangular matrices (that is, there exists an n×n nonsingular matrix P such that the matrices P−1A1P, …, P−1AkP 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−1AaP, the initial configuration vector is given by P−1v0, 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.