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

11

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) .cD(s,M)sMDθscMθ(s1)θ(s2)θ(sn)

Abaixo, suponha que o domínio D seja fixo. Defina uma relação de equivalência sobre o conjunto de cadeias T=D|s| modo que ab se para cada DFA M seja a,bL(M) ou a,bL(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/ será apenas o próprio TEstou interessado no número de classes de equivalência wrt. em função do número de estados n que permitimos para o DFA. Claramente, se n=|D||s| (ignorar constantes), então |T/|=|T|. (Obviamente, n aqui será uma função de |s| .)

Questões

  1. Qual é o menor n para o qual |T/|=|T|?
  2. O que acontece abaixo disso? Em particular,
    • existe um n tal que |T/|=O(|s||D|) ?
    • existe um tal que ?n|T/|=O(|s|×|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.kk

Evgenij Thorstensen
fonte

Respostas:

1

Resposta à pergunta 1,

Qual é o menor para o qual?n|T/|=|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,wxsep(w,x)
sep(w,x)wxn

n=O(s2/5(logs)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 .

Bjørn Kjos-Hanssen
fonte