License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.31
URN: urn:nbn:de:0030-drops-109758
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10975/
Go to the corresponding LIPIcs Volume Portal

Grädel, Erich ; Schalthöfer, Svenja

Choiceless Logarithmic Space

pdf-format:
LIPIcs-MFCS-2019-31.pdf (0.5 MB)

Abstract

One of the most important open problems in finite model theory is the question whether there is a logic characterising efficient computation. While this question usually concerns Ptime, it can also be applied to other complexity classes, and in particular to Logspace which can be seen as a formalisation of efficient computation for big data. One of the strongest candidates for a logic capturing Ptime is Choiceless Polynomial Time (CPT). It is based on the idea of choiceless algorithms, a general model of symmetric computation over abstract structures (rather than their encodings by finite strings). However, there is currently neither a comparably strong candidate for a logic for Logspace, nor a logic transferring the idea of choiceless computation to Logspace.
We propose here a notion of Choiceless Logarithmic Space which overcomes some of the obstacles posed by Logspace as a less robust complexity class. The resulting logic is contained in both Logspace and CPT, and is strictly more expressive than all logics for Logspace that have been known so far. Further, we address the question whether this logic can define all Logspace-queries, and prove that this is not the case.

BibTeX - Entry

@InProceedings{grdel_et_al:LIPIcs:2019:10975,
  author =	{Erich Gr{\"a}del and Svenja Schalth{\"o}fer},
  title =	{{Choiceless Logarithmic Space}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10975},
  URN =		{urn:nbn:de:0030-drops-109758},
  doi =		{10.4230/LIPIcs.MFCS.2019.31},
  annote =	{Keywords: Finite Model Theory, Logics for Logspace, Choiceless Computation}
}

Keywords: Finite Model Theory, Logics for Logspace, Choiceless Computation
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

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