License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2011.277
URN: urn:nbn:de:0030-drops-32373
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3237/
Go to the corresponding LIPIcs Volume Portal

Grohe, Martin ; Grußien, Berit ; Hernich, André ; Laubner, Bastian

L-Recursion and a new Logic for Logarithmic Space

pdf-format:
24.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{grohe_et_al:LIPIcs:2011:3237,
  author =	{Martin Grohe and Berit Gru{\ss}ien and Andr{\'e} Hernich and Bastian Laubner},
  title =	{{L-Recursion and a new Logic for Logarithmic Space}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{277--291},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Marc Bezem},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3237},
  URN =		{urn:nbn:de:0030-drops-32373},
  doi =		{10.4230/LIPIcs.CSL.2011.277},
  annote =	{Keywords: descriptive complexity, logarithmic space, fixed-point logics}
}

Keywords: descriptive complexity, logarithmic space, fixed-point logics
Collection: Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL
Issue Date: 2011
Date of publication: 31.08.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI