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 | Source: | Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, 5162. p. 363-374 | Series/Report: | Lecture Notes in Computer Science | Series/Report no.: | 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. | Document URI: | http://hdl.handle.net/1942/8496 | ISBN: | 978-3-540-85237-7 | DOI: | 10.1007/978-3-540-85238-4_29 | ISI #: | 000259139800029 | Category: | A1 | Type: | Proceedings Paper | Validations: | ecoom 2009 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
mfcs08.pdf | Non Peer-reviewed author version | 290.52 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
9
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
7
checked on Mar 27, 2024
Page view(s)
58
checked on Sep 7, 2022
Download(s)
104
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.