scientific article; zbMATH DE number 979011

zbMath0869.03018MaRDI QIDQ4332930

Martin Otto

Publication date: 18 February 1997

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

zbMATH Keywords

countingfinite model theoryEhrenfeucht-Fraïssé gamesLindström quantifiersPTIME canonizationbounded 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) Complexity of computation (including implicit computational complexity) (03D15) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other infinitary logic (03C75)

Related Items (40)

On symmetric circuits and fixed-point logics ⋮ On Preservation Theorems for Two-Variable Logic ⋮ Modal and guarded characterisation theorems over finite transition systems ⋮ PEBBLE GAMES AND LINEAR EQUATIONS ⋮ Symbioses between mathematical logic and computer science ⋮ Semantic Restrictions over Second-Order Logic ⋮ The Complexity of Counting Quantifiers on Equality Languages ⋮ Canonization for two variables and puzzles on the square ⋮ CFI Construction and Balanced Graphs ⋮ Metafinite model theory ⋮ Super/rosy \(L^k\)-theories and classes of finite structures ⋮ Is Polynomial Time Choiceless? ⋮ Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem ⋮ On the Descriptive Complexity of Linear Algebra ⋮ Unnamed Item ⋮ INTERLEAVING LOGIC AND COUNTING ⋮ Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus ⋮ RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC! ⋮ Fifty years of the spectrum problem: survey and new results ⋮ The complexity of counting quantifiers on equality languages ⋮ Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Undecidability results on two-variable logics ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Large finite structures with few \(L^k\)-types ⋮ On the expressive power of linear algebra on graphs ⋮ On matrices and \(K\)-relations ⋮ The Computational Complexity of Quantified Reciprocals ⋮ From a zoo to a zoology: Towards a general theory of graph polynomials ⋮ On the power of built-in relations in certain classes of program schemes ⋮ The Relational Polynomial-Time Hierarchy and Second-Order Logic ⋮ Lower bounds for invariant queries in logics with counting. ⋮ Adding for-loops to first-order logic ⋮ Regular Graphs and the Spectra of Two-Variable Logic with Counting ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws ⋮ Canonisation and Definability for Graphs of Bounded Rank Width ⋮ On polynomial time computation over unordered structures

This page was built for publication: