Elements of finite model theory.
From MaRDI portal
Publication:703864
zbMath1060.03002MaRDI QIDQ703864
Publication date: 12 January 2005
Published in: Texts in Theoretical Computer Science. An EATCS Series (Search for Journal in Brave)
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)
Related Items
Complexity of model checking for reaction systems, On finding short resolution refutations and small unsatisfiable subsets, 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, Existential monadic second order logic on random rooted trees, \( \gamma \)-variable first-order logic of preferential attachment random graphs, Bounded situation calculus action theories, A logical approach to locality in pictures languages, Parameterized model checking of rendezvous systems, Nonmaximal decidable structures, Model checking Petri nets with names using data-centric dynamic systems, Tree automata and pigeonhole classes of matroids. I, Analogical proportions, A parameterized view on the complexity of dependence logic, Model theoretical aspects of weakly aggregative modal logic, Axiomatisability and hardness for universal Horn classes of hypergraphs, The first order definability of graphs: Upper bounds for quantifier depth, An Ehrenfeucht-Fraïssé game approach to collapse results in database theory, On definability of team relations with \(k\)-invariant atoms, Parameterized complexity of fair deletion problems, A remark on the complexity of consistent conjunctive query answering under primary key violations, First-order query rewriting for inconsistent databases, Subshifts as models for MSO logic, Super/rosy \(L^k\)-theories and classes of finite structures, A representation theorem for (\(q\)-)holonomic sequences, Solutions and query rewriting in data exchange, Relativised homomorphism preservation at the finite level, The language of plain SO-tgds: composition, inversion and structural properties, Expressiveness and static analysis of extended conjunctive regular path queries, Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras, The ins and outs of first-order runtime verification, The complexity of weighted counting for acyclic conjunctive queries, Equivariant unification, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Structural characterizations of the navigational expressiveness of relation algebras on a tree, Meta-kernelization with structural parameters, Model-checking hierarchical structures, On the model-checking of monadic second-order formulas with edge set quantifications, Compact labelings for efficient first-order model-checking, The complexity of reasoning with FODD and GFODD, Keeping logic in the trivium of computer science: a teaching perspective, An optimal construction of Hanf sentences, Algorithmic correspondence and completeness in modal logic. V. Recursive extensions of SQEMA, On complexity of Ehrenfeucht-Fraïssé games, The implication problem for `closest node' functional dependencies in complete XML documents, Logical laws for existential monadic second-order sentences with infinite first-order parts, Query languages for data exchange: beyond unions of conjunctive queries, Solving problems on graphs of high rank-width, Relational hidden variables and non-locality, Expressivity of imperfect information logics without identity, Partial fixed point for finite models in second order logic, The complexity of Bayesian networks specified by propositional and relational languages, Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false, Regular languages of nested words: fixed points, automata, and synchronization, Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination, Book review of: E. Grädel, P. Kolaitis, L. Libkin, M. Marx, I. Spencer, M. Vardi, Y. Venema, S. Weinstein, Finite model theory and its applications, Second-order propositional modal logic and monadic alternation hierarchies, Recursive definitions and fixed-points on well-founded structures, Second-order propositional modal logic: expressiveness and completeness results, A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences, Work-sensitive dynamic complexity of formal languages, Expressive power and abstraction in Essence, Expressive power of entity-linking frameworks, Open-world probabilistic databases: semantics, algorithms, complexity, First-order rewritability of ontology-mediated queries in linear temporal logic, Circle graphs and monadic second-order logic, Muller message-passing automata and logics, On first-order definitions of subgraph isomorphism properties, On the convergence of probabilities of first-order sentences for recursive random graph models, MSO 0-1 law for recursive random trees, On the complexity of propositional and relational credal networks, First-order under-approximations of consistent query answers, The navigational power of web browsers, Ehrenfeucht-Fraïssé games in finite set theory, Existential monadic second order convergence law fails on sparse random graphs, Database query processing using finite cursor machines, Descriptive complexity of graph spectra, A model-theoretic characterization of constant-depth arithmetic circuits, A logician's view of graph polynomials, CompoSAT: specification-guided coverage for model finding, Partitioning graphs into induced subgraphs, The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws, Consistent query answering for primary keys in Datalog, On the expressive power of linear algebra on graphs, First-order complexity of subgraph isomorphism via Kneser graphs, Relating structure and power: comonadic semantics for computational resources (extended abstract), Universal algebra and hardness results for constraint satisfaction problems, Affine systems of equations and counting infinitary logic, From a zoo to a zoology: Towards a general theory of graph polynomials, Exploiting forwardness: satisfiability and query-entailment in forward guarded fragment, From Hilbert's program to a logic tool box, Varieties, On the power of deep pushdown stacks, On the expressiveness of \textsc{Lara}: a proposal for unifying linear and relational algebra, Logical separability of labeled data examples under ontologies, Defining long words succinctly in FO and MSO, \(\gamma\)-variable first-order logic of uniform attachment random graphs, Existential second-order logic and modal logic with quantified accessibility relations, Computation on structures. Behavioural theory, logic, complexity, Limiting Until in Ordered Tree Query Languages, Two-Variable Logic with Counting and Trees, On the Tutte and Matching Polynomials for Complete Graphs, Trakhtenbrot’s Theorem in Coq, Solving Problems on Graphs of High Rank-Width, The mu-calculus and Model Checking, Logical properties of random graphs from small addable classes, Undecidability of QLTL and QCTL with two variables and one monadic predicate letter, Parameterized Complexity Classes under Logical Reductions, On the Hybrid Extension of CTL and CTL +, Controlled query evaluation with open queries for a decidable relational submodel, Arity and alternation: a proper hierarchy in higher order logics, Using Evolution Graphs for Describing Topology-Aware Prediction Models in Large Clusters, On the equivalence between FDs in XML and FDs in relations, Querying Regular Graph Patterns, Unnamed Item, Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures, Short Monadic Second Order Sentences about Sparse Random Graphs, Rational, recognizable, and aperiodic partially lossy queue languages, Process-centric views of data-driven business artifacts, Tight lower and upper bounds for the complexity of canonical colour refinement, Descriptive complexity of deterministic polylogarithmic time and space, Rational elements of summation semirings, Message exchange games in strategic contexts, Property Testing for Bounded Degree Databases, Unnamed Item, Unnamed Item, Meta-kernelization using well-structured modulators, The dynamic complexity of acyclic hypergraph homomorphisms, EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs, Complexity results on register context-free grammars and related formalisms, Separation logics and modalities: a survey, Computability of validity and satisfiability in probability logics over finite and countable models, Expressive Power and Succinctness of the Positive Calculus of Relations, Computer-Supported Exploration of a Categorical Axiomatization of Modeloids, SO F : A Semantic Restriction over Second-Order Logic and Its Polynomial-Time Hierarchy, On the Descriptive Complexity of Linear Algebra, Unnamed Item, Language Games, Fixpoint logics over hierarchical structures, Computing thejth solution of a first-order query, Logical laws for short existential monadic second-order sentences about graphs, Ontology-Mediated Query Answering with Data-Tractable Description Logics, Unnamed Item, Unnamed Item, On the locality of arb-invariant first-order formulas with modulo counting quantifiers, Unnamed Item, Unnamed Item, Unnamed Item, A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES, When Is Reachability Intrinsically Decidable?, Approximations of Mappings, Successor-Invariant First-Order Logic on Classes of Bounded Degree, Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic, Yes, the “missing axiom” of matroid theory is lost forever, On the Computational Complexity of Non-Dictatorial Aggregation, Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates, Extending two-variable logic on data trees with order on data values and its automata, Unnamed Item, Finding Reductions Automatically, Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs, Definability of Combinatorial Functions and Their Linear Recurrence Relations, Recursive Definitions and Fixed-Points, Unnamed Item, Recognizability, hypergraph operations, and logical types, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Comparison of expressive power of some query languages for databases, Whither semantics?, Unary automatic graphs: an algorithmic perspective, Analysing Complexity in Classes of Unary Automatic Structures, Unnamed Item, Unnamed Item, Measurement-Theoretic Foundations of Observational-Predicate Logic, Where First-Order and Monadic Second-Order Logic Coincide, Relating Structure and Power: Comonadic Semantics for Computational Resources, Unnamed Item, Conversation and Games, Spoilt for Choice: Full First-Order Hierarchical Decompositions, Ehrenfeucht-Fraïssé Games on Random Structures, Zero-one laws for \(k\)-variable first-order logic of sparse random graphs, Difference hierarchies and duality with an application to formal languages, Complexity of the Steiner Network Problem with Respect to the Number of Terminals, Unnamed Item, On the Parameterised Intractability of Monadic Second-Order Logic, Zero-one laws for sentences with \(k\) variables, Unnamed Item, Logical complexity of induced subgraph isomorphism for certain families of graphs, Building a Knowledge Base System for an Integration of Logic Programming and Classical Logic, On distinguishing sets of structures by first-order sentences of minimal quantifier rank, Unnamed Item, REDUCTION TECHNIQUES FOR PROVING DECIDABILITY IN LOGICS AND THEIR MEET–COMBINATION, Unnamed Item, An Infinitary System for the Least Fixed-Point Logic restricted to Finite Models, First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries, Canonisation and Definability for Graphs of Bounded Rank Width, On the decidability of axiomatized mereotopological theories, On Composing Finite Forests with Modal Logics, Enumeration for FO Queries over Nowhere Dense Graphs, Regular model checking revisited, Relativized adjacency, Seurat games on Stockmeyer graphs, On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves, Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино?, First-order Logic with Connectivity Operators, Lifted inference with tree axioms, Nonstandard methods for finite structures, Representation and processing of instantaneous and durative temporal phenomena, Asymptotic elimination of partially continuous aggregation functions in directed graphical models, Faster Property Testers in a Variation of the Bounded Degree Model, Feferman-vaught decompositions for prefix classes of first order logic, Inductive definitions in logic versus programs of real-time cellular automata, Arboreal categories and equi-resource homomorphism preservation theorems, Positive First-order Logic on Words and Graphs, Arboreal Categories: An Axiomatic Theory of Resources, Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic, Efficient Evaluation of Arbitrary Relational Calculus Queries, Presburger Büchi tree automata with applications to logics with expressive counting, A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases, Unnamed Item, First-order definable counting-only queries, A framework for comparing query languages in their ability to express Boolean queries, Independence-friendly logic without Henkin quantification, Guarded Negation, An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning, The descriptive complexity of subgraph isomorphism without numerics, An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
