Choiceless Logarithmic Space

DOI10.4230/LIPICS.MFCS.2019.31OpenAlexW2970311880MaRDI QIDQ5092391FDOQ5092391

Authors: Erich Grädel, Svenja Schalthöfer 

Publication date: 21 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10975/pdf/LIPIcs-MFCS-2019-31.pdf/

Recommendations

• Is polynomial time choiceless?
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Characterising choiceless polynomial time with first-order interpretations
• Choiceless polynomial time
• scientific article

zbMATH Keywords

finite model theorychoiceless computationlogics for logspace

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Undirected connectivity in log-space
• Languages that Capture Complexity Classes
• An optimal lower bound on the number of variables for graph identification
• Finite model theory and its applications.
• Affine systems of equations and counting infinitary logic
• L-recursion and a new logic for logarithmic space
• Structure and complexity of relational queries
• Title not available (Why is that?)
• Choiceless polynomial time
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Choiceless polynomial time on structures with small abelian colour classes
• Choiceless computation and symmetry
• Is polynomial time choiceless?
• Characterising choiceless polynomial time with first-order interpretations
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Title not available (Why is that?)
• Rank logic is dead, long live rank logic!

Cited In (4)

• For completeness, sublogarithmic space is no space.
• The Sublogarithmic Alternating Space World
• Separating LREC from LFP
• Unification and Logarithmic Space

This page was built for publication: Choiceless Logarithmic Space

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