Finite-model theory -- A personal perspective
From MaRDI portal
Publication:688663
DOI10.1016/0304-3975(93)90218-IzbMATH Open0788.03037WikidataQ59410892 ScholiaQ59410892MaRDI QIDQ688663FDOQ688663
Authors: Ronald Fagin 
Publication date: 5 June 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Probabilities on finite models
- Paths, Trees, and Flowers
- Title not available (Why is that?)
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Fixed-point extensions of first-order logic
- Relationships between nondeterministic and deterministic tape complexities
- Concerning measures in first order calculi
- Title not available (Why is that?)
- Title not available (Why is that?)
- Zero-One Laws for Sparse Random Graphs
- A spectrum hierarchy
- The complexity of theorem-proving procedures
- Some simplified NP-complete graph problems
- Title not available (Why is that?)
- Nondeterministic Space is Closed under Complementation
- Horn clauses and database dependencies
- Model theory.
- Classification theory and the number of non-isomorphic models
- Title not available (Why is that?)
- On monadic NP vs monadic co-NP
- An application of games to the completeness problem for formalized theories
- Reachability is harder for directed than for undirected finite graphs
- Languages that Capture Complexity Classes
- Title not available (Why is that?)
- Monadic generalized spectra
- Title not available (Why is that?)
- Universal graphs and universal functions
- Asymmetric graphs
- Homogeneous Universal Relational Systems.
- The method of forced enumeration for nondeterministic automata
- Title not available (Why is that?)
- Course of mathematical logic. Vol. 1: Relation and logical formula. Translation edited by David Louvish
- Turing machines and the spectra of first-order formulas
- Title not available (Why is that?)
- Relative complexity of checking and evaluating
- Relational queries computable in polynomial time
- Title not available (Why is that?)
- Title not available (Why is that?)
- Number of quantifiers is better than number of tape cells
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sentences true in all constructive models
- 0-1 laws and decision problems for fragments of second-order logic
- Upper and lower bounds for first order expressibility
- Nonconvergence, undecidability, and intractability in asymptotic problems
- Structure and complexity of relational queries
- Probabilities of First-Order Sentences about Unary Functions
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Title not available (Why is that?)
- Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
- A zero-one law for logic with a fixed-point operator
- Complexity of the first-order theory of almost all finite structures
- Almost sure theories
- On random models of finite power and monadic logic
- A logical approach to asymptotic combinatorics I. First order properties
- A counterexample to a conjecture of Scott and Suppes
- The Gödel class with identity is unsolvable
- Title not available (Why is that?)
- Monotone versus positive
- Title not available (Why is that?)
- Relativizing Time, Space, and Time-Space
- Title not available (Why is that?)
- A two‐cardinal characterization of double spectra
- Expectations for Inbreeding Depression on Self-Fertilization of Tetraploids
- The decision problem for standard classes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Deductive System for Existential Least Fixpoint Logic
- On the definability of properties of finite graphs
Cited In (40)
- Locally finite languages
- Expressivity and Complexity of Dependence Logic
- Title not available (Why is that?)
- Existential second-order logic and modal logic with quantified accessibility relations
- 0-1 laws by preservation
- Title not available (Why is that?)
- Probabilities in first—order logic of a unary function and a binary relation
- Elements of finite model theory.
- A technique for proving decidability of containment and equivalence of linear constraint queries
- Title not available (Why is that?)
- Some connections between finite and infinite model theory
- Descriptive complexity of finite structures: Saving the quantifier rank
- A general condition for collapse results
- Verifiable properties of database transactions
- Query languages for bags and aggregate functions
- Finitely representable databases
- A probabilistic view of Datalog parallelization
- Queries with arithmetical constraints
- Günter Asser (1926–2015)
- Asymptotic invariants, complexity of groups and related problems.
- A logical approach to locality in pictures languages
- Almost everywhere elimination of probability quantifiers
- Finite Model Theory on Tame Classes of Structures
- Computability by monadic second-order logic
- Title not available (Why is that?)
- Closure properties of locally finite \(\omega\)-languages
- Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures
- A decidable class of nested iterated schemata
- Lattice of algebraically closed sets in one-based theories
- The complexity of reasoning with FODD and GFODD
- Metafinite model theory
- Logic, semigroups and automata on words
- First-order spectra with one binary predicate
- Finite and infinite model theory - a historical perspective
- On the variable hierarchy of first-order spectra
- Finite model theory
- Subtournaments isomorphic to \(W_5\) in a indecomposable tournament
- A query language for NC
- Computing with infinitary logic
- On the expressive power of counting
This page was built for publication: Finite-model theory -- A personal perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688663)
