Finite-model theory -- A personal perspective

DOI10.1016/0304-3975(93)90218-IzbMath0788.03037WikidataQ59410892 ScholiaQ59410892MaRDI QIDQ688663

Ronald Fagin

Publication date: 5 June 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

descriptive complexity theoryexpository paperfinite-model theorygeneralized spectrazero-one- laws

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13)

Related Items

Closure properties of locally finite \(\omega\)-languages, A logical approach to locality in pictures languages, First-order spectra with one binary predicate, Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures, Computability by monadic second-order logic, Query languages for bags and aggregate functions, Finitely representable databases, A query language for NC, Metafinite model theory, A probabilistic view of Datalog parallelization, 0-1 laws by preservation, Queries with arithmetical constraints, On the Variable Hierarchy of First-Order Spectra, The complexity of reasoning with FODD and GFODD, Subtournaments isomorphic to \(W_5\) in a indecomposable tournament, On the expressive power of counting, Computing with infinitary logic, Descriptive complexity of finite structures: Saving the quantifier rank, Locally finite languages, A Decidable Class of Nested Iterated Schemata, Probabilities in first—order logic of a unary function and a binary relation, Expressivity and Complexity of Dependence Logic, A technique for proving decidability of containment and equivalence of linear constraint queries, Logic, semigroups and automata on words, Verifiable properties of database transactions, Almost everywhere elimination of probability quantifiers, Günter Asser (1926–2015), Asymptotic invariants, complexity of groups and related problems, Existential second-order logic and modal logic with quantified accessibility relations

Cites Work

• On the definability of properties of finite graphs
• 0-1 laws and decision problems for fragments of second-order logic
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On random models of finite power and monadic logic
• Fixed-point extensions of first-order logic
• Nonconvergence, undecidability, and intractability in asymptotic problems
• The method of forced enumeration for nondeterministic automata
• A logical approach to asymptotic combinatorics I. First order properties
• Number of quantifiers is better than number of tape cells
• Upper and lower bounds for first order expressibility
• Model theory.
• Some simplified NP-complete graph problems
• Relative complexity of checking and evaluating
• Classification theory and the number of non-isomorphic models
• Structure and complexity of relational queries
• On monadic NP vs monadic co-NP
• Relationships between nondeterministic and deterministic tape complexities
• Concerning measures in first order calculi
• Course of mathematical logic. Vol. 1: Relation and logical formula. Translation edited by David Louvish
• Probabilities of First-Order Sentences about Unary Functions
• Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
• A counterexample to a conjecture of Scott and Suppes
• An application of games to the completeness problem for formalized theories
• The Gödel class with identity is unsolvable
• Complexity of the first-order theory of almost all finite structures
• Reachability is harder for directed than for undirected finite graphs
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• A zero-one law for logic with a fixed-point operator
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Monotone versus positive
• Zero-One Laws for Sparse Random Graphs
• Nondeterministic Space is Closed under Complementation
• Sentences true in all constructive models
• Almost sure theories
• Relativizing Time, Space, and Time-Space
• Horn clauses and database dependencies
• A two‐cardinal characterization of double spectra
• A spectrum hierarchy
• Monadic generalized spectra
• Expectations for Inbreeding Depression on Self-Fertilization of Tetraploids
• The decision problem for standard classes
• Probabilities on finite models
• A Deductive System for Existential Least Fixpoint Logic
• Turing machines and the spectra of first-order formulas
• Paths, Trees, and Flowers
• Universal graphs and universal functions
• Homogeneous Universal Relational Systems.
• The complexity of theorem-proving procedures
• Asymmetric graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item