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 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.