Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
Authors:
- Wim MartensWMWim Martens
- Frank NevenFNFrank Neven
- Thomas SchwentickTSThomas Schwentick
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 39 (4) , 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 form, 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
This publication has 31 references indexed in Scilit:
- Optimizing Schema Languages for XML: Numerical Constraints and InterleavingSIAM Journal on Computing, 2009
- Using Forward Reachability Analysis for Verification of Lossy Channel SystemsFormal Methods in System Design, 2004
- Reasoning on regular path queriesACM SIGMOD Record, 2003
- Intersection of Regular Languages and Star Hierarchy2002
- Normal form algorithms for extended context-free grammarsTheoretical Computer Science, 2001
- Caterpillars: a context specification techniqueMarkup Languages: Theory and Practice, 2000
- Storing semistructured data with STOREDACM SIGMOD Record, 1999
- One-Unambiguous Regular LanguagesInformation and Computation, 1998
- One-Unambiguous Regular LanguagesInformation and Computation, 1998
- Domino-tiling gamesJournal of Computer and System Sciences, 1986