Efficient inclusion checking for deterministic tree automata and XML schemas

DOI10.1016/j.ic.2009.03.003zbMath1191.68377OpenAlexW2090802466MaRDI QIDQ1041037

Jérôme Champavère, Joachim Niehren, Rémi Gilleron, Aurélien Lemay

Publication date: 27 November 2009

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2009.03.003

zbMATH Keywords

algorithmic complexitytree automatalanguage inclusionXML shemas

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (4)

Nested Regular Expressions Can Be Compiled to Small Deterministic Nested Word Automata ⋮ Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking ⋮ Queries on XML streams with bounded delay and concurrency ⋮ Limitations of lower bound methods for deterministic nested word automata

Uses Software

• Ltur
• Datalog LITE

Cites Work

• Unnamed Item
• Unnamed Item
• Automata for XML -- a survey
• On the minimization of XML schemas and tree automata for unranked trees
• Streaming tree automata
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Regular expressions into finite automata
• Haskell overloading is DEXPTIME-complete
• Typechecking for XML transformers
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Deciding Equivalence of Finite Tree Automata
• Marrying Words and Trees
• Schema-Guided Induction of Monadic Queries
• Efficient Inclusion Checking for Deterministic Tree Automata and DTDs
• Mathematical Foundations of Computer Science 2004
• Database Theory - ICDT 2005
• Datalog LITE
• Rewriting Techniques and Applications
• One-unambiguous regular languages

This page was built for publication: Efficient inclusion checking for deterministic tree automata and XML schemas