Artemov, Sergei N.; Kuznets, Roman (2014). Logical omniscience as infeasibility. Annals of pure and applied logic, 165(1), pp. 625. Elsevier 10.1016/j.apal.2013.07.003
Text
1s2.0S0168007213001024main.pdf  Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (346kB)  Request a copy 


Text
ak13.pdf  Accepted Version Available under License Publisher holds Copyright. Download (329kB)  Preview 
Logical theories for representing knowledge are often plagued by the socalled Logical Omniscience Problem. The problem stems from the clash between the desire to model rational agents, which should be capable of simple logical inferences, and the fact that any logical inference, however complex, almost inevitably consists of inference steps that are simple enough. This contradiction points to the fruitlessness of trying to solve the Logical Omniscience Problem qualitatively if the rationality of agents is to be maintained. We provide a quantitative solution to the problem compatible with the two important facets of the reasoning agent: rationality and resource boundedness. More precisely, we provide a test for the logical omniscience problem in a given formal theory of knowledge. The quantitative measures we use are inspired by the complexity theory. We illustrate our framework with a number of examples ranging from the traditional implicit representation of knowledge in modal logic to the language of justification logic, which is capable of spelling out the internal inference process. We use these examples to divide representations of knowledge into logically omniscient and not logically omniscient, thus trying to determine how much information about the reasoning process needs to be present in a theory to avoid logical omniscience.
Item Type:  Journal Article (Original Article) 

Division/Institute:  08 Faculty of Science > Institute of Computer Science (INF) > Logic and Theory Group (LTG) 08 Faculty of Science > Institute of Computer Science (INF) 
UniBE Contributor:  Artemov, Sergei N. and Kuznets, Roman 
Subjects:  000 Computer science, knowledge & systems 500 Science > 510 Mathematics 
ISSN:  01680072 
Publisher:  Elsevier 
Language:  English 
Submitter:  Florian Ranzi 
Date Deposited:  26 Jan 2015 09:24 
Last Modified:  21 Sep 2015 09:51 
Publisher DOI:  10.1016/j.apal.2013.07.003 
BORIS DOI:  10.7892/boris.61795 
URI:  http://boris.unibe.ch/id/eprint/61795 