scientific article; zbMATH DE number 979011

zbMATH Open0869.03018MaRDI QIDQ4332930FDOQ4332930

Authors: Martin Otto 

Publication date: 18 February 1997

Title of this publication is not available (Why is that?)

Recommendations

• The expressive power of fixed-point logic with counting
• Finite Variable Logics in Descriptive Complexity Theory
• Bounded variable logics: Two, three, and more
• scientific article; zbMATH DE number 803291
• Elements of finite model theory.

zbMATH Keywords

finite model theorycountingPTIME canonizationEhrenfeucht-Fraïssé gamesLindström quantifiersbounded variable infinitary logiccanonization problemfixed point logics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other infinitary logic (03C75) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (43)

• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Lower bounds for invariant queries in logics with counting.
• The Computational Complexity of Quantified Reciprocals
• On the expressive power of linear algebra on graphs
• Inapproximability of unique games in fixed-point logic with counting
• Title not available (Why is that?)
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• Is polynomial time choiceless?
• Adding for-loops to first-order logic
• Canonization for two variables and puzzles on the square
• On polynomial time computation over unordered structures
• Constraint satisfaction with counting quantifiers
• On the power of built-in relations in certain classes of program schemes
• Symbioses between mathematical logic and computer science
• Fifty years of the spectrum problem: survey and new results
• Rank logic is dead, long live rank logic!
• Super/rosy \(L^k\)-theories and classes of finite structures
• Consistency for counting quantifiers
• On symmetric circuits and fixed-point logics
• Large finite structures with few \(L^k\)-types
• Constraint satisfaction, graph isomorphism, and the pebbling comonad
• On matrices and \(K\)-relations
• On the Descriptive Complexity of Linear Algebra
• Undecidability results on two-variable logics
• INTERLEAVING LOGIC AND COUNTING
• Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
• Canonisation and Definability for Graphs of Bounded Rank Width
• The Complexity of Counting Quantifiers on Equality Languages
• Modal and guarded characterisation theorems over finite transition systems
• CFI Construction and Balanced Graphs
• Regular graphs and the spectra of two-variable logic with counting
• Metafinite model theory
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• From a zoo to a zoology: Towards a general theory of graph polynomials
• PEBBLE GAMES AND LINEAR EQUATIONS
• Semantic restrictions over second-order logic
• On Preservation Theorems for Two-Variable Logic
• Logics of finite Hankel rank
• The complexity of counting quantifiers on equality languages
• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• Approximations of isomorphism and logics with linear-algebraic operators
• On the expressive power of linear algebra on graphs
• The Relational Polynomial-Time Hierarchy and Second-Order Logic

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4332930)