DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2017.26

Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs

Authors: Berit Grußien

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Abstract

We show that the class of chordal claw-free graphs admits LREC=-definable canonization. LREC= is a logic that extends first-order logic with counting by an operator that allows it to formalize a limited form of recursion. This operator can be evaluated in logarithmic space. It follows that there exists a logarithmic-space canonization algorithm for the class of chordal claw-free graphs, and that LREC= captures logarithmic space on this graph class. Since LREC= is contained in fixed-point logic with counting, we also obtain that fixed-point logic with counting captures polynomial time on the class of chordal claw-free graphs.

Cite as

Berit Grußien. Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gruien:LIPIcs.CSL.2017.26,
  author =	{Gru{\ss}ien, Berit},
  title =	{{Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.26},
  URN =		{urn:nbn:de:0030-drops-76900},
  doi =		{10.4230/LIPIcs.CSL.2017.26},
  annote =	{Keywords: Descriptive complexity, logarithmic space, polynomial time, chordal claw-free graphs}
}

Document

DOI: 10.4230/LIPIcs.CSL.2011.277

L-Recursion and a new Logic for Logarithmic Space

Authors: Martin Grohe, Berit Grußien, André Hernich, and Bastian Laubner

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

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.

Cite as

Martin Grohe, Berit Grußien, André Hernich, and Bastian Laubner. L-Recursion and a new Logic for Logarithmic Space. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 277-291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.CSL.2011.277,
  author =	{Grohe, Martin and Gru{\ss}ien, Berit and Hernich, Andr\'{e} and Laubner, Bastian},
  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 =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.277},
  URN =		{urn:nbn:de:0030-drops-32373},
  doi =		{10.4230/LIPIcs.CSL.2011.277},
  annote =	{Keywords: descriptive complexity, logarithmic space, fixed-point logics}
}

Search Results

Documents authored by Grußien, Berit

Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs

Abstract

Cite as

L-Recursion and a new Logic for Logarithmic Space

Abstract

Cite as

Thanks for your feedback!

Could not send message