L-Recursion and a new Logic for Logarithmic Space

Martin Grohe, Berit Grußien, André Hernich +1

We extend first-order logic with counting by a new operator that allows it to formalise a limited form of recursion which can be evaluated in logarithmic space. The resulting logic…