5 papers
Deciding characteristic formulae: A journey in the branching-time spectrum
Luca Aceto, Antonis Achilleos, Aggeliki Chalki +1
Characteristic formulae give a complete logical description of the behaviour of processes modulo some chosen notion of behavioural semantics. They allow one to reduce equivalence o…
The complexity of deciding characteristic formulae in van Glabbeek's branching-time spectrum
Luca Aceto, Antonis Achilleos, Aggeliki Chalki +1
Characteristic formulae give a complete logical description of the behaviour of processes modulo some chosen notion of behavioural semantics. They allow one to reduce equivalence o…
On the power of counting the total number of computation paths of NPTMs
Eleni Bakali, Aggeliki Chalki, Sotiris Kanellopoulos +2
In this paper, we define and study variants of several complexity classes of decision problems that are defined via some criteria on the number of accepting paths of an NPTM. In th…
Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes
Antonis Achilleos, Aggeliki Chalki
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 co…
Characterizations and approximability of hard counting classes below #P
Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis
An important objective of research in counting complexity is to understand which counting problems are approximable. In this quest, the complexity class TotP, a hard subclass of #P…