Complexity Classifications via Algebraic Logic

Tutkimustuotos: KonferenssiartikkeliScientificvertaisarvioitu

6 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
Otsikko31st EACSL Annual Conference on Computer Science Logic, CSL 2023
ToimittajatBartek Klin, Elaine Pimentel
Sivumäärä18
ISBN (elektroninen)9783959772648
DOI - pysyväislinkit
TilaJulkaistu - 1 helmik. 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaAnnual Conference on Computer Science Logic - Warsaw, Puola
Kesto: 13 helmik. 202316 helmik. 2023

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
Vuosikerta252
ISSN (painettu)1868-8969

Conference

ConferenceAnnual Conference on Computer Science Logic
Maa/AluePuola
KaupunkiWarsaw
Ajanjakso13/02/2316/02/23

Julkaisufoorumi-taso

  • Jufo-taso 1

!!ASJC Scopus subject areas

  • Software

Sormenjälki

Sukella tutkimusaiheisiin 'Complexity Classifications via Algebraic Logic'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä