2026-07-20T05:09:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3237 2024-03-06T10:33:59Z ddc:004 open_access

L-Recursion and a new Logic for Logarithmic Space Grohe, Martin Grußien, Berit Hernich, André Laubner, Bastian descriptive complexity logarithmic space fixed-point logics 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Grohe and Berit Grußien and André Hernich and Bastian Laubner 2011 Is Part Of LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2011.277 urn:nbn:de:0030-drops-32373 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.277 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode