Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/589
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | MARTENS, Wim | - |
dc.contributor.author | NEVEN, Frank | - |
dc.contributor.author | Schwentick, Thomas | - |
dc.date.accessioned | 2005-02-11T14:54:01Z | - |
dc.date.available | 2005-02-11T14:54:01Z | - |
dc.date.issued | 2004 | - |
dc.identifier.citation | MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS. p. 889-900 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/1942/589 | - |
dc.description.abstract | We study the complexity of the inclusion, equivalence, and intersection problem for simple regular expressions arising in practical XML schemas. These basically consist of the concatenation of factors where each factor is a disjunction of strings possibly extended with ‘*’ or ‘?’. We obtain lower and upper bounds for various fragments of simple regular expressions. Although we show that inclusion and intersection are already intractable for very weak expressions, we also identify some tractable cases. For equivalence, we only prove an initial tractability result leaving the complexity of more general cases open. The main motivation for this research comes from database theory, or more specifically XML and semi-structured data.We namely show that all lower and upper bounds for inclusion and equivalence, carry over to the corresponding decision problems for extended context-free grammars and single-type tree grammars, which are abstractions of DTDs and XML Schemas, respectively.For intersection, we show that the complexity only carries over for DTDs. | - |
dc.format.extent | 149814 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | Springer | - |
dc.relation.ispartofseries | LECTURE NOTES IN COMPUTER SCIENCE | - |
dc.title | Complexity of Decision Problems for Simple Regular Expressions. | - |
dc.type | Journal Contribution | - |
local.bibliographicCitation.conferencename | MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS | - |
dc.identifier.epage | 900 | - |
dc.identifier.spage | 889 | - |
local.bibliographicCitation.jcat | A1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
local.relation.ispartofseriesnr | 3153 | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1007/b99679 | - |
dc.identifier.isi | 000223615400070 | - |
item.fullcitation | MARTENS, Wim; NEVEN, Frank & Schwentick, Thomas (2004) Complexity of Decision Problems for Simple Regular Expressions.. In: MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS. p. 889-900. | - |
item.validation | ecoom 2005 | - |
item.contributor | MARTENS, Wim | - |
item.contributor | NEVEN, Frank | - |
item.contributor | Schwentick, Thomas | - |
item.fulltext | With Fulltext | - |
item.accessRights | Open Access | - |
crisitem.journal.issn | 0302-9743 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
35neven.pdf | 146.3 kB | Adobe PDF | View/Open |
WEB OF SCIENCETM
Citations
28
checked on May 7, 2024
Page view(s)
130
checked on Nov 7, 2023
Download(s)
324
checked on Nov 7, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.