Approximate consistency for transformations on words and trees

DOI10.1016/J.TCS.2016.01.032MaRDI QIDQ264563zbMATH OpenOpenAlexFDO

Authors Michel de Rougemont, Adrien Vieilleribière

Publication date 31 March 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.01.032

zbMATH Keywords

complexityapproximationdatabase theory

Mathematics Subject Classification ID

Randomized algorithms (68W20) Data structures (68P05) Database theory (68P15)

Recommendations

• Deciding equivalence of linear tree-to-word transducers in polynomial time
• scientific article; zbMATH DE number 3894494
• On ground tree transformations and congruences induced by tree automata.
• Convergence of program transformers in the metric space of trees
• Equivalence problems for tree transducers: a brief survey
• scientific article; zbMATH DE number 4043278
• Approximated determinisation of weighted tree automata
• scientific article; zbMATH DE number 4108162
• scientific article; zbMATH DE number 5654542
• STACS 2004

Cites work

• scientific article; zbMATH DE number 480237 (Why is no real title available?)
• scientific article; zbMATH DE number 1953133 (Why is no real title available?)
• scientific article; zbMATH DE number 2119725 (Why is no real title available?)
• Approximate membership for regular languages modulo the edit distance
• Approximate satisfiability and equivalence
• Efficient testing of large graphs
• On Context-Free Languages
• Probability Inequalities for Sums of Bounded Random Variables
• Property testing and its connection to learning and approximation
• Property testing of regular tree languages
• Random sampling with a reservoir
• Sublinear DTD validity
• XML data exchange

Cited in

(1)

• Approximate satisfiability and equivalence

This page was built for publication: Approximate consistency for transformations on words and trees

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