Accumulative knowledge under bounded resources. (13th February 2015)

• Record Type: Journal Article
• Authors: Jamroga, Wojciech; Tabatabaei, Masoud
• Is Part Of: Journal of logic and computation. Volume 28:Number 3(2018)
• Page Start: 581
• Page End: 604
• Publication Date: 2015-02-13
• Subjects: Reasoning about knowledge -- multi-agent systems -- belief update -- resource-bounded agents -- epistemic logic -- temporal logic -- strategic ability; Logic programming -- Periodicals; Logic, Symbolic and mathematical -- Periodicals; Computational complexity -- Periodicals; 005.115
• DOI: 10.1093/logcom/exv003
• Languages: English
• ISSNs: 0955-792X

Abstract

Abstract: A possible purpose of performing an action is to gather information. Such information-collecting actions are usually resource-consuming. The resources needed for performing them can be for example time or memory, but also money, specialized equipment, etc. In this work, we propose a formal framework to study how the ability of an agent to improve its knowledge changes as a result of changing the available resources. We introduce a model for resource-consuming information-collecting actions, and show how the process of accumulating knowledge can be modelled. Based on this model, we propose a modal logic for reasoning about the epistemic abilities of agents. We present some validities of the logic, and show that the model-checking problem sits in the first level of polynomial hierarchy. We also discuss the connection between our framework and classic information theory. More specifically, we show that the notion of uncertainty given by Hartley measure can be seen as a special case of an agent's ability to improve its knowledge using information-collecting actions.