Minimal NFA and biRFSA Languages

Michel Latteux; Yves Roos; Alain Terlutte

RAIRO - Theoretical Informatics and Applications (2008)

  • Volume: 43, Issue: 2, page 221-237
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Latteux, Michel, Roos, Yves, and Terlutte, Alain. "Minimal NFA and biRFSA Languages." RAIRO - Theoretical Informatics and Applications 43.2 (2008): 221-237. <http://eudml.org/doc/92913>.

@article{Latteux2008,
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. },
author = {Latteux, Michel, Roos, Yves, Terlutte, Alain},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Residual finite state automata; minimal NFA; residual finite state automata; minimal NFA},
language = {eng},
month = {5},
number = {2},
pages = {221-237},
publisher = {EDP Sciences},
title = {Minimal NFA and biRFSA Languages},
url = {http://eudml.org/doc/92913},
volume = {43},
year = {2008},
}

TY - JOUR
AU - Latteux, Michel
AU - Roos, Yves
AU - Terlutte, Alain
TI - Minimal NFA and biRFSA Languages
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/5//
PB - EDP Sciences
VL - 43
IS - 2
SP - 221
EP - 237
AB - 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.
LA - eng
KW - Residual finite state automata; minimal NFA; residual finite state automata; minimal NFA
UR - http://eudml.org/doc/92913
ER -

References

top
  1. Dana Angluin. Inference of reversible languages. J. ACM29 (1982) 741–765.  Zbl0485.68066
  2. André Arnold, Anne Dicky, and Maurice Nivat. A note about minimal non deterministic finite automata. Bull. EATCS47 (1992) 166–169.  Zbl0751.68038
  3. Christian Carrez. On the minimalization of non-deterministic automaton. Technical report, Laboratoire de Calcul de la Faculté des Sciences de Lille (1970).  
  4. Jean-Marc Champarnaud and Fabien Coulon. NFA reduction algorithms by means of regular inequalities. Theoretical Computer Science327 (2004) 241–253.  Zbl1037.68078
  5. François Denis, Aurélien Lemay, and Alain Terlutte. Residual finite state automata. In Proceedings of STACS 20012010. Springer-Verlag, Dresden (2001) 144–157.  Zbl0976.68089
  6. Michael R. Garey and David S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979).  Zbl0411.68039
  7. JE Hopcroft and JD Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Massachusetts (1979).  
  8. Harry B. HuntIII, Daniel J. Rosenkrantz, and Thomas G. Szymanski. On the equivalence, containment, and covering problems for the regular and context-free languages. Journal of Computer and System Sciences12 (1976) 222–268.  Zbl0334.68044
  9. Michel Latteux, Aurélien Lemay, Yves Roos, and Alain Terlutte. Identification of biRFSA languages. Theoretical Computer Science356 (2006) 212–223.  Zbl1160.68417
  10. Michel Latteux, Yves Roos, and Alain Terlutte. BiRFSA languages and minimal NFAs. Technical Report GRAPPA-0205, GRAppA, (2006).  Zbl1166.68025
  11. Oliver Matz and Andreas Potthoff. 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).  
  12. Dominique Perrin. Finite automata. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B). Elsevier (1990) 1–57.  
  13. Jean-Eric Pin. On reversible automata. In Proceedings of the first LATIN conference, Saõ-Paulo. Lecture Notes in Computer Science 583. Springer Verlag (1992) 401–416.  
  14. L.J. Stockmeyer and A.R. Meyer. 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.  Zbl0359.68050
  15. Hellis Tamm and Esko Ukkonen. Bideterministic automata and minimal representations of regular languages. Theoretical Computer Science328 (2004) 135–149.  Zbl1071.68052

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.