Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/12824
Title: | Succinctness of regular expressions with interleaving, intersection and counting | Authors: | GELADE, Wouter | Issue Date: | 2010 | Publisher: | ELSEVIER SCIENCE BV | Source: | THEORETICAL COMPUTER SCIENCE, 411(31-33), p. 2987-2998 | Abstract: | 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. (C) 2010 Elsevier B.V. All rights reserved. | Notes: | [Gelade, W] Hasselt Univ, B-3590 Diepenbeek, Belgium. [Gelade, W] Transnatl Univ Limburg, Sch Informat Technol, Dept WNI, B-3590 Diepenbeek, Belgium. | Keywords: | Regular Expressions; Succinctness | Document URI: | http://hdl.handle.net/1942/12824 | ISSN: | 0304-3975 | e-ISSN: | 1879-2294 | DOI: | 10.1016/j.tcs.2010.04.036 | ISI #: | 000279339100017 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2011 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
succ.pdf | Published version | 471.57 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
30
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
24
checked on Apr 14, 2024
Page view(s)
82
checked on Sep 7, 2022
Download(s)
216
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.