14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Could you please give an example of NXA containing a (some) cycle(s) for a finite language? $\endgroup$ – Abuzer Yakaryilmaz Oct 3 '14 at 15:11
  • 2
    $\begingroup$ If there are cycles there might be infinitely many accepting paths (if you allow $\epsilon$ edges), so you have to forbid $\epsilon$-cycles. $\endgroup$ – Yuval Filmus Oct 3 '14 at 15:31
  • $\begingroup$ @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. $\endgroup$ – domotorp Oct 3 '14 at 18:18
  • $\begingroup$ Btw, how do you define cycle? Paths leading to accepting states should be cycle-free? $\endgroup$ – domotorp Oct 3 '14 at 18:19
5
$\begingroup$

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)TV 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 σ=a1at, we denote the product AatAa1 by M(σ). Let S = {A1, …, Ak}.

A subspace W of V is said to be S-invariant when AWW for every AS. 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 vV. 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.

$\endgroup$
  • $\begingroup$ How does using the quotient vector space V/W translate to using a NXA with < n states? $\endgroup$ – Abel Molina Oct 9 '14 at 9:08
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Oct 9 '14 at 21:39
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.