Full Paper View Go Back

A Novel Approach to Minimize DFA State Machines Using Linked List

Yogesh Pant1

Section:Research Paper, Product Type: Isroset-Journal
Vol.6 , Issue.4 , pp.41-45, Aug-2018


CrossRef-DOI:   https://doi.org/10.26438/ijsrcse/v6i4.4145


Online published on Aug 31, 2018


Copyright © Yogesh Pant . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library


XML View     PDF Download

How to Cite this Paper

  • IEEE Citation
  • MLA Citation
  • APA Citation
  • BibTex Citation
  • RIS Citation

IEEE Style Citation: Yogesh Pant, “A Novel Approach to Minimize DFA State Machines Using Linked List,” International Journal of Scientific Research in Computer Science and Engineering, Vol.6, Issue.4, pp.41-45, 2018.

MLA Style Citation: Yogesh Pant "A Novel Approach to Minimize DFA State Machines Using Linked List." International Journal of Scientific Research in Computer Science and Engineering 6.4 (2018): 41-45.

APA Style Citation: Yogesh Pant, (2018). A Novel Approach to Minimize DFA State Machines Using Linked List. International Journal of Scientific Research in Computer Science and Engineering, 6(4), 41-45.

BibTex Style Citation:
@article{Pant_2018,
author = {Yogesh Pant},
title = {A Novel Approach to Minimize DFA State Machines Using Linked List},
journal = {International Journal of Scientific Research in Computer Science and Engineering},
issue_date = {8 2018},
volume = {6},
Issue = {4},
month = {8},
year = {2018},
issn = {2347-2693},
pages = {41-45},
url = {https://www.isroset.org/journal/IJSRCSE/full_paper_view.php?paper_id=812},
doi = {https://doi.org/10.26438/ijcse/v6i4.4145}
publisher = {IJCSE, Indore, INDIA},
}

RIS Style Citation:
TY - JOUR
DO = {https://doi.org/10.26438/ijcse/v6i4.4145}
UR - https://www.isroset.org/journal/IJSRCSE/full_paper_view.php?paper_id=812
TI - A Novel Approach to Minimize DFA State Machines Using Linked List
T2 - International Journal of Scientific Research in Computer Science and Engineering
AU - Yogesh Pant
PY - 2018
DA - 2018/08/31
PB - IJCSE, Indore, INDIA
SP - 41-45
IS - 4
VL - 6
SN - 2347-2693
ER -

1186 Views    449 Downloads    109 Downloads
  
  

Abstract :
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.

Key-Words / Index Term :
DFA; NFA; Regular expressions; Compiler Design; Linked List

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.
[8] B. L. Hutchings and R. Franklin and D. Carver “Scalable Hardware Implementation on Finite Automata” Department of Electrical and Computer Engineering
[9] 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.
[10] R. Smith, C. Estan, and S. Jha. Xfa, “Faster signature matching with extended automata”, In IEEE Symposium on Security and Privacy, May 2008.
[11] 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.

Authorization Required

 

You do not have rights to view the full text article.
Please contact administration for subscription to Journal or individual article.
Mail us at  support@isroset.org or view contact page for more details.

Go to Navigation