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.
References-
[1] 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).
[2] Bruce William Watson, “Constructing Minimal Acyclic Deterministic Finite Automata”. FASTAR Research Group.
[3] 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.
[4] 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)
[5] Isaac Keslassy, David Hay, Yossi Kanizo, Isaac Keslassy, David Hay, Yossi Kanizo. “Optimal Fast Hashing”, Technical Report Tr08-05, Comnet, Technion, Israel.
[6] 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.
[7] 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.