Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/8496

Title: Succinctness of Regular Expressions with Interleaving, Intersection and Counting
Authors: GELADE, Wouter
Issue Date: 2008
Publisher: Springer
Citation: Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, 5162. p. 363-374
Series/Report: Lecture Notes in Computer Science, 5162
Abstract: Studying the impact of operations, such as intersection and interleaving, on the succinctness of regular expressions has recently received renewed attention [12–14]. 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 can not 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 can not 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.
URI: http://hdl.handle.net/1942/8496
DOI: 10.1007/978-3-540-85238-4_29
ISI #: 000259139800029
ISBN: 978-3-540-85237-7
ISSN: 0302-9743
Category: A1
Type: Proceedings Paper
Validation: ecoom, 2009
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Preprint290.52 kBAdobe PDF

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