Property testing of regular tree languages

DOI10.1007/978-3-540-27836-8_78MaRDI QIDQ5466526zbMATH OpenOpenAlexFDO

Authors Frédéric Magniez, Michel de Rougemont

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99859

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Property testing of regular tree languages
• Top-down tree edit-distance of regular tree languages
• Regular languages are testable with a constant number of queries
• Alignment distance of regular tree languages
• Approximate membership for regular languages modulo the edit distance

Cited in

(6)

• Test sets for the universal and existential closure of regular tree languages.
• Property testing of regular tree languages
• Measure Properties of Game Tree Languages
• Approximate satisfiability and equivalence
• Approximate membership for regular languages modulo the edit distance
• Streaming Property Testing of Visibly Pushdown Languages *

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

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