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.
Mots-clés : residual finite state automata, minimal NFA
@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}, mrnumber = {2512256}, zbl = {1166.68025}, language = {en}, url = {http://archive.numdam.org/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 - http://archive.numdam.org/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 http://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ita:2008022/
[1] Inference of reversible languages. J. ACM 29 (1982) 741-765. | MR | Zbl
.[2] A note about minimal non deterministic finite automata. Bull. EATCS 47 (1992) 166-169. | Zbl
, , and .[3] On the minimalization of non-deterministic automaton. Technical report, Laboratoire de Calcul de la Faculté des Sciences de Lille (1970).
.[4] NFA reduction algorithms by means of regular inequalities. Theoretical Computer Science 327 (2004) 241-253. | MR | Zbl
and .[5] Residual finite state automata. In Proceedings of STACS 2001 2010. Springer-Verlag, Dresden (2001) 144-157. | MR | Zbl
, , and .[6] Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979). | MR | Zbl
and .[7] Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Massachusetts (1979). | MR | Zbl
and .[8] On the equivalence, containment, and covering problems for the regular and context-free languages. Journal of Computer and System Sciences 12 (1976) 222-268. | MR | Zbl
, , and .[9] Identification of biRFSA languages. Theoretical Computer Science 356 (2006) 212-223. | MR | Zbl
, , , and .[10] BiRFSA languages and minimal NFAs. Technical Report GRAPPA-0205, GRAppA, (2006).
, , and .[11] Computing small nondeterministic automata. In U.H. Engberg, K.G. Larsen, and A. Skou, Eds., Workshop on Tools and Algorithms for the Construction and Analysis of Systems (1995).
and .[12] Finite automata. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B). Elsevier (1990) 1-57. | MR | Zbl
.[13] On reversible automata. In Proceedings of the first LATIN conference, Saõ-Paulo. Lecture Notes in Computer Science 583. Springer Verlag (1992) 401-416. | MR
.[14] Word problems requiring exponential time(preliminary report). In STOC '73: Proceedings of the fifth annual ACM symposium on Theory of computing. ACM Press, NY, USA (1973) 1-9. | MR | Zbl
and .[15] Bideterministic automata and minimal representations of regular languages. Theoretical Computer Science 328 (2004) 135-149. | MR | Zbl
and .Cité par Sources :