Logical Omniscience As Infeasibility. Artemov, S. & Kuznets, R. *Annals of Pure and Applied Logic*, 165(1):6–25, 2014. Paper doi abstract bibtex Abstract Logical theories for representing knowledge are often plagued by the so-called 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.

@Article{ak13,
Author = {Artemov, Sergei and Kuznets, Roman },
Title = {{Logical Omniscience As Infeasibility}},
Journal = {Annals of Pure and Applied Logic},
Number = 1,
Pages = {6--25},
Volume = 165,
url = {2013/ak13.pdf},
year = 2014,
issn = {0168-0072},
doi = {http://dx.doi.org/10.1016/j.apal.2013.07.003},
abstract = {Abstract Logical theories for representing knowledge
are often plagued by the so-called 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. }
}

Downloads: 0

{"_id":"mheoeh5cuyMuwRgBe","bibbaseid":"artemov-kuznets-logicalomniscienceasinfeasibility-2014","authorIDs":[],"author_short":["Artemov, S.","Kuznets, R."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Artemov"],"firstnames":["Sergei"],"suffixes":[]},{"propositions":[],"lastnames":["Kuznets"],"firstnames":["Roman"],"suffixes":[]}],"title":"Logical Omniscience As Infeasibility","journal":"Annals of Pure and Applied Logic","number":"1","pages":"6–25","volume":"165","url":"2013/ak13.pdf","year":"2014","issn":"0168-0072","doi":"http://dx.doi.org/10.1016/j.apal.2013.07.003","abstract":"Abstract Logical theories for representing knowledge are often plagued by the so-called 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. ","bibtex":"@Article{ak13,\n Author =\t {Artemov, Sergei and Kuznets, Roman },\n Title =\t {{Logical Omniscience As Infeasibility}},\n Journal =\t {Annals of Pure and Applied Logic},\n Number =\t 1,\n Pages =\t {6--25},\n Volume =\t 165,\n url =\t\t {2013/ak13.pdf},\n year =\t 2014,\n issn =\t {0168-0072},\n doi =\t\t {http://dx.doi.org/10.1016/j.apal.2013.07.003},\n abstract =\t {Abstract Logical theories for representing knowledge\n are often plagued by the so-called Logical\n Omniscience Problem. The problem stems from the\n clash between the desire to model rational agents,\n which should be capable of simple logical\n inferences, and the fact that any logical inference,\n however complex, almost inevitably consists of\n inference steps that are simple enough. This\n contradiction points to the fruitlessness of trying\n to solve the Logical Omniscience Problem\n qualitatively if the rationality of agents is to be\n maintained. We provide a quantitative solution to\n the problem compatible with the two important facets\n of the reasoning agent: rationality and resource\n boundedness. More precisely, we provide a test for\n the logical omniscience problem in a given formal\n theory of knowledge. The quantitative measures we\n use are inspired by the complexity theory. We\n illustrate our framework with a number of examples\n ranging from the traditional implicit representation\n of knowledge in modal logic to the language of\n justification logic, which is capable of spelling\n out the internal inference process. We use these\n examples to divide representations of knowledge into\n logically omniscient and not logically omniscient,\n thus trying to determine how much information about\n the reasoning process needs to be present in a\n theory to avoid logical omniscience. }\n}\n\n\n\n","author_short":["Artemov, S.","Kuznets, R."],"key":"ak13","id":"ak13","bibbaseid":"artemov-kuznets-logicalomniscienceasinfeasibility-2014","role":"author","urls":{"Paper":"http://home.inf.unibe.ch/~brambi/2013/ak13.pdf"},"downloads":0},"bibtype":"article","biburl":"http://home.inf.unibe.ch/~brambi/ltg.bib","creationDate":"2020-02-26T09:06:59.054Z","downloads":0,"keywords":[],"search_terms":["logical","omniscience","infeasibility","artemov","kuznets"],"title":"Logical Omniscience As Infeasibility","year":2014,"dataSources":["jFQMeatnEb8qn3qdH"]}