Testable and untestable classes of first-order formulae
From MaRDI portal
Publication:440006
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
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
