Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Inria Mostrare Connect in order to contact the contributor
Submitted on : Friday, March 16, 2012 - 2:43:37 PM
Last modification on : Friday, November 18, 2022 - 10:13:58 AM
Long-term archiving on: : Tuesday, December 13, 2016 - 6:33:38 PM


Files produced by the author(s)


  • HAL Id : inria-00618451, version 1



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⟩



Record views


Files downloads