Complexity of Decision Problems for XML Schemas and Chain Regular Expressions

DOI10.1137/080743457zbMath1211.68162OpenAlexW2134781086MaRDI QIDQ3586189

Wim Martens, Thomas Schwentick, Frank Neven

Publication date: 6 September 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/6f6a792eddc9c2e7e7aaa5f8f31df7b49c96805a

zbMATH Keywords

complexityequivalenceregular expressionsintersectioninclusionXML schemas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Database theory (68P15) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Data structures (68P05)

Related Items (15)

Deciding twig-definability of node selecting tree automata ⋮ Fast learning of restricted regular expressions and dtds ⋮ Generating, sampling and counting subclasses of regular tree languages ⋮ Learning from positive and negative examples: dichotomies and parameterized algorithms ⋮ Games for active XML revisited ⋮ Simplifying XML schema: single-type approximations of regular tree languages ⋮ Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking ⋮ Unnamed Item ⋮ Schemas for unordered XML on a DIME ⋮ Conjunctive query containment over trees using schema information ⋮ Distributed XML design ⋮ Complexity of universality and related problems for partially ordered NFAs ⋮ Unnamed Item ⋮ Deterministic regular expressions with back-references ⋮ Learning algorithms

Uses Software

• XDuce

This page was built for publication: Complexity of Decision Problems for XML Schemas and Chain Regular Expressions