Número de classes de equivalência em idiomas regulares em função do tamanho do DFA

Esta pergunta está relacionada a uma pergunta recente de Janoma .

fundo

Na programação restrição, um normal global de restrição ao longo de um domínio é um par (S, M) com s um tuplo de variáveis (o escopo) e M um DFA sobre o domínio D . Uma atribuição \ theta a s satisfaz c se M aceitar a sequência \ theta (s_1) \ theta (s_2) \ ldots \ theta (s_n) .$c$$D$$(s, M)$$s$$M$$D$$\theta$$s$$c$$M$$\theta(s_1)\theta(s_2)\ldots\theta(s_n)$

Abaixo, suponha que o domínio $D$ seja fixo. Defina uma relação de equivalência $\sim$ sobre o conjunto de cadeias $T = D^{|s|}$ modo que $a \sim b$ se para cada DFA $M$ seja $a, b \in L(M)$ ou $a, b \not\in L(M)$ . Intuitivamente, duas cadeias são equivalentes se nenhum DFA puder distingui-las. Se isso for verdade, eles também satisfazem as mesmas restrições regulares .

Se não restringirmos os DFAs de forma alguma, o conjunto de classes de equivalência $T/{\sim}$ será apenas o próprio $T$Estou interessado no número de classes de equivalência wrt. $\sim$ em função do número de estados $n$ que permitimos para o DFA. Claramente, se $n = |D|^{|s|}$ (ignorar constantes), então $|T/{\sim}| = |T|$. (Obviamente, $n$ aqui será uma função de $|s|$ .)

Questões

1. Qual é o menor $n$ para o qual $|T/{\sim}| = |T|$?
2. O que acontece abaixo disso? Em particular,
   • existe um $n$ tal que $|T/{\sim}| = O(|s|^{|D|})$ ?
   • existe um tal que ?$n$$|T/{\sim}| = O(|s| \times |D|)$

Minha motivação para essa pergunta é que ter um número polinomial ( ) de classes de equivalência como essa me deu um caso tratável de problemas de restrição com restrições de cardinalidade. Agora estou tentando ver se algo nesse sentido pode ser feito para a restrição regular.$|s|^{|D|}$

Edit : Observe também esta resposta de Hermann Gruber à pergunta referenciada no topo. Os limites no artigo, os links de resposta, devem produzir um tal que a resposta à pergunta 1 deve ser , mas não é óbvio para mim.$k$$\geq k$

Resposta à pergunta 1,

Qual é o menor para o qual?$n$$|T/{\sim}|=|T|$

Temos que é o menor número de estados em qualquer DFA que aceita um dos e , mas não o outro. O limite superior mais conhecido em é então (veja alguns slides de Jeffrey Shallit )

$$n=\max_{|w|=|x|=s,\\ w\ne x}\mathrm{sep}(w,x)$$ $\mathrm{sep}(w,x)$$w$$x$$n$

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

que foi obtido em

Robson, JM , Separando strings com pequenos autômatos , Inf. Processo. Lett. 30, No. 4, 209-214 (1989). ZBL0666.68051 .