scientific article; zbMATH DE number 979011
finite model theorycountingPTIME canonizationEhrenfeucht-Fraïssé gamesLindström quantifiersbounded variable infinitary logiccanonization problemfixed point logics
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)
- On the expressive power of linear algebra on graphs
- The Relational Polynomial-Time Hierarchy and Second-Order Logic
- 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
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- scientific article; zbMATH DE number 7561610 (Why is no real title available?)
- 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
- The Complexity of Counting Quantifiers on Equality Languages
- Modal and guarded characterisation theorems over finite transition systems
- Canonisation and Definability for Graphs of Bounded Rank Width
- CFI Construction and Balanced Graphs
- Metafinite model theory
- Regular graphs and the spectra of two-variable logic with counting
- 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
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)
