A Review of DFA Minimizing State Machines Using Hash-Tables
| ||International Journal of Computer Trends and Technology (IJCTT)|| |
|© - April Issue 2013 by IJCTT Journal|
|Volume-4 Issue-4 |
|Year of Publication : 2013|
|Authors : Vishal Garg, Anu|
Vishal Garg, Anu "A Review of DFA Minimizing State Machines Using Hash-Tables"International Journal of Computer Trends and Technology (IJCTT),V4(4):779-782 April Issue 2013 .ISSN 2231-2803.www.ijcttjournal.org. Published by Seventh Sense Research Group.
Abstract: -In algorithm design, DFA minimization is an important problem. DFA minimization is based on the notion of DFA equivalence: Two DFA’s are called equivalent DFA’s if and only if they accept the same strings of same set. A large number of computational problems can be solved easily by the encoding method. We can encode the combinatorial objects which we want to use as strings over a finite alphabet. If a DFA accept the collection of encoded strings, then standard algorithms from computational linear algebra can be efficiently used to solve the computational problems.
 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.
Keywords — Deterministic Finite Automata, NFA, Regular expressions, Compiler Design, Generic Programming. Performance.