Matching patterns of an automaton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present an algorithm permitting to search in a text for the patterns of a regular set. Unlike many classical algorithms, we shall assume that the input of the algorithm is a deterministic automaton and not a regular expression. Our algorithm is based on the notion of failure function and mainly consists in efficiently constructing a new deterministic automaton. This construction is shown to be more efficient both in time and space than naive algorithms such as the powerset algorithm used for determinization. In particular, its space complexity is linear in the size of the obtained automaton.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings
EditorsZvi Galil, Esko Ukkonen
PublisherSpringer Verlag
Pages286-297
Number of pages12
ISBN (Print)3540600442, 9783540600442
DOIs
StatePublished - 1995
Event6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995 - Espoo, Finland
Duration: Jul 5 1995Jul 7 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume937
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995
CountryFinland
CityEspoo
Period7/5/957/7/95

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Matching patterns of an automaton'. Together they form a unique fingerprint.

  • Cite this

    Mohri, M. (1995). Matching patterns of an automaton. In Z. Galil, & E. Ukkonen (Eds.), Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings (pp. 286-297). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 937). Springer Verlag. https://doi.org/10.1007/3-540-60044-2_49