Optimizing Schema Languages for XML: Numerical Constraints and Interleaving

DOI10.1137/070697367MaRDI QIDQ3642874zbMATH OpenOpenAlexFDO

Authors Wouter Gelade, Wim Martens, Frank Neven

Publication date 6 November 2009

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

Full work available at URL https://semanticscholar.org/paper/60d94c0db73a44182020c0ebae65acf80077d357

zbMATH Keywords

complexityoptimizationregular expressionsXML schema languages

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• Complexity of decision problems for XML schemas and chain regular expressions
• Mathematical Foundations of Computer Science 2004
• Simplifying XML schema: single-type approximations of regular tree languages
• scientific article; zbMATH DE number 1945841
• Numerical constraints on XML data

Cited in

(10)

• Boolean operations and inclusion test for attribute-element constraints
• Complexity of decision problems for XML schemas and chain regular expressions
• Numerical Constraints for XML
• Shuffled languages -- representation and recognition
• Simplifying XML schema: single-type approximations of regular tree languages
• Mathematical Foundations of Computer Science 2004
• Succinctness of pattern-based schema languages for XML
• Regular Expressions with Counting: Weak versus Strong Determinism
• Schemas for unordered XML on a DIME
• Efficient inclusion for a class of XML types with interleaving and counting

Describes a project that uses

Uses Software

• XDuce

This page was built for publication: Optimizing Schema Languages for XML: Numerical Constraints and Interleaving

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