A Novel Approach to Minimize DFA State Machines Using Linked List
Keywords:
DFA, NFA, Regular expressions, Compiler Design, Linked ListAbstract
DFA minimization is a significant problem in algorithm design. Minimization of DFA works on the concept of DFA equivalence: Two DFA’s are equivalent if and only if both accept the identical strings of same set. Plethora of computational problems can be solved simply by using the encoding method. Combinatorial objects which are to be used as strings over a finite alphabet can be encoded. Standard algorithms from computational linear algebra are subjected to be used efficiently to solve the computational problems if a DFA recognize the set of encoded strings. This proposed method provides better results whereas other methods may face serious problem of time and space complexities.
References
Ernest ketcha am, derrick g. kourie, and brucngasse w. watson,“On Implementation and Performance of Table-Driven DFA-Based String Processors”. Int. J. Found. Comput. Sci. 19, 53 (2008).
Bruce William Watson, “Constructing Minimal Acyclic Deterministic Finite Automata”. FASTAR Research Group.
Domenico Ficara, Stefano Giordano, Gregorio Procissi, Fabio Vitucci, Gianni Antichi, and Andrea Di Pietro.. “An improved DFA for fast regular expression matching”, SIGCOMM Comput. Commun. Rev. 38, September 2008.
Todd J. Green, Ashish Gupta, Gerome Miklau, Makoto Onizuka, and Dan Suciu. “Processing XML streams with deterministic automata and stream indexes”, ACM Trans. Database Syst. 29, 4 (December 2004)
Isaac Keslassy, David Hay, Yossi Kanizo, Isaac Keslassy, David Hay, Yossi Kanizo. “Optimal Fast Hashing”, Technical Report Tr08-05, Comnet, Technion, Israel.
Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), 4.13 Partitioning, “The Design and Analysis of Computer Algorithms”, Addison-Wesley, pp. 157–162.
Aakanksha Pandey, Dr. Nilay Khare and Akhtar Rasool“Efficient Design and Implementation of DFA Based Pattern Matching on Hardware”, IJCSI March 2012.
B. L. Hutchings and R. Franklin and D. Carver “Scalable Hardware Implementation on Finite Automata” Department of Electrical and Computer Engineering
S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley, and J. Turner . “ Algorithms to accelerate multiple regular expressions matching for deep packet inspection”, In Proc. of SIGCOMM `06, pages 339-350. ACM.
R. Smith, C. Estan, and S. Jha. Xfa, “Faster signature matching with extended automata”, In IEEE Symposium on Security and Privacy, May 2008.
Vlad Slavici, Daniel Kunkle, Gene Cooperman and Stephen Linton, “Finding the Minimal DFA of Very Large Finite State Automata with an Application to Token Passing Networks” Northeastern University, 29 March 2011.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
