Checking determinism of regular expressions with counting
The paper is concerned with improving the worst-case run time of regular expression determinism testing algorithms. In particular, improvements are made with regards to regular expression counting operators. Complexity of \textit{matching} problems is not considered. Informally, a regular expression is weakly deterministic if, when matching a word against the expression, a symbol can be matched to only one position in the expression without looking ahead. A regular expression is strongly deterministic if it is weakly deterministic and if the operators appearing in the expression can only be used in a unique way when matching the expression with a word. Based on earlier works [\textit{B. Groz}, \textit{S. Maneth} and \textit{S. Staworko}, ``Deterministic regular expressions in linear time, in: Proceedings of the 31st symposium on principles of database systems, PODS '12. New York, NY: ACM. 49--60 (2012; \url{doi:10.1145/2213556.2213566}); \textit{P. Kilpeläinen}, ``Checking determinism of XML schema content models in optimal time, Inf. Syst. 36, No. 3, 596--617 (2009; \url{doi:10.1016/j.is.2010.10.001})], the authors generalise linear-time determinism testing algorithms established previously for standard regular expressions onto regular expressions with counting. The paper culminates in presenting an \(O(|\Sigma_E| |E|)\)-time algorithm for checking weak determinism of regular expressions with counting, and in presenting an \(O(|E|)\)-time algorithm for checking \textit{strong} determinism of regular expressions in that same class. The results will find applications in the analysis of XML content models (weakly deterministic as per a W3C requirement) or queries over XML streams where strongly deterministic regular expressions are naturally found.
- Checking determinism of regular expressions with counting
- Regular expressions with counting: weak versus strong determinism
- Regular Expressions with Counting: Weak versus Strong Determinism
- Deciding definability by deterministic regular expressions
- Deterministic regular expressions with interleaving
- Checking determinism of regular expressions with counting
- Deterministic regular languages
- scientific article; zbMATH DE number 193480 (Why is no real title available?)
- Mathematical Foundations of Computer Science 2004
- One-unambiguity of regular expressions with numeric occurrence indicators
- One-unambiguous regular languages
- Regular expressions into finite automata
- Regular expressions with counting: weak versus strong determinism
- Succinctness of the Complement and Intersection of Regular Expressions
- The membership problem for regular expressions with unordered concatenation and numerical constraints
- Context-free grammars for deterministic regular expressions with interleaving
- Deterministic regular expressions with back-references
- Efficient testing and matching of deterministic regular expressions
- Closure properties and descriptional complexity of deterministic regular expressions
- Deterministic regular expressions with interleaving
- Checking determinism of regular expressions with counting
- Deterministic regular expressions with back-references
- The complexity of SORE-definability problems
- Quantitative Verification of Stochastic Regular Expressions
- Regular expressions with counting: weak versus strong determinism
- Regular Expressions with Counting: Weak versus Strong Determinism
- Succinct determinisation of counting automata via sphere construction
- Deciding determinism of unary languages
This page was built for publication: Checking determinism of regular expressions with counting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2343138)
