3 papers
cs.LO2026
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…
cs.LO2024
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…
cs.CC2024
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…