Minimal NFA and biRFSA Languages

Michel Latteux 1 Yves Roos 1, 2, * Alain Terlutte 1, 2
* Auteur correspondant
2 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : 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.
Type de document :
Article dans une revue
RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2009, 43 (2), pp.221-237. 〈10.1051/ita:2008022〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00296658
Contributeur : Yves Roos <>
Soumis le : mardi 15 juillet 2008 - 08:45:32
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

Collections

Citation

Michel Latteux, Yves Roos, Alain Terlutte. Minimal NFA and biRFSA Languages. RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2009, 43 (2), pp.221-237. 〈10.1051/ita:2008022〉. 〈inria-00296658〉

Partager

Métriques

Consultations de la notice

224