Document Server@UHasselt >
Research >
Research publications >

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
Citation: 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.
URI: http://hdl.handle.net/1942/10421
DOI: 10.1137/080743457
ISI #: 000277584200003
ISSN: 0097-5397
Category: A1
Type: Journal Contribution
Validation: ecoom, 2011
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Published version768.4 kBAdobe PDF
Peer-reviewed author version1.31 MBAdobe PDF

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