Testable and untestable classes of first-order formulae

DOI10.1016/j.jcss.2012.01.007zbMath1260.68458OpenAlexW2117580027MaRDI QIDQ440006

Thomas Zeugmann, Charles Jordan

Publication date: 17 August 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2115/49938

zbMATH Keywords

first-order logicrandomized algorithmsproperty testingAckermann's classRamsey's class

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Logic in computer science (03B70) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Randomized algorithms (68W20) Other classical first-order model theory (03C68)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\omega\)-regular languages are testable with a constant number of queries
• A variant of the hypergraph removal lemma
• Satisfiability of formulae with one \(\forall\) is decidable in exponential time
• 0-1 laws and decision problems for fragments of second-order logic
• A separation theorem in property testing
• Generalizations of the removal lemma
• Complexity results for classes of quantificational formulas
• Decidability of a portion of the predicate calculus
• Self-testing/correcting with applications to numerical problems
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Regular Languages are Testable with a Constant Number of Queries
• A combinatorial characterization of the testable graph properties
• Untestable Properties in the Kahr-Moore-Wang Class
• Testability and repair of hereditary hypergraph properties
• Property testing and its connection to learning and approximation
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• Weak Second‐Order Arithmetic and Finite Automata
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• The Bernays-Schönfinkel-Ramsey class for set theory: semidecidability
• Relational Properties Expressible with One Universal Quantifier Are Testable
• Computational Complexity of Probabilistic Turing Machines
• Asymptotic probabilities for second-order existential Kahr-Moore-Wang sentences
• Testing the diameter of graphs
• Testing graphs for colorability properties*
• Robust Characterizations of Polynomials with Applications to Program Testing
• Introduction to Testing Graph Properties
• lgorithmic and Analysis Techniques in Property Testing
• Approximate Hypergraph Partitioning and Applications
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Efficient testing of large graphs
• Property testing in bounded degree graphs