Efficient Testing and Matching of Deterministic Regular Expressions

Benoît Groz, Sebastian Maneth

Research output: Contribution to journalArticlepeer-review


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 languageEnglish
Pages (from-to)372-399
Number of pages28
JournalJournal of Computer and System Sciences
Early online date20 Jun 2017
Publication statusPublished - 1 Nov 2017

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

Cite this