Logic in Finite Structures: Definability, Complexity, and Randomness

In Dale Jacquette (ed.), A Companion to Philosophical Logic. Oxford, UK: Blackwell. pp. 332–348 (2006)
  Copy   BIBTEX

Abstract

This chapter contains sections titled: Validity in the Finite Model Theory in the Finite? Definability and Complexity First‐Order Definability Second‐Order Definability Inductive Definability Infinitary Logics Random Graphs and 0–1 Laws.

Categories

Add categories

Keywords

Reprint years

ISBN(s)

9780470996751   9780631216711

DOI

10.1002/9780470996751.ch23

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,075

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Arithmetical definability over finite structures.Troy Lee - 2003 - Mathematical Logic Quarterly 49 (4):385.
The complexity of definability by open first-order formulas.Carlos Areces, Miguel Campercholi, Daniel Penazzi & Pablo Ventura - 2020 - Logic Journal of the IGPL 28 (6):1093-1105.
Automata presenting structures: A survey of the finite string case.Sasha Rubin - 2008 - Bulletin of Symbolic Logic 14 (2):169-209.
Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.
How to define a linear order on finite models.Lauri Hella, Phokion G. Kolaitis & Kerkko Luosto - 1997 - Annals of Pure and Applied Logic 87 (3):241-267.
Finite variable logics in descriptive complexity theory.Martin Grohe - 1998 - Bulletin of Symbolic Logic 4 (4):345-398.
Logics that define their own semantics.H. Imhof - 1999 - Archive for Mathematical Logic 38 (8):491-513.
First-order definability on finite structures.M. Ajtai - 1989 - Annals of Pure and Applied Logic 45 (3):211-225.
Second‐order and Inductive Definability on Finite Structures.Michel De Rougemont - 1987 - Mathematical Logic Quarterly 33 (1):47-63.
Computational model theory: an overview.M. Vardi - 1998 - Logic Journal of the IGPL 6 (4):601-624.
Capturing Relativized Complexity Classes without Order.Anuj Dawar, Georg Gottlob & Lauri Hella - 1998 - Mathematical Logic Quarterly 44 (1):109-122.
Some aspects of model theory and finite structures.Eric Rosen - 2002 - Bulletin of Symbolic Logic 8 (3):380-403.
Definability of second order generalized quantifiers.Juha Kontinen - 2010 - Archive for Mathematical Logic 49 (3):379-398.
On uniform definability of types over finite sets for NIP formulas.Shlomo Eshel & Itay Kaplan - 2020 - Journal of Mathematical Logic 21 (3):2150015.
On uniform definability of types over finite sets for NIP formulas.Shlomo Eshel & Itay Kaplan - 2020 - Journal of Mathematical Logic 21 (3).

Analytics

Added to PP
2023-06-15

Downloads
15 (#949,044)

6 months
7 (#433,721)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Scott Weinstein
University of Pennsylvania

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references