Complexity of decision problems for XML schemas and chain regular expressions

DOI10.1137/080743457MaRDI QIDQ3586189zbMATH OpenOpenAlexFDO

Authors Wim Martens, Frank Neven, Thomas Schwentick

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

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

Recommendations

• Mathematical Foundations of Computer Science 2004
• Optimizing Schema Languages for XML: Numerical Constraints and Interleaving
• Regular expression types for XML
• Definability by weakly deterministic regular expressions with counters is decidable
• The complexity of SORE-definability problems

Cited in

(18)

• Deciding twig-definability of node selecting tree automata
• Fast learning of restricted regular expressions and dtds
• Optimizing Schema Languages for XML: Numerical Constraints and Interleaving
• Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking
• Learning from positive and negative examples: dichotomies and parameterized algorithms
• Linear time membership in a class of regular expressions with counting, interleaving, and unordered concatenation
• The complexity of SORE-definability problems
• Games for active XML revisited
• Schemas for unordered XML on a DIME
• scientific article; zbMATH DE number 7350780 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• Deterministic regular expressions with back-references
• Distributed XML design
• Learning algorithms
• Generating, sampling and counting subclasses of regular tree languages
• Conjunctive query containment over trees using schema information
• Simplifying XML schema: single-type approximations of regular tree languages
• Complexity of universality and related problems for partially ordered NFAs

Describes a project that uses

Uses Software

• XDuce

This page was built for publication: Complexity of decision problems for XML schemas and chain regular expressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586189)