Google scholar arxiv informatics ads IJAIS publications are indexed with Google Scholar, NASA ADS, Informatics et. al.

Call for Paper

-

April Edition 2021

International Journal of Applied Information Systems solicits high quality original research papers for the April 2021 Edition of the journal. The last date of research paper submission is March 15, 2021.

String Searching with DFA-based Algorithm

Preye Ejendibia, Barileé B. Baridam. Published in Information Sciences

International Journal of Applied Information Systems
Year of Publication: 2015
Publisher: Foundation of Computer Science (FCS), NY, USA
Authors: Preye Ejendibia, Barileé B. Baridam
10.5120/ijais2015451415
Download full text
  1. Preye Ejendibia and Barileé B Baridam. Article: String Searching with DFA-based Algorithm. International Journal of Applied Information Systems 9(8):1-6, October 2015. BibTeX

    @article{key:article,
    	author = "Preye Ejendibia and Barileé B. Baridam",
    	title = "Article: String Searching with DFA-based Algorithm",
    	journal = "International Journal of Applied Information Systems",
    	year = 2015,
    	volume = 9,
    	number = 8,
    	pages = "1-6",
    	month = "October",
    	note = "Published by Foundation of Computer Science (FCS), NY, USA"
    }
    

Abstract

Searching for information in large depositories or the Internet employs the concept of string searching. With the world-wide web expanding with databases from diverse fields it has become a growing concern for database curators to find an efficient searching algorithms for the task. In comparative terms, the power of an algorithm over another is in its time-complexity and efficiency of operation. A lot of algorithms have been designed for the task of string searching. Also, some of the fast string searching algorithms were developed based on the Deterministic Finite Automata (DFA), which prompts the need to thoroughly research and investigate how this principle is applied. This paper analyses and compares the searching power of DFA and brute-force searching algorithms. The DFA approach is used to overcome the problem of backtracking, which is faced with the brute-force approach thereby improving the time complexity, the speed and efficiency of search based on results obtained.

Reference

  1. Ben Wellner (471 13 0453 7) and Michael Dant (390 80 0003 1) The Unix “GREP” utility, “CS520 – Introduction to Formal Models” http://pages.cs.wisc.edu/~mdant/cs520_4.html
  2. J. Kaur, B. Chauhan and J. K. Korepal “Implementation of Query Processor Using Automata and Natural Language Processing” International Journal of Scientific and Research Publications, ISSN: 2250-3153 Volume 3, Issue 5, pp. 1- 5, May 2013.
  3. E. Gribkoff “Applications of Deterministic Finite Automata” ECS 120 UC Davis, Spring 2013.
  4. N. Singla, D. Garg “String Matching Algorithms and their Applicability in various Applications” International Journal of Soft Computing and Engineering (IJSCE) ISSN: 2231-2307, Volume 1, Issue 6, pp. 218 – 222, January 2012.
  5. G. A. Stephen, “String Searching Algorithms” Singapore: World Scientific, Chapter 2, pp. 5-37, 2001.
  6. S. Mitra, T. Acharya “Data Mining: Multmedia, Soft Computting and Bioinformatics” New Jersey: Wiley-Interscience, Chapter 4, pp. 143-169, 2003.
  7. J. D. Ullman, Video Lecture “Informal Introduction to finite automata” Stanford University, May 2012, www.coursera.com
  8. J. E. Hopcroft, R. Motwani and J. D. Ullman “Finite Autmata and Regular Expression” Introduction to automata theory, languages and computation, New York: Addison Wesley, pp. 13-45, 2006.
  9. D. Knuth, J. Morris and V. Pratt “Fast pattern matching in strings” SIAM journal of Computting, Volume 6, pp. 323-350, 1977.
  10. A.V. Aho, M.J. Corasick “Efficient string matching: an aid to bibliographic search” Communications of the ACM, Volume 18, No. 6, pp. 333-340, June 1975.
  11. R. S. Boyer, J. S. Moore “A fast string searching algorithm” Communications of the ACM, Volume 20, No. 10 pp.762-772, October 1977.
  12. R. N. Hoorspool “Practical fast searching in strings” Software – Practice and Experience, Volume 10 No. 6, pp. 501-506, 1980.
  13. R. M. Karp and M. O. Rabin “Efficient randomized pattern matching algorithms” IBM Journal of Research and Development, Volume 31, No 6, pp. 249-260, 1987.
  14. D. M. Sunday “A very fast substring searchalgorithm” Communications of the ACM, Volume 33, No. 8, pp. 132-142, August 1990.
  15. A. V. Aho and J. D. Ullman “Patterns, Automata and Regular expressions” Foundations of Computer Science, New York: W. H. Freeman & Company, pp. 530-571.
  16. M. V. Lawson “Introduction to finite automata; Non-deterministic automata; Kleene’s Theorem” Finite Automata, 1 ed. New York: Chapman and Hall/CRC, pp.1-14, pp. 53-60, 2003.

Keywords

Brute-force, DFA, Algorithms, String Searching.