Elements of finite model theory.
From MaRDI portal
Publication:703864
zbMATH Open1060.03002MaRDI QIDQ703864FDOQ703864
Authors: Leonid Libkin 
Publication date: 12 January 2005
Published in: Texts in Theoretical Computer Science. An EATCS Series (Search for Journal in Brave)
Recommendations
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)
Cited In (only showing first 100 items - show all)
- Partial fixed point for finite models in second order logic
- Defining long words succinctly in FO and MSO
- Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination
- \(\gamma\)-variable first-order logic of uniform attachment random graphs
- A strategy for dynamic programs: start over and muddle through
- Zero-one laws for sentences with \(k\) variables
- Tight lower and upper bounds for the complexity of canonical colour refinement
- When Is Reachability Intrinsically Decidable?
- MSO 0-1 law for recursive random trees
- Computation on structures. Behavioural theory, logic, complexity
- The quantum monad on relational structures
- Existential monadic second order convergence law fails on sparse random graphs
- Work-sensitive dynamic complexity of formal languages
- Difference hierarchies and duality with an application to formal languages
- First-order rewritability of ontology-mediated queries in linear temporal logic
- \( \gamma \)-variable first-order logic of preferential attachment random graphs
- Complexity of the Steiner Network Problem with Respect to the Number of Terminals
- Yes, the ``missing axiom of matroid theory is lost forever
- Symmetric circuits for rank logic
- On the convergence of probabilities of first-order sentences for recursive random graph models
- On the Hybrid Extension of CTL and CTL +
- Achieving new upper bounds for the hypergraph duality problem through logic
- Tree automata and pigeonhole classes of matroids. I
- Consistent query answering for primary keys in Datalog
- First-order complexity of subgraph isomorphism via Kneser graphs
- Computing thejth solution of a first-order query
- Analysing Complexity in Classes of Unary Automatic Structures
- A parameterized view on the complexity of dependence logic
- Title not available (Why is that?)
- Title not available (Why is that?)
- Rational elements of summation semirings
- Database query processing using finite cursor machines
- Trakhtenbrot’s Theorem in Coq
- Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment
- Meta-kernelization using well-structured modulators
- On definability of team relations with \(k\)-invariant atoms
- Complexity results on register context-free grammars and related formalisms
- The dynamic complexity of acyclic hypergraph homomorphisms
- Title not available (Why is that?)
- Building a Knowledge Base System for an Integration of Logic Programming and Classical Logic
- Axiomatization of betweenness in order-theoretic trees
- Where first-order and monadic second-order logic coincide
- Zero-one laws for \(k\)-variable first-order logic of sparse random graphs
- On the expressiveness of \textsc{Lara}: a proposal for unifying linear and relational algebra
- On the first-order complexity of induced subgraph isomorphism
- Descriptive complexity of deterministic polylogarithmic time and space
- Expressive Power and Succinctness of the Positive Calculus of Relations
- Logical separability of labeled data examples under ontologies
- The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws
- Undecidability of QLTL and QCTL with two variables and one monadic predicate letter
- On finding short resolution refutations and small unsatisfiable subsets
- Recursive definitions and fixed-points
- Existential monadic second order logic on random rooted trees
- A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences
- The navigational power of web browsers
- Expressive power of entity-linking frameworks
- Nonmaximal decidable structures
- Model theoretical aspects of weakly aggregative modal logic
- Lifted inference with tree axioms
- Parameterized model checking of rendezvous systems
- Language games
- Varieties
- Ontology-Mediated Query Answering with Data-Tractable Description Logics
- A finite-model-theoretic view on propositional proof complexity
- Property testing for bounded degree databases
- Comparison of expressive power of some query languages for databases
- Parameterized Complexity Classes under Logical Reductions
- Axiomatisability and hardness for universal Horn classes of hypergraphs
- Title not available (Why is that?)
- Message exchange games in strategic contexts
- The mu-calculus and Model Checking
- Relativised homomorphism preservation at the finite level
- Regular model checking revisited
- Ehrenfeucht-Fraïssé games in finite set theory
- On the Descriptive Complexity of Linear Algebra
- From Hilbert's program to a logic tool box
- Meta-kernelization with structural parameters
- Structural characterizations of the navigational expressiveness of relation algebras on a tree
- Arity and alternation: a proper hierarchy in higher order logics
- Solving problems on graphs of high rank-width
- Logical laws for short existential monadic second-order sentences about graphs
- The complexity of reasoning with FODD and GFODD
- Relating structure and power: comonadic semantics for computational resources (extended abstract)
- Relating structure and power: comonadic semantics for computational resources
- On the Tutte and Matching Polynomials for Complete Graphs
- Whither semantics?
- A logician's view of graph polynomials
- On Composing Finite Forests with Modal Logics
- Computability of validity and satisfiability in probability logics over finite and countable models
- Expressivity of imperfect information logics without identity
- Title not available (Why is that?)
- Extension complexity, MSO logic, and treewidth
- Recursive definitions and fixed-points on well-founded structures
- Keeping logic in the trivium of computer science: a teaching perspective
- Parameterized complexity of fair vertex evaluation problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Open-world probabilistic databases: semantics, algorithms, complexity
- Expressive power and abstraction in Essence
- Logical laws for existential monadic second-order sentences with infinite first-order parts
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)
