<p>Answer to Question 1,</p>

<blockquote>
  <p>What is the smallest <span class="math-container">$n$</span> for which <span class="math-container">$|T/{\sim}|=|T|$</span>?</p>
</blockquote>

<p>We have <span class="math-container">$$n=\max_{|w|=|x|=s,\\ w\ne x}\mathrm{sep}(w,x)$$</span>
where <span class="math-container">$\mathrm{sep}(w,x)$</span> is the smallest number of states in any DFA that accepts one of <span class="math-container">$w$</span> and <span class="math-container">$x$</span>, but not the other.
The best known upper bound on <span class="math-container">$n$</span> is then (see <a href="https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf" rel="nofollow noreferrer">some slides by Jeffrey Shallit</a>)</p>

<blockquote>
  <p><span class="math-container">$n=O(s^{2/5}(\log s)^{3/5})$</span>.</p>
</blockquote>

<p>which was obtained in</p>

<p><em>Robson, J. M.</em>, <a href="http://dx.doi.org/10.1016/0020-0190(89)90215-9" rel="nofollow noreferrer"><strong>Separating strings with small automata</strong></a>, Inf. Process. Lett. 30, No. 4, 209-214 (1989). <a href="https://zbmath.org/?q=an:0666.68051" rel="nofollow noreferrer">ZBL0666.68051</a>.</p>

CC BY-SA 4.0
2018-09-24T07:19:51.087Z
2018-09-24T07:55:14.503Z
2018-09-24T07:55:14.503Z
Bjørn Kjos-Hanssen
<p>This question is related to a <a href="https://cstheory.stackexchange.com/questions/7913/what-is-the-number-of-languages-accepted-by-a-dfa-of-size-n">recent
question</a>
by <a href="https://cstheory.stackexchange.com/users/5396/janoma">Janoma</a>.</p>
<h2>Background</h2>
<p>In constraint programming, a <strong>regular</strong> global constraint <span class="math-container">$c$</span> over a
domain <span class="math-container">$D$</span> is a pair <span class="math-container">$(s, M)$</span> with <span class="math-container">$s$</span> a tuple of variables (the
scope) and <span class="math-container">$M$</span> a DFA over the domain <span class="math-container">$D$</span>. An assignment <span class="math-container">$\theta$</span> to
<span class="math-container">$s$</span> satisfies <span class="math-container">$c$</span> if <span class="math-container">$M$</span> accepts the string
<span class="math-container">$\theta(s_1)\theta(s_2)\ldots\theta(s_n)$</span>.</p>
<p>Below, assume that the domain <span class="math-container">$D$</span> is fixed. Define an equivalence
relation <span class="math-container">$\sim$</span> over the set of strings <span class="math-container">$T = D^{|s|}$</span> such that <span class="math-container">$a
\sim b$</span> if for every DFA <span class="math-container">$M$</span> either <span class="math-container">$a, b \in L(M)$</span> or <span class="math-container">$a, b \not\in
L(M)$</span>. Intuitively, two strings are equivalent iff no DFA can
distinguish them. If that is true, then they also satisfy the same
<strong>regular</strong> constraints.</p>
<p>If we do not restrict the DFAs in any way, then the set of equivalence
classes <span class="math-container">$T/{\sim}$</span> is just <span class="math-container">$T$</span> itself. I am interested in the number of
equivalence classes wrt. <span class="math-container">$\sim$</span> as a function of the number of states <span class="math-container">$n$</span>
that we allow for the DFA. Clearly, if <span class="math-container">$n = |D|^{|s|}$</span> (ignore
constants) then <span class="math-container">$|T/{\sim}| = |T|$</span>. (Of course, <span class="math-container">$n$</span> here will itself be a
function of <span class="math-container">$|s|$</span>.)</p>
<h2>Questions</h2>
<ol>
<li>What is the smallest <span class="math-container">$n$</span> for which <span class="math-container">$|T/{\sim}| = |T|$</span>?</li>
<li>What happens below that? In particular,
<ul>
<li>is there an <span class="math-container">$n$</span> such that <span class="math-container">$|T/{\sim}| = O(|s|^{|D|})$</span>?</li>
<li>is there an <span class="math-container">$n$</span> such that <span class="math-container">$|T/{\sim}| = O(|s| \times |D|)$</span>?</li>
</ul>
</li>
</ol>
<p>My motivation for this question is that having a polynomial
(<span class="math-container">$|s|^{|D|}$</span>) number of equivalence classes like this gave me a
tractable case of constraint problems with cardinality constraints. I
am now trying to see if something along these lines can be done for
the regular constraint.</p>
<p><strong>Edit</strong>: Note also <a href="https://cstheory.stackexchange.com/questions/7913/what-is-the-number-of-languages-accepted-by-a-dfa-of-size-n/7922#7922">this answer</a> by <a href="https://cstheory.stackexchange.com/users/2367/hermann-gruber">Hermann Gruber</a> to the question referenced at the top. The bounds in the paper the answer links should yield a <span class="math-container">$k$</span> such that the answer to question 1 must be <span class="math-container">$\geq k$</span>, but it is not obvious to me.</p>

<co.combinatorics><fl.formal-languages><automata-theory><regular-language>
Number of equivalence classes in regular languages as a function of DFA size
Evgenij Thorstensen
# Number of equivalence classes in regular languages as a function of DFA size

(Asked by: username_0 on 2011-08-22)

This question is related to a [recent
question](https://cstheory.stackexchange.com/questions/7913/what-is-the-number-of-languages-accepted-by-a-dfa-of-size-n)
by [Janoma](https://cstheory.stackexchange.com/users/5396/janoma).

## Background

In constraint programming, a **regular** global constraint $c$ over a
domain $D$ is a pair $(s, M)$ with $s$ a tuple of variables (the
scope) and $M$ a DFA over the domain $D$. An assignment $\theta$ to
$s$ satisfies $c$ if $M$ accepts the string
$\theta(s\_1)\theta(s\_2)\ldots\theta(s\_n)$.

Below, assume that the domain $D$ is fixed. Define an equivalence
relation $\sim$ over the set of strings $T = D^{|s|}$ such that $a
\sim b$ if for every DFA $M$ either $a, b \in L(M)$ or $a, b \not\in
L(M)$. Intuitively, two strings are equivalent iff no DFA can
distinguish them. If that is true, then they also satisfy the same
**regular** constraints.

If we do not restrict the DFAs in any way, then the set of equivalence
classes $T/{\sim}$ is just $T$ itself. I am interested in the number of
equivalence classes wrt. $\sim$ as a function of the number of states $n$
that we allow for the DFA. Clearly, if $n = |D|^{|s|}$ (ignore
constants) then $|T/{\sim}| = |T|$. (Of course, $n$ here will itself be a
function of $|s|$.)

## Questions

1. What is the smallest $n$ for which $|T/{\sim}| = |T|$?
2. What happens below that? In particular,
   * is there an $n$ such that $|T/{\sim}| = O(|s|^{|D|})$?
   * is there an $n$ such that $|T/{\sim}| = O(|s| \times |D|)$?

My motivation for this question is that having a polynomial
($|s|^{|D|}$) number of equivalence classes like this gave me a
tractable case of constraint problems with cardinality constraints. I
am now trying to see if something along these lines can be done for
the regular constraint.

**Edit**: Note also [this answer](https://cstheory.stackexchange.com/questions/7913/what-is-the-number-of-languages-accepted-by-a-dfa-of-size-n/7922#7922) by [Hermann Gruber](https://cstheory.stackexchange.com/users/2367/hermann-gruber) to the question referenced at the top. The bounds in the paper the answer links should yield a $k$ such that the answer to question 1 must be $\geq k$, but it is not obvious to me.

**Tags:** co.combinatorics, fl.formal-languages, automata-theory, regular-language


---

## 1 answers

### Answer by username_1 on 2018-09-24. Score: 1

Answer to Question 1,

> What is the smallest $n$ for which $|T/{\sim}|=|T|$?

We have $$n=\max\_{|w|=|x|=s,\\ w\ne x}\mathrm{sep}(w,x)$$
where $\mathrm{sep}(w,x)$ is the smallest number of states in any DFA that accepts one of $w$ and $x$, but not the other.
The best known upper bound on $n$ is then (see [some slides by Jeffrey Shallit](https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf))

> $n=O(s^{2/5}(\log s)^{3/5})$.

which was obtained in

*Robson, J. M.*, [**Separating strings with small automata**](http://dx.doi.org/10.1016/0020-0190(89)90215-9), Inf. Process. Lett. 30, No. 4, 209-214 (1989). [ZBL0666.68051](https://zbmath.org/?q=an:0666.68051).


---

