<p>I detail the comment below, as you could be interested in this answer.
I don't know about NFA, but if your goal is to represent this language with a small automaton,  you could use the model of <em>alternating</em> automata, or AFA.</p>

<p>Intuitively, DFA are with $0$ player: the run is updated automatically, NFA are with $1$ player who has to choose a good run, and AFA are played by two players: one tries to accept, the other to reject. The word is in the language if the "good" player (who wants to accept) has a winning strategy on this word. This does not increase the expressive power of automata.</p>

<p>Here, you have an AFA with essentially $kr (\log n)^k$ states: 
At one point the opposite player can guess that some letter with same position modulo $r$ will be equal to the current one.
Then the "good" player guesses $k$ bit positions of the current letter (this requires $(\log n)^k$ memory) : one which will be different for each later equivalent position. Then we just have to check that one of these bits is indeed different every $r$ positions.</p>

CC BY-SA 3.0
2014-07-16T10:10:34.980Z
Thanks @Denis. While this is an interesting model, I'm specifically interested in either NFA or NXA (Non deterministic Xor Automaton), as these are the ones I know to simulate as a part of a larger algorithm I have. I know how to build $\widetilde O(2^{rk})$ NXA for this language and $\widetilde O(4^{rk})$ NFA, but I believe it's likely that a $[2^{k\cdot o(r)}\cdot \text{poly}\ n]$ sized NFA/NXA for it exists.
R B
CC BY-SA 3.0
2014-07-16T09:49:30.467Z
2014-07-16T16:52:04.043Z
2014-07-16T16:52:04.043Z
Denis
<p>This question is about an extension of a language <a href="https://cstheory.stackexchange.com/questions/20468/bounds-on-the-size-of-the-smallest-nfa-for-l-k-distinct">discussed in this question</a>.</p>

<p>We define the $r$-skip $k$-distinct language as follows:</p>

<p>$$L_{r,k}=\{\sigma_1\sigma_2\cdots \sigma_{rk}\in\Sigma^{rk} | \forall i\neq j\in [rk],i=j \mod r\implies \sigma_i \neq\sigma_j\}$$</p>

<p>That is, the set of letters whose distance is a multiplication of $r$ are different.</p>

<p>This language is finite and therefore regular. Specifically, if $|\Sigma|=n$, then $|L_{r,k}|=$$({n\choose{k}}\cdot k!)^r$.</p>

<p>For $r=1$ we get the language $L_{k-distinct}$ defined in the linked question.</p>

<p>A natural NFA build for $L_{r,k}$ uses the color coding scheme and for a $(|\Sigma|,k)$-perfect hashing family $\mathcal F$ (i.e. mapping the letters into $k$ indices) selects a hash function $f\in \mathcal F$ by an epsilon transition and then verifies that each set of letters $\Sigma_i = \{\sigma_j|i=j \mod r\}$ is distinct.</p>

<p>Such perfect hashing family build of size $O(e^{k+\log^3 k}\cdot n\log n)$ is known</p>

<p>The resulting automaton is of size $O((2e)^{r(k+O(\log^3 k))}\cdot n\ \text{polylog}\ n)$, which is the same as we would get for $L_{1,rk}$ (which is $L_{rk-distinct}$) by using the same approach.
(The reason for this size, at least in a naive build, is that the automaton state have to encode which of the $k$ colors we've seen for each of the $r$ letter sets). </p>

<p>A more careful build would give $O(4^{r(k+O(\log^2 k))}\cdot n\ \text{polylog}\ n)$ sized automaton (same goes for $L_{1,rk}$).</p>

<p>This sounds <em>wasteful</em>, as a lot fewer comparison are needed as $r$ grows larger (and $rk$ is constant).</p>

<p><strong>What is the smallest automaton we can build for $L_{r,k}$?</strong></p>

CC BY-SA 3.0
2014-07-15T22:55:50.050Z
at least there is a small alternating automaton
Denis
CC BY-SA 3.0
2014-07-16T04:44:40.893Z
@Denis - what do you mean?
R B
<fl.formal-languages><regular-language><upper-bounds><nondeterminism>
Bounds on the size of NFA for $r$-skip $k$-distinct language
R B
# Bounds on the size of NFA for $r$-skip $k$-distinct language

(Asked by: username_0 on 2014-07-14)

This question is about an extension of a language [discussed in this question](https://cstheory.stackexchange.com/questions/20468/bounds-on-the-size-of-the-smallest-nfa-for-l-k-distinct).

We define the $r$-skip $k$-distinct language as follows:

$$L\_{r,k}=\{\sigma\_1\sigma\_2\cdots \sigma\_{rk}\in\Sigma^{rk} | \forall i\neq j\in [rk],i=j \mod r\implies \sigma\_i \neq\sigma\_j\}$$

That is, the set of letters whose distance is a multiplication of $r$ are different.

This language is finite and therefore regular. Specifically, if $|\Sigma|=n$, then $|L\_{r,k}|=$$({n\choose{k}}\cdot k!)^r$.

For $r=1$ we get the language $L\_{k-distinct}$ defined in the linked question.

A natural NFA build for $L\_{r,k}$ uses the color coding scheme and for a $(|\Sigma|,k)$-perfect hashing family $\mathcal F$ (i.e. mapping the letters into $k$ indices) selects a hash function $f\in \mathcal F$ by an epsilon transition and then verifies that each set of letters $\Sigma\_i = \{\sigma\_j|i=j \mod r\}$ is distinct.

Such perfect hashing family build of size $O(e^{k+\log^3 k}\cdot n\log n)$ is known

The resulting automaton is of size $O((2e)^{r(k+O(\log^3 k))}\cdot n\ \text{polylog}\ n)$, which is the same as we would get for $L\_{1,rk}$ (which is $L\_{rk-distinct}$) by using the same approach.
(The reason for this size, at least in a naive build, is that the automaton state have to encode which of the $k$ colors we've seen for each of the $r$ letter sets).

A more careful build would give $O(4^{r(k+O(\log^2 k))}\cdot n\ \text{polylog}\ n)$ sized automaton (same goes for $L\_{1,rk}$).

This sounds *wasteful*, as a lot fewer comparison are needed as $r$ grows larger (and $rk$ is constant).

**What is the smallest automaton we can build for $L\_{r,k}$?**

**Tags:** fl.formal-languages, regular-language, upper-bounds, nondeterminism
> **Comments:**
> **username_1**: at least there is a small alternating automaton  
> **username_0**: @Denis - what do you mean?  

---

## 1 answers

### Answer by username_1 on 2014-07-16. Score: 2

I detail the comment below, as you could be interested in this answer.
I don't know about NFA, but if your goal is to represent this language with a small automaton, you could use the model of *alternating* automata, or AFA.

Intuitively, DFA are with $0$ player: the run is updated automatically, NFA are with $1$ player who has to choose a good run, and AFA are played by two players: one tries to accept, the other to reject. The word is in the language if the "good" player (who wants to accept) has a winning strategy on this word. This does not increase the expressive power of automata.

Here, you have an AFA with essentially $kr (\log n)^k$ states:
At one point the opposite player can guess that some letter with same position modulo $r$ will be equal to the current one.
Then the "good" player guesses $k$ bit positions of the current letter (this requires $(\log n)^k$ memory) : one which will be different for each later equivalent position. Then we just have to check that one of these bits is indeed different every $r$ positions.

> **Comments:**
> **username_0**: Thanks @Denis. While this is an interesting model, I'm specifically interested in either NFA or NXA (Non deterministic Xor Automaton), as these are the ones I know to simulate as a part of a larger algorithm I have. I know how to build $\widetilde O(2^{rk})$ NXA for this language and $\widetilde O(4^{rk})$ NFA, but I believe it's likely that a $[2^{k\cdot o(r)}\cdot \text{poly}\ n]$ sized NFA/NXA for it exists.  

---

