Elements of finite model theory.
From MaRDI portal
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01)
Recommendations
Cited in
(only showing first 100 items - show all)- On the expressive power of linear algebra on graphs
- On finding short resolution refutations and small unsatisfiable subsets
- Partial fixed point for finite models in second order logic
- Undecidability of QLTL and QCTL with two variables and one monadic predicate letter
- Arboreal categories and equi-resource homomorphism preservation theorems
- Arboreal Categories: An Axiomatic Theory of Resources
- A framework for comparing query languages in their ability to express Boolean queries
- A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES
- CompoSAT: specification-guided coverage for model finding
- On the expressive power of linear algebra on graphs
- Existential second-order logic and modal logic with quantified accessibility relations
- Complexity of model checking for reaction systems
- Recognizability, hypergraph operations, and logical types
- Defining long words succinctly in FO and MSO
- Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination
- On distinguishing sets of structures by first-order sentences of minimal quantifier rank
- Feferman-vaught decompositions for prefix classes of first order logic
- First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries
- Recursive definitions and fixed-points
- Efficient Evaluation of Arbitrary Relational Calculus Queries
- EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs
- Existential monadic second order logic on random rooted trees
- A logical description of priority separable games
- scientific article; zbMATH DE number 7566055 (Why is no real title available?)
- scientific article; zbMATH DE number 7566073 (Why is no real title available?)
- A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences
- Inapproximability of unique games in fixed-point logic with counting
- Executable first-order queries in the logic of information flows
- The pebble-relation comonad in finite model theory
- The navigational power of web browsers
- \(\gamma\)-variable first-order logic of uniform attachment random graphs
- On the descriptive complexity of temporal constraint satisfaction problems
- Highly expressive query languages for unordered data trees
- Structural tractability of counting of solutions to conjunctive queries
- A formalization of programs in first-order logic with a discrete linear order
- A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- Zero-one laws for sentences with \(k\) variables
- Tight lower and upper bounds for the complexity of canonical colour refinement
- A strategy for dynamic programs: start over and muddle through
- When Is Reachability Intrinsically Decidable?
- The complexity of weighted counting for acyclic conjunctive queries
- Finite-model theory -- A personal perspective
- MSO 0-1 law for recursive random trees
- Expressive power of entity-linking frameworks
- Spoilt for Choice: Full First-Order Hierarchical Decompositions
- Model-checking hierarchical structures
- An optimal construction of Hanf sentences
- Computation on structures. Behavioural theory, logic, complexity
- Nonmaximal decidable structures
- Separation logics and modalities: a survey
- Model theoretical aspects of weakly aggregative modal logic
- Bounded situation calculus action theories
- The quantum monad on relational structures
- Algorithmic correspondence and completeness in modal logic. V. Recursive extensions of SQEMA
- Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras
- Existential monadic second order convergence law fails on sparse random graphs
- Work-sensitive dynamic complexity of formal languages
- Unary automatic graphs: an algorithmic perspective
- Difference hierarchies and duality with an application to formal languages
- Lifted inference with tree axioms
- Presburger Büchi tree automata with applications to logics with expressive counting
- The first order definability of graphs: Upper bounds for quantifier depth
- First-order query rewriting for inconsistent databases
- Descriptive complexity for counting complexity classes
- An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
- \( \gamma \)-variable first-order logic of preferential attachment random graphs
- First-order rewritability of ontology-mediated queries in linear temporal logic
- Muller message-passing automata and logics
- On the computational complexity of non-dictatorial aggregation
- The implication problem for `closest node' functional dependencies in complete XML documents
- Conversation and games
- Seurat games on Stockmeyer graphs
- A logical approach to locality in pictures languages
- Parameterized model checking of rendezvous systems
- Yes, the ``missing axiom of matroid theory is lost forever
- Complexity of the Steiner Network Problem with Respect to the Number of Terminals
- Enumeration for FO Queries over Nowhere Dense Graphs
- Language games
- The ins and outs of first-order runtime verification
- On the convergence of probabilities of first-order sentences for recursive random graph models
- On the decidability of axiomatized mereotopological theories
- Game comonads \& generalised quantifiers
- On the satisfiability of local first-order logics with data
- Varieties
- Symmetric circuits for rank logic
- Ontology-Mediated Query Answering with Data-Tractable Description Logics
- On the Hybrid Extension of CTL and CTL +
- Logical properties of random graphs from small addable classes
- scientific article; zbMATH DE number 1324669 (Why is no real title available?)
- Logical complexity of induced subgraph isomorphism for certain families of graphs
- Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
- Super/rosy L^k-theories and classes of finite structures
- A finite-model-theoretic view on propositional proof complexity
- Property testing for bounded degree databases
- Relativized adjacency
- First-order definable counting-only queries
- Finite model theory and its applications.
- Achieving new upper bounds for the hypergraph duality problem through logic
- Comparison of expressive power of some query languages for databases
This page was built for publication: Elements of finite model theory.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703864)
