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.

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.

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.

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.

Current classical planners are very successful in finding (nonoptimal) plans, even for large planning instances. To do so, most planners rely on a preprocessing stage that computes a grounded representation of the task. Whenever the grounded task is too big to be generated (i.e., whenever this preprocess fails) the instance cannot even be tackled by the actual planner. To address this issue, we introduce a partial grounding approach that grounds only a projection of the task, when complete grounding is not feasible. We propose a guiding mechanism that, for a given domain, identifies the parts of a task that are relevant to find a plan by using off-the-shelf machine learning methods. Our empirical evaluation attests that the approach is capable of solving planning instances that are too big to be fully grounded.

In this paper we introduce a prioritized default logic. We build this logic modularly from Standard Deontic Logic by the addition of default rules and priorities among them. Our main aim is to provide a logical framework to reason about scenarios where prescriptive and descriptive statements coexist and may be incomplete and contradictory. We motivate and illustrate the technical elements of our work with the use of examples (classical, and coming from software engineering). In addition, we present sound, complete, and terminating (with loop check) tableau-based proof calculi for credulous and sceptical reasoning in our logic.

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.

Let F = F, R be a finite Kripke frame.A congruence of F is a bisimulation of F that is also an equivalence relation on F. The set of all congruences of F is a lattice under the inclusion ordering.In this article we investigate this lattice in the case that F is a finite line frame.We give concrete descriptions of the join and meet of two congruences with a nontrivial upper bound.Through these descriptions we show that for every nontrivial congruence ρ, the interval [Id F , ρ] embeds into the lattice of divisors of a suitable positive integer.We also prove that any two congruences with a nontrivial upper bound permute.

We investigate model theoretic properties of XPath with data (in)equality tests over the class of data trees, i.e., the class of trees where each node contains a label from a finite alphabet and a data value from an infinite domain. We provide notions of (bi)simulations for XPpath logics containing the child, parent, ancestor and descendant axes to navigate the tree. We show that these notions precisely characterize the equivalence relation associated with each logic. We study formula complexity measures consisting of the number of nested axes and nested subformulas in a formula; these notions are akin to the notion of quantifier rank in first-order logic. We show characterization results for fine grained notions of equivalence and (bi)simulation that take into account these complexity measures. We also prove that positive fragments of these logics correspond to the formulas preserved under (non-symmetric) simulations. We show that the logic including the child axis is equivalent to the fragment of first-order logic invariant under the corresponding notion of bisimulation. If upward navigation is allowed the characterization fails but a weaker result can still be established. These results hold both over the class of possibly infinite data trees and over the class of finite data trees. Besides their intrinsic theoretical value, we argue that bi-simulations are useful tools to prove (non)expressivity results for the logics studied here, and we substantiate this claim with examples.

International audience

Many description logics (DLs) combine knowledge representation on an abstract, logical level with an interface to 'concrete' domains like numbers and strings with built-in predicates such as >, +, and prefix-of. These hybrid DLs have turned out to be useful in several application areas, such as reasoning about conceptual database models. We propose to further extend such DLs with key constraints that allow the expression of statements like 'US citizens are uniquely identified by their social security number'. Based on this idea, we introduce a number of natural description logics and perform a detailed analysis of their decidability and computational complexity. It turns out that naive extensions with key constraints easily lead to undecidability, whereas more careful extensions yield NExpTime-complete DLs for a variety of useful concrete domains.

Abstract Hybrid languages are expansions of propositional modal languages which can refer to (or even quantify over) worlds. The use of strong hybrid languages dates back to at least [Pri67], but recent work (for example [BS98, BT98a, BT99]) has focussed on a more constrained system called H(↓, @). We show in detail that (↓, @) is modally natural. We begin by studying its expressivity, and provide model theoretic characterizations (via a restricted notion of Ehrenfeucht-Fraïssé game, and an enriched notion of bisimulation) and a syntactic characterization (in terms of bounded formulas). The key result to emerge is that (↓, @) corresponds to the fragment of first-order logic which is invariant for generated submodels. We then show that (↓, @) enjoys (strong) interpolation, provide counterexamples for its finite variable fragments, and show that weak interpolation holds for the sublanguage (@). Finally, we provide complexity results for (@) and other fragments and variants, and sharpen known undecidability results for (↓, @).

1 ILLC, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands. E-mail: [email protected] 2 INRIA, Lorraine, 615, rue du Jardin Botanique, 54602 Villers lès Nancy Cedex, France. E-mail: [email protected]

We provide a resolution‐based proof procedure for modal, description and hybrid logic that improves on previous proposals in important ways. It avoids translations into large undecidable logics, and works directly on modal, description or hybrid logic formulas instead. In addition, by using the hybrid machinery it avoids the complexities of earlier propositional resolution‐based methods for modal logic. It combines ideas from the method of prefixes used in tableaux, and resolution ideas in such a way that some of the heuristics and optimizations devised in either field are applicable.

We present a formal model for the specification of telephone features by means of description logics. Our framework permits the formal definition of the basic telephone system as well as the specification of additional features (call waiting, call forwarding, etc.). Furthermore, by using standard reasoning tasks from description logics, the properties of features can be formally proved and interactions detected. An EXPTIME upper bound for the complexity of detecting feature interaction as a satisfiability problem is provided by exploiting well-known results for expressive description languages.