Succinctness of regular expressions with interleaving, intersection and counting

In this paper, we study the succinctness of regular expressions (REs) extended with interleaving, intersection and counting operators. We show that in a translation from REs with interleaving to standard regular expressions a double exponential size increase cannot be avoided. We also consider the c...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2010-06, Vol.411 (31), p.2987-2998
Main Author: Gelade, Wouter
Format: Article
Language:English
Subjects:
Applied sciences
C (programming language)
Complexity
Computer science
control theory
systems
Counting
Exact sciences and technology
Intersections
Lower bounds
Mathematical analysis
Miscellaneous
Operators
Regular Expressions
Succinctness
Theoretical computing
Translations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we study the succinctness of regular expressions (REs) extended with interleaving, intersection and counting operators. We show that in a translation from REs with interleaving to standard regular expressions a double exponential size increase cannot be avoided. We also consider the complexity of translations to finite automata. We give a tight exponential lower bound on the translation of REs with intersection to NFAs, and, for each of the three classes of REs, we show that in a translation to a DFA a double exponential size increase cannot be avoided. Together with known results, this gives a complete picture of the complexity of translating REs extended with interleaving, intersection or counting into (standard) regular expressions, NFAs, and DFAs.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2010.04.036