License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2023.27
URN: urn:nbn:de:0030-drops-174880
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17488/
Go to the corresponding LIPIcs Volume Portal

Jaakkola, Reijo ; Kuusisto, Antti

Complexity Classifications via Algebraic Logic

pdf-format:
LIPIcs-CSL-2023-27.pdf (0.8 MB)

Abstract

Complexity and decidability of logics is an active research area involving a wide range of different logical systems. We introduce an algebraic approach to complexity classifications of computational logics. Our base system GRA, or general relation algebra, is equiexpressive with first-order logic FO. It resembles cylindric algebra but employs a finite signature with only seven different operators, thus also giving a very succinct characterization of the expressive capacities of first-order logic. We provide a comprehensive classification of the decidability and complexity of the systems obtained by limiting the allowed sets of operators of GRA. We also discuss variants and extensions of GRA, and we provide algebraic characterizations of a range of well-known decidable logics.

BibTeX - Entry

@InProceedings{jaakkola_et_al:LIPIcs.CSL.2023.27,
  author =	{Jaakkola, Reijo and Kuusisto, Antti},
  title =	{{Complexity Classifications via Algebraic Logic}},
  booktitle =	{31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-264-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{252},
  editor =	{Klin, Bartek and Pimentel, Elaine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17488},
  URN =		{urn:nbn:de:0030-drops-174880},
  doi =		{10.4230/LIPIcs.CSL.2023.27},
  annote =	{Keywords: Decidability, complexity, algebraic logic, fragments of first-order logic}
}

Keywords: Decidability, complexity, algebraic logic, fragments of first-order logic
Collection: 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Issue Date: 2023
Date of publication: 01.02.2023

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