Point-set Neighborhood Logic

AiMLProceeding PaperSelected
Yanjing Wang, Junhua Yu
Advances in Modal Logic Vol. 15: 697-718
Publication year: 2024

In this paper, we propose Point-set Neighborhood Logic (PSNL) to reason about neighborhood structures. The bimodal language of PSNL is defined via a mutual induction of point-formulas and set-formulas. We show that this simple language is equally expressive as the language of Instantial Neighborhood Logic (INL). As the main results, we first give two complete proof systems, one in Hilbert-style and one in Gentzen sequent-style, each featuring two intertwined $\mathsf{K}$-like systems. The proof of strong completeness of the Hilbert-style system is based on a direct canonical model construction without relying on a normal form. Based on the sequent calculus, we establish the uniform interpolation property of PSNL, from which that of INL follows.

Knowing How to Plan about Planning: Higher-order and Meta-level Epistemic Planning

AIJBeyond know-thatSelected
Yanjun Li, Yanjing Wang
Artificial Intelligence, to appear
Publication year: 2024

Automated planning in AI and the logics of knowing how have close connections. In the recent literature, various planning-based know-how logics have been proposed and studied, making use of several notions of planning in AI. In this paper, we explore the reverse direction by using a multi-agent logic of knowing how to do know-how-based planning via model checking and theorem proving/satisfiability checking. Based on our logical framework, we propose two new classes of related planning problems: higher-order epistemic planning and meta-level epistemic planning, which generalize the current genre of epistemic planning in the literature. The former is for planning about planning, i.e., planning with higher-order goals that are again about epistemic planning, e.g., finding a plan for an agent to make sure p such that the adversary does not know how to make p false in the future. The latter is about planning at the meta-level by abstract reasoning combining knowledge-how from different agents, e.g., given that i knows how to prove a lemma and i knows j knows how to prove the theorem once the lemma is proved, we should derive that i knows how to let j knows how to prove the theorem. To make these possible, our framework features not only the operators of know-that and know-how but also a temporal operator \Box, which can help in capturing both the local and global knowledge-how. We axiomatize this powerful logic over finite models with perfect recall and show its decidability. We also give a PTIME algorithm for the model checking problem over finite models.

(A new paper greatly extending the idea presented at TARK2021)

Strong Permission Bundled: First Steps

DEONProceeding Paper
Zilu Wang, Yanjing Wang
Proceedings of DEON 2023
Publication year: 2023

In this paper, we introduce a novel framework for deontic logic of strong permission that accommodates free choice. Our approach treats permission as a bundled modality, which combines a universal quantifier with a possibility modality such that an action type \alpha is permitted if and only if every token of \alpha can be executed in some deontically ideal world. Our formalization of action tokens and their types is inspired by the BHK-style interpretation for intuitionistic logic. We axiomatize the logics of strong permission under various conditions. In addition to satisfying the desirable logical requirements found in the literature, our framework also predicts interesting new phenomena related to permission and distribution laws that align with our linguistic intuition.

Someone knows that local reasoning on hypergraphs is a weakly aggregative modal logic

Journal PaperSelectedSynthese
Yifeng Ding, Jixin Liu, Yanjing Wang
Synthese, to appear
Publication year: 2023

This paper connects the following four topics: a class of generalized graphs whose relations do not have fixed arities called hypergraphs, a family of non-normal modal logics rejecting the aggregative axiom, an epistemic framework fighting logical omniscience, and the classical group knowledge modality of `someone knows’. Through neighborhood frames as their meeting point, we show that, among many completeness results obtained in this paper, the limit of a family of weakly aggregative logics is both exactly the modal logic of hypergraphs and also the epistemic logic of local reasoning with veracity and positive introspection, and upon adding a single combinatorial axiom, it is also the logic of `someone knows’ for a fixed finite number of positively introspective agents. At the core of all these completeness results is a new canonical neighborhood model construction for monotone modal logics that is capable of dealing with all these diverse cases. We also provide an axiomatization for the logic of all non-n-colorable hypergraphs based on a filtration argument that also shows the decidability of the logics of hypergraphs we study.

(a largely extended journal version of the LORI21 conference paper)

Epistemic Syllogistic: First Steps

Proceeding PaperTARK
Yipu Li, Yanjing Wang
Proceedings of TARK 2023, EPTCS 379, pp. 392–406.
Publication year: 2023

Aristotle’s discussions on modal syllogistic have often been viewed as error-prone and have garnered significant attention in the literature due to historical interests. However, from a contemporary standpoint, they also introduced natural fragments of first-order modal logic, warranting a comprehensive technical analysis. In this paper, drawing inspiration from the natural logic program, we propose and examine several variants of modal syllogistic within the epistemic context, thereby coining the term “epistemic syllogistic.” Specifically, we concentrate on the de re interpretation of epistemic syllogisms containing non-trivial yet natural expressions such as “all things known to be A are also known to be not B.” We explore the epistemic apodeictic syllogistic and its extensions, which accommodate more complex terms. Our main contributions include several axiomatizations of these logics, with completeness proofs that may be of independent interest.

Epistemic Logic

Beyond know-thatEncyclopedia EntrySelectedTopics
Rasmus Rendsvig, John Symons, and Yanjing Wang
"Epistemic Logic", The Stanford Encyclopedia of Philosophy (Winter 2023 Edition), Edward N. Zalta & Uri Nodelman (eds.), forthcoming
Publication year: 2023

Update of the entry “Epistemic Logic” of The Stanford Encyclopedia of Philosophy

Are Bundles Good Deals for First-order Modal Logic?

bundled fragmentsJournal PaperSelected
Mo Liu, Anantha Padmanabha, R Ramanujam, Yanjing Wang
Information and Computation
Publication year: 2023

Bundled products are often offered as good deals to customers. When we bundle quantifiers and modalities together (as in ∃x□, ◊∀x etc.) in first-order modal logic (FOML), we get new logical operators whose combinations produce interesting fragments of FOML without any restriction on the arity of predicates, the number of variables, or the modal scope. It is well-known that finding decidable fragments of FOML is hard, so we may ask: do bundled fragments that exploit the distinct expressivity of FOML constitute good deals in balancing the expressivity and complexity? There are a few positive earlier results on some particular fragments. In this paper, we try to fully map the terrain of bundled fragments of FOML in (un)decidability, and in the cases without a definite answer yet, we show that they lack the finite model property. Moreover, whether the logics are interpreted over constant domains (across states/worlds) or increasing domains presents another layer of complexity. We also present the \textit{loosely bundled fragment}, which generalizes the bundles and yet retain decidability (over increasing domain models).

Tense Logics over Lattices

Proceeding PaperWoLLIC
Xiaoyang Wang, Yanjing Wang
Proceedings of WoLLIC 2022
Publication year: 2022

Lattice theory has intimate connections with modal logic via algebraic semantics and lattices of modal logics. However, one less explored direction is to view lattices as relational structures extending partial orders, and study the modal logic over them. In this paper, following the earlier steps of Burgess and van Benthem in the 1980s, we use the basic tense logic and its extension with infimum and supremum binary modalities and nominals to talk about lattices based on Kripke semantics. As the main results and also the first steps of a general research program, we obtain a series of complete finite axiomatizations of lattices and (un)bounded lattices.

Quantifier-free Epistemic Term-Modal Logic with Assignment Operator

APALJournal Paper
Yanjing Wang, Yu Wei, Jeremy Seligman
Annals of Pure and Applied Logic 173(3), 103071
Publication year: 2022

In standard epistemic logic, the names and the existence of agents are usually assumed to be common knowledge implicitly. This is unreasonable for various applications in computer science and philosophy. Inspired by term-modal logic and assignment operators in dynamic logic, we introduce a lightweight modal predicate logic where names can be non-rigid, and the existence of agents can be uncertain. The language can handle various de dicto/de re distinctions in a natural way. We characterize the expressive power of our language, obtain complete axiomatisations of the logics over several classes of varying-domain/constant-domain epistemic models, and show their (un)decidability.

(Largely extended journal version of the AiML18 paper)

Model Theoretical Aspects of Weakly Aggregative Modal Logic

Journal Paper
Jixin Liu, Yifeng Ding, Yanjing Wang
Journal of Logic, Language and Information (to appear)
Publication year: 2022

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, deontic logic, and the logic of belief, and in this paper, we study some basic model theoretical aspects of WAML. Specifically, we first give a van Benthem-Rosen characterization theorem of WAML based on an intuitive notion of bisimulation. Then, in contrast to many well known normal or non-normal modal logics, we show that each basic WAML system K_n lacks Craig interpolation. Finally, by model theoretical techniques, we show that an extension of K_2 does have Craig interpolation, as an example of amending the interpolation problem of WAML.

(Extended journal version of the LORI19 conference paper)

Mereological Bimodal Logics

Journal PaperRSL
Dazhu Li, Yanjing Wang
Review of Symbolic Logic 15(4): 823 - 858
Publication year: 2022

In this paper, using a propositional modal language extended with the window modality, we capture the first-order properties of various mereological theories. In this setting, \Box \phi reads all my parts are \phi, interpreted on the models with a whole-part binary relation under various constraints. We show that all the usual mereological theories can be captured by modal formulas in our language via frame correspondence. We also correct a mistake in the existing completeness proof for a basic system of mereology by providing a new construction of the canonical model.

 

Inquisitive Logic as an Epistemic Logic of Knowing How

APALBeyond know-thatEpistemicization of Non-classical LogicsJournal PaperSelected
Haoyu Wang, Yanjing Wang, Yunsong Wang
Annals of Pure and Applied Logic (accepted)
Publication year: 2022

In this paper, we present an alternative interpretation of propositional inquisitive logic as an epistemic logic of knowing how. In our setting, an inquisitive logic formula α being supported by a state is formalized as “knowing how to resolve α” (more colloquially, “knowing how α is true”) holds on the S5 epistemic model corresponding to the state. Based on this epistemic interpretation, we use a dynamic epistemic logic with both know-how and know-that operators to capture the epistemic information behind the innocent-looking connectives in inquisitive logic. We show that the set of valid know-how formulas corresponds precisely to the inquisitive logic. The main result is a complete axiomatization with intuitive axioms using the full dynamic epistemic language. Moreover, we show that the know-how operator and the dynamic operator can both be eliminated without changing the expressivity over models, which is consistent with the modal translation of inquisitive logic existing in the literature. We hope our framework can give an intuitive alternative interpretation of various concepts and technical results in inquisitive logic, and provide a powerful and flexible tool to do inquisitive reasoning in an epistemic context.

Generalized Bundled Fragments of First-order Modal Logic

Beyond know-thatbundled fragmentsProceeding Paper
Mo Liu, Anantha Padmanabha, R. Ramanujam and Yanjing Wang
MFCS 2022
Publication year: 2022

When we bundle quantifiers and modalities together (as in $\exists x \Box$, $\Diamond \forall x$ etc.) in first-order modal logic (FOML), we get new logical operators whose combinations produce interesting \textit{bundled} fragments of FOML. It is well-known that finding decidable fragments of \FOML is hard, but existing work shows that certain bundled fragments are decidable [Padmanabha et al 2018], without any restriction on the arity of predicates, the number of variables, or the modal scope. In this paper, we explore generalized bundles such as $\forall x\forall y \Box, \forall x\exists y \Diamond$ etc., and map the terrain with regard to decidability, presenting both decidability and undecidability results. In particular, we propose the loosely bundled fragment which is decidable over increasing domains and encompasses all known decidable bundled fragments.

An Epistemic Interpretation of Tensor Disjunction

AiMLBeyond know-thatEpistemicization of Non-classical LogicsSelectedTopics
Haoyu Wang, Yanjing Wang, Yunsong Wang
Publication year: 2022

In this paper, we present an epistemic interpretation of the tensor disjunction in dependence logic, inspired by the weak disjunction studied by Medvedev under a formalized BHK-like semantics. To put the tensor disjunction in the same picture with intuitionistic and classical disjunctions, we give an alternative epistemic semantics to inquisitive logic with tensor, studied by Ciardelli and Barbero (2019). We then use a much more powerful epistemic language with propositional quantifiers to give a complete axiomatization where the non-classical formulas are reduced in the system to classical but epistemic ones. It also turns out that the idea of the tensor disjunction can be generalized greatly without adding expressive power, resulting in a (k, n)-parametrized general tensor that captures the epistemic state that knowing k out of n given answers to the corresponding n questions are correct. The standard tensor is simply a special case where k=1 and n=2.

君子与顽童:大学教师的职业伦理

BookTranslation
Steven M. Cahn, Translated by Yanjing Wang
《君子与顽童:大学教师的职业伦理(25周年纪念版)》 斯蒂文·M.卡恩 著 王彦晶译 北京大学出版社 2021年1月
Publication year: 2021

Chinese Translation of Saints and Scamps: Ethics in Academia by Dr. Steven Cahn

“君子”与“顽童”指的是大学教师当中存在着的两种极端情况:既有恪守职业及学术伦理的大学者和教育家,也有对学生、学术以及学术共同体不负责任的渎职者。本书是西方教师职业伦理的经典之作,作者既是哲学家又是长期任职于世界著名大学的管理者。本书从教学、研究以及行政服务等角度,系统地梳理了大学教师的职责,探讨了其中的职业伦理问题。作为一位大学教授,不仅意味着科研和学术成就,也意味着要做一名合格的老师和学术共同体中负责任的一员。书中的讨论不仅仅停留在抽象的哲学层面,还结合了大量的类比以及生动的例子,并从制度设计及个人选择的角度给出了很多可操作的建议,对大学的各级管理者、教员以及即将走上大学教师工作岗位的年轻学者都会有所启示。

译后记

Planning-based knowing how: a unified approach

AIJBeyond know-thatJournal PaperSelected
Yanjun Li, Yanjing Wang
Artificial Intelligence, Volume 296, July 2021, 103487
Publication year: 2021

Various logical notions of know-how have been recently proposed and studied in the literature based on different types of epistemic planning in different frameworks. This paper proposes a unified logical framework to incorporate the existing and some new notions of know-how. We define the semantics of the know-how operator using a unified notion of epistemic planning with parameters of different types of plans specified by a programming language. Surprisingly, via a highly unified completeness proof, we show that all the ten intuitive notions of plans discussed in this paper lead to exactly the same know-how logic, which is proven to be decidable. We also show that over finite models, the know-how logic based on knowledge-based plans requires an extension with an axiom capturing the compositionality of the plans. In the context of epistemic planning, our axiomatization results reveal the core principles behind the very idea of epistemic planning, independent of the particular notion of plans. Moreover, since epistemic planning can be expressed by the know-how modality in our object language, we can greatly generalize the planning problems that can be solved formally by model checking various formulas in our know-how language.

Neighborhood Semantics for Logic of Knowing How

Beyond know-thatJournal PaperSelectedSynthese
Yanjun Li, Yanjing Wang
Synthese (accpeted)
Publication year: 2021

In this paper, we give an alternative semantics to the non-normal logic of knowing how proposed by Fervari et al. (2017), based on a class of Kripke neighbor-hood models with both the epistemic relations and neighborhood structures. This alternative semantics is inspired by the same quantifier alternation pattern of ∃∀in the semantics of the know-how modality and the (monotonic) neighborhood semantics for the standard modality. We show that this new semantics is equivalent to the original Kripke semantics in terms of the validities. A key result is a representation theorem showing that the more abstract Kripke neighborhood models can be represented by the concrete Kripke models with action transitions modulo the valid formulas. We prove the completeness of the logic for the neighborhood semantics. The neighborhood semantics can be adapted to other variants of logics of knowing how. It provides us a powerful technical tool to study these logics while preserving the basic semantic intuition.

Knowing How to Plan

Beyond know-thatProceeding PaperTARK
Yanjun Li, Yanjing Wang
in Proceedings of TARK2021
Publication year: 2021

Various planning-based know-how logics have been proposed and studied in the recent literature. In this paper, we use such a logic to do know-how-based planning via model checking. In particular, we can handle the higher-order epistemic planning involving know-how formulas as the goal, e.g., find a plan to make sure p such that the adversary does not know how to make p false afterward. We give a PTIME-algorithm for the model checking problem over finite epistemic transition systems and axiomatize the logic under the assumption of perfect recall.

Hypergraphs, local reasoning, and weakly aggregative modal logic

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

Abstract. This paper connects the following three apparently unrelated topics: an epistemic framework fighting logical omniscience, a class of generalized graphs without the arities of relations, and a family of nonnormal modal logic rejecting the aggregative axiom. Through neighborhood frames as their meeting point, we show that, among many completeness results obtained in this paper, the limit of a family of weakly aggregative logics is both exactly the modal logic of hypergraphs and also the epistemic logic of local reasoning with veracity and positive introspection, which also answers a question left open by Fagin and Halpern (1988). The logics studied are shown to be decidable based on a filtration construction.

De Re Updates

Proceeding PaperTARK
Michael Cohen, Wen Tang, Yanjing Wang
Proceedings of TARK2021
Publication year: 2021

In this paper, we propose a lightweight yet powerful dynamic epistemic logic that not only captures the distinction between de dicto and de re knowledge but also the distinction between de dicto and de re updates. The logic is based on the dynamified version of an epistemic language extended with the assignment operator borrowed from dynamic logic, following the work of Wang and Seligman (2018). We obtain complete axiomatizations for the counterparts of public announcement logic and event-model-based DEL based on new reduction axioms taking care of the interactions between dynamics and assignments.

Bisimulations for Knowing How Logics

Beyond know-thatJournal PaperRSL
Raul Fervari, Fernando R. Velázquez-Quesada, Yanjing Wang
Review of Symbolic Logic (in Press)
Publication year: 2021

As a new type of epistemic logic, the logic of knowing how essentially captures the high-level epistemic reasoning about the knowledge of various plans to achieve certain goals. Existing work focuses on the axiomatizations of such logics. This paper makes the first study of their model theoretical properties, by introducing suitable notions of bisimulation for a family of five logics of knowing how based on various notions of plans. As an application of these notions of bisimulation, we study and compare the expressive power of these logics.

(A preliminary version of this paper was first presented at SR2017.)

A logic of knowing why

Beyond know-thatJournal PaperSynthese
Xu, Chao and Wang, Yanjing and Studer, Thomas
Synthese, Volume 198, Pages 1259–1285
Publication year: 2021

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.

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 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-thatbundled fragmentsProceeding 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.

 

(largely extended journal version of the TARK2015 paper)

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-thatbundled fragmentsProceeding 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 PaperRSLSelected
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

Notes
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

This short note establishes the equivalence of the indexed semantics by Wang (2006) and the epistemic world semantics of Kaneko and Suzuki (2003) for epistemic logic of bounded depths.

In A Festschrift for Jeroen Groenendijk, Martin Stokhof, and Frank Veltman (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