CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Streamlining of DFA based Pattern Matchers

by Ashish Kumar Pandey, Amit Sinha
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 161 - Number 6
Year of Publication: 2017
Authors: Ashish Kumar Pandey, Amit Sinha
10.5120/ijca2017913212

Ashish Kumar Pandey, Amit Sinha . Streamlining of DFA based Pattern Matchers. International Journal of Computer Applications. 161, 6 ( Mar 2017), 10-13. DOI=10.5120/ijca2017913212

@article{ 10.5120/ijca2017913212,
author = { Ashish Kumar Pandey, Amit Sinha },
title = { Streamlining of DFA based Pattern Matchers },
journal = { International Journal of Computer Applications },
issue_date = { Mar 2017 },
volume = { 161 },
number = { 6 },
month = { Mar },
year = { 2017 },
issn = { 0975-8887 },
pages = { 10-13 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume161/number6/27151-2017913212/ },
doi = { 10.5120/ijca2017913212 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:06:23.755750+05:30
%A Ashish Kumar Pandey
%A Amit Sinha
%T Streamlining of DFA based Pattern Matchers
%J International Journal of Computer Applications
%@ 0975-8887
%V 161
%N 6
%P 10-13
%D 2017
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper presents an efficient algorithm for finding matches to a given regular expression in given text using optimization of DFA. To match a regular expression of length n, a serial machine requires 0(2^n) memory and takes 0(1) time per text character. The proposed approach requires only 0(n^2) space and still process a text character in 0(1) time (one clock cycle).The improvement is due to the optimization of DFA that means without converting it into the NFA, directly convert into the DFA. Finite Automaton (DFA) used to perform the matching. Furthermore, the paper presents a simple, fast algorithm that quickly constructs the DFA for the given regular expression.

References
  1. J. E. Hopcroft and J. D. Ullman, Introduction to automata theory,languages, and computation,” Addison Wesley, 1979.
  2. Y. Sun, H. Liu, V. Valgenti, and M. S. Kim, “Hybrid regular expression matching for deep packet inspection on multi-core architecture,” in Proceedings of the 19th International onference on Computer Communications and Networks, ICCCN’10, Aug. 2010, pp. 1–7.
  3. P.Jayaprabha and Rm. Somasundaram ,”Content Based Image Retrieval Methods Using Graphical Image Retrieval Algorithm (GIRA)”., Computer Science And Application, Vol. 1, No. 1, January, 2012.
  4. 1997,http://www.igm.univmlv.fr/~lecroq/string/index.html C. Charras and T. Lecroq: Exact String MatchingAlgorithms. Univ. de Rouen.
  5. Srikanthan, Sharanyan ,“Implementing the dynamic time warping algorithm in multithreaded environments for realtime and unsupervised pattern discovery”., Computer and Communication Technology (ICCCT), 2011 2ndInternational Conference on 394 – 398, 15-17 Sept. 2011.
  6. Stan Salvador & Philip Chan,”Fast DTW: Toward Accurate Dynamic Time Warping in Linear Time and Space”.KDDWorkshop on Mining Temporal and Sequential Data, pp. 70-80, 2004. (http://cs.fit.edu/~pkc/papers/tdm04.pdf).
  7. Chu, S., E. Keogh, D. Hart & Michael Pazzani. Iterative, Deepening Dynamic Time Warping for Time Series. In Proc.of the Second SIAM Intl. Conf. on Data Mining. Arlington, Virginia, 2002.
  8. Arcangel, Cory. "On Compression". Retrieved 6 March 2013.
  9. Jaiswal, R.C. Audio-Video Engineering. Pune, Maharashtra: Nirali Prakashan. p. 3.41. (2009).ISBN 9788190639675.
  10. "Video Coding". Center for Signal and Information Processing Research. Georgia Institute of Technology. Retrieved 6March 2013.
Index Terms

Computer Science
Information Sciences

Keywords

DFA NFA

Powered by PhDFocusTM