| Issue |
RAIRO-Theor. Inf. Appl.
Volume 43, Number 2, April-June 2009
|
|
|---|---|---|
| Page(s) | 221 - 237 | |
| DOI | https://doi.org/10.1051/ita:2008022 | |
| Published online | 23 May 2008 | |
Minimal NFA and biRFSA Languages
1
Laboratoire d'Informatique Fondamentale de Lille, UMR CNRS 8022,
Université de Lille 1, 59655 Villeneuve d'Ascq Cedex, France; michel.latteuxyves.roos@lifl.fr
2
Équipe Grappa–EA 3588,
Université de Lille 3,
Domaine universitaire du “Pont de bois”,
BP 149, 59653 Villeneuve d'Ascq Cedex, France;
alain.terlutte@univ-lille3.fr
Received:
1
June
2006
Accepted:
25
February
2008
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.
Mathematics Subject Classification: 68Q45
Key words: Residual finite state automata; minimal NFA
© EDP Sciences, 2008
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.