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. (shrink)

Syntactic logics do not suffer from the problems of logical omniscience but are often thought to lack interesting properties relating to epistemic notions. By focusing on the case of rule-based agents, I develop a framework for modelling resource-bounded agents and show that the resulting models have a number of interesting properties.

We introduce a three-tiered framework for modelling and reasoning about agents who (i) can use possibly complete reasoning systems without any restrictions but who nevertheless are (ii) bounded in the sense that they never reach infinitely many results and, finally, who (iii) perform their reasoning in time. This last aspect does not concern so much the time it takes for agents to actually carry out their reasoning, as the time which can bring about external changes in the agents’ states such (...) as arriving of new information or discarding previously available information due to bounds of the agent’s resources. These three aspects are treated with the maximal possible degree of independence from each other. The treatment of layer (iii) can be combined with arbitrary logic at level (ii) which, in turn, can be combined with arbitrary agent logic at level (i). At the level (iii), we discuss briefly the duality (or rather, complementarity) of system descriptions based on actions and transitions, on the one hand, and states and their changes, on the other. We settle for the latter and present a simple language, for describing state changes, which is parameterized by an arbitrary language for describing properties of the states. The language can be viewed as a simple fragment of step logic, admitting however various extensions by appropriate choices of the underlying logic. Alternatively, it can be seen as a very specific fragment of temporal logic (with a variant of ‘until’ or ‘chop’ operator), and is interpreted over dense linear time. The reasoning system presented here is sound, as well as strongly complete and decidable (provided that so is the parameter logic for reasoning about single states). We give the main idea of the completeness proof and suggest a wide range of possible applications, which is a simple consequence of the parametric character of both the language and the reasoning system. We address then in more detail the case of non-omniscient rational agents, (ii). Their models are syntactic structures (sets of available formulae) similar in spirit, though not in the technical formulation, to the models used in other syntax oriented approaches and in active logic. We give a new sound, complete and decidable system for reasoning about such agents. Finally, we illustrate its extensions with the internal reasoning of agents, (i), by equipping them with some example logics. (shrink)

The logical omniscience problem, whereby standard models of epistemic logic treat an agent as believing all consequences of its beliefs and knowing whatever follows from what else it knows, has received plenty of attention in the literature. But many attempted solutions focus on a fairly narrow specification of the problem: avoiding the closure of belief or knowledge, rather than showing how the proposed logic is of philosophical interest or of use in computer science or artificial intelligence. Sentential epistemic logics, as (...) opposed to traditional possible worlds approaches, do not suffer from the problems of logical omniscience but are often thought to lack interesting epistemic properties. In this paper, I focus on the case of rule-based agents, which play a key role in contemporary AI research but have been neglected in the logical literature. I develop a framework for modelling monotonic, nonmonotonic and introspective rule-based reasoners which have limited cognitive resources and prove that the resulting models have a number of interesting properties. An axiomatization of the resulting logic is given, together with completeness, decidability and complexity results. (shrink)