Second-order propositional modal logic: expressiveness and completeness results
File(s)
Accepted version
Author(s)
Belardinelli, F
van der Hoek, W
Kuijer, LB
Type
Journal Article
Abstract
In this paper we advance the state-of-the-art on the application of second-order propositional modal logic (SOPML) in the representation of individual and group knowledge, as well as temporal and spatial reasoning. The main theoretical contributions of the paper can be summarised as follows. Firstly, we introduce the language of (multi-modal) SOPML and interpret it on a variety of different classes of Kripke frames according to the features of the accessibility relations and of the algebraic structure of the quantification domain of propositions. We provide axiomatisations for some of these classes, and show that SOPML is unaxiomatisable on the remaining classes. Secondly, we introduce novel notions of (bi)simulations and prove that they indeed preserve the interpretation of formulas in (the universal fragment of) SOPML. Then, we apply this formal machinery to study the expressiveness of Second-order Propositional Epistemic Logic (SOPEL) in representing higher-order knowledge, i.e., the knowledge agents have about other agents’ knowledge, as well as graph-theoretic notions (e.g., 3-colorability, Hamiltonian paths, etc.). The final outcome is a rich formalism to represent and reason about relevant concepts in artificial intelligence, while still having a model checking problem that is no more computationally expensive than that of the less expressive quantified boolean logic.
Date Issued
2018-10-01
Date Acceptance
2018-07-14
Citation
Artificial Intelligence, 2018, 263 (10), pp.3-45
ISSN
0004-3702
Publisher
Elsevier
Start Page
3
End Page
45
Journal / Book Title
Artificial Intelligence
Volume
263
Issue
10
Copyright Statement
© 2018 Elsevier Ltd. All rights reserved. This manuscript is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Licence http://creativecommons.org/licenses/by-nc-nd/4.0/
Subjects
Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science
Modal logic
Knowledge representation
Second-order propositional modal logic
Epistemic logic
Local properties
MULTIAGENT SYSTEMS
TEMPORAL LOGIC
QUANTIFIERS
KNOWLEDGE
Artificial Intelligence & Image Processing
0801 Artificial Intelligence and Image Processing
0802 Computation Theory and Mathematics
1702 Cognitive Sciences
Publication Status
Published
Date Publish Online
2018-07-18