TY - GEN
T1 - Counting Computations with Formulae
T2 - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023
AU - Chalki, Aggeliki
N1 - Publisher Copyright: © Antonis Achilleos and Aggeliki Chalki;
PY - 2023/8/21
Y1 - 2023/8/21
N2 - We present quantitative logics with two-step semantics based on the framework of quantitative logics introduced by Arenas et al. (2020) and the two-step semantics defined in the context of weighted logics by Gastin & Monmege (2018). We show that some of the fragments of our logics augmented with a least fixed point operator capture interesting classes of counting problems. Specifically, we answer an open question in the area of descriptive complexity of counting problems by providing logical characterisations of two subclasses of #P, namely SpanL and TotP, that play a significant role in the study of approximable counting problems. Moreover, we define logics that capture FPSPACE and SpanPSPACE, which are counting versions of PSPACE.
AB - We present quantitative logics with two-step semantics based on the framework of quantitative logics introduced by Arenas et al. (2020) and the two-step semantics defined in the context of weighted logics by Gastin & Monmege (2018). We show that some of the fragments of our logics augmented with a least fixed point operator capture interesting classes of counting problems. Specifically, we answer an open question in the area of descriptive complexity of counting problems by providing logical characterisations of two subclasses of #P, namely SpanL and TotP, that play a significant role in the study of approximable counting problems. Moreover, we define logics that capture FPSPACE and SpanPSPACE, which are counting versions of PSPACE.
KW - #P
KW - counting problems
KW - descriptive complexity
KW - quantitative logics
UR - https://www.scopus.com/pages/publications/85171465538
UR - https://iris.ru.is/ws/files/217825265/LIPIcs.MFCS.2023.7.pdf
U2 - 10.4230/LIPIcs.MFCS.2023.7
DO - 10.4230/LIPIcs.MFCS.2023.7
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023
A2 - Leroux, Jerome
A2 - Lombardy, Sylvain
A2 - Peleg, David
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 28 August 2023 through 1 September 2023
ER -