Symmetric circuits for rank logic

DOI10.4230/LIPICS.CSL.2018.20MaRDI QIDQ5079744FDO

Authors Anuj Dawar, Gregory Wilsenach

Publication date 28 May 2022

Full work available at URL https://arxiv.org/abs/1804.02939

zbMATH Keywords

circuitscircuit characterizationfixed-point logic with ranksymmetric circuitsuniform families of circuitscircuit frameworkfinite model theory, descriptive complexity

Mathematics Subject Classification ID

Logic in computer science (03B70)

Recommendations

• Symmetric Circuits for Rank Logic
• Rank logic is dead, long live rank logic!
• Rank logic is dead, long live rank logic!
• scientific article
• On symmetric circuits and fixed-point logics

Cites work

• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1086678 (Why is no real title available?)
• Definability by constant-depth polynomial-size circuits
• Definability of linear equation systems over groups and rings
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Elements of finite model theory.
• Logical hierarchies in PTIME
• On Symmetric and Choiceless Computation
• On symmetric circuits and fixed-point logics
• Rank logic is dead, long live rank logic!
• Relational queries computable in polynomial time

Cited in

(2)

• On symmetric circuits and fixed-point logics
• scientific article; zbMATH DE number 6691390 (Why is no real title available?)

This page was built for publication: Symmetric circuits for rank logic

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