Abstract
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.
| Original language | English |
|---|---|
| Title of host publication | 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023 |
| Editors | Jerome Leroux, Sylvain Lombardy, David Peleg |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| ISBN (Electronic) | 9783959772921 |
| DOIs | |
| Publication status | Published - 21 Aug 2023 |
| Event | 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023 - Bordeaux, France Duration: 28 Aug 2023 → 1 Sept 2023 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 272 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023 |
|---|---|
| Country/Territory | France |
| City | Bordeaux |
| Period | 28/08/23 → 1/09/23 |
Bibliographical note
Publisher Copyright:© Antonis Achilleos and Aggeliki Chalki;
Other keywords
- #P
- counting problems
- descriptive complexity
- quantitative logics