Relational Properties Expressible with One Universal Quantifier Are Testable

DOI10.1007/978-3-642-04944-6_12MaRDI QIDQ3646124zbMATH OpenOpenAlexFDO

Authors 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

logical classificationproperty testingrelational structures

Mathematics Subject Classification ID

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

Recommendations

• Testable and untestable classes of first-order formulae
• A note on the testability of Ramsey's class
• Untestable Properties Expressible with Four First-Order Quantifiers
• Efficient testing of large graphs
• Untestable Properties in the Kahr-Moore-Wang Class

Cites work

• 0-1 laws and decision problems for fragments of second-order logic
• \(\omega\)-regular languages are testable with a constant number of queries
• A combinatorial characterization of the testable graph properties, it's all about regularity
• A separation theorem in property testing
• Approximate hypergraph partitioning and applications
• Decidability of a portion of the predicate calculus
• Efficient testing of large graphs
• scientific article; zbMATH DE number 5485484 (Why is no real title available?)
• scientific article; zbMATH DE number 3635490 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 965572 (Why is no real title available?)
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Regular languages are testable with a constant number of queries
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Testing the diameter of graphs
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(5)

• Indistinguishability and First-Order Logic
• Untestable Properties Expressible with Four First-Order Quantifiers
• A note on the testability of Ramsey's class
• Testable and untestable classes of first-order formulae
• Testability in group theory

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

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