In this paper, we present a prenex form theorem for a version of Independence Friendly logic, a logic with imperfect information. Lifting classical results to such logics turns out not to be straightforward, because independence conditions make the formulas sensitive to signalling phenomena. In particular, nested quantification over the same variable is shown to cause problems. For instance, renaming of bound variables may change the interpretations of a formula, there are only restricted quantifier extraction theorems, (...) and slashed connectives cannot be so easily removed. Thus we correct some claims from Hintikka [8], Caicedo & Krynicki [3] and Hodges [11]. We refine definitions, in particular the notion of equivalence, and sharpen preconditions, allowing us to restore those claims, including the prenex form theorem of Caicedo & Krynicki [3], and, as a side result, we obtain an application to Skolem forms of classical formulas. It is a known fact that a complete calculus for IF-logic is impossible, but with our results we establish several quantifier rules that form a partial calculus of equivalence for a general version of IF-logic reflecting general properties of information flow in games. (shrink)

We present a compositional semantics for first-order logic with imperfect information that is equivalent to Sevenster and Sandu’s equilibrium semantics (under which the truth value of a sentence in a finite model is equal to the minimax value of its semantic game). Our semantics is a generalization of an earlier semantics developed by the first author that was based on behavioral strategies, rather than mixed strategies.

This paper is a short survey of different languageswith imperfect information introduced in (Hintikka and Sandu 1989).The imperfect information concerns both quantifiers and connectives.At the end, I will sketch a connection between these languages and linearlogic.

© Springer-Verlag Berlin Heidelberg 2015. When reasoning about knowledge of procedures under imperfect information, the explicit representation of epistemic possibilities blows up the S5like models of standard epistemic logic. To overcome this drawback, in this paper, we propose a new logical framework based on compact models without epistemic accessibility relations for reasoning about knowledge of procedures. Inspired by the 3-valued abstraction method in model checking, we introduce hyper models which encode the imperfect procedural information. We (...) give a highly non-trivial 2-valued semantics of epistemic dynamic logic on such models while validating all the usual S5 axioms. Our approach is suitable for applications where procedural information is ‘learned’ incrementally, as demonstrated by various examples. (shrink)

We analyse the two definitions of generalized quantifiers for logics of dependence and independence that have been proposed by F. Engström, comparing them with a more general, higher order definition of team quantifier. We show that Engström’s definitions can be identified, by means of appropriate lifts, with special classes of team quantifiers. We point out that the new team quantifiers express a quantitative and a qualitative component, while Engström’s quantifiers only range over the latter. We further argue that (...) Engström’s definitions are just embeddings of the first-order generalized quantifiers into team semantics, and fail to capture an adequate notion of team-theoretical generalized quantifier, save for the special cases in which the quantifiers are applied to flat formulas. We also raise several doubts concerning the meaningfulness of the monotone/nonmonotone distinction in this context. In the appendix we develop some proof theory for Engström’s quantifiers. (shrink)

In this article we investigate the family of independence-friendly (IF) logics in the equality-free setting, concentrating on questions related to expressive power. Various natural equality-free fragments of logics in this family translate into existential second-order logic with prenex quantification of function symbols only and with the first-order parts of formulae equality-free. We study this fragment of existential second-order logic. Our principal technical result is that over finite models with a vocabulary consisting of unary relation symbols (...) only, this fragment of second-order logic is weaker in expressive power than first-order logic (with equality). Results about the fragment could turn out useful for example in the study of independence-friendly modal logics. In addition to proving results of a technical nature, we address issues related to a perspective from which IF logic is regarded as a specification framework for games, and also discuss the general significance of understanding fragments of second-order logic in investigations related to non-classical logics. (shrink)

We introduce and study a PDL-style logic for reasoning about protocols, or plans, under imperfect information. Our paper touches on a number of issues surrounding the relationship between an agent’s abilities, available choices, and information in an interactive situation. The main question we address is under what circumstances can the agent commit to a protocol or plan, and what can she achieve by doing so?

We propose a non-standard interpretation of Alternating-time Temporal Logic with imperfect information, for which no commonly accepted semantics has been proposed yet. Rather than changing the semantic structures, we generalize the usual interpretation of formulae in single states to sets of states. We also propose a new epistemic operator for ?practical? or ?constructive? knowledge, and we show that the new logic (which we call Constructive Strategic Logic) is strictly more expressive than most existing solutions, (...) while it retains the same model checking complexity. Finally, we study properties of constructive knowledge and other operators in this non-standard semantics. (shrink)

This paper refines the game theoretic analysis of conversations in Asher et al. by adding epistemic concepts to make explicit the intuitive idea that conversationalists typically conceive of conversational strategies in a situation of imperfect information. This ‘epistemic’ turn has important ramifications for linguistic analysis, and we illustrate our approach with a detailed treatment of linguistic examples.

We present a variant of ATL with incomplete information which includes the distributed knowledge operators corresponding to synchronous action and perfect recall. The cooperation modalities assume the use the distributed knowledge of coalitions and accordingly refer to perfect recall incomplete information strategies. We propose a model-checking algorithm for the logic. It is based on techniques for games with imperfect information and partially observable objectives, and involves deciding emptiness for automata on infinite trees. We (...) also propose an axiomatic system and prove its completeness for a rather expressive subset. As for the constructs left outside this completely axiomatised subset, we present axioms by which they can be defined in the subset on the class of models in which every state has finitely many successors and give a complete axiomatisation for a “flat” subset of the logic with these constructs included. (shrink)

I will show that the semantic structure of a new imperfect-information propositional logic can be described in terms of extensive forms of semantic games. I will discuss some ensuing properties of these games such as imperfect recall, informational consistency, and team playing. Finally, I will suggest a couple of applications that arise in physics, and most notably in quantum theory and quantum logics.

The papers collected in this volume exemplify some of the trends in current approaches to logic, language and computation. Written by authors with varied academic backgrounds, the contributions are intended for an interdisciplinary audience. The first part of this volume addresses issues relevant for multi-agent systems: reasoning with incomplete information, reasoning about knowledge and beliefs, and reasoning about games. Proofs as formal objects form the subject of Part II. Topics covered include: contributions on logical frameworks, linear (...) logic, and different approaches to formalized reasoning. Part III focuses on representations and formal methods in linguistic theory, addressing the areas of comparative and temporal expressions, modal subordination, and compositionality. (shrink)

We shall introduce in this paper a language whose formulas will be interpreted by games of imperfect information. Such games will be defined in the same way as the games for first-order formulas except that the players do not have complete information of the earlier course of the game. Some simple logical properties of these games will be stated together with the relation of such games of imperfect information to higher-order logic. Finally, a (...) set of applications will be outlined. (shrink)

In recent years, the trend to present the notion of imperfection as a plus rather than a problem has resonated across a range of social and creative disciplines and a wealth of world localities. As digital tools allow media users to share ever more suave selfies and success stories, psychologists promote 'the gifts of imperfections' and point to perfectionism as a catalyst for rising depression and burnout complaints and suicide rates among millennials. As sound technologies increasingly permit musicians to 'smoothen' (...) their work, composers increasingly praise glitches, noise, and cracks. As genetic engineering upgrades with swift speed, philosophers, marketeers, and physicians plea 'against perfection' and supermarkets successfully advertize 'perfectly imperfect' vegetables. Meanwhile, cultural analysts point at skewed perspectives, blurry images, and other 'deliberate imperfections' in new and historical cinema, painting, photography, music, and literature. In less positive terms, scholars in fields ranging from disability studies to tourism critically interrogate a trend to fetishize imperfection and poverty. They rightfully warn against projecting privileged (and, often, emphatically western-biased) feel-good stories onto the less privileged, the distorted, or the frail. Imperfections synthesizes the swiftly growing but fragmented critical scholarship on mistakes, glitches, and other aesthetics and logics of imperfection into the first transdisciplinary, transnational framework of imperfection studies. With this framework, the editors offer scholars and students across various disciplines tools to craft more historically grounded and critically informed conceptualizations of the imperfect. (shrink)

When seeking to coordinate in a game with imperfect information, it is often relevant for a player to know what other players know. Keeping track of the information acquired in a play of infinite duration may, however, lead to infinite hierarchies of higher-order knowledge. We present a construction that makes explicit which higher-order knowledge is relevant in a game and allows us to describe a class of games that admit coordinated winning strategies with finite memory.

We associate the semantic game with chance moves conceived by Blinov with Blamey’s partial logic. We give some equivalent alternatives to the semantic game, some of which are with a third player, borrowing the idea of introducing the pseudo-player called Nature in game theory. We observe that IF propositional logic proposed by Sandu and Pietarinen can be equivalently translated to partial logic, which implies that imperfect information may not be necessary for IF (...) propositional logic. We also indicate that some independent quantifiers can be regarded as dependent quantifiers of indeterminate sequence, using the interjunction connective in partial logic. We conclude our paper by indicating some further research in a more general setting. (shrink)

Hintikka and Sandu’s independence-friendly logic is a conservative extension of first-order logic that allows one to consider semantic games with imperfect information. In the present article, we first show how several variants of the Monty Hall problem can be modeled as semantic games for IF sentences. In the process, we extend IF logic to include semantic games with chance moves and dub this extension stochastic IF logic. Finally, we use stochastic IF (...) class='Hi'>logic to analyze the Sleeping Beauty problem, leading to the conclusion that the thirders are correct while identifying the main error in the halfers’ argument. (shrink)

We consider a simple modal logic whose nonmodal part has conjunction and disjunction as connectives and whose modalities come in adjoint pairs, but are not in general closure operators. Despite absence of negation and implication, and of axioms corresponding to the characteristic axioms of _T_, _S4_, and _S5_, such logics are useful, as shown in previous work by Baltag, Coecke, and the first author, for encoding and reasoning about information and misinformation in multiagent systems. For the propositional-only fragment (...) of such a dynamic epistemic logic, we present an algebraic semantics, using lattices with agent-indexed families of adjoint pairs of operators, and a cut-free sequent calculus. The calculus exploits operators on sequents, in the style of “nested” or “tree-sequent” calculi; cut-admissibility is shown by constructive syntactic methods. The applicability of the logic is illustrated by reasoning about the muddy children puzzle, for which the calculus is augmented with extra rules to express the facts of the muddy children scenario. (shrink)

This unique compendium presents a comprehensive and self-contained theory of material development under imperfect information and its applications. The book describes new approaches to synthesis and selection of materials with desirable characteristics. Such approaches provide the ability of systematic and computationally effective analysis in order to predict composition, structure and related properties of new materials. The volume will be a useful advanced textbook for graduate students. It is also suitable for academicians and practitioners who wish to have (...) fundamental models in new material synthesis and selection. (shrink)

A key benefit of Bayesian reasoning is that it stipulates how to optimally integrate unreliable sources of information. The authors present evidence that humans use Bayesian inference to determine how much to trust advice from another person, based on information about that person's knowledge and strategy.

numbers as in the following example ♦1,1♦1,2 2,3 5,4p We denote the set of formulas of this modal language by M L(k). For each modality type i, there will be an accessibility relation Ri. That is, an k-ary modal structure for the modal propositional language L will have the form..

The article studies preferences of agents in a setting with imperfect information. For such a setting, the authors propose a new class of preferences. It is said that an agent prefers one statement over another if, among all indistinguishable worlds, the agent prefers the worlds where the first statement is true to those where the second one is true. The main technical result is a sound and complete logical system describing the interplay between a binary modality capturing (...) preferences and the knowledge modality. The proof of completeness is using a newly proposed “tumbled pairs” technique. (shrink)

The aim of this paper1 is to provide a unified semantic analysis for three important readings of the Italian Imperfetto (and Presente): the PROGressive, the HABitual, and the FUTurate reading. To highlight the role of the utterance context in setting the relevant parameters of interpretation, explicit temporal adverbials are left out of the scene and prominence is given to the situations where the context provides the temporal information required to discriminate between alternative readings, by exploiting a single logical form. (...) The paper is organized as follows. After a short presentation of the data (sect. 1), in the second section I discuss some intuitive features of imperfectivity by focusing on the fact that the conclusion of an event or series of events is left open. This indeterminacy with respect to a given perspective point is formalized in the third section of the paper by resorting to a branching time model. In the third section a unitary treatment (based on the derivation of a single logical form) is proposed for the three main readings of tenses such as the Presente and the Imperfetto and for an intriguing side effect that, in some particular circumstances, makes a "perfective" reading possible. Since the context has a key role in this reconstruction of imperfectivity, the last section of the paper is devoted to the consideration of the temporal parameters to which the evaluation of an utterance is relativized. (shrink)

We present a new notion of game equivalence that captures basic powers of interacting players. We provide a representation theorem, a complete logic, and a new game algebra for basic powers. In doing so, we establish connections with imperfect information games and epistemic logic. We also identify some new open problems concerning logic and games.

We present a new notion of game equivalence that captures basic powers of interacting players. We provide a representation theorem, a complete logic, and a new game algebra for basic powers. In doing so, we establish connections with imperfect information games and epistemic logic. We also identify some new open problems concerning logic and games.

With agents relying more and more on information from central servers rather than their own sensors, knowledge becomes property not of a specific agent but of the data that the agents can access. The article proposes a dynamic logic of data-informed knowledge that describes an interplay between three modalities and one relation capturing the properties of this form of knowledge. The main technical results are the undefinability of two dynamic operators through each other, a sound and complete (...) axiomatisation, and a model checking algorithm. (shrink)

We examine the relationship between dependence logic and game logics. A variant of dynamic game logic, called Transition Logic, is developed, and we show that its relationship with dependence logic is comparable to the one between first-order logic and dynamic game logic discussed by van Benthem. This suggests a new perspective on the interpretation of dependence logic formulas, in terms of assertions about reachability in games of imperfect information against Nature. (...) We then capitalize on this intuition by developing expressively equivalent variants of dependence logic in which this interpretation is taken to the foreground. (shrink)

We discuss games of both perfect and imperfect information at two levels of structural detail: players’ local actions, and their global powers for determining outcomes of the game. We propose matching logical languages for both. In particular, at the ‘action level’, imperfect information games naturally model a combined ‘dynamic-epistemic language’ – and we find correspondences between special axioms and particular modes of playing games with their information dynamics. At the ‘outcome level’, we present suitable (...) notions of game equivalence, plus some simple representation results. (shrink)

In this paper we show how recent concepts from Dynamic Logic, and in particular from Dynamic Epistemic logic, can be used to model and interpret quantum behavior. Our main thesis is that all the non-classical properties of quantum systems are explainable in terms of the non-classical flow of quantum information. We give a logical analysis of quantum measurements (formalized using modal operators) as triggers for quantum information flow, and we compare them with other logical operators (...) previously used to model various forms of classical information flow: the “test” operator from Dynamic Logic, the “announcement” operator from Dynamic Epistemic Logic and the “revision” operator from Belief Revision theory. The main points stressed in our investigation are the following: (1) The perspective and the techniques of “logical dynamics” are useful for understanding quantum information flow. (2) Quantum mechanics does not require any modification of the classical laws of “static” propositional logic, but only a non-classical dynamics of information. (3) The main such non-classical feature is that, in a quantum world, all information-gathering actions have some ontic side-effects. (4) This ontic impact can affect in its turn the flow of information, leading to non-classical epistemic side-effects (e.g. a type of non-monotonicity) and to states of “objectively imperfect information”. (5) Moreover, the ontic impact is non-local: an information-gathering action on one part of a quantum system can have ontic side-effects on other, far-away parts of the system. (shrink)

In this paper we show that first-order languages extended with partially ordered connectives and partially ordered quantifiers define, under a certain interpretation, their own truth-predicate. The interpretation in question is in terms of games of imperfect information. This result is compared with those of Kripke and Feferman.

We study partiality in propositional logics containing formulas with either undefined or over-defined truth-values. Undefined values are created by adding a four-place connective W termed transjunction to complete models which, together with the usual Boolean connectives is shown to be functionally complete for all partial functions. Transjunction is seen to be motivated from a game-theoretic perspective, emerging from a two-stage extensive form semantic game of imperfect information between two players. This game-theoretic approach yields an interpretation where (...) partiality is generated as a property of non-determinacy of games. Over-defined values are produced by adding a weak, contradictory negation or, alternatively, by relaxing the assumption that games are strictly competitive. In general, particular forms of extensive imperfect information games give rise to a generalised propositional logic where various forms of informational dependencies and independencies of connectives can be studied. (shrink)

The logic of ‘being informed’ gives a formal analysis of a cognitive state that does not coincide with either belief, or knowledge. To Floridi, who first proposed the formal analysis, the latter is supported by the fact that unlike knowledge or belief, being informed is a factive, but not a reflective state. This paper takes a closer look at the formal analysis itself, provides a pure and an applied semantics for the logic of being informed, and tries (...) to find out to what extent the formal analysis can contribute to an information-based epistemology. (shrink)