Complexity of decision problems for XML schemas and chain regular expressions

DOI10.1137/080743457zbMATH Open1211.68162OpenAlexW2134781086MaRDI QIDQ3586189FDOQ3586189

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

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

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)

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
• Mathematical Foundations of Computer Science 2004
• Complexity of universality and related problems for partially ordered NFAs
• Conjunctive query containment over trees using schema information
• The complexity of SORE-definability problems
• Title not available (Why is that?)
• 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
• Linear time membership in a class of regular expressions with counting, interleaving, and unordered concatenation
• Distributed XML design
• Deterministic regular expressions with back-references

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)