scientific article; zbMATH DE number 1324669

Publication date: 17 August 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Turing machines optimization problems finite automata finite model theory complexity classes fixed-point logic oracles 0-1 laws Lindström quantifiers logic for PTIME logics with fixed-point operators

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Related Items (only showing first 100 items - show all)

Backdoors to Normality for Disjunctive Logic Programs ⋮ Expressiveness of Logic Programs under the General Stable Model Semantics ⋮ CFI Construction and Balanced Graphs ⋮ Unnamed Item ⋮ Games and Lindström theorems ⋮ First-order Logic with Connectivity Operators ⋮ Inputs, Outputs, and Composition in the Logic of Information Flows ⋮ Nonstandard methods for finite structures ⋮ Homogeneous 1‐based structures and interpretability in random structures ⋮ Random ℓ‐colourable structures with a pregeometry ⋮ Unnamed Item ⋮ Logical laws for short existential monadic second-order sentences about graphs ⋮ Reversible Regular Languages: Logical and Algebraic Characterisations ⋮ A Practical Approach to Courcelle's Theorem ⋮ Expressibility of Higher Order Logics ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ A framework for comparing query languages in their ability to express Boolean queries ⋮ Relating Structure and Power: Comonadic Semantics for Computational Resources ⋮ Datalog: Bag Semantics via Set Semantics ⋮ FINDING THE LIMIT OF INCOMPLETENESS I ⋮ The Relational Polynomial-Time Hierarchy and Second-Order Logic ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ REDUCTION TECHNIQUES FOR PROVING DECIDABILITY IN LOGICS AND THEIR MEET–COMBINATION ⋮ Canonisation and Definability for Graphs of Bounded Rank Width ⋮ Spectra of short monadic sentences about sparse random graphs ⋮ On finding short resolution refutations and small unsatisfiable subsets ⋮ Boolean dependence logic and partially-ordered connectives ⋮ Strictly balanced uniform hypergraphs and generalizations of zero-one law ⋮ Describing parameterized complexity classes ⋮ On symmetric circuits and fixed-point logics ⋮ Succinct definitions in the first order theory of graphs ⋮ Computing queries with higher-order logics ⋮ On the lengths of symmetry breaking-preserving games on graphs ⋮ A pebbling comonad for finite rank and variable logic, and an application to the equirank-variable homomorphism preservation theorem ⋮ Entropy of formulas ⋮ Expressive equivalence of least and inflationary fixed-point logic ⋮ Modal and guarded characterisation theorems over finite transition systems ⋮ An existential locality theorem ⋮ Reasoning about negligibility and proximity in the set of all hyperreals ⋮ The mu-calculus and Model Checking ⋮ On Enumerating Query Plans Using Analytic Tableau ⋮ Parameterized Complexity Classes under Logical Reductions ⋮ Analogical proportions ⋮ Arity and alternation: a proper hierarchy in higher order logics ⋮ The Complexity of Counting Quantifiers on Equality Languages ⋮ On the expressive power of semijoin queries ⋮ The first order definability of graphs: Upper bounds for quantifier depth ⋮ Equivariant algorithms for constraint satisfaction problems over coset templates ⋮ Short Monadic Second Order Sentences about Sparse Random Graphs ⋮ Tight lower and upper bounds for the complexity of canonical colour refinement ⋮ Expressiveness and complexity of graph logic ⋮ An Ehrenfeucht-Fraïssé game approach to collapse results in database theory ⋮ Limit points of spectra for first-order properties of random hypergraphs ⋮ Monadic second-order properties of very sparse random graphs ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ First-order logic formalisation of impossibility theorems in preference aggregation ⋮ Rational elements of summation semirings ⋮ Fixed-parameter tractable distances to sparse graph classes ⋮ Unnamed Item ⋮ Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ First order sentences about random graphs: small number of alternations ⋮ A descriptive complexity approach to the linear hierarchy. ⋮ XML with data values: Typechecking revisited. ⋮ Sahlqvist theorem for modal fixed point logic ⋮ Zero-one \(k\)-law ⋮ On the Descriptive Complexity of Linear Algebra ⋮ Subtournaments isomorphic to \(W_5\) in a indecomposable tournament ⋮ On the computation of zone and double zone diagrams ⋮ Ontology-Mediated Query Answering with Data-Tractable Description Logics ⋮ Positive existential definability of parallelism in terms of betweenness in Archimedean ordered affine geometry ⋮ On the locality of arb-invariant first-order formulas with modulo counting quantifiers ⋮ Tarski’s Influence on Computer Science ⋮ Digraph width measures in parameterized algorithmics ⋮ The Descriptive Complexity of Parity Games ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC! ⋮ A characterization of definability of second-order generalized quantifiers with applications to non-definability ⋮ Approximations of Mappings ⋮ Decomposable graphs and definitions with no quantifier alternation ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ Typical automorphism groups of finite nonrigid structures ⋮ The complexity of higher-order queries ⋮ Circle graphs and monadic second-order logic ⋮ The descriptive complexity of decision problems through logics with relational fixed-point and capturing results ⋮ Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory ⋮ Logical limit laws for minor-closed classes of graphs ⋮ SOME MODEL THEORY OF GUARDED NEGATION ⋮ First-order and monadic properties of highly sparse random graphs ⋮ The complexity of counting quantifiers on equality languages ⋮ Computable Queries for Object Oriented Databases ⋮ Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs ⋮ Relative expressive power of navigational querying on graphs ⋮ Ehrenfeucht-Fraïssé games in finite set theory ⋮ The axiomatics of ordered geometry: I. Ordered incidence spaces ⋮ Comparing the succinctness of monadic query languages over finite trees ⋮ Finding Reductions Automatically ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Structural properties of XPath fragments ⋮ Homomorphism preservation on quasi-wide classes

This page was built for publication: