Minimal NFA and biRFSA languages
Latteux, Michel ; Roos, Yves ; Terlutte, Alain1
1 Équipe Grappa–EA 3588, Université de Lille 3, Domaine universitaire du “Pont de bois”, BP 149, 59653 Villeneuve d’Ascq Cedex, France;
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 2, pp. 221-237.

Voir la notice de l'article dans Numdam

In this paper, we define the notion of biRFSA which is a residual finate state automaton (RFSA) whose the reverse is also an RFSA. The languages recognized by such automata are called biRFSA languages. We prove that the canonical RFSA of a biRFSA language is a minimal NFA for this language and that each minimal NFA for this language is a sub-automaton of the canonical RFSA. This leads to a characterization of the family of biRFSA languages. In the second part of this paper, we define the family of biseparable automata. We prove that every biseparable NFA is uniquely minimal among all NFAs recognizing a same language, improving the result of H. Tamm and E. Ukkonen for bideterministic automata.

DOI : 10.1051/ita:2008022
Classification : 68Q45
Mots-clés : residual finite state automata, minimal NFA

Latteux, Michel  ; Roos, Yves  ; Terlutte, Alain 1

1 Équipe Grappa–EA 3588, Université de Lille 3, Domaine universitaire du “Pont de bois”, BP 149, 59653 Villeneuve d’Ascq Cedex, France; 
@article{ITA_2009__43_2_221_0,
     author = {Latteux, Michel and Roos, Yves and Terlutte, Alain},
     title = {Minimal {NFA} and {biRFSA} languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {221--237},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {2},
     year = {2009},
     doi = {10.1051/ita:2008022},
     zbl = {1166.68025},
     mrnumber = {2512256},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2008022/}
}
TY  - JOUR
AU  - Latteux, Michel
AU  - Roos, Yves
AU  - Terlutte, Alain
TI  - Minimal NFA and biRFSA languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
SP  - 221
EP  - 237
VL  - 43
IS  - 2
PB  - EDP-Sciences
UR  - https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2008022/
DO  - 10.1051/ita:2008022
LA  - en
ID  - ITA_2009__43_2_221_0
ER  - 
%0 Journal Article
%A Latteux, Michel
%A Roos, Yves
%A Terlutte, Alain
%T Minimal NFA and biRFSA languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2009
%P 221-237
%V 43
%N 2
%I EDP-Sciences
%U https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2008022/
%R 10.1051/ita:2008022
%G en
%F ITA_2009__43_2_221_0
Latteux, Michel; Roos, Yves; Terlutte, Alain. Minimal NFA and biRFSA languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 2, pp. 221-237. doi : 10.1051/ita:2008022. https://geodesic-test.mathdoc.fr/articles/10.1051/ita:2008022/

Cité par Sources :