Deterministic Regular Expressions in Linear Time

Abstract : Deterministic regular expressions are widely used in XML processing. For instance, all regular expressions in DTDs and XML Schemas are required to be deterministic. In this paper we show that determinism of a regular expression e can be tested in linear time. The best known algorithms, based on the Glushkov automaton, require O(σ|e|) time, where σ is the number of distinct symbols in e. We fur- ther show that matching a word w against an expression e can be achieved in combined linear time O(|e| + |w|), for a wide range of deterministic regular expressions: (i) star-free (for multiple input words), (ii) bounded-occurrence, i.e., ex- pressions in which each symbol appears a bounded number of times, and (iii) bounded plus-depth, i.e., expressions in which the nesting depth of alternating plus (union) and con- catenation symbols is bounded. Our algorithms use a new structural decomposition of the parse tree of e. For match- ing arbitrary deterministic regular expressions we present an O(|e| + |w| log log |e|) time algorithm.
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/inria-00618451
Contributor : Inria Mostrare <>
Submitted on : Friday, March 16, 2012 - 2:43:37 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on: Tuesday, December 13, 2016 - 6:33:38 PM

File

1.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00618451, version 1

Collections

Citation

Benoit Groz, Sebastian Maneth, Slawomir Staworko. Deterministic Regular Expressions in Linear Time. PODS-31th ACM Symposium on Principles of Database Systems, 2012, Scottsdale, United States. pp.12. ⟨inria-00618451⟩

Share

Metrics

Record views

1152

Files downloads

1648