NFA Reduction Algorithms by Means of Regular Inequalities

  • Jean-Marc Champarnaud
  • Fabien Coulon
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


We present different techniques for reducing the number of states and transitions in nondeterministic automata. These techniques are based on the two preorders over the set of states, related to the inclusion of left and right languages. Since their exact computation is \( \mathcal{N}\mathcal{P} \)-hard, we focus on polynomial approximations which enable a reduction of the NFA all the same. Our main algorithm relies on a first approximation, which can be easily implemented by means of matrix products with an \( \mathcal{O}(sn^4 ) \) time complexity, and optimized to an \( \mathcal{O}(sn^3 ) \) time complexity, where s is the average nondeterministic arity and n is the number of states. This first algorithm appears to be more efficient than the known techniques based on equivalence relations as described by Lucian Ilie and Sheng Yu. Afterwards, we briefly describe some more accurate approximations and the exact (but exponential) calculation of these preorders by means of determinization.


Time Complexity Equivalence Relation Matrix Product Regular Expression High Order Approximation 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    J. Amilhastre, P. Janssen, and M.C. Vilarem. FA minimization heuristics for a class of finite languages. In O. Boldt and H. Jürgensen, editors, Automata Implementation, WIA’99, Lecture Notes in Computer Science, volume 2214, pages 1–12. Springer, 2001.CrossRefGoogle Scholar
  2. 2.
    V. Antimirov. Rewriting regular inequalities. Lecture notes in computer science, 965:116–125, 1995.Google Scholar
  3. 3.
    J.A. Brzozowski. Canonical regular expressions and minimal state graphs for definite events. Mathematical Theory of Automata, MRI Symposia Series, 12:529–561, 1962.Google Scholar
  4. 4.
    J.-M. Champarnaud and F. Coulon. Theoretical study and implementation of the canonical automaton. Technical Report AIA 2003.03, LIFAR, Université de Rouen, 2003.Google Scholar
  5. 5.
    J.-M. Champarnaud, F. Coulon, and T. Paranthoën. Compact and fast algorithms for regular expression search. Technical Report AIA 2003.01, LIFAR, Université de Rouen, 2003.Google Scholar
  6. 6.
    J. Daciuk, B.-W. Watson, and R.-E. Watson. Incremental construction of minimal acyclic finite state automata and transducers. In L. Karttunen, editor, FSMNLP’98, pages 48–55. Association for Computational Linguistics, Somerset, New Jersey, 1998.Google Scholar
  7. 7.
    John E. Hopcroft. An n log n algorithm for minimizing the states in a finite automaton. In Z. Kohavi, editor, The Theory of Machines and Computations, pages 189–196. Academic Press, 1971.Google Scholar
  8. 8.
    H. Hunt, D. Rosenkrantz, and T. Szymanski. On the equivalence, containment and covering problems for the regular and context-free languages. J. Comput. System Sci., 12:222–268, 1976.zbMATHMathSciNetGoogle Scholar
  9. 9.
    L. Ilie and S. Yu. Algorithms for computing small NFAs. In K. Diks and W. Rytter, editors, Lecture Notes in Computer Science, volume 2420, pages 328–340. Springer, 2002.Google Scholar
  10. 10.
    J. Jaja. An introduction to parallel algorithms. Addison-Wesley, 1992.Google Scholar
  11. 11.
    T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM J. Comput. Vol 22, No 6, pages 1117–1141, 1993.zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Trans. Comp., C(19):617–627, 1970.CrossRefMathSciNetGoogle Scholar
  13. 13.
    H. Sengoku. Minimization of nondeterministic finite automata. Master’s thesis, Kyoto University, 1992.Google Scholar
  14. 14.
    S. Wu and U. Manber. Fast text searching algorithm allowing errors. In Communication of the ACM, 31, pages 83–91, October 1992.CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Jean-Marc Champarnaud
    • 1
  • Fabien Coulon
    • 1
  1. 1.LIFARUniversity of RouenFrance

Personalised recommendations