The week's pick
Reseach Article
LR Rotation Rule for Creating Minimal NFA
| International Journal of Applied Information Systems |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 8 - Number 6 |
| Year of Publication: 2015 |
| Authors: Himanshu Pandey, V. K Singh, Neeraj Kumar Verma |
10.5120/ijais15-451324
|
Himanshu Pandey, V. K Singh, Neeraj Kumar Verma . LR Rotation Rule for Creating Minimal NFA. International Journal of Applied Information Systems. 8, 6 ( April 2015), 1-4. DOI=10.5120/ijais15-451324
Abstract
The problem of creating a minimal NFA is a primal (fundamental) problem. Reducing the size of NFA by using LR rotation rule has been shown to reduce importantly the search time. In [1] Ilie and Yu describe a construction of a right invariant equivalence relation on the states of a non-deterministic finite state automaton. We give a more efficient LR Rotation rule for constructing the minimal NFA. In this paper we represent new LR Rotation rule for the state minimization of NFA. The description of the proposed methods is given and we also shown the results of the numerical experiments. We conceive 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 cases. NFA reduction algorithm also reduces the complexity of Kameda-Weiner algorithm. We have shown empirically that these algorithms are effective in largely reducing the memory requirement of NFA minimization algorithm and algorithm minimization of the number of rules for NFA grows each year.
References
- L. 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.
- M. Albert and Steve Linton: July 2014, "A Practical Algorithm for Reducing Non-Deterministic Finite State Automata", Elsevier Science.
- A V. Tsyganov: September 2012, "Local Search Heuristics for NFA State Minimization Problem", Int. J. Communications, Network and System Sciences, 2012, 5, 638-643.
- 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.
- H. Bj¨orklunda, Wim Martens: April 2011, "The Tractability Frontier for NFA Minimization", International Colloquium on Automata, Languages and Programming 2008.
- Y. Zhou Yuliu Chen, "The QFD-based Decision-making Approach for Strategic BPR" Beijing 100084, P. R. China.
- G. Xing, August 20-22, 2007 "Minimized Thompson NFA", Western Kentucky University, Bowling Green, KY 42101.
- V. Garg, Anu: June 2013, "DFA Minimizing State Machines Using Hash- Tables", International Journal of Engineering Trends and Technology (IJETT) - Volume4 Issue6- June 2013.
- V. 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.
- 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.
- W. Wieczorek: 2012, "Induction of Non-Deterministic Finite Automata on Supercomputers", JMLR: Workshop and Conference Proceedings 21:237{242, 2012. The 11th ICGI.
- 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
- 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.
- S. H. Rodger, "JFLAP: An Interactive Formal Languages and Automata Package," Jones and Bartlett Publishers, Inc. , USA, 2006.
- 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
- J. Hromkovic, "Algorithmics for Hard Problems—Intro- duction to Combinatorial Optimization, Randomization, Approximation, and Heuristics," Springer, Berlin, 2001.
- F. Glover and G. A. Kohenberger, "Handbook of Meta-heuristics," Kluwer Academic Publishers, Boston, 2003.
- 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
Keywords