Relational Properties Expressible with One Universal Quantifier Are Testable

DOI10.1007/978-3-642-04944-6_12zbMath1260.03016OpenAlexW1550790952MaRDI QIDQ3646124

Charles Jordan, Thomas Zeugmann

Publication date: 19 November 2009

Published in: Stochastic Algorithms: Foundations and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04944-6_12

zbMATH Keywords

relational structuresproperty testinglogical classification

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Model theory of finite structures (03C13)

Related Items (1)

Testable and untestable classes of first-order formulae

Cites Work

• \(\omega\)-regular languages are testable with a constant number of queries
• 0-1 laws and decision problems for fragments of second-order logic
• A separation theorem in property testing
• Decidability of a portion of the predicate calculus
• Self-testing/correcting with applications to numerical problems
• Regular Languages are Testable with a Constant Number of Queries
• A combinatorial characterization of the testable graph properties
• Property testing and its connection to learning and approximation
• Weak Second‐Order Arithmetic and Finite Automata
• Testing the diameter of graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Approximate Hypergraph Partitioning and Applications
• Efficient testing of large graphs
• Property testing in bounded degree graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Relational Properties Expressible with One Universal Quantifier Are Testable