@inproceedings{6770303a7bae4b6aa7b2f6898067ba22,
title = "Complexity Classifications via Algebraic Logic",
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.",
keywords = "algebraic logic, complexity, Decidability, fragments of first-order logic",
author = "Reijo Jaakkola and Antti Kuusisto",
note = "Funding Information: Funding The authors were funded by the Academy of Finland project Theory of computational logics, grant numbers 324435, 328987 (to December 2021) and 352419, 352420, 353027 (2022 onwards). Reijo Jaakkola: Academy of Finland project Theory of Computational Logics, grant 328987 Antti Kuusisto: Academy of Finland project Theory of Computational Logics, grants 324435, 328987, 352419, 352420, 353027 Publisher Copyright: {\textcopyright} Reijo Jaakkola and Antti Kuusisto; licensed under Creative Commons License CC-BY 4.0.; Annual Conference on Computer Science Logic ; Conference date: 13-02-2023 Through 16-02-2023",
year = "2023",
month = feb,
day = "1",
doi = "10.4230/LIPIcs.CSL.2023.27",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
editor = "Bartek Klin and Elaine Pimentel",
booktitle = "31st EACSL Annual Conference on Computer Science Logic, CSL 2023",
}