www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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.
URI: http://hdl.handle.net/1942/12824
DOI: 10.1016/j.tcs.2010.04.036
ISI #: 000279339100017
ISSN: 0304-3975
Category: A1
Type: Journal Contribution
Validation: ecoom, 2011
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Published version471.57 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.