@inproceedings{8006e055d58f4a2da4540e406d17609d,
title = "Matching patterns of an automaton",
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.",
author = "Mehryar Mohri",
note = "Funding Information: ★Work partially supported by the Spanish MICINN grants TIN2009-14205-C04-02 and Consolider Ingenio 2010: MIPRCV (CSD2007-00018) and by IMPIVA and the E.U. by means of the ERDF in the context of the R+D Program for Technological Institutes of IMPIVA network for 2010 (IMIDIC-2010/191). Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1995.; 6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995 ; Conference date: 05-07-1995 Through 07-07-1995",
year = "1995",
doi = "10.1007/3-540-60044-2_49",
language = "English (US)",
isbn = "3540600442",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "286--297",
editor = "Zvi Galil and Esko Ukkonen",
booktitle = "Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings",
}