Simplifying XML schema: single-type approximations of regular tree languages

DOI10.1016/j.jcss.2013.01.009zbMath1408.68091OpenAlexW2032174658MaRDI QIDQ389236

Wouter Gelade, Tomasz Idziaszek, Frank Neven, Wim Martens, Jan Paredaens

Publication date: 20 January 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2013.01.009

zbMATH Keywords

XMLcomplexityapproximationXML schema

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Closure properties and descriptional complexity of deterministic regular expressions ⋮ Optimal probabilistic generation of XML documents ⋮ Deciding twig-definability of node selecting tree automata ⋮ Deciding top-down determinism of regular tree languages ⋮ Generating, sampling and counting subclasses of regular tree languages ⋮ Checking in polynomial time whether or not a regular tree language is deterministic top-down

Uses Software

• Relax NG

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Succinctness of pattern-based schema languages for XML
• On the minimization of XML schemas and tree automata for unranked trees
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Succinctness of the Complement and Intersection of Regular Expressions
• Deciding Equivalence of Finite Tree Automata
• Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
• Forest Expressions
• One-unambiguous regular languages
• Normal form algorithms for extended context-free grammars

This page was built for publication: Simplifying XML schema: single-type approximations of regular tree languages