Antonis Achilleos
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Antonis Achilleos has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
- Adrian Francalanza
University of Malta, Msida, Malta
15 shared publications - Luca Aceto
Reykjavik University
14 shared publications - Anna Ingólfsdóttir
Reykjavik University, Reykjavik, Iceland
10 shared publications - Elli Anastasiadi
Aalborg University
6 shared publications - Karoliina Lehtinen
LIS CNRS Aix-Marseille University
5 shared publications - Duncan Paul Attard
University of Malta
3 shared publications
Latest Publications
- Open Access
- 17 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 27 (1) , 1-57
Centralized vs. Decentralized Monitors for Hyperproperties
This article focuses on the runtime verification of hyperproperties expressed in Hyper- \(\mathsf{rec}\) HML, an expressive yet simple logic for describing properties of sets of traces. To this end, we consider a simple language of monitors that observe sets of system executions and report verdicts w.r.t. a given Hyper- \(\mathsf{rec}\) HML formula. We first employ a unique omniscient monitor that centrally observes all system traces. Since centralized monitors are not ideal for distributed settings, we also provide a language for decentralized monitors, where each trace has a dedicated monitor; these monitors yield a unique verdict by communicating their observations to one another. For both the centralized and the decentralized settings, we provide a synthesis procedure that, given a formula, yields a monitor that is correct (i.e., sound and violation complete). A key step in proving the correctness of the synthesis for decentralized monitors is a result showing that, for each formula, the synthesized centralized monitor and its corresponding decentralized one are weakly bisimilar for a suitable notion of weak bisimulation.- 17 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 27 (1) , 1-57
Open AccessCentralized vs. Decentralized Monitors for Hyperproperties
This article focuses on the runtime verification of hyperproperties expressed in Hyper- \(\mathsf{rec}\) HML, an expressive yet simple logic for describing properties of sets of traces. To this end, we consider a simple language of monitors that observe sets of system executions and report verdicts w.r.t. a given Hyper- \(\mathsf{rec}\) HML formula. We first employ a unique omniscient monitor that centrally observes all system traces. Since centralized monitors are not ideal for distributed settings, we also provide a language for decentralized monitors, where each trace has a dedicated monitor; these monitors yield a unique verdict by communicating their observations to one another. For both the centralized and the decentralized settings, we provide a synthesis procedure that, given a formula, yields a monitor that is correct (i.e., sound and violation complete). A key step in proving the correctness of the synthesis for decentralized monitors is a result showing that, for each formula, the synthesized centralized monitor and its corresponding decentralized one are weakly bisimilar for a suitable notion of weak bisimulation. - Open Access
- 17 September 2025
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 428, 13-28
The Complexity of Deciding Characteristic Formulae Modulo Nested Simulation (extended abstract)
This paper studies the complexity of determining whether a formula in the modal logics characterizing the nested-simulation semantics is characteristic for some process, which is equivalent to determining whether the formula is satisfiable and prime. The main results are that the problem of determining whether a formula is prime in the modal logic characterizing the 2-nested-simulation preorder is coNP-complete and is PSPACE-complete in the case of the n-nested-simulation preorder, when n ≥ 3. This establishes that deciding characteristic formulae for the n-nested simulation semantics is PSPACE-complete, when n ≥ 3. In the case of the 2-nested simulation semantics, that problem lies in the complexity class DP, which consists of languages that can be expressed as the intersection of one language in NP and of one in coNP.
- 17 September 2025
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 428, 13-28
Open AccessThe Complexity of Deciding Characteristic Formulae Modulo Nested Simulation (extended abstract)
This paper studies the complexity of determining whether a formula in the modal logics characterizing the nested-simulation semantics is characteristic for some process, which is equivalent to determining whether the formula is satisfiable and prime. The main results are that the problem of determining whether a formula is prime in the modal logic characterizing the 2-nested-simulation preorder is coNP-complete and is PSPACE-complete in the case of the n-nested-simulation preorder, when n ≥ 3. This establishes that deciding characteristic formulae for the n-nested simulation semantics is PSPACE-complete, when n ≥ 3. In the case of the 2-nested simulation semantics, that problem lies in the complexity class DP, which consists of languages that can be expressed as the intersection of one language in NP and of one in coNP.
- Open Access
- 7 August 2024
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 20, Is
Complexity results for modal logic with recursion via translations and tableaux
This paper studies the complexity of classical modal logics and of their extension with fixed-point operators, using translations to transfer results across logics. In particular, we show several complexity results for multi-agent logics via translations to and from the $\mu$-calculus and modal logic, which allow us to transfer known upper and lower bounds. We also use these translations to introduce terminating and non-terminating tableau systems for the logics we study, based on Kozen's tableau for the $\mu$-calculus and the one of Fitting and Massacci for modal logic. Finally, we describe these tableaux with $\mu$-calculus formulas, thus reducing the satisfiability of each of these logics to the satisfiability of the $\mu$-calculus, resulting in a general 2EXP upper bound for satisfiability testing.
- 7 August 2024
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 20, Is
Open AccessComplexity results for modal logic with recursion via translations and tableaux
This paper studies the complexity of classical modal logics and of their extension with fixed-point operators, using translations to transfer results across logics. In particular, we show several complexity results for multi-agent logics via translations to and from the $\mu$-calculus and modal logic, which allow us to transfer known upper and lower bounds. We also use these translations to introduce terminating and non-terminating tableau systems for the logics we study, based on Kozen's tableau for the $\mu$-calculus and the one of Fitting and Massacci for modal logic. Finally, we describe these tableaux with $\mu$-calculus formulas, thus reducing the satisfiability of each of these logics to the satisfiability of the $\mu$-calculus, resulting in a general 2EXP upper bound for satisfiability testing.
- 27 September 2023
- Published by Elsevier in Science of Computer Programming
- Vol. 232
A monitoring tool for linear-time μHML
- 27 September 2023
- Published by Elsevier in Science of Computer Programming
- Vol. 232
A monitoring tool for linear-time μHML
- 14 June 2022
- Published by Springer Nature
- p. 181-199
A Synthesis Tool for Optimal Monitors in a Branching-Time Setting
- 14 June 2022
- Published by Springer Nature
- p. 181-199
A Synthesis Tool for Optimal Monitors in a Branching-Time Setting
- Open Access
Monitoring hyperproperties with circuits
This paper presents an extension of the safety fragment of Hennessy-Milner Logic with recursion over sets of traces, in the spirit of Hyper-LTL. It then introduces a novel monitoring setup that employs circuit-like structures to combine verdicts from regular monitors. The main contribution of this study is the monitors and their semantics themselves, as well as a monitor-synthesis procedure from formulae in the logic that yields `circuit-like monitors' of this type that are sound and violation complete over a finite set of infinite traces.
Open AccessMonitoring hyperproperties with circuits
This paper presents an extension of the safety fragment of Hennessy-Milner Logic with recursion over sets of traces, in the spirit of Hyper-LTL. It then introduces a novel monitoring setup that employs circuit-like structures to combine verdicts from regular monitors. The main contribution of this study is the monitors and their semantics themselves, as well as a monitor-synthesis procedure from formulae in the logic that yields `circuit-like monitors' of this type that are sound and violation complete over a finite set of infinite traces.
- Open Access
Axiomatizing recursion-free, regular monitors
Monitors are a key tool in the field of runtime verification, where they are used to verify system properties by analyzing execution traces generated by processes. Work on runtime monitoring carried out in a series of papers by Aceto et al.$~$has specified monitors using a variation on the regular fragment of Milner's CCS and studied two trace-based notions of equivalence over monitors, namely verdict and $\omega$-verdict equivalence. This article is devoted to the study of the equational logic of monitors modulo those two notions of equivalence. It presents complete equational axiomatizations of verdict and $\omega$-verdict equivalence for closed and open terms over recursion-free monitors. It is also shown that verdict equivalence has no finite equational axiomatization over open monitors when the set of actions is finite and contains at least two actions.
Open AccessAxiomatizing recursion-free, regular monitors
Monitors are a key tool in the field of runtime verification, where they are used to verify system properties by analyzing execution traces generated by processes. Work on runtime monitoring carried out in a series of papers by Aceto et al.$~$has specified monitors using a variation on the regular fragment of Milner's CCS and studied two trace-based notions of equivalence over monitors, namely verdict and $\omega$-verdict equivalence. This article is devoted to the study of the equational logic of monitors modulo those two notions of equivalence. It presents complete equational axiomatizations of verdict and $\omega$-verdict equivalence for closed and open terms over recursion-free monitors. It is also shown that verdict equivalence has no finite equational axiomatization over open monitors when the set of actions is finite and contains at least two actions.