Efficient inclusion checking for deterministic tree automata and XML schemas

DOI10.1016/j.ic.2009.03.003zbMath1191.68377MaRDI 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 complexity; tree automata; language inclusion; XML shemas

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

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

• 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
• Unnamed Item
• Unnamed Item