Martin Grohe ; Berit Grußien ; André Hernich ; Bastian Laubner - L-Recursion and a new Logic for Logarithmic Space

lmcs:938 - Logical Methods in Computer Science, March 13, 2013, Volume 9, Issue 1 - https://doi.org/10.2168/LMCS-9(1:11)2013
L-Recursion and a new Logic for Logarithmic SpaceArticle

Authors: Martin Grohe ORCID; Berit Grußien ; André Hernich ; Bastian Laubner

    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 LREC has a data complexity in LOGSPACE, and it defines LOGSPACE-complete problems like deterministic reachability and Boolean formula evaluation. We prove that LREC is strictly more expressive than deterministic transitive closure logic with counting and incomparable in expressive power with symmetric transitive closure logic STC and transitive closure logic (with or without counting). LREC is strictly contained in fixed-point logic with counting FPC. We also study an extension LREC= of LREC that has nicer closure properties and is more expressive than both LREC and STC, but is still contained in FPC and has a data complexity in LOGSPACE. Our main results are that LREC captures LOGSPACE on the class of directed trees and that LREC= captures LOGSPACE on the class of interval graphs.


    Volume: Volume 9, Issue 1
    Published on: March 13, 2013
    Imported on: March 7, 2012
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1211 times.
    This article's PDF has been downloaded 283 times.