Weakly Aggregative Modal Logic: Characterization and Interpolation

LORIProceeding Paper
Jixin Liu, Yanjing Wang, Yifeng Ding
Proceedings of LORI 2019
Publication year: 2019

Abstract. Weakly Aggregative Modal Logic (WAML) is a collection of disguised polyadic modal logics with n-ary modalities whose arguments are all the same. WAML has some interesting applications on epistemic logic and logic of games, so we study some basic model theoretical aspects of WAML in this paper. Specically, we give a van Benthem-Rosen characterization theorem of WAML based on an intuitive notion of bisimulation and show that each basic WAML system Kn lacks Craig Interpolation.

Multi-agent knowing how via multi-step plans: a dynamic epistemic planning based approach

Beyond know-thatLORIProceeding Paper
Yanjun Li, Yanjing Wang
Proceedings of LORI 2019
Publication year: 2019

Abstract. There are currently two approaches to the logic of knowing how: the planning-based one and the coalition-based one. However, the rst is single-agent, and the second is based on single-step joint actions. In this paper, to overcome both limitations, we propose a multi-agent framework for the logic of knowing how, based on multi-step dynamic epistemic planning studied in the literature. We obtain a sound and com- plete axiomatization and show that the logic is decidable, although the corresponding multi-agent epistemic planning problem is undecidable.

Knowledge-now and Knowledge-all

LORIProceeding Paper
Xinyu Wang, Yanjing Wang
Proceedings of LORI 2019
Publication year: 2019

Abstract: In this paper, we propose a logical framework extending the standard epistemic logic with a new knowledge operator $\G_i$ which captures the knowledge about (physically) necessary facts, e.g., scientific knowledge. Semantically, the truth of $\G_i\phi$ depends on not only the epistemically indistinguishable worlds from the current real world but also the relevant (physically) possible worlds which are clearly distinguishable. Essentially, $\G_i$ is a bundle of the standard epistemic modality and a necessity-like modality. We axiomatize the corresponding epistemic logic completely in single- and multi-agent cases with interesting interaction axioms between the two epistemic operators.

How to Agree without Understanding Each Other: Public Announcement Logic with Boolean Definitions

Proceeding PaperTARK
Gattinger, Malvin and Wang, Yanjing
In Proceedings on Conference on Theoretical Aspects of Rationality and Knowledge (TARK) 2019, 2019
Publication year: 2019

Abstract. In standard epistemic logic, knowing that p is the same as knowing that p is true, but it does not say anything about understanding p or knowing its meaning. In this paper, we present a conservative extension of Public Announcement Logic (PAL) in which agents have knowledge or belief about both the truth values and the meanings of propositions. We give a complete axiomatization of PAL with Boolean Definitions and discuss various examples. An agent may understand a proposition without knowing its truth value or the other way round. Moreover, multiple agents can agree on something without agreeing on its meaning and vice versa.

A logic of knowing why

Beyond know-thatJournal PaperSynthese
Xu, Chao and Wang, Yanjing and Studer, Thomas
Synthese, To appear, 2019
Publication year: 2019

Abstract. When we say “I know why he was late”, we know not only the fact that he was late, but also an explanation of this fact. We propose a logical framework of “knowing why” inspired by the existing formal studies on why-questions, scientific explanation, and justification logic. We introduce the $Ky_i$ operator into the language of epistemic logic to express “agent i knows why phi” and propose a Kripke-style semantics of such expressions in terms of knowing an explanation of phi. We obtain two sound and complete axiomatizations w.r.t. two different model classes depending on different assumptions about introspection.

A dynamic epistemic framework for reasoning about conformant probabilistic plans

AIJJournal Paper
Li, Yanjun and Kooi, Barteld and Wang, Yanjing
Artificial Intelligence, 268: 54—84, 2019
Publication year: 2019

Abstract: In this paper, we introduce a probabilistic dynamic epistemic logical framework that can be applied for reasoning and verifying conformant probabilistic plans in a single agent setting. In conformant probabilistic planning (CPP), we are looking for a linear plan such that the probability of achieving the goal after executing the plan is no less than a given threshold probability $\delta$. Our logical framework can trace the change of the belief state of the agent during the execution of the plan and verify the conformant plans. Moreover, with this logic, we can enrich the CPP framework by formulating the goal as a formula in our language with action modalities and probabilistic beliefs. As for the main technical results, we provide a complete axiomatization of the logic and show the decidability of its validity problem.

When Names Are Not Commonly Known: Epistemic Logic with Assignments

AiMLBeyond know-thatBook ChapterProceeding Paper
Wang, Yanjing and Seligman, Jeremy
Advances in Modal Logic Vol.12, College Publications: 611—628, 2018
Publication year: 2018

Abstract: In standard epistemic logic, agent names are usually assumed to be common knowledge implicitly. This is unreasonable for various applications. Inspired by term modal logic and assignment operators in dynamic logic, we introduce a lightweight modal predicate logic where names can be non-rigid. The language can handle various de dicto and de re distinctions in a natural way. The main technical result is a complete axiomatisation of this logic over S5 models.

True lies

Journal PaperSynthese
AAgotnes, Thomas and van Ditmarsch, Hans and Wang, Yanjing
Synthese, 195(10): 4581—4615, 2018
Publication year: 2018

Abstract: A true lie is a lie that becomes true when announced. In a logic of announcements, where the announcing agent is not modelled, a true lie is a formula (that is false and) that becomes true when announced. We investigate true lies and other types of interaction between announced formulas, their preconditions and their postconditions, in the setting of Gerbrandy’s logic of believed announcements, wherein agents may have or obtain incorrect beliefs. Our results are on the satisfiability and validity of instantiations of these semantically defined categories, on iterated announcements, including arbitrarily often iterated announcements, and on syntactic characterization. We close with results for iterated announcements in the logic of knowledge (instead of belief), and for lying as private announcements (instead of public announcements) to different agents. Detailed examples illustrate our lying concepts.

Bundled fragments of first-order modal logic: (un)decidability

Beyond know-thatProceeding Paper
Padmanabha, Anantha and Ramanujam, R. and Wang, Yanjing
In Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2018, 2018
Publication year: 2018

Abstract: Quantified modal logic provides a natural logical language for reasoning about modal attitudes even while retaining the richness of quantification for referring to predicates over domains. But then most fragments of the logic are undecidable, over many model classes. Over the years, only a few fragments (such as the monodic) have been shown to be decidable. In this paper, we study fragments that bundle quantifiers and modalities together, inspired by earlier work on epistemic logics of know-how/why/what. As always with quantified modal logics, it makes a significant difference whether the domain stays the same across worlds, or not. In particular, we show that the bundle \forall \Box is undecidable over constant domain interpretations, even with only monadic predicates, whereas \exists \Box bundle is decidable. On the other hand, over increasing domain interpretations, we get decidability with both \forall \Box and \exists \Box bundles with unrestricted predicates. In these cases, we also obtain tableau based procedures that run in PSPACE. We further show that the \exists \Box bundle cannot distinguish between constant domain and increasing domain interpretations.

Beyond Knowing That: A New Generation of Epistemic Logics

Beyond know-thatBook ChapterSelected
Wang, Yanjing
Jaakko Hintikka on knowledge and game theoretical semantics, Springer, 12: 499—533, 2018
Publication year: 2018

 

Abstract. Epistemic logic has become a major field of philosophical logic ever since the groundbreaking work by Hintikka (1962). Despite its various successful applications in theoretical computer science, AI, and game theory, the technical development of the field has been mainly focusing on the propositional part, i.e., the propositional modal logics of “knowing that”. However, knowledge is expressed in everyday life by using various other locutions such as “knowing whether”, “knowing what”, “knowing how” and so on (knowing-wh hereafter). Such knowledge expressions are better captured in quantified epistemic logic, as was already discussed by Hintikka (1962) and his sequel works at length. This paper aims to draw the attention back again to such a fascinating but largely neglected topic. We first survey what Hintikka and others did in the literature of quantified epistemic logic, and then advocate a new quantifier-free approach to study the epistemic logics of knowing-wh, which we believe can balance expressivity and complexity, and capture the essential reasoning patterns about knowing-wh. We survey our recent line of work on the epistemic logics of “knowing whether”, “knowing what” and “knowing how” to demonstrate the use of this new approach.

A logic of goal-directed knowing how

Beyond know-thatJournal PaperSelectedSynthese
Wang, Yanjing
Synthese, 195(10): 4419—4439, 2018
Publication year: 2018

Abstract: In this paper, we propose a decidable single-agent modal logic for reasoning about goal-directed “knowing how”, based on ideas from linguistics, philosophy, modal logic, and automated planning in AI. We first define a modal language to express “I know how to guarantee (Formula presented.) given (Formula presented.)” with a semantics based not on standard epistemic models but on labeled transition systems that represent the agent’s knowledge of his own abilities. The semantics is inspired by conformant planning in AI. A sound and complete proof system is given to capture valid reasoning patterns, which highlights the compositional nature of “knowing how”. The logical language is further extended to handle knowing how to achieve a goal while maintaining other conditions.

(This is an extended journal version of the LORI2015 paper)

Strategically knowing how

Beyond know-thatIJCAIProceeding PaperSelected
Fervari, Raul and Herzig, Andreas and Li, Yanjun and Wang, Yanjing
In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI) 2017, 2017
Publication year: 2017

Abstract. 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 axiomatization 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 both knowledge-that and knowledge-how.

More for free: A dynamic epistemic framework for conformant planning over transition systems

Journal PaperSelected
Li, Yanjun and Yu, Quan and Wang, Yanjing
Journal of Logic and Computation, 27(8): 2383—2410, 2017
Publication year: 2017

Abstract: In this article, we introduce a lightweight dynamic epistemic logical framework for automated planning under initial uncertainty. We generalize the standard conformant planning problem in AI (over transition systems) in two crucial aspects: first, the planning goal can be any formula expressed in an epistemic propositional dynamic logic (EPDL); second, procedural constraints of the desired plan specified by regular expressions can be imposed. We then reduce the problem of generalized conformant planning to the model checking problem of our logic. Although our conformant planning problem is much more general than the standard one with Boolean goals and no procedural constraints, the complexity is still PSPACE-complete which is equally hard as standard conformant planning over explicit transition systems.

Knowing values and public inspection

Beyond know-thatICLAProceeding Paper
Van Eijck, Jan and Gattinger, Malvin and Wang, Yanjing
In Proceedings of International Conference on Logic and its Applications (ICLA) 2017, 2017
Publication year: 2017

Abstract: We present a basic dynamic epistemic logic of “knowing the value”. Analogous to public announcement in standard DEL, we study “public inspection”, a new dynamic operator which updates the agents’ knowledge about the values of constants.We provide a sound and strongly complete axiomatization for the single and multi-agent case, making use of the well-known Armstrong axioms for dependencies in databases.

Achieving while maintaining: A logic of knowing how with intermediate constraints

Beyond know-thatICLAProceeding Paper
Li, Yanjun and Wang, Yanjing
In Proceedings of International Conference on Logic and its Applications (ICLA) 2017, 2017
Publication year: 2017

Abstract: In this paper, we propose a ternary knowing how operator to express that the agent knows how to achieve $\phi$ given $\psi$ while maintaining $\chi$ in-between. It generalizes the logic of goal-directed knowing how proposed by Wang in [10]. We give a sound and complete axiomatization of this logic.

A New Modal Framework for Epistemic Logic

Beyond know-thatProceeding PaperSelectedTARK
Wang, Yanjing
Proceedings of Conference on Theoretical Aspects of Rationality and Knowledge (TARK) 2017, 251: 515—534, 2017
Publication year: 2017

Abstract: Recent years witnessed a growing interest in non-standard epistemic logics of knowing whether, knowing how, knowing what, knowing why and so on. The new epistemic modalities introduced in those logics all share, in their semantics, the general schema of \exists x\phi, e.g., knowing how to achieve \phi roughly means that there exists a way such that you know that it is a way to ensure that \phi Moreover, the resulting logics are decidable. Inspired by those particular logics, in this work, we propose a very general and powerful framework based on quantifier-free predicate language extended by a new modality x, which packs exactly x together. We show that the resulting language, though much more expressive, shares many good properties of the basic propositional modal logic over arbitrary models, such as finite-tree-model property and van Benthem-like characterization w.r.t. first-order modal logic. We axiomatize the logic over S5 frames with intuitive axioms to capture the interaction between x and know-that operator in an epistemic setting.

Knowing Your Ability

Beyond know-thatJournal Paper
Lau, Tszyuen and Wang, Yanjing
Philosophical Forum, 47(3-4): 415—423, 2016
Publication year: 2016

Abstract:In this article, we present an attempt to reconcile intellectualism and the anti-intellectualist ability account of knowledge-how by reducing “S knows how to F” to, roughly speaking, “S knows that she has the ability to F demonstrated by a concrete way w.” More precisely, “S has a certain ability” is further formalized as the proposition that S can guarantee a certain goal by a concrete way w of some method under some precondition. Having the knowledge of our own ability, we can plan our future actions accordingly, which would not be possible by merely having the ability without knowing it, and this pinpoints the crucial difference between knowledge-how and ability. Our semi-formal account avoids most of the objections to both intellectualism and the anti-intellectualist ability account and provides a multistage learning process of knowledge-how, which reveals various subtleties.

Knowing value logic as a normal modal logic

AiMLBeyond know-thatBook ChapterProceeding Paper
Gu, Tao and Wang, Yanjing
Advances in Modal Logic, College Publications, 11: 362—381, 2016
Publication year: 2016

Abstract. Recent years witness a growing interest in nonstandard epistemic logics of “knowing whether”, “knowing what”, “knowing how”, and so on. These logics are usually not normal, i.e., the standard axioms and reasoning rules for modal logic may be invalid. In this paper, we show that the conditional “knowing value” logic proposed by Wang and Fan (2013) can be viewed as a disguised normal modal logic by treating the negation of the Kv operator as a special diamond. Under this perspective, it turns out that the original first-order Kripke semantics can be greatly simplified by introducing a ternary relation R_i^c in standard Kripke models, which associates one world with two i-accessible worlds that do not agree on the value of constant c. Under intuitive constraints, the modal logic based on such Kripke models is exactly the one studied by Wang and Fan (2013,2014). Moreover, there is a very natural binary generalization of the “knowing value” diamond, which, surprisingly, does not increase the expressive power of the logic. The resulting logic with the binary diamond has a transparent normal modal system, which sharpens our understanding of the “knowing value” logic and simplifies some previously hard problems.

Representing Imperfect Information of Procedures with Hyper Models

ICLAProceeding Paper
Wang, Yanjing
In Proceedings of International Conference on Logic and its Applications (ICLA) 2015, 2015
Publication year: 2015

Abstract. When reasoning about knowledge of procedures under imperfect information, the explicit representation of epistemic possibilities blows up the S5-like 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.

From rules to runs: A dynamic epistemic take on imperfect information games

Journal Paper
Li, Kai and Wang, Yanjing
Studies in Logic, 8(4): 74—107, 2015
Publication year: 2015

Abstract: In the literature of game theory, the information sets of extensive form games have different interpretations, which may lead to confusions and paradoxical cases. We argue that the problem lies in the mix-up of two interpretations of the extensive form game structures: game rules or game runs which do not always coincide. In this paper, we try to separate and connect these two views by proposing a dynamic epistemic framework in which we can compute the runs step by step from the game rules plus the given assumptions of the players. We propose a modal logic to describe players’ knowledge and its change during the plays, and provide a complete axiomatization. We also show that, under certain conditions, the mix-up of the rules and the runs is not harmful due to the structural similarity of the two.

Epistemic Informativeness

Book Chapter
Wang, Yanjing and Fan, Jie
Modality, Semantics and Interpretations, {publisher}: 121—129, 2015
Publication year: 2015

Abstract. In this paper, we introduce and formalize the concept of epistemic informativeness (EI) of statements: the set of new propositions that an agent comes to know from the truthful announcement of the statements. We formalize EI in multi-agent Public Announcement Logic and characterize it by proving that two basic statements are the same in EI iff the logical equivalence of the two is common knowledge after a certain announcement. As a corollary applied to identity statements, a=b and a=a are different in EI iff a=b is not common knowledge. This may shed new light on the differences in cognitive value of a=a and a=b , even when they are both known to be true, as long as a=b is not commonly known to all.

Contingency and Knowing Whether

Beyond know-thatJournal PaperSelected
Fan, Jie and Wang, Yanjing and Ditmarsch, Hans Van
Review of Symbolic Logic, 8(1): 75—107, 2015
Publication year: 2015

Abstract: A proposition is noncontingent, if it is necessarily true or it is necessarily false. In an epistemic context, ‘a proposition is noncontingent’ means that you know whether the proposition is true. In this paper, we study contingency logic with the noncontingency operator ? but without the necessity operator 2. This logic is not a normal modal logic, because Kw(\phi \to \psi)\to(Kw \phi\to \psi) is not valid. Contingency logic cannot define many usual frame properties, and its expressive power is weaker than that of basic modal logic over classes of models without reflexivity. These features make axiomatizing contingency logics nontrivial, especially for the axiomatization over symmetric frames. In this paper, we axiomatize contingency logics over various frame classes using a novel method other than the methods provided in the literature, based on the ‘almost-definability’ schema AD proposed in our previous work. We also present extensions of contingency logic with dynamic operators. Finally, we compare our work to the related work in the fields of contingency logic and ignorance logic, where the two research communities have similar results but are apparently unaware of each other’s work. One goal of our paper is to bridge this gap.

A logic of knowing how

Beyond know-thatLORIProceeding Paper
Wang, Yanjing
In Proceedings of LORI ’15, 2015
Publication year: 2015

Abstract: In this paper, we propose a single-agent modal logic framework for reasoning about goal-direct “knowing how” based on ideas from linguistics, philosophy, modal logic and automated planning. We first define a modal language to express “I know how to guarantee phi given $\psi$” with a semantics not based on standard epistemic models but labelled transition systems that represent the agent’s knowledge of his own abilities. A sound and complete proof system is given to capture the valid reasoning patterns about “knowing how” where the most important axiom suggests its compositional nature.

A Dynamic Epistemic Framework for Conformant Planning

Proceeding PaperTARK
Yu, Quan and Li, Yanjun and Wang, Yanjing
In Proceedings on Conference on Theoretical Aspects of Rationality and Knowledge (TARK) 2015, 2015
Publication year: 2015

Abstract: In this paper, we introduce a lightweight dynamic epistemic logical framework for automated plan-ning under initial uncertainty. We reduce plan verification and conformant planning to model check-ing problems of our logic. We show that the model checking problem of the iteration-free fragment is PSPACE-complete. By using two non-standard (but equivalent) semantics, we give novel model checking algorithms to the full language and the iteration-free language.

Hidden protocols: Modifying our expectations in an evolving world

AIJJournal PaperSelected
Van Ditmarsch, Hans and Ghosh, Sujata and Verbrugge, Rineke and Wang, Yanjing
Artificial Intelligence, 208(1): 18—40, 2014
Publication year: 2014

Abstract. When agents know a protocol, this leads them to have expectations about future observations. Agents can update their knowledge by matching their actual observations with the expected ones. They eliminate states where they do not match. In this paper, we study how agents perceive protocols that are not commonly known, and propose a semantics-driven logical framework to reason about knowledge in such scenarios. In particular, we introduce the notion of epistemic expectation models and a propositional dynamic logic-style epistemic logic for reasoning about knowledge via matching agents’ expectations to their observations. It is shown how epistemic expectation models can be obtained from epistemic protocols. Furthermore, a characterization is presented of the effective equivalence of epistemic protocols. We introduce a new logic that incorporates updates of protocols and that can model reasoning about knowledge and observations. Finally, the framework is extended to incorporate fact-changing actions, and a worked-out example is given.

(Extended journal version of the TARK2011 paper)

Conditionally knowing what

AiMLBeyond know-thatBook ChapterProceeding Paper
Wang, Yanjing and Fan, Jie
Advances in Modal Logic Vol.10, College Publications: 569—587, 2014
Publication year: 2014

Abstract. Classic epistemic logic focuses on propositional knowledge expressed by “knowing that” operators. However, there are various types of knowledge used in natural language, in terms of “knowing how”, “knowing whether”, “knowing what”, and so on. In [10], Plaza proposed an intuitive know-what operator which was generalized in [16] by introducing a condition. The latter know-what operator can express natural conditional knowledge such as $\backslash$I know what your password is, if it is 4-digits”, which is not simply a material implication. Essentially this know-what operator packages a first-order quantifier and an S5-modality together in a non-trivial way, thus making it hard to axiomatize. In [16] an axiomatization is given for the single-agent epistemic logic with both know-that and know-what operators, while leaving axiomatizing the multi-agent case open due to various technical difficulties. In this paper, we solve this open problem. The completeness proof is highly non-trivial, compared to the singleagent case, which requires different techniques inspired by first-order intensional logic.

Book Review: Logical Dynamics of Information and Interaction

Journal Paper
Wang, Yanjing
Studia Logica, 102(3): 647—654, 2014
Publication year: 2014

 

Abstract. An extensive review of Johan van Benthem’s book Logical Dynamics of Information and Interaction

Almost necessary

AiMLBeyond know-thatBook ChapterProceeding Paper
Fan, Jie and Wang, Yanjing and van Ditmarsch, Hans
Advances in Modal Logic Vol.10, College Publications, 10: 178—196, 2014
Publication year: 2014

Abstract. A formula is contingent if it is possibly true and possibly false. A formula is non- contingent if it is not contingent, i.e., if it is necessarily true or necessarily false. In an epistemic setting, a formula is contingent’ means that you are ignorant about its value, whereas a formula is non-contingent’ means that you know whether it is true. Although non-contingency is definable in terms of necessity as above, necessity is not always definable in terms of non-contingency, as studied in the literature. We propose an almost-definability’ schema AD for non-contingency logic, the logic with the noncontingency operator as the only modality, making precise when necessity is definable with non-contingency. Based on AD we propose a notion of bisimulation for non- contingency logic, and characterize non-contingency logic as the (non-contingency) bisimulation invariant fragment of modal logic and of first-order logic. A known pain for non-contingency logic is the absence of axioms characterizing frame properties. This makes it harder to find axiomatizations of non-contingency logic over given frame classes. In particular, no axiomatization over symmetric frames is known, despite the rich results about non-contingency logic obtained in the literature since the 1960s. We demonstrate that the almost-definability’ schema AD can guide our search for proper axioms for certain frame properties, and help us in defining the canonical models. Following this idea, as the main result, we give a complete axiomatization of non-contingency logic over symmetric frames.

Reasoning about agent types and the hardest logic puzzle ever

Journal PaperSelected
Liu, Fenrong and Wang, Yanjing
Minds and Machines, 23(1): 123—161, 2013
Publication year: 2013

 

Abstract. In this paper, we first propose a simple formal language to specify types of agents in terms of necessary conditions for their announcements. Based on this language, types of agents are treated as ‘first-class citizens’ and studied extensively in various dynamic epistemic frameworks which are suitable for reasoning about knowledge and agent types via announcements and questions. To demonstrate our approach, we discuss various versions of Smullyan’s Knights and Knaves puzzles, including the Hardest Logic Puzzle Ever (HLPE) proposed by Boolos (in Harv Rev Philos 6:62-65, 1996). In particular, we formalize HLPE and verify a classic solution to it. Moreover, we propose a spectrum of new puzzles based on HLPE by considering subjective (knowledge-based) agent types and relaxing the implicit epistemic assumptions in the original puzzle. The new puzzles are harder than the previously proposed ones in the literature, in the sense that they require deeper epistemic reasoning. Surprisingly, we also show that a version of HLPE in which the agents do not know the others’ types does not have a solution at all. Our formalism paves the way for studying these new puzzles using automatic model checking techniques.

 

On axiomatizations of public announcement logic

Journal PaperSelectedSynthese
Wang, Yanjing and Cao, Qinxiang
Synthese, 190(SUPPL.1): 103—134, 2013
Publication year: 2013

 

Abstract. In the literature, different axiomatizations of Public Announcement Logic (PAL) have been proposed. Most of these axiomatizations share a “core set” of the so-called “reduction axioms”. In this paper, by designing non-standard Kripke semantics for the language of PAL, we show that the proof system based on this core set of axioms does not completely axiomatize PAL without additional axioms and rules. In fact, many of the intuitive axioms and rules we took for granted could not be derived from the core set. Moreover, we also propose and advocate an alternative yet meaningful axiomatization of PAL without the reduction axioms. The completeness is proved directly by a detour method using the canonical model where announcements are treated as merely labels for modalities as in normal modal logics. This new axiomatization and its completeness proof may sharpen our understanding of PAL and can be adapted to other dynamic epistemic logics.

 

(largely extended journal version of the LORI2011 paper)

Knowing that, knowing what, and public communication: Public announcement logic with Kv operators

Beyond know-thatIJCAIProceeding Paper
Wang, Yanjing and Fan, Jie
In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI) 2013, 2013
Publication year: 2013

An alternative axiomatization of DEL and its applications

IJCAIProceeding Paper
Wang, Yanjing and Aucher, Guillaume
In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI) 2013, 2013
Publication year: 2013

A note on equivalence of two semantics for epistemic logic of shallow depths

Misc
Wang, Yanjing
The dynamic, inquisitive, and visionary life of ϕ, ?ϕ, and ◊ϕ: A Festschrift for Jeroen Groenendijk, Martin Stokhof, and Frank Veltman, {publisher}, 2013
Publication year: 2013

On the logic of lying

Book Chapter
Van Ditmarsch, Hans and Van Eijck, Jan and Sietsma, Floor and Wang, Yanjing
Games, Actions and Social Software, Springer, 7010 LNCS: 41—72, 2012
Publication year: 2012

Not All Those Who Wander Are Lost: Dynamic Epistemic Reasoning in Navigation

AiMLBook ChapterProceeding Paper
Wang, Yanjing and Li, Yanjun
Advances in Modal Logic, College Publications, 9: 559—580, 2012
Publication year: 2012

Abstract. In everyday life, people get lost even when they have the map: they simply may not know where they are in the map. However, when moving forward they may have new observations which can help to locate themselves by reasoning. In this paper, we propose and develop a semantic-driven dynamic epistemic framework to handle epistemic reasoning in such navigation scenarios. Our framework can be viewed as a careful blend of dynamic epistemic logic and epistemic temporal logic, thus enjoying features from both frameworks. We made an in-depth study on many model theoretical aspects of the proposed framework and provide a complete axiomatization.

Reasoning about protocol change and knowledge

ICLAProceeding Paper
Wang, Yanjing
In Proceedings of International Conference on Logic and its Applications (ICLA) 2011, 2011
Publication year: 2011

Abstract. In social interactions, protocols govern our behavior and assign meaning to actions. In this paper, we investigate the dynamics of protocols and their epistemic effects. We develop two logics, inspired by Propositional Dynamic Logic (PDL) and Public Announcement Logic (PAL), for reasoning about protocol change and knowledge updates. We show that these two logics can be translated back to the standard PDL and PAL respectively.

On axiomatizations of PAL

LORIProceeding Paper
Wang, Yanjing
In Proceedings of LORI 2011, 2011
Publication year: 2011

Abstract. In the literature, different axiomatizations of Public Announcement Logic (PAL) were proposed. Most of these axiomatizations share a ‘core set’ of the so-called reduction axioms. In particular, there is a composition axiom which stipulates how two consecutive announcements are composed into one. In this paper, by designing non-standard Kripke semantics for the language of PAL, we show that without the composition axiom the core set does not completely axiomatize PAL. In fact, most of the intuitive ‘axioms’ and rules we took for granted could not be derived from the core set. The non-standard semantics we proposed is of its own interest in modelling realistic agents. We show that with the help of different composition axioms we may axiomatize PAL w.r.t. such non-standard semantics.

Logic of information flow on communication channels (full paper)

Proceeding Paper
Wang, Yanjing and Sietsma, Floor and Van Eijck, Jan
In Proceedings of DALT 2010, 2011
Publication year: 2011

Abstract. In this paper, we develop an epistemic logic for specifying and reasoning about information flow on the underlying communication channels. By combining ideas from Dynamic Epistemic Logic (DEL) and Interpreted Systems (IS), our semantics offers a natural and neat way of modeling multi-agent communication scenarios with different assumptions about the observational power of agents. We relate our logic to the standard DEL and IS approaches and demonstrate its use by studying a telephone call communication scenario.

Abstract appeared at AAMAS2010

Hidden protocols

Proceeding PaperTARK
van Ditmarsch, Hans and Ghosh, Sujata and Verbrugge, Rineke and Wang, Yanjing
In Proceedings of Conference on Theoretical Aspects of Rationality and Knowledge (TARK) 2011, 2011
Publication year: 2011

When agents know a protocol, this leads them to have expectations about future observations. Agents can update their knowledge by matching their actual observations with the expected ones. They eliminate states where they do not match. In this paper, we study how agents perceive protocols that are not commonly known, and propose a logic to reason about knowledge in such scenarios.

Composing models

Journal PaperSelected
van Eijck, Jan and Sietsma, Floor and Wang, Yanjing
Journal of Applied Non-Classical Logics, 21(3-4): 397—425, 2011
Publication year: 2011

 

Abstract. We propose and study a new composition operation on (epistemic) multi-agent models with different vocabularies of propositional letters. This operation allows us to compose large models by small components representing agents’ partial observational information. Our investigation provides ways to decompose (locally generated) epistemic models such that the truth of certain formulas are preserved. By using the composition operation we also propose and study action model composition and action model updates on models with arbitrary vocabularies.

To know or not to know: Epistemic approaches to security protocol verification

Journal PaperSynthese
Dechesne, Francien and Wang, Yanjing
Synthese, 177(SUPPL. 1): 51—76, 2010
Publication year: 2010

 

Abstract.  Security properties naturally combine temporal aspects of protocols with aspects of knowledge of the agents. Since BAN-logic, there have been several initiatives and attempts to incorporate epistemics into the analysis of security protocols. In this paper, we give an overview of work in the field and present it in a unified perspective, with comparisons on technical subtleties that have been employed in different approaches. Also, we study to which degree the use of epistemics is essential for the analysis of security protocols. We look for formal conditions under which knowledge modalities can bring extra expressive power to pure temporal languages. On the other hand, we discuss the cost of the epistemic operators in terms of model checking complexity.

Epistemic Modelling and Protocol Dynamics

PhD Thesis
Wang, Yanjing
PhD Thesis, University of Amsterdam, 2010
Publication year: 2010

Verifying epistemic protocols under common knowledge

Proceeding PaperTARK
Wang, Yanjing and Kuppusamy, Lakshmanan and van Eijck, Jan
In Proceedings of Conference on Theoretical Aspects of Rationality and Knowledge (TARK) 2009, 2009
Publication year: 2009

Abstract. Epistemic protocols are communication protocols aiming at transfer of knowledge in a controlled way. Typically, the preconditions or goals for protocol actions depend on the knowledge of agents, often in nested form. Informal epistemic protocol descriptions for muddy children, coordinated attack, dining cryptographers, Russian cards, secret key exchange are well known. The contribution of this paper is a formal study of a natural requirement on epistemic protocols, that the contents of the protocol can be assumed to be common knowledge. By formalizing this requirement we can prove that there can be no unbiased deterministic protocol for the Russian cards problem. For purposes of our formal analysis we introduce an epistemic protocol language, and we show that its model checking problem is decidable.

Refinement of Kripke Models for dynamics

Proceeding Paper
Dechesne, Francien and Orzan, Simona and Wang, Yanjing
In Proceedings of ICTAC 2008, 2008
Publication year: 2008

Abstract. We propose a property-preserving refinement/abstraction theory for Kripke Modal Labelled Transition Systems incorporating not only state mapping but also label and proposition lumping, in order to have a compact but informative abstraction. We develop a 3-valued version of Public Announcement Logic (PAL) which has a dynamic operator that changes the model in the spirit of public broadcasting. We prove that the refinement relation on static models assures us to safely reason about any dynamic properties in terms of PAL-formulas on the abstraction of a model. The theory is in particular interesting and applicable for an epistemic setting as the example of the Muddy Children puzzle shows, especially in the view of the growing interest for epistemic modelling and (automatic) verification of communication protocols.

Propositional dynamic logic as a logic of belief revision

Proceeding Paper
Van Eijck, Jan and Wang, Yanjing
In Proceedings of WOLLIC 2008, 2008
Publication year: 2008

PDL over accelerated labeled transition systems

Proceeding Paper
Chen, Taolue and Van De Pol, Jaco and Wang, Yanjing
In Proceedings of IFIP/IEEE International Symposium on Theoretical Aspects of Software Engineering (TASE) 2008, 2008
Publication year: 2008

Abstract. We present a thorough study of Propositional Dynamic Logic over a variation of labeled transition systems, called accelerated labelled transition systems, which are transition systems labeled with regular expressions over action labels. We study the model checking and satisfiability decision problems. Through a notion of regular expression rewriting, we reduce these two problems to the corresponding ones of PDL in the traditional semantics (w.r.t. LTS). As for the complexity, both of problems are proved to be EXPSPACE-complete. Moreover, the program, complexity of model checking problem turns out to be Nlogspace-complete. Furthermore, we provide an axiomatization for PDL which involves Kleene Algebra as an Oracle. The soundness and completeness are shown.

Risk Balance in Exchange Protocols

Proceeding Paper
Torabi Dashti, Mohammad and Wang, Yanjing
In Proceedings of ASIAN 2007, 2007
Publication year: 2007

Dynamic epistemic verification of security protocols : framework and case study

LORIProceeding Paper
Dechesne, Francien and Wang, Yanjing
In Proceedings of LORI 2007, 2007
Publication year: 2007