Regular Expressions with Counting: Weak versus Strong Determinism
- 1 January 2012
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 41 (1), 160-190
- https://doi.org/10.1137/100814196
Abstract
We study deterministic regular expressions extended with the counting operator. There exist two notions of determinism, strong and weak determinism, which are equally expressive for standard regular expressions. This, however, changes dramatically in the presence of counting. In particular, we show that weakly deterministic expressions with counting are exponentially more succinct and strictly more expressive than strongly deterministic ones, even though they still do not capture all regular languages. In addition, we present a finite automaton model with counters, study its properties, and investigate the natural extension of the Glushkov construction translating expressions with counting into such counting automata. This translation yields a deterministic automaton if and only if the expression is strongly deterministic. These results then also allow us to derive upper bounds for decision problems for strongly deterministic expressions with counting.Keywords
This publication has 9 references indexed in Scilit:
- Checking determinism of XML Schema content models in optimal timeInformation Systems, 2011
- Optimizing Schema Languages for XML: Numerical Constraints and InterleavingSIAM Journal on Computing, 2009
- Succinctness of Regular Expressions with Interleaving, Intersection and CountingLecture Notes in Computer Science, 2008
- One-unambiguity of regular expressions with numeric occurrence indicatorsInformation and Computation, 2007
- Attribute grammars for scalable query processing on XML streamsThe VLDB Journal, 2006
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTIONInternational Journal of Foundations of Computer Science, 2002
- One-Unambiguous Regular LanguagesInformation and Computation, 1998
- Regular expressions into finite automataTheoretical Computer Science, 1993
- A tale of two grepsSoftware: Practice and Experience, 1988