Sublinear DTD validity

DOI10.1007/978-3-319-15579-1_58MaRDI QIDQ2799222zbMATH OpenOpenAlexFDO

Authors Antoine Ndione, Aurélien Lemay, Joachim Niehren

Publication date 8 April 2016

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-15579-1_58

zbMATH Keywords

DTDproperty testingregular tree automataXML

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Formal languages and automata (68Q45) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 1953123
• Validating XML documents in the streaming model with external memory
• Visibly Pushdown Transducers for Approximate Validation of Streaming XML
• Approximate Structural Consistency
• Efficient Inclusion Checking for Deterministic Tree Automata and DTDs

Cites work

• \(\omega\)-regular languages are testable with a constant number of queries
• A relation between edit distance for ordered trees and edit distance for Euler strings
• Adding nesting structure to words
• Approximate membership for regular languages modulo the edit distance
• Approximate satisfiability and equivalence
• Computingϵ-Free NFA from Regular Expressions inO(nlog²(n)) Time
• Every property of hyperfinite graphs is testable
• scientific article; zbMATH DE number 1241385 (Why is no real title available?)
• Regular Expressions and NFAs Without ε-Transitions
• Regular expressions into finite automata
• Regular languages are testable with a constant number of queries
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• The tree-to-tree editing problem

Cited in

(5)

• Approximate consistency for transformations on words and trees
• Validating XML documents in the streaming model with external memory
• scientific article; zbMATH DE number 1953123 (Why is no real title available?)
• Visibly Pushdown Transducers for Approximate Validation of Streaming XML
• Property testing of regular languages with applications to streaming property testing of visibly pushdown languages

This page was built for publication: Sublinear DTD validity

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