Finite model theory.
From MaRDI portal
This is the second edition of the book which first appeared in 1995. As is stated in the preface, it is a thoroughly revised and enlarged version of the original text. The most relevant change is the addition of a new Chapter 11 which deals with logic for PTIME. In Chapter 9, the authors have added an application of negative fixed-point logic. For more details see the review of the first edition in Zbl 0841.03014.
Recommendations
- Finite model theory and its applications.
- Elements of finite model theory.
- Finite Model Theory
- scientific article; zbMATH DE number 803291
- Model theory.
- scientific article; zbMATH DE number 176207
- scientific article; zbMATH DE number 2156368
- Some Aspects of Model Theory and Finite Structures
- scientific article; zbMATH DE number 5038454
Cited in
(only showing first 100 items - show all)- Affine systems of equations and counting infinitary logic
- Harmonious logic: Craig's interpolation theorem and its descendants
- Partially ordered connectives and monadic monotone strict NP
- Exploiting functional dependencies in declarative problem specifications
- Hybrid logic meets IF modal logic
- A descriptive complexity approach to the linear hierarchy.
- XML with data values: Typechecking revisited.
- First order sentences about random graphs: small number of alternations
- On the computation of zone and double zone diagrams
- The descriptive complexity of decision problems through logics with relational fixed-point and capturing results
- Logical limit laws for minor-closed classes of graphs
- First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
- Attribute grammars for unranked trees as a query language for structured documents
- Describing parameterized complexity classes
- On the lengths of symmetry breaking-preserving games on graphs
- Expressive equivalence of least and inflationary fixed-point logic
- Modal and guarded characterisation theorems over finite transition systems
- An existential locality theorem
- Strictly balanced uniform hypergraphs and generalizations of zero-one law
- A pebbling comonad for finite rank and variable logic, and an application to the equirank-variable homomorphism preservation theorem
- Analogical proportions
- Modulo constraints and the complexity of typechecking XML views
- Two first-order logics of permutations
- On the width of regular classes of finite structures
- Infinite spectra of first-order properties for random hypergraphs
- On compactness of logics that can express properties of symmetry or connectivity
- Spectra of short monadic sentences about sparse random graphs
- Boolean dependence logic and partially-ordered connectives
- On symmetric circuits and fixed-point logics
- Succinct definitions in the first order theory of graphs
- Computing queries with higher-order logics
- Arity and alternation: a proper hierarchy in higher order logics
- On the expressive power of semijoin queries
- Tight lower and upper bounds for the complexity of canonical colour refinement
- Monadic second-order properties of very sparse random graphs
- Fixed-parameter tractable distances to sparse graph classes
- Digraph width measures in parameterized algorithmics
- A characterization of definability of second-order generalized quantifiers with applications to non-definability
- Decomposable graphs and definitions with no quantifier alternation
- Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
- The first order definability of graphs with separators via the Ehrenfeucht game
- A reducibility for the dot-depth hierarchy
- \(N\)-dimensional versus \((N-1)\)-dimensional connectivity testing of first-order queries to semi-algebraic sets
- Limit points of spectra for first-order properties of random hypergraphs
- Descriptive complexity of deterministic polylogarithmic time and space
- Rational elements of summation semirings
- Expressiveness of hybrid temporal logic on data words
- Ontology-Mediated Query Answering with Data-Tractable Description Logics
- On the locality of arb-invariant first-order formulas with modulo counting quantifiers
- Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
- Reasoning about negligibility and proximity in the set of all hyperreals
- The mu-calculus and Model Checking
- Parameterized Complexity Classes under Logical Reductions
- The Complexity of Counting Quantifiers on Equality Languages
- Approximations of mappings
- Equivariant algorithms for constraint satisfaction problems over coset templates
- On enumerating query plans using analytic tableau
- On the Descriptive Complexity of Linear Algebra
- The Descriptive Complexity of Parity Games
- Finding Reductions Automatically
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- Separating Graph Logic from MSO
- First-order logic formalisation of impossibility theorems in preference aggregation
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Courcelle's theorem -- a game-theoretic approach
- Sahlqvist theorem for modal fixed point logic
- Zero-one \(k\)-law
- Subtournaments isomorphic to W₅ in a indecomposable tournament
- scientific article; zbMATH DE number 2051828 (Why is no real title available?)
- Short monadic second order sentences about sparse random graphs
- Tarski's influence on computer science
- A finite-model-theoretic view on propositional proof complexity
- Rank logic is dead, long live rank logic!
- Achieving new upper bounds for the hypergraph duality problem through logic
- SOME MODEL THEORY OF GUARDED NEGATION
- Comparing the succinctness of monadic query languages over finite trees
- scientific article; zbMATH DE number 1357763 (Why is no real title available?)
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Computable queries for object oriented databases
- Expressibility of higher order logics
- Typical automorphism groups of finite nonrigid structures
- The parameterized space complexity of model-checking bounded variable first-order logic
- The complexity of higher-order queries
- Finding the limit of incompleteness. I
- Consistency for counting quantifiers
- REDUCTION TECHNIQUES FOR PROVING DECIDABILITY IN LOGICS AND THEIR MEET–COMBINATION
- Relating structure and power: comonadic semantics for computational resources
- Datalog: Bag Semantics via Set Semantics
- Homogeneous 1-based structures and interpretability in random structures
- Random \(\ell\)-colourable structures with a pregeometry
- Logical laws for short existential monadic second-order sentences about graphs
- First-order and monadic properties of highly sparse random graphs
- The complexity of counting quantifiers on equality languages
- Reversible regular languages: logical and algebraic characterisations
- A Practical Approach to Courcelle's Theorem
- Constraint satisfaction with counting quantifiers
- Backdoors to normality for disjunctive logic programs
- Expressiveness of logic programs under the general stable model semantics
- Relative expressive power of navigational querying on graphs
- CFI Construction and Balanced Graphs
This page was built for publication: Finite model theory.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4255575)
