Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/10421
Title: | Complexity of Decision Problems for XML Schemas and Chain Regular Expressions | Authors: | MARTENS, Wim NEVEN, Frank Schwentick, Thomas |
Issue Date: | 2009 | Source: | SIAM JOURNAL ON COMPUTING, 39(4). p. 1486-1530 | Abstract: | We study the complexity of the inclusion, equivalence, and intersection problem of extended CHAin Regular Expressions (eCHAREs). These are regular expressions with a very simple structure: they basically consist of the concatenation of factors, where each factor is a disjunction of strings, possibly extended with “∗”, “+”, or “?”. Though of a very simple from, the usage of such expressions is widespread as eCHAREs, for instance, constitute a super class of the regular expressions most frequently used in practice in schema languages for XML. In particular, we show that all our lower and upper bounds for the inclusion and equivalence problem carry over to the corresponding decision problems for extended context-free grammars, and to single-type and restrained competition tree grammars. These grammars form abstractions of Document Type Definitions (DTDs), XML Schema definitions (XSDs) and the class of one-pass preorder typeable XML schemas, respectively. For the intersection problem, we show that obtained complexities only carry over to DTDs. In this respect, we also study two other classes of regular expressions related to XML: deterministic expressions and expressions where the number of occurrences of alphabet symbols is bounded by a constant. | Keywords: | complexity; regular expressions; inclusion; equivalence; intersection; XML schemas | Document URI: | http://hdl.handle.net/1942/10421 | ISSN: | 0097-5397 | e-ISSN: | 1095-7111 | DOI: | 10.1137/080743457 | ISI #: | 000277584200003 | Rights: | (c) 2009 Society for Industrial and Applied Mathematics | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2011 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
siam09b.pdf | Peer-reviewed author version | 1.34 MB | Adobe PDF | View/Open |
martens2010.pdf Restricted Access | Published version | 768.4 kB | Adobe PDF | View/Open Request a copy |
WEB OF SCIENCETM
Citations
37
checked on Oct 14, 2024
Page view(s)
78
checked on Sep 7, 2022
Download(s)
188
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.