CFP last date
15 May 2024
Call for Paper
June Edition
IJAIS solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 15 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Analysis of ANN Training Algorithms for Hand Geometry-Based Access Control

Kazeem B. Adedeji Apena Waliu O. Adu Michael R.
Random Articles
Reseach Article

A New NFA Reduction Algorithm for State Minimization Problem

by Himanshu Pandey, V. K Singh, Amit Pandey
journal cover thumbnail

International Journal of Applied Information Systems
Foundation of Computer Science (FCS), NY, USA
Volume 8 - Number 3
Year of Publication: 2015
Authors: Himanshu Pandey, V. K Singh, Amit Pandey
10.5120/ijais15-451298

Himanshu Pandey, V. K Singh, Amit Pandey . A New NFA Reduction Algorithm for State Minimization Problem. International Journal of Applied Information Systems. 8, 3 ( February 2015), 27-30. DOI=10.5120/ijais15-451298

@article{ 10.5120/ijais15-451298,
author = { Himanshu Pandey, V. K Singh, Amit Pandey },
title = { A New NFA Reduction Algorithm for State Minimization Problem },
journal = { International Journal of Applied Information Systems },
issue_date = { February 2015 },
volume = { 8 },
number = { 3 },
month = { February },
year = { 2015 },
issn = { 2249-0868 },
pages = { 27-30 },
numpages = {9},
url = { https://www.ijais.org/archives/volume8/number3/717-1298/ },
doi = { 10.5120/ijais15-451298 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-07-05T18:58:50.527832+05:30
%A Himanshu Pandey
%A V. K Singh
%A Amit Pandey
%T A New NFA Reduction Algorithm for State Minimization Problem
%J International Journal of Applied Information Systems
%@ 2249-0868
%V 8
%N 3
%P 27-30
%D 2015
%I Foundation of Computer Science (FCS), NY, 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.

References
  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. Wojciech Wieczorek : 2012, "Induction of Non-Deterministic Finite Automata on Supercomputers", JMLR: Workshop and Conference Proceedings 21:237{242, 2012 The 11th ICGI.
  12. 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
  13. 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.
  14. S. H. Rodger, "JFLAP: An Interactive Formal Languages and Automata Package," Jones and Bartlett Publishers, Inc. , USA, 2006.
  15. 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
  16. J. Hromkovic, "Algorithmics for Hard Problems—Intro- duction to Combinatorial Optimization, Randomization, Approximation, and Heuristics," Springer, Berlin, 2001.
  17. F. Glover and G. A. Kohenberger, "Handbook of Meta-heuristics," Kluwer Academic Publishers, Boston, 2003.
  18. 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.
Index Terms

Computer Science
Information Sciences

Keywords

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

Powered by PhDFocusTM