14 March 2019 in Fundamenta Informaticae
We present nine SAT-solvers and compare their efficiency for several decision and combinatorial problems: three classical NP-complete problems of the graph theory, bounded Post correspondence problem (BPCP), extended string correction problem (ESCP),
31 January 2024 in IEEE Transactions on Reliability
Expressing attack-defence trees in a multiagent setting allows for studying a new aspect of security scenarios, namely, how the number of agents and their task assignment impact the performance, e.g. , attack time, of strategies executed by opposing coalitions. Optimal scheduling of agents' actions, a nontrivial problem, is thus vital. We discuss associated caveats and propose an algorithm that synthesizes such an assignment, targeting minimal attack time and using the minimal number of agents for a given attack-defence tree. We also investigate an alternative approach for the same problem using rewriting logic, starting with a simple and elegant declarative model, whose correctness (in terms of schedule's optimality) is self-evident. We then refine this specification, inspired by the design of our specialized algorithm, to obtain an efficient system that can be used as a playground to explore various aspects of attack-defence trees. We compare the two approaches on different benchmarks.
9 February 2026 in Autonomous Agents and Multi-Agent Systems
We define extensions of \(\textbf{CTL}\) and TCTL with strategic operators, called Strategic \(\textbf{CTL}\) (SCTL) and Strategic TCTL (STCTL), respectively. For each of the above logics we give a synchronous and asynchronous semantics, i.e. STCTL is interpreted over networks of extended Timed Automata (TA) that either make synchronous moves or synchronise via joint actions. We consider several semantics regarding information: imperfect (i) and perfect (I), and recall: imperfect (r) and perfect (R). We prove that SCTL is more expressive than ATL for all semantics,and this holds for the timed versions as well. Moreover, the model checking problem for SCTL \(_{{\textbf {ir}}}\) is of the same complexity as for ATL \(_{{\textbf {ir}}}\), the model checking problem for STCTL \(_{{\textbf {iR}}}\) is of the same complexity as for TCTL, while for STCTL \(_{{\textbf {iR}}}\) it is undecidable as for ATL \(_{{\textbf {iR}}}\). The above results suggest to use SCTL \(_{{\textbf {ir}}}\) and STCTL \(_{{\textbf {ir}}}\) in practical applications. Therefore, we use the tool IMITATOR to support model checking of STCTL \(_{{\textbf {ir}}}\).
25 September 2018 in Scientific Annals of Computer Science