Property testing of regular tree languages

DOI10.1007/s00453-007-9028-3zbMath1131.68055OpenAlexW2011798949MaRDI QIDQ2461542

Michel de Rougemont, Frédéric Magniez

Publication date: 28 November 2007

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9028-3

zbMATH Keywords

Property testingRegular tree languagesEdit distance with moves

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

Approximate consistency for transformations on words and trees ⋮ Property Testing for Bounded Degree Databases ⋮ Testing membership for timed automata ⋮ A metric for rooted trees with unlabeled vertices based on nested parentheses ⋮ Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes

Cites Work

• Unnamed Item
• Unnamed Item
• \(\omega\)-regular languages are testable with a constant number of queries
• Self-testing/correcting with applications to numerical problems
• Edit distance with move operations
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Property testing and its connection to learning and approximation
• The Tree-to-Tree Correction Problem
• On the Robustness of Functional Equations
• Designing programs that check their work
• Robust Characterizations of Polynomials with Applications to Program Testing
• One-unambiguous regular languages
• Efficient testing of large graphs

This page was built for publication: Property testing of regular tree languages