A Logic for Conditional Local Strategic Reasoning

Journal of Logic, Language and Information - We consider systems of rational agents who act and interact in pursuit of their individual and collective objectives. We study and formalise the...     

Hierarchies of modal and temporal logics with reference pointers

We introduce and study hierarchies of extensions of the propositional modal and temporal languages with pairs of new syntactic devices: point of reference-reference pointer which enable semantic references to be made within a formula. We propose three different but equivalent semantics for the extended languages, discuss and compare their expressiveness. The languages with reference pointers are shown to have great expressive power (especially when their frugal syntax is taken into account), perspicuous semantics, and simple deductive systems. For instance, Kamp's and Stavi's temporal operators, as well as nominals (names, clock variables), are definable in them. Universal validity in these languages is proved undecidable. The basic modal and temporal logics with reference pointers are uniformly axiomatized and a strong completeness theorem is proved for them and extended to some classes of their extensions.     

State and path coalition effectivity models of concurrent multi-player games

We consider models of multi-player games where abilities of players and coalitions are defined in terms of sets of outcomes which they can effectively enforce. We extend the well-studied state effectivity models of one-step games in two different ways. On the one hand, we develop multiple state effectivity functions associated with different long-term temporal operators. On the other hand, we define and study coalitional path effectivity models where the outcomes of strategic plays are infinite paths. For both extensions we obtain representation results with respect to concrete models arising from concurrent game structures. We also apply state and path coalitional effectivity models to provide alternative, arguably more natural and elegant semantics to the alternating-time temporal logic ATL*, and discuss their technical and conceptual advantages.     

Strategic games and truly playable effectivity functions

A well-known result in the logical analysis of cooperative games states that the so-called playable effectivity functions exactly correspond to strategic games. More precisely, this result states that for every playable effectivity function E there exists a strategic game that assigns to coalitions of players exactly the same power as E, and every strategic game generates a playable effectivity function. While the latter direction of the correspondence is correct, we show that the former does not hold for a number of infinite state games. We point out where the original proof of correspondence goes wrong, and we present examples of playable effectivity functions for which no equivalent strategic game exists. Then, we characterize the class of truly playable effectivity functions, that do correspond to strategic games. Moreover, we discuss a construction that transforms any playable effectivity function into a truly playable one while preserving the power of most (but not all) coalitions. We also show that Coalition Logic (CL), a formalism used to reason about effectivity functions, is not expressive enough to distinguish between playable and truly playable effectivity functions, and we extend it to a logic that can make that distinction while still enjoying the good meta-logical properties of CL, such as finite axiomatization and decidability via finite model property.     

Metric propositional neighborhood logics on natural numbers

Interval logics formalize temporal reasoning on interval structures over linearly (or partially) ordered domains, where time intervals are the primitive ontological entities and truth of formulae is defined relative to time intervals, rather than time points. In this paper, we introduce and study Metric Propositional Neighborhood Logic (MPNL) over natural numbers. MPNL features two modalities referring, respectively, to an interval that is “met by” the current one and to an interval that “meets” the current one, plus an infinite set of length constraints, regarded as atomic propositions, to constrain the length of intervals. We argue that MPNL can be successfully used in different areas of computer science to combine qualitative and quantitative interval temporal reasoning, thus providing a viable alternative to well-established logical frameworks such as Duration Calculus. We show that MPNL is decidable in double exponential time and expressively complete with respect to a well-defined sub-fragment of the two-variable fragment ${{\rm FO}^2[\mathbb{N},=,<,s]}$ of first-order logic for linear orders with successor function, interpreted over natural numbers. Moreover, we show that MPNL can be extended in a natural way to cover full ${{\rm FO}^2[\mathbb{N},=,<,s]}$ , but, unexpectedly, the latter (and hence the former) turns out to be undecidable.     

The dark side of interval temporal logic: marking the undecidability border

Unlike the Moon, the dark side of interval temporal logics is the one we usually see: their ubiquitous undecidability. Identifying minimal undecidable interval logics is thus a natural and important issue in that research area. In this paper, we identify several new minimal undecidable logics amongst the fragments of Halpern and Shoham’s logic HS, including the logic of the overlaps relation, over the classes of all finite linear orders and all linear orders, as well as the logic of the meets and subinterval relations, over the classes of all and dense linear orders. Together with previous undecidability results, this work contributes to bringing the identification of the dark side of interval temporal logics very close to the definitive picture.