Testable and untestable classes of first-order formulae
type: Item
instance of: scholarly article
title: Testable and untestable classes of first-order formulae
zbMATH Open document ID: 1260.68458
author: Charles Jordan
author: Thomas Zeugmann
published in: Journal of Computer and System Sciences
publication date: 2012-08-17T00:00:00Z
full work available at URL: http://hdl.handle.net/2115/49938
reviewed by: Efstratios Rappos
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 03B10
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03C68
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6067746
zbMATH Keywords: property testing
zbMATH Keywords: first-order logic
zbMATH Keywords: randomized algorithms
zbMATH Keywords: Ackermann's class
zbMATH Keywords: Ramsey's class
MaRDI profile type: Publication
OpenAlex ID: W2117580027
cites work: Efficient testing of large graphs
cites work: A combinatorial characterization of the testable graph properties
cites work: Regular languages are testable with a constant number of queries
cites work: Q3424887
cites work: A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
cites work: A separation theorem in property testing
cites work: Testability and repair of hereditary hypergraph properties
cites work: Self-testing/correcting with applications to numerical problems
cites work: Q5691140
cites work: Weak Second‐Order Arithmetic and Finite Automata
cites work: \(\omega\)-regular languages are testable with a constant number of queries
cites work: Q4282510
cites work: Q3152421
cites work: Testing graphs for colorability properties*
cites work: Approximate Hypergraph Partitioning and Applications
cites work: Q4195937
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Property testing in bounded degree graphs
cites work: Introduction to Testing Graph Properties
cites work: Property testing and its connection to learning and approximation
cites work: Hypergraph regularity and the multidimensional Szemerédi theorem
cites work: Satisfiability of formulae with one \(\forall\) is decidable in exponential time
cites work: Relational Properties Expressible with One Universal Quantifier Are Testable
cites work: Untestable Properties in the Kahr-Moore-Wang Class
cites work: ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
cites work: 0-1 laws and decision problems for fragments of second-order logic
cites work: Q4536345
cites work: Complexity results for classes of quantificational formulas
cites work: Q5641083
cites work: The Bernays-Schönfinkel-Ramsey class for set theory: semidecidability
cites work: Testing the diameter of graphs
cites work: Generalizations of the removal lemma
cites work: Regular Partitions of Hypergraphs: Regularity Lemmas
cites work: Q3060865
cites work: Q4788610
cites work: Q3615896
cites work: lgorithmic and Analysis Techniques in Property Testing
cites work: Robust Characterizations of Polynomials with Applications to Program Testing
cites work: Decidability of a portion of the predicate calculus
cites work: A variant of the hypergraph removal lemma
cites work: Asymptotic probabilities for second-order existential Kahr-Moore-Wang sentences
DOI: 10.1016/J.JCSS.2012.01.007
review text: This article studies property testing which identifies structures which may have a desired property, and the classification of logic sentences according to their testability. The article begins with an introduction and a historic background to property testing, followed by a summary of the main contribution of this article, which proves that all relational properties that begin with the logic prefix \(\exists^{*}\forall\exists^{*}\) are testable.NEWLINENEWLINEThe second section contains a large number of necessary background definitions and preliminary theorems which are necessary for proving the main results. The proof of the main result follows in the third section. The next two sections, Sections 4 and 5, concentrate on the classification of testable and untestable classes, respectively. This includes a proof that Ackermann's first-order class and Ramsey's class are testable, and provide a more simple example, compared to \(\forall^{12}\exists^{5}\), of an untestable class. This very interesting article concludes with a summary of the contributions and a useful list of relevant references.
description: scientific article; zbMATH DE number 6067746