On the minimization of XML schemas and tree automata for unranked trees

DOI10.1016/j.jcss.2006.10.021zbMath1115.68099OpenAlexW2129828874MaRDI QIDQ882435

Wim Martens, Joachim Niehren

Publication date: 23 May 2007

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

Full work available at URL: https://hal.inria.fr/inria-00088406/file/mini.pdf

zbMATH Keywords

minimizationXML schema languagesunranked tree automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Data structures (68P05)

Related Items (19)

Optimal probabilistic generation of XML documents ⋮ State Complexity of Kleene-Star Operations on Trees ⋮ Nested Regular Expressions Can Be Compiled to Small Deterministic Nested Word Automata ⋮ Unnamed Item ⋮ Generating, sampling and counting subclasses of regular tree languages ⋮ Simplifying XML schema: single-type approximations of regular tree languages ⋮ State complexity of the concatenation of regular tree languages ⋮ Efficient inclusion testing for simple classes of unambiguous \(\omega \)-automata ⋮ State Complexity of Regular Tree Languages for Tree Matching ⋮ Distributed XML design ⋮ Queries on XML streams with bounded delay and concurrency ⋮ Operational state complexity of nested word automata ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ Bottom-up unranked tree-to-graph transducers for translation into semantic graphs ⋮ State Trade-Offs in Unranked Tree Automata ⋮ A Kleene Theorem for Forest Languages ⋮ From Tree Automata to Rational Tree Expressions ⋮ Learning algorithms ⋮ Efficient inclusion checking for deterministic tree automata and XML schemas

Uses Software

• XPath

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of typechecking top-down XML transformations
• Minimizing finite automata is computationally hard
• Learning regular sets from queries and counterexamples
• An observation on time-storage trade off
• Query automata over finite trees
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Deciding Equivalence of Finite Tree Automata
• The complexity of XPath query evaluation and XML typing
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• Complexity of automaton identification from given data
• Minimal NFA Problems are Hard
• Fundamentals of Computation Theory
• Grammatical Inference: Algorithms and Applications
• Database Programming Languages
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Rewriting Techniques and Applications

This page was built for publication: On the minimization of XML schemas and tree automata for unranked trees