Rank logic is dead, long live rank logic!

DOI10.1017/JSL.2018.33zbMATH Open1425.68134OpenAlexW2922213978MaRDI QIDQ4628673FDOQ4628673

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/

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

zbMATH Keywords

finite model theorygroup actiondescriptive complexityfixed-point logic with countingrank logicsolvability operator

Mathematics Subject Classification ID

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

Cites Work

• On the Hardness of Graph Isomorphism
• Title not available (Why is that?)
• An optimal lower bound on the number of variables for graph identification
• Finite model theory and its applications.
• Title not available (Why is that?)
• Affine systems of equations and counting infinitary logic
• A note on closure properties of logspace MOD classes
• Title not available (Why is that?)
• On finite rigid structures
• Pebble games with algebraic rules
• Definability of linear equation systems over groups and rings
• Choiceless polynomial time on structures with small abelian colour classes
• Title not available (Why is that?)

Cited In (5)

• On the descriptive complexity of temporal constraint satisfaction problems
• Rank logic is dead, long live rank logic!
• Game comonads \& generalised quantifiers
• Choiceless Logarithmic Space
• Symmetric Circuits for Rank Logic

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)