Rank logic is dead, long live rank logic!

DOI10.1017/JSL.2018.33MaRDI QIDQ4628673zbMATH OpenOpenAlexFDO

Authors Erich Grädel, Wied Pakusa

Publication date 15 March 2019

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2015/5427/

zbMATH Keywords

descriptive complexityfinite model theoryfixed-point logic with countinggroup actionrank logicsolvability operator

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Descriptive complexity and finite models (68Q19)

Recommendations

• Rank logic is dead, long live rank logic!
• Symmetric Circuits for Rank Logic
• scientific article; zbMATH DE number 4008383
• Logical hierarchies in PTIME
• Infinitary logic and inductive definability over finite structures

Cites work

• A note on closure properties of logspace MOD classes
• Affine systems of equations and counting infinitary logic
• An optimal lower bound on the number of variables for graph identification
• Choiceless polynomial time on structures with small abelian colour classes
• Definability of linear equation systems over groups and rings
• Finite model theory and its applications.
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 176518 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 979011 (Why is no real title available?)
• On finite rigid structures
• On the Hardness of Graph Isomorphism

Cited in

(15)

• Symmetric Circuits for Rank Logic
• Symmetric circuits for rank logic
• Choiceless Logarithmic Space
• Rank logic is dead, long live rank logic!
• On the descriptive complexity of temporal constraint satisfaction problems
• Game comonads \& generalised quantifiers
• Game comonads \& generalised quantifiers
• Limitations of game comonads for invertible-map equivalence via homomorphism indistinguishability
• Quantifiers closed under partial polymorphisms
• Limits of symmetric computation (invited talk)
• Compressing CFI graphs and lower bounds for the Weisfeiler-Leman refinements
• Separating rank logic from polynomial time
• Linear algebraic quantifiers
• Computational complexity of the Weisfeiler-Leman dimension
• Computational complexity of the Weisfeiler-Leman dimension

This page was built for publication: Rank logic is dead, long live rank logic!

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