Google scholar arxiv informatics ads IJAIS publications are indexed with Google Scholar, NASA ADS, Informatics et. al.

Call for Paper

-

November Edition 2021

International Journal of Applied Information Systems solicits high quality original research papers for the November 2021 Edition of the journal. The last date of research paper submission is October 15, 2021.

A New NFA Reduction Algorithm for State Minimization Problem

Himanshu Pandey, V. K Singh, Amit Pandey Published in Algorithms

International Journal of Applied Information Systems
Year of Publication: 2015
© 2013 by IJAIS Journal
10.5120/ijais15-451298
Download full text
  1. Himanshu Pandey, V K Singh and Amit Pandey. Article: A New NFA Reduction Algorithm for State Minimization Problem. International Journal of Applied Information Systems 8(3):27-30, February 2015. BibTeX

    @article{key:article,
    	author = "Himanshu Pandey and V. K Singh and Amit Pandey",
    	title = "Article: A New NFA Reduction Algorithm for State Minimization Problem",
    	journal = "International Journal of Applied Information Systems",
    	year = 2015,
    	volume = 8,
    	number = 3,
    	pages = "27-30",
    	month = "February",
    	note = "Published by Foundation of Computer Science, New York, USA"
    }
    

Abstract

The problem of creating a minimal NFA is a primal (fundamental) problem. Reducing the size of NFA by using NFA Reduction Algorithm has been shown to reduce importantly the search time. This paper innovate a new NFA reduction algorithm for the state minimization of NFA. The analysis of the proposed algorithm is given and also demonstrates the results of the numerical experiments. This paper conceives the problem of reducing the number of state and transition of Non Deterministic Finite Automata. Numerical experiments show that NFA reduction algorithm produces a minimal automation in all most condition. NFA reduction algorithm also resolves the complexity of Kameda-Weiner algorithm. This paper shown empirically that these algorithm are effective in largely reducing the memory requirement of NFA minimization algorithm.

Reference

  1. Lucian llie, Roberto Solis-Oba, Sheng yu: 2005,"Reducing the Size of NFAs by Using Equivalences and Preorders", Lecture Notes in Computer Science, Volume 3537, 2005, pp 310-321 in Springer.
  2. M. Albert and Steve Linton: July 2014. "A Practical Algorithm for Reducing Non-Deterministic Finite State Automata", Elsevier Science.
  3. Andrey V. Tsyganov: September 2012, "Local Search Heuristics for NFA State Minimization Problem", Int. J. Communications, Network and System Sciences, 2012, 5, 638-643.
  4. H. Gruber and M. Holzer: "Computational Complexity of NFA Minimization for Finite and Unary Languages",Institut f¨ur Informatik, Ludwig-Maximilians-Universit¨at M¨unchen, Oettingenstraße 67, D-80538 M¨unchen, Germany.
  5. Henrik Bj¨orklunda, Wim Martens: April 2011, "The Tractability Frontier for NFA Minimization", International Colloquium on Automata, Languages and Programming 2008.
  6. Yonghua Zhou Yuliu Chen, "The QFD-based Decision-making Approach for Strategic BPR" Beijing 100084, P. R. China.
  7. Guangming Xing, August 20-22, 2007 "Minimized Thompson NFA", Western Kentucky University, Bowling Green, KY 42101.
  8. V. Garg, Anu: June 2013, "DFA Minimizing State Machines Using Hash- Tables" ,International Journal of Engineering Trends and Technology (IJETT) - Volume4 Issue6- June 2013.
  9. Vlastimil Ko?sa?r, Martin ?Z ´adn´?k, Jan Ko?renek, 2007 "NFA Reduction for Regular Expressions Matching Using FPGA", MSM 0021630528, the IT4Innovations Centre of Excellence CZ. 1. 05/1. 1. 00/02. 0070 and the grant BUT FIT-S-11-1.
  10. M. Vázquez de Parga, P. García, Damián López, 2013 "A polynomial double reversal minimization algorithm for deterministic finite automata", Theoretical Computer Science 487 (2013) 17–22.
  11. J. Vuillemin, N. Gama: Dec 2009, "Efficient Equivalence and Minimization for Non Deterministic Xor Automata", [Research Report] 2010, pp. 25. .
  12. Wojciech Wieczorek : 2012, "Induction of Non-Deterministic Finite Automata on Supercomputers", JMLR: Workshop and Conference Proceedings 21:237{242, 2012 The 11th ICGI.
  13. M. Mohri, F. Pereira and M. Riley, "AT&T General- Purpose Finite-State Machine Software Tools," 1997. http://www. research. att. com/sw/tools/fsm
  14. S. Lombardy, R. Poss, Y. Régis-Gianas and J. Sa-karovitch, "Introducing VAUCANSON," In: O. H. Ibarra and Z. Dang, Eds. , Implementation and Application of Automata, CIAA 2003, Santa Barbara, 16-18 July 2003, pp. 96-107.
  15. S. H. Rodger, "JFLAP: An Interactive Formal Languages and Automata Package," Jones and Bartlett Publishers, Inc. , USA, 2006.
  16. T. Kameda and P. Weiner, "On the State Minimization of Nondeterministic Finite Automata," IEEE Transactions on Computers, Vol. C-19, No. 7, 1970, pp. 617-627. doi:10. 1109/T-C. 1970. 222994
  17. J. Hromkovic, "Algorithmics for Hard Problems—Intro- duction to Combinatorial Optimization, Randomization, Approximation, and Heuristics," Springer, Berlin, 2001.
  18. F. Glover and G. A. Kohenberger, "Handbook of Meta-heuristics," Kluwer Academic Publishers, Boston, 2003.
  19. V. Kell, A. Maier, A. Potthoff, W. Thomas and U. Wer-muth, "AMORE: A System for Computing Automata, Monoids and Regular Expressions," Proceedings of the 6th Annual Symposium on Theoretical Aspects of Com-puter Science on STACS 89, Springer-Verlag, New York.

Keywords

Non Deterministic Finite Automata (NFA), Simplest Automation Matrix, Rearward Automaton Matrix, Simplified Functional Matrix (SFM).