We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

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