scientific article; zbMATH DE number 979011
bounded variable infinitary logiccanonization problemcountingEhrenfeucht-Fraïssé gamesfinite model theoryfixed point logicsLindström quantifiersPTIME canonization
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Model theory of finite structures (03C13) Other infinitary logic (03C75) Logic with extra quantifiers and operators (03C80) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)
- 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
- Bounded variable logics: Two, three, and more
- Canonization for two variables and puzzles on the square
- Metafinite model theory
- Program schemes, arrays, Lindström quantifiers and zero-one laws
- Lower bounds for invariant queries in logics with counting.
- Adding for-loops to first-order logic
- Modal and guarded characterisation theorems over finite transition systems
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- On the expressive power of linear algebra on graphs
- On symmetric circuits and fixed-point logics
- Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
- Large finite structures with few \(L^k\)-types
- Symbioses between mathematical logic and computer science
- Is polynomial time choiceless?
- Logics of finite Hankel rank
- The Complexity of Counting Quantifiers on Equality Languages
- PEBBLE GAMES AND LINEAR EQUATIONS
- Semantic restrictions over second-order logic
- On the Descriptive Complexity of Linear Algebra
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- The Computational Complexity of Quantified Reciprocals
- Super/rosy L^k-theories and classes of finite structures
- On Preservation Theorems for Two-Variable Logic
- Rank logic is dead, long live rank logic!
- On polynomial time computation over unordered structures
- Fifty years of the spectrum problem: survey and new results
- Consistency for counting quantifiers
- Undecidability results on two-variable logics
- On the expressive power of linear algebra on graphs
- Approximations of isomorphism and logics with linear-algebraic operators
- scientific article; zbMATH DE number 7561610 (Why is no real title available?)
- The complexity of counting quantifiers on equality languages
- Constraint satisfaction with counting quantifiers
- Regular graphs and the spectra of two-variable logic with counting
- CFI Construction and Balanced Graphs
- The Relational Polynomial-Time Hierarchy and Second-Order Logic
- Canonisation and Definability for Graphs of Bounded Rank Width
- On matrices and K-relations
- Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
- INTERLEAVING LOGIC AND COUNTING
- Inapproximability of unique games in fixed-point logic with counting
- Constraint satisfaction, graph isomorphism, and the pebbling comonad
- Canonization for bounded and dihedral color classes in choiceless polynomial time
- Are targeted messages more effective?
- Separating rank logic from polynomial time
- Linear algebraic quantifiers
- Symmetric proofs in the ideal proof system
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)
