Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/8496
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | GELADE, Wouter | - |
dc.date.accessioned | 2008-09-25T06:34:59Z | - |
dc.date.available | 2008-09-25T06:34:59Z | - |
dc.date.issued | 2008 | - |
dc.identifier.citation | Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, 5162. p. 363-374 | - |
dc.identifier.isbn | 978-3-540-85237-7 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/1942/8496 | - |
dc.description.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. | - |
dc.language.iso | en | - |
dc.publisher | Springer | - |
dc.relation.ispartofseries | Lecture Notes in Computer Science | - |
dc.title | Succinctness of Regular Expressions with Interleaving, Intersection and Counting | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.authors | Ochmanski, Edward | - |
local.bibliographicCitation.authors | Tyszkiewicz, Jerzy | - |
local.bibliographicCitation.conferencedate | August 25-29 | - |
local.bibliographicCitation.conferencename | Mathematical Foundations of Computer Science | - |
local.bibliographicCitation.conferenceplace | Torun, Poland | - |
dc.identifier.epage | 374 | - |
dc.identifier.spage | 363 | - |
dc.identifier.volume | 5162 | - |
local.bibliographicCitation.jcat | A1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Proceedings Paper | - |
local.relation.ispartofseriesnr | 5162 | - |
dc.bibliographicCitation.oldjcat | C1 | - |
dc.identifier.doi | 10.1007/978-3-540-85238-4_29 | - |
dc.identifier.isi | 000259139800029 | - |
local.bibliographicCitation.btitle | Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science | - |
item.contributor | GELADE, Wouter | - |
item.fulltext | With Fulltext | - |
item.validation | ecoom 2009 | - |
item.fullcitation | GELADE, Wouter (2008) Succinctness of Regular Expressions with Interleaving, Intersection and Counting. In: Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, 5162. p. 363-374. | - |
item.accessRights | Open Access | - |
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 May 4, 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.