Efficient Testing and Matching of Deterministic Regular Expressions

Benoît Groz; Sebastian Maneth

doi:10.1016/j.jcss.2017.05.013

Efficient Testing and Matching of Deterministic Regular Expressions

Benoît Groz, Sebastian Maneth

Research output: Contribution to journal › Article › peer-review

Abstract

A linear time algorithm is presented for testing determinism of a regular expression. It is shown that an input word of length n can be matched against a deterministic regular expression of length m in time O(m + n log logm). If the deterministic regular expression has bounded depth of alternating union and concatenation operators, then matching can be performed in time O(m + n). These results extend to regular expressions containing numerical occurrence indicators.

Original language	English
Pages (from-to)	372-399
Number of pages	28
Journal	Journal of Computer and System Sciences
Volume	89
Early online date	20 Jun 2017
DOIs	https://doi.org/10.1016/j.jcss.2017.05.013
Publication status	Published - 1 Nov 2017

Access to Document

10.1016/j.jcss.2017.05.013

jcss2017-3Accepted author manuscript, 309 KB

http://www.sciencedirect.com/science/article/pii/S0022000017300843

Fingerprint Dive into the research topics of 'Efficient Testing and Matching of Deterministic Regular Expressions'. Together they form a unique fingerprint.

Cite this

@article{1d2fc20578334800a7634ef019526b9a,

title = "Efficient Testing and Matching of Deterministic Regular Expressions",

abstract = "A linear time algorithm is presented for testing determinism of a regular expression. It is shown that an input word of length n can be matched against a deterministic regular expression of length m in time O(m + n log logm). If the deterministic regular expression has bounded depth of alternating union and concatenation operators, then matching can be performed in time O(m + n). These results extend to regular expressions containing numerical occurrence indicators.",

author = "Beno{\^i}t Groz and Sebastian Maneth",

year = "2017",

month = nov,

day = "1",

doi = "10.1016/j.jcss.2017.05.013",

language = "English",

volume = "89",

pages = "372--399",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "ACADEMIC PRESS INC ELSEVIER SCIENCE",

}

TY - JOUR

T1 - Efficient Testing and Matching of Deterministic Regular Expressions

AU - Groz, Benoît

AU - Maneth, Sebastian

PY - 2017/11/1

Y1 - 2017/11/1

N2 - A linear time algorithm is presented for testing determinism of a regular expression. It is shown that an input word of length n can be matched against a deterministic regular expression of length m in time O(m + n log logm). If the deterministic regular expression has bounded depth of alternating union and concatenation operators, then matching can be performed in time O(m + n). These results extend to regular expressions containing numerical occurrence indicators.

AB - A linear time algorithm is presented for testing determinism of a regular expression. It is shown that an input word of length n can be matched against a deterministic regular expression of length m in time O(m + n log logm). If the deterministic regular expression has bounded depth of alternating union and concatenation operators, then matching can be performed in time O(m + n). These results extend to regular expressions containing numerical occurrence indicators.

U2 - 10.1016/j.jcss.2017.05.013

DO - 10.1016/j.jcss.2017.05.013

M3 - Article

VL - 89

SP - 372

EP - 399

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

ER -