Minimizando autômatos residuais de estado finito

Autômatos residuais de estado finito (RFSAs, definidos em [DLT02]) são NFAs que possuem alguns recursos interessantes em comum com os DFAs. Em particular, sempre existe um RFSA de tamanho mínimo canônico para cada idioma regular, e o idioma reconhecido por cada estado no RFSA é um resíduo, assim como em um DFA. No entanto, enquanto um estado mínimo de DFAs forma uma bijeção com todos os resíduos, os estados canônicos de RFSAs estão em bijeção com os resíduos principais; pode haver exponencialmente menos desses, portanto os RFSAs podem ser muito mais compactos que os DFAs para representar idiomas comuns.

No entanto, não sei dizer se existe um algoritmo eficiente para minimizar RFSAs ou se há um resultado de dureza. Qual é a complexidade de minimizar RFSAs?

Na navegação [BBCF10], não parece que isso seja de conhecimento geral. Por um lado, espero que isso seja difícil, porque muitas perguntas simples sobre RFSAs como "este NFA é um RFSA?" são muito difíceis, PSPACE-completo neste caso. Por outro lado, [BHKL09] mostra que os RFSAs canônicos são eficientemente aprendíveis no modelo de professor minimamente adequado [A87] da Angluin, e aprender eficientemente um RFSA mínimo e minimizar os RFSAs parece ser de igual dificuldade. No entanto, até onde eu sei, o algoritmo de [BHKL09] não implica um algoritmo de minimização, pois o tamanho dos contra-exemplos não é limitado e não está claro como testar eficientemente os RFSAs quanto à igualdade para simular o oráculo do contra-exemplo . Testar dois NFAs quanto à igualdade é completo no PSPACE , por exemplo.

Referências

[A87] Angluin, D. (1987). Aprendendo conjuntos regulares com consultas e contra-exemplos. Informação e computação, 75: 87-106

[BBCF10] Berstel, J., Boasson, L., Carton, O., & Fagnot, I. (2010). Minimização de autômatos. arXiv: 1010.5318 .

[BHKL09] Bollig, B., Habermehl, P., Kern, C., & Leucker, M. (2009). Aprendizagem no estilo Angluin da NFA. In IJCAI , 9: 1004-1009.

Denis, F., Lemay, A. e Terlutte, A. (2002). Autômatos residuais de estado finito. Fundemnta Informaticae , 51 (4): 339-368.

$\to$$A$$k$$k$$A$$\to$

$\to$$A_1,A_2,\ldots,A_n$$\bigcup_{i=1}^nL(A_i) = \Sigma^*$

$L$$k$$L$$A_i$$L$$k$$\bigcup_{i=1}^nL(A_i)$$k+1$$k$$N$$L$$\bigcup_{i=1}^nL(A_i) = \Sigma^*$

$R$$S$$(x_i,y_i)$$i$$x_iy_i\in L$$i\neq j$$x_iy_j \notin R$$x_jy_i\notin R$

$S$$k$$\bigcup_{i=1}^nL(A_i)$$x_i$$S$$N$$q_i$$x_i$$q$$x_i^{-1}L$$N$

$\to$$\to$$\to$$\to$

$N$

T. Jiang e B. Ravikumar. Problemas mínimos de NFA são difíceis. SIAM Journal on Computing, 22 (6): 1117-1141, dezembro de 1993.

Hermann Gruber e Markus Holzer. Encontrar limites mais baixos para a complexidade não-determinística do estado é difícil. Em Oscar H. Ibarra e Zhe Dang, editores, 10a Conferência Internacional sobre Desenvolvimentos em Teoria da Linguagem (DLT 2006), Santa Barbara (CA), EUA, volume 4036 de Lecture Notes in Computer Science, páginas 363--374. Springer, junho de 2006.

Hermann Gruber e Markus Holzer. Encontrar limites mais baixos para a complexidade do estado não determinístico é difícil. Relatório Técnico ECCC TR06-027, Colóquio Eletrônico sobre Complexidade Computacional, 2006.