Complexity Classifications via Algebraic Logic

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

6 Downloads (Pure)

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.

Original languageEnglish
Title of host publication31st EACSL Annual Conference on Computer Science Logic, CSL 2023
EditorsBartek Klin, Elaine Pimentel
Number of pages18
ISBN (Electronic)9783959772648
DOIs
Publication statusPublished - 1 Feb 2023
Publication typeA4 Article in conference proceedings
EventAnnual Conference on Computer Science Logic - Warsaw, Poland
Duration: 13 Feb 202316 Feb 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume252
ISSN (Print)1868-8969

Conference

ConferenceAnnual Conference on Computer Science Logic
Country/TerritoryPoland
CityWarsaw
Period13/02/2316/02/23

Keywords

  • algebraic logic
  • complexity
  • Decidability
  • fragments of first-order logic

Publication forum classification

  • Publication forum level 1

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Complexity Classifications via Algebraic Logic'. Together they form a unique fingerprint.

Cite this