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)

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

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)