Indistinguishability and First-Order Logic

DOI10.1007/978-3-540-79228-4_8zbMath1139.68392OpenAlexW2167782730MaRDI QIDQ3502636

Charles Jordan, Thomas Zeugmann

Publication date: 27 May 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79228-4_8

zbMATH Keywords

graph theorylogicproperty testingdescriptive complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Basic properties of first-order languages and structures (03C07) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\omega\)-regular languages are testable with a constant number of queries
• Self-testing/correcting with applications to numerical problems
• Design and analysis of randomized algorithms. Introduction to design paradigms.
• On monadic NP vs monadic co-NP
• On uniformity within \(NC^ 1\)
• 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
• Parity, circuits, and the polynomial-time hierarchy
• A First-Order Isomorphism Theorem
• Three theorems regarding testing graph properties
• Testing graphs for colorability properties*
• Robust Characterizations of Polynomials with Applications to Program Testing
• On the Computational Complexity of Algorithms
• Efficient testing of large graphs