Simulating Logspace-Recursion with Logarithmic Quantifier Depth

Steffen van Bergerem, Martin Grohe, Sandra Kiefer +1

The fixed-point logic LREC= was developed by Grohe et al. (CSL 2011) in the quest for a logic to capture all problems decidable in logarithmic space. It extends FO+C, first-order l…