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.CSL.2015.390
URN: urn:nbn:de:0030-drops-54279
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5427/
Go to the corresponding LIPIcs Volume Portal

Grädel, Erich ; Pakusa, Wied

Rank Logic is Dead, Long Live Rank Logic!

pdf-format:
24.pdf (0.5 MB)

Abstract

Motivated by the search for a logic for polynomial time, we study rank logic (FPR) which extends fixed-point logic with counting (FPC) by operators that determine the rank of matrices over finite fields. While FPR can express most of the known queries that separate FPC from PTIME, nearly nothing was known about the limitations of its expressive power.

In our first main result we show that the extensions of FPC by rank operators over different prime fields are incomparable. This solves an open question posed by Dawar and Holm and also implies that rank logic, in its original definition with a distinct rank operator for every field, fails to capture polynomial time. In particular we show that the variant of rank logic FPR* with an operator that uniformly expresses the matrix rank over finite fields is more expressive than FPR.

One important step in our proof is to consider solvability logic FPS which is the analogous extension of FPC by quantifiers which express the solvability problem for linear equation systems over finite fields. Solvability logic can easily be embedded into rank logic, but it is open whether it is a strict fragment. In our second main result we give a partial answer to this question: in the absence of counting, rank operators are strictly more expressive than solvability quantifiers.

BibTeX - Entry

@InProceedings{grdel_et_al:LIPIcs:2015:5427,
  author =	{Erich Gr{\"a}del and Wied Pakusa},
  title =	{{Rank Logic is Dead, Long Live Rank Logic!}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{390--404},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Stephan Kreutzer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5427},
  URN =		{urn:nbn:de:0030-drops-54279},
  doi =		{10.4230/LIPIcs.CSL.2015.390},
  annote =	{Keywords: logic, descriptive complexity, polynomial time, rank logic}
}

Keywords: logic, descriptive complexity, polynomial time, rank logic
Collection: 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)
Issue Date: 2015
Date of publication: 07.09.2015

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