<p>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.</p>

<p>Like domotorp, we will view a configuration of an <i>n</i>-state XOR automaton as a vector in <i>V</i>=GF(2)<sup><i>n</i></sup>.</p>

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

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

<p>For each <i>a</i>∈Σ, let <i>A</i><sub><i>a</i></sub> be the <i>n</i>×<i>n</i> matrix over GF(2) which represents the transition caused by letter <i>a</i>.  For example, the configuration vector after reading the input string <i>a</i><i>b</i> is <i>A</i><sub><i>b</i></sub><i>A</i><sub><i>a</i></sub><i>v</i><sub>0</sub>.  For a string <i>σ</i>=<i>a</i><sub>1</sub>…<i>a</i><sub><i>t</i></sub>, we denote the product <i>A</i><sub><i>a</i><sub><i>t</i></sub></sub>…<i>A</i><sub><i>a</i><sub>1</sub></sub> by <i>M</i>(<i>σ</i>).  Let <i>S</i> = {<i>A</i><sub>1</sub>, …, <i>A</i><sub><i>k</i></sub>}.</p>

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

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

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

<p>Because <i>L</i> is finite, let <i>m</i> be an integer larger than the length of any string in <i>L</i>.</p>

<p><strong>Lemma 1</strong>.  For any string <i>σ</i> of length at least <i>m</i>, we have that <i>M</i>(<i>σ</i>)=0.</p>

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

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

<p>We need one more fact from linear algebra.</p>

<p><strong>Lemma 2</strong>.  Let <i>A</i><sub>1</sub>, …, <i>A</i><sub><i>k</i></sub> be <i>n</i>×<i>n</i> matrices over a field, and define <i>M</i>(<i>σ</i>) as above.  If there is <i>m</i>≥0 such that <i>M</i>(<i>σ</i>)=0 for every string <i>σ</i> of length at least <i>m</i>, then the matrices <i>A</i><sub>1</sub>, …, <i>A</i><sub><i>k</i></sub> are simultaneously similar to strictly lower triangular matrices (that is, there exists an <i>n</i>×<i>n</i> nonsingular matrix <i>P</i> such that the matrices <i>P</i><sup>−1</sup><i>A</i><sub>1</sub><i>P</i>, …, <i>P</i><sup>−1</sup><i>A</i><sub><i>k</i></sub><i>P</i> are strictly lower triangular).</p>

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

<p>Now consider the <i>n</i>-state XOR automaton in which the transition matrix corresponding to symbol <i>a</i>∈Σ is given by <i>P</i><sup>−1</sup><i>A</i><sub><i>a</i></sub><i>P</i>, the initial configuration vector is given by <i>P</i><sup>−1</sup><i>v</i><sub>0</sub>, and the characteristic (row) vector of the accepting states is given by <i>s</i><i>P</i>.  By construction, this XOR automaton accepts the same language <i>L</i>.  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.</p>

CC BY-SA 3.0
2014-10-09T09:08:49.270Z
How does using the quotient vector space V/W translate to using a NXA with < n states?
Abel Molina
CC BY-SA 3.0
2014-10-09T21:39:46.977Z
@Abel: Let W be a nontrivial S-invariant subspace contained in R. Then each matrix A_a induces a linear mapping $\overline{A_a}$ from V/W to itself (because W is S-invariant), and the row vector s induces a linear mapping $\bar{s}$ from V/W to GF(2) (because W is contained in R). Because W is nontrivial, d:=dim(V/W)<n. Now consider a basis of V/W that contains v_0 mod W, and write linear mappings $\overline{A_a}$ and linear mapping $\bar{s}$ in this basis as matrices and a row vector, respectively. These matrices and row vector define an XOR automaton for the same language with d(<n) states.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-06T18:36:20.887Z
2014-10-06T18:36:20.887Z
Tsuyoshi Ito
<p>I think I can prove that cycles do not help over the unary alphabet.</p>

<p>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.</p>

CC BY-SA 3.0
2014-10-03T20:05:17.517Z
2014-10-03T20:05:17.517Z
domotorp
<p>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).</p>

<p>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).</p>

<p>This is not necessarily the case for NXAs.</p>

<p>Denote by $xsc(L)$ the <em>xor-state complexity</em> of a language $L$, </p>

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

<blockquote>
  <p>Is it true that for every finite language $L$: $$axsc(L)=xsc(L)\ ?$$</p>
</blockquote>

CC BY-SA 3.0
2014-10-03T15:11:00.130Z
Could you please give an example of NXA containing a (some) cycle(s) for a finite language?
Abuzer Yakaryilmaz
CC BY-SA 3.0
2014-10-03T15:31:34.747Z
If there are cycles there might be infinitely many accepting paths (if you allow $\epsilon$ edges), so you have to forbid $\epsilon$-cycles.
Yuval Filmus
CC BY-SA 3.0
2014-10-03T18:18:38.527Z
@Abuzer The one state automaton without any accepting states is an example. I know it is a stupid example but that's the point of the question, that every cycle is removable.
domotorp
CC BY-SA 3.0
2014-10-03T18:19:27.597Z
Btw, how do you define cycle? Paths leading to accepting states should be cycle-free?
domotorp
<fl.formal-languages><automata-theory><nondeterminism><minimization>
Does XOR automata (NXA) for finite languages benefit from cycles?
R B
# Does XOR automata (NXA) for finite languages benefit from cycles?

(Asked by: username_0 on 2014-10-02)

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)\ ?$$

**Tags:** fl.formal-languages, automata-theory, nondeterminism, minimization
> **Comments:**
> **username_1**: Could you please give an example of NXA containing a (some) cycle(s) for a finite language?  
> **username_2**: If there are cycles there might be infinitely many accepting paths (if you allow $\epsilon$ edges), so you have to forbid $\epsilon$-cycles.  
> **username_3**: @Abuzer The one state automaton without any accepting states is an example. I know it is a stupid example but that's the point of the question, that every cycle is removable.  
> **username_3**: Btw, how do you define cycle? Paths leading to accepting states should be cycle-free?  

---

## 2 answers

### Answer by username_4 on 2014-10-06. Score: 5 | Accepted answer

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 *v*0 = (1, 0, …, 0)T ∈ *V* be the elementary vector corresponding to the initial state, and let *s* be the row vector whose *i*th entry is 1 if and only if state *i* is an accepting state. The subspace *R* = {*v*: *s**v*=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 *a**b* is *A**b**A**a**v*0. For a string *σ*=*a*1…*a**t*, we denote the product *A**a**t*…*A**a*1 by *M*(*σ*). Let *S* = {*A*1, …, *A**k*}.

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

Now consider any vector *v*∈*V*. Because the only *S*-invariant subspace of *V* that contains *v*0 is *V* itself, *v* can be written as a linear combination of vectors of the form *M*(*τ*)*v*0 for some strings *τ*. Because *M*(*σ*)*M*(*τ*)*v*0 = *M*(*τ**σ*)*v*0 = 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*1, …, *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*1, …, *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*−1*A*1*P*, …, *P*−1*A**k**P* 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*−1*A**a**P*, the initial configuration vector is given by *P*−1*v*0, and the characteristic (row) vector of the accepting states is given by *s**P*. 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.

> **Comments:**
> **username_5**: How does using the quotient vector space V/W translate to using a NXA with < n states?  
> **username_4**: @Abel: Let W be a nontrivial S-invariant subspace contained in R. Then each matrix A_a induces a linear mapping $\overline{A_a}$ from V/W to itself (because W is S-invariant), and the row vector s induces a linear mapping $\bar{s}$ from V/W to GF(2) (because W is contained in R). Because W is nontrivial, d:=dim(V/W)<n. Now consider a basis of V/W that contains v_0 mod W, and write linear mappings $\overline{A_a}$ and linear mapping $\bar{s}$ in this basis as matrices and a row vector, respectively. These matrices and row vector define an XOR automaton for the same language with d(<n) states.  

---

### Answer by username_3 on 2014-10-03. Score: 4

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.


---

