Bisimulation is a crucial tool for investigating and understanding the semantic properties of labeled transition systems (LTSs) and relational models in general. In particular, it plays a fundamental role in characterizing model equivalence with respect to a given logical language and in guiding the construction of minimal models. In this paper, we study bisimulation in the context of a logic for expressing knowing-how assertions, which are related to an agent's ability to achieve a given goal. We begin by revisiting an existing notion of bisimulation for this logic and reformulating it using purely semantic clauses. We then establish adequacy results for this new notion. Next, we provide a computational analysis of the problem of checking whether two models are bisimilar. In particular, we show that this problem is PSPACE-complete. We also investigate two approaches to model minimization in this setting, each exhibiting different computational properties. Along the way, our systematic study of bisimulation yields additional by-product results, w.r.t., for example, the complexity of the definability problem for this logic.

We present AKR , a model checking tool for an adaptative probabilistic knowing-how epistemic logic. The tool takes as input the specification of a scenario modeled via a probabilistic LTS (in PRISM notation), a collection of regular expressions acting as agent’s perception, a knowing-how property, and checks whether the formula holds in the model under the given perception. The tool combines automata-based techniques with calls to the PRISM tool to compute the result. AKR is a publicly available, open-source tool entirely programmed in Python . We describe the tool’s architecture and illustrate its use via some examples.

We introduce a probabilistic version of knowing-how modal logics. More precisely, our logics extend extant approaches to model the ability of an agent to achieve a given goal with a certain probability. On the semantic side, we enrich the models of the logic with probability distributions over the agent's actions. Then, we investigate different languages to describe such structures. First, we consider a probabilistic version of the linear plan-based logic of knowing how, and discuss its properties. Then, we consider indistinguishability classes, and obtain two logics, one that has `non-adaptative' plans, and another with `adaptative' plans. In all cases we investigate the computational complexity of their model-checking problem, obtaining undecidability results for the first and the second logic, while for the last one the problem is decidable in polynomial time. We also explore the semantics of the new logics under non-probabilistic models to compare them to the original non-probabilistic ones.

We introduce linear-time temporal logics with past operators featuring a simple assignment modality that performs local changes on the models. Such structures are infinite sequences of valuations interpreting variables by elements from a possibly infinite data domain. We study several fragments as well as the case with the Boolean domain, for which we establish that it is actually as expressive as first-order logic over infinite sequences of propositional valuations. For the logics over concrete domains N, Z and Q equipped with the respective linear ordering and equality tests, we show the satisfiability problem is decidable, and that the logics are as expressive as the version without the assignment operator. Interestingly, this entails such assignments provide a huge concise ness, which is then helpful for succinct specifications.

Labelled tableaux have been a traditional approach to define satisfiability checking procedures for Modal Logics. In many cases, they can also be used to obtain tight complexity bounds and lead to efficient implementations of reasoning tools. More recently, it has been shown that the expressive power provided by the operators characterizing Hybrid Logics (nominals and satisfiability modalities) can be used to internalize labels, leading to well-behaved inference procedures for fairly expressive logics. The resulting procedures are attractive because they do not use external mechanisms outside the language of the logic at hand, and have good logical and computational properties. Many tableau systems based on Hybrid Logic have been investigated, with more recent efforts concentrating on Modal Logics that support data comparison operators. Here, we introduce an internalized tableau calculus for XPath, arguably one of the most prominent approaches for querying semistructured data. More precisely, we define data-aware tableaux for XPath featuring data comparison operators and enriched with nominals and the satisfiability modalities from Hybrid Logic. We prove that the calculus is sound, complete and terminating. Moreover, we show that tableaux can be explored in polynomial space, therefore establishing that the satisfiability problem for the logic is PSpace-complete. Finally, we explore different extensions of the calculus, in particular how to handle data trees and other frame classes.

Abstract We introduce a novel semantics for a multi-agent epistemic operator of knowing how, based on an indistinguishability relation between plans. Our proposal is, arguably, closer to the standard presentation of knowing that modalities in classical epistemic logic. We study the relationship between this new semantics and previous approaches, showing that our setting is general enough to capture them. We also study the logical properties of the new semantics. First, we define a sound and complete axiomatization. Second, we define a suitable notion of bisimulation and prove correspondence theorems. Finally, we investigate the computational complexity of the model checking and satisfiability problems for the new logic.

We investigate the complexity of the model-checking problem for a family of modal logics capturing the notion of “knowing how”. We consider the most standard ability-based knowing how logic, for which we show that model-checking is PSpace-complete. By contrast, a multi-agent variant based on an uncertainty relation between plans in which uncertainty is encoded by a regular language, is shown to admit a PTime model-checking problem. We extend with budgets the above-mentioned ability-logics, as done for ATL-like logics. We show that for the former logic enriched with budgets, the complexity increases to at least ExpSpace-hardness, whereas for the latter, the PTime bound is preserved. Other variant logics are discussed along the paper.

Abstract We report on an implementation of a tableaux calculus for sceptical consequence in Default Logic built on Hybrid Modal Logic. In turn, our tool offers support for checking default consequence over formulas from Propositional Logic, Basic Modal Logic and Hybrid Logic. We develop a test suite for assessing the correctness, scalability, and efficiency of our system, and inform on the results. Interestingly, our method can be adapted to generate examples for other default provers.

Abstract Default Logics are a family of non-monotonic formalisms having so-called defaults and extensions as their common foundation. Traditionally, default logics have been defined and dealt with via syntactic notions of consequence in propositional or first-order logic. Here, we build default logics on modal logics. First, we present these default logics syntactically. Then, we elaborate on an algebraic counterpart. More precisely, we extend the notion of a modal algebra to accommodate for defaults and extensions. Our algebraic view of default logics concludes with an algebraic completeness result and a way of comparing default logics borrowing ideas from the concept of bisimulation in modal logic. To our knowledge, this take on default logics approach is novel. Interestingly, it also lays the groundwork for studying default logics from a dynamic logic perspective.

We study the expressivity and complexity of two modal logics interpreted on finite forests and equipped with standard modalities to reason on submodels. The logic \(\mathsf {ML} ({\color{black}{{\vert\!\!\vert\!\vert}}})\) extends the modal logic K with the composition operator \({\color{black}{{\vert\!\!\vert\!\vert}}}\) from ambient logic whereas \(\mathsf {ML} (\mathbin {\ast })\) features the separating conjunction \(\mathbin {\ast }\) from separation logic. Both operators are second-order in nature. We show that \(\mathsf {ML} ({\color{black}{{\vert\!\!\vert\!\vert}}})\) is as expressive as the graded modal logic \(\mathsf {GML}\) (on trees) whereas \(\mathsf {ML} (\mathbin {\ast })\) is strictly less expressive than \(\mathsf {GML}\) . Moreover, we establish that the satisfiability problem is Tower -complete for \(\mathsf {ML} (\mathbin {\ast })\) , whereas it is (only) AExp Pol -complete for \(\mathsf {ML} ({\color{black}{{\vert\!\!\vert\!\vert}}})\) , a result that is surprising given their relative expressivity. As by-products, we solve open problems related to sister logics such as static ambient logic and modal separation logic.

Abstract We study a family of modal logics interpreted on tree-like structures, and featuring local quantifiers $$\exists ^{k}p$$ ∃ k p that bind the proposition p to worlds that are accessible from the current one in at most k steps. We consider a first-order and a second-order semantics for the quantifiers, which enables us to relate several well-known formalisms, such as hybrid logics, $$\textsf {S5Q}$$ S 5 Q and graded modal logic. To better stress these connections, we explore fragments of our logics, called herein round-bounded fragments. Depending on whether first or second-order semantics is considered, these fragments populate the hierarchy $${2\textsc {NExp} \subset 3\textsc {NExp} \subset \cdots }$$ 2 NE X P ⊂ 3 NE X P ⊂ ⋯ or the hierarchy $${2\textsc {AExp}_{pol} \subset 3\textsc {AExp}_{pol} \subset \cdots }$$ 2 AE X P pol ⊂ 3 AE X P pol ⊂ ⋯ , respectively. For formulae up-to modal depth k, the complexity improves by one exponential.

In this paper we introduce sound and strongly complete axiomatizations for XPath with data constraints extended with hybrid operators. First, we present HXPath=, a multi-modal version of XPath with data, extended with nominals and the hybrid operator @. Then, we introduce an axiomatic system for HXPath=, and we prove it is strongly complete with respect to the class of abstract data models, i.e., data models in which data values are abstracted as equivalence relations. We prove a general completeness result similar to the one presented in, e.g., [BtC06], that ensures that certain extensions of the axiomatic system we introduce are also complete. The axiomatic systems that can be obtained in this way cover a large family of hybrid XPath languages over different classes of frames, for which we present concrete examples. In addition, we investigate axiomatizations over the class of tree models, structures widely used in practice. We show that a strongly complete, finitary, first-order axiomatization of hybrid XPath over trees does not exist, and we propose two alternatives to deal with this issue. We finally introduce filtrations to investigate the status of decidability of the satisfiability problem for these languages.

Abstract Modal separation logics are formalisms that combine modal operators to reason locally, with separating connectives that allow to perform global updates on the models. In this work, we design Hilbert-style proof systems for the modal separation logics $\text {MSL}(\ast ,\langle \neq \rangle )$ and $\text {MSL}(\ast ,\Diamond )$, where $\ast $ is the separating conjunction, $\Diamond $ is the standard modal operator and $\langle \neq \rangle $ is the difference modality. The calculi only use the logical languages at hand (no external features such as labels) and can be divided in two main parts. First, normal forms for formulae are designed and the calculi allow to transform every formula into a formula in normal form. Second, another part of the calculi is dedicated to the axiomatization for formulae in normal form, which may still require non-trivial developments but is more manageable.

We study the expressivity and complexity of two modal logics interpreted on finite forests and equipped with standard modalities to reason on submodels. The logic ML(|) extends the modal logic K with the composition operator | from ambient logic, whereas ML(*) features the separating conjunction * from separation logic. Both operators are second-order in nature. We show that ML(|) is as expressive as the graded modal logic GML (on trees) whereas ML(*) is strictly less expressive than GML. Moreover, we establish that the satisfiability problem is Tower-complete for ML(*), whereas it is (only) AExpPol-complete for ML(|), a result which is surprising given their relative expressivity. As by-products, we solve open problems related to sister logics such as static ambient logic and modal separation logic.

Abstract We introduce a modal separation logic MSL whose models are memory states from separation logic and the logical connectives include modal operators as well as separating conjunction and implication from separation logic. With such a combination of operators, some fragments of MSL can be seen as genuine modal logics whereas some others capture standard separation logics, leading to an original language to speak about memory states. We analyse the decidability status and the computational complexity of several fragments of MSL, obtaining surprising results by design of proof methods that take into account the modal and separation features of MSL. For example, the satisfiability problem for the fragment of MSL with $\Diamond $, the difference modality $\langle \neq \rangle $ and separating conjunction $\ast $ is shown Tower-complete whereas the restriction either to $\Diamond $ and $\ast $ or to $\langle \neq \rangle $ and $\ast $ is only NP-complete. We establish that the full logic MSL admits an undecidable satisfiability problem. Furthermore, we investigate variants of MSL with alternative semantics and we build bridges with interval temporal logics and with logics equipped with sabotage operators.

Relation-changing modal logics are extensions of the basic modal logic with dynamic operators that modify the accessibility relation of a model during the evaluation of a formula.These languages are equipped with dynamic modalities that are able, for example, to delete, add, and swap edges in the model, both locally and globally.We study the satisfiability problem for some of these logics.We first show that they can be translated into hybrid logic.As a result, we can transfer some results from hybrid logics to relation-changing modal logics.We discuss in particular, decidability for some fragments.We then show that satisfiability is, in general, undecidable for all the languages introduced, via translations from memory logics.

In this paper, we propose a single-agent logic of goal-directed knowing how extending the standard epistemic logic of knowing that with a new knowing how operator. The semantics of the new operator is based on the idea that knowing how to achieve phi means that there exists a (uniform) strategy such that the agent knows that it can make sure phi. We give an intuitive axiomatisation of our logic and prove the soundness, completeness, and decidability of the logic. The crucial axioms relating knowing that and knowing how illustrate our understanding of knowing how in this setting. This logic can be used in representing and reasoning about knowledge-how.