Finite-model theory -- A personal perspective
type: Item
instance of: scholarly article
title: Finite-model theory -- A personal perspective
zbMATH Open document ID: 0788.03037
DOI: 10.1016/0304-3975(93)90218-I
author: Ronald Fagin
published in: Theoretical Computer Science
publication date: 1994-06-05T00:00:00Z
review text: This clearly written expository paper surveys finite-model theory, the model theory of finite structures. The author -- a pioneer of finite- model theory -- focuses on results and problems springing from work in his Ph.D. thesis, thereby covering most of the main issues on finite- model theory. Among the topics discussed are: Spectra and generalized spectra, zero-one-laws and descriptive complexity theory.
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 438311
zbMATH Keywords: expository paper
zbMATH Keywords: finite-model theory
zbMATH Keywords: generalized spectra
zbMATH Keywords: zero-one- laws
zbMATH Keywords: descriptive complexity theory
Wikidata QID: Q59410892
reviewed by: Jörg Flum
MaRDI profile type: Publication
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Reachability is harder for directed than for undirected finite graphs
cites work: Monotone versus positive
cites work: Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
cites work: Q3714043
cites work: Expectations for Inbreeding Depression on Self-Fertilization of Tetraploids
cites work: A zero-one law for logic with a fixed-point operator
cites work: Relativizing Time, Space, and Time-Space
cites work: Structure and complexity of relational queries
cites work: Model theory.
cites work: Q3235339
cites work: A logical approach to asymptotic combinatorics I. First order properties
cites work: A Deductive System for Existential Least Fixpoint Logic
cites work: Nonconvergence, undecidability, and intractability in asymptotic problems
cites work: The complexity of theorem-proving procedures
cites work: Q4134974
cites work: Q4107930
cites work: Q3905252
cites work: Paths, Trees, and Flowers
cites work: An application of games to the completeness problem for formalized theories
cites work: Q4052071
cites work: Asymmetric graphs
cites work: Q4065548
cites work: Q4058132
cites work: Monadic generalized spectra
cites work: A spectrum hierarchy
cites work: A two‐cardinal characterization of double spectra
cites work: Probabilities on finite models
cites work: Horn clauses and database dependencies
cites work: On monadic NP vs monadic co-NP
cites work: Q4728289
cites work: Course of mathematical logic. Vol. 1: Relation and logical formula. Translation edited by David Louvish
cites work: Concerning measures in first order calculi
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: The Gödel class with identity is unsolvable
cites work: Complexity of the first-order theory of almost all finite structures
cites work: The decision problem for standard classes
cites work: Q3758820
cites work: Fixed-point extensions of first-order logic
cites work: Q4124353
cites work: Q4166743
cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME
cites work: Number of quantifiers is better than number of tape cells
cites work: Upper and lower bounds for first order expressibility
cites work: Relational queries computable in polynomial time
cites work: Languages that Capture Complexity Classes
cites work: Nondeterministic Space is Closed under Complementation
cites work: Q3830533
cites work: Turing machines and the spectra of first-order formulas
cites work: Homogeneous Universal Relational Systems.
cites work: Q4142699
cites work: On random models of finite power and monadic logic
cites work: 0-1 laws and decision problems for fragments of second-order logic
cites work: Q4071737
cites work: Q3856727
cites work: Almost sure theories
cites work: Probabilities of First-Order Sentences about Unary Functions
cites work: Q3668890

Finite-model theory -- A personal perspective (cites work)
cites work: Universal graphs and universal functions

Finite-model theory -- A personal perspective (cites work)
cites work: Relationships between nondeterministic and deterministic tape complexities

Finite-model theory -- A personal perspective (cites work)
cites work: Classification theory and the number of non-isomorphic models

Finite-model theory -- A personal perspective (cites work)
cites work: Zero-One Laws for Sparse Random Graphs

Finite-model theory -- A personal perspective (cites work)
cites work: Q5537599

Finite-model theory -- A personal perspective (cites work)
cites work: The method of forced enumeration for nondeterministic automata

Finite-model theory -- A personal perspective (cites work)
cites work: A counterexample to a conjecture of Scott and Suppes

Finite-model theory -- A personal perspective (cites work)
cites work: Q3970879

Finite-model theory -- A personal perspective (cites work)
cites work: Q5833217

Finite-model theory -- A personal perspective (cites work)
cites work: Q5797034

Finite-model theory -- A personal perspective (cites work)
cites work: On the definability of properties of finite graphs

Finite-model theory -- A personal perspective (cites work)
cites work: Relative complexity of checking and evaluating

Finite-model theory -- A personal perspective (cites work)
cites work: Sentences true in all constructive models