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
- 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
- Recognizability, hypergraph operations, and logical types
- Existential second-order logic and modal logic with quantified accessibility relations
- Complexity of model checking for reaction systems
- On distinguishing sets of structures by first-order sentences of minimal quantifier rank
- 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
- Separation logics and modalities: a survey
- Finite-model theory -- A personal perspective
- The complexity of weighted counting for acyclic conjunctive queries
- Model-checking hierarchical structures
- An optimal construction of Hanf sentences
- Bounded situation calculus action theories
- Algorithmic correspondence and completeness in modal logic. V. Recursive extensions of SQEMA
- Unary automatic graphs: an algorithmic perspective
- Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras
- The first order definability of graphs: Upper bounds for quantifier depth
- First-order query rewriting for inconsistent databases
- Muller message-passing automata and logics
- The implication problem for `closest node' functional dependencies in complete XML documents
- A logical approach to locality in pictures languages
- On the decidability of axiomatized mereotopological theories
- The ins and outs of first-order runtime verification
- Title not available (Why is that?)
- Super/rosy \(L^k\)-theories and classes of finite structures
- Finite model theory and its applications.
- Independence-friendly logic without Henkin quantification
- A remark on the complexity of consistent conjunctive query answering under primary key violations
- Model checking Petri nets with names using data-centric dynamic systems
- Finite Model Theory
- Controlled query evaluation with open queries for a decidable relational submodel
- Limiting Until in ordered tree query languages
- Equivariant unification
- Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures
- On the model-checking of monadic second-order formulas with edge set quantifications
- Querying regular graph patterns
- Second-order propositional modal logic and monadic alternation hierarchies
- On the power of deep pushdown stacks
- Canonisation and Definability for Graphs of Bounded Rank Width
- Process-centric views of data-driven business artifacts
- Compact labelings for efficient first-order model-checking
- Regular languages of nested words: fixed points, automata, and synchronization
- Faster Property Testers in a Variation of the Bounded Degree Model
- Circle graphs and monadic second-order logic
- Extending two-variable logic on data trees with order on data values and its automata
- Title not available (Why is that?)
- Query languages for data exchange: beyond unions of conjunctive queries
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)
