Yanjing Wang
Department of Philosophy Peking University
Journal Paper
Publication Types:
Knowing How to Plan about Planning: Higher-order and Meta-level Epistemic Planning
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 
, 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)
Someone knows that local reasoning on hypergraphs is a weakly aggregative modal logic
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)
Are Bundles Good Deals for First-order Modal Logic?
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).
Quantifier-free Epistemic Term-Modal Logic with Assignment Operator
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
Weakly Aggregative Modal Logic (WAML) is a collection of disguised polyadic modal logics with 
-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 
lacks Craig interpolation. Finally, by model theoretical techniques, we show that an extension of 
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
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, 
reads all my parts are 
, 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
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.
Planning-based knowing how: a unified approach
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
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.
Bisimulations for Knowing How Logics
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
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
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.
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.
A logic of goal-directed knowing how
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)
More for free: A dynamic epistemic framework for conformant planning over transition systems
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 Your Ability
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.
From rules to runs: A dynamic epistemic take on imperfect information games
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.
Contingency and Knowing Whether
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 
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.
Hidden protocols: Modifying our expectations in an evolving world
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)
Book Review: Logical Dynamics of Information and Interaction
Abstract. An extensive review of Johan van Benthem’s book Logical Dynamics of Information and Interaction
Reasoning about agent types and the hardest logic puzzle ever
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
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)
Composing models
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.
A preliminary version of this paper was presented at LOFT 2010.
To know or not to know: Epistemic approaches to security protocol verification
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.