Boolean formulas can be used to model real-world facts. In some situation we may havea Boolean formula that closely approximates a real-world fact, but we need to fine-tune itso that it models the real-world fact exactly. This is a problem of theory revision where thetheory is in the form of a Boolean formula. An algorithm is presented for revising a class ofBoolean formulas that are expressible as conjunctions of Horn clauses. Each of the clausesin the formulas considered here has a unique unnegated variable that does not appear inany other clauses, and is not `F'. The revision algorithm uses equivalence and membershipqueries to revise a given formula into a formula that is equivalent to an unknown targetformula having the same set of unnegated variables. The amount of time required by thealgorithm to perform this revision is logarithmic in the number of variables, and polynomialin the number of clauses in the unknown formula. An early version of this work waspresented at the 2003 Midwest Artificial Intelligence and Cognitive Science Conference [4].

Traditional Inductive Logic Programming (ILP) focuses on the setting where the target theory is a generalisation of the observations. This is known as Observational Predicate Learning (OPL). In the Theory Completion setting the target theory is not in the same predicate as the observations (non-OPL). This thesis investigates two alternative simple extensions to traditional ILP to perform non-OPL or Theory Completion. Both techniques perform extraction-case abduction from an existing background theory and one seed observation. The first technique -- Logical Back-propagation -- modifies the existing background theory so that abductions can be achieved by a form of constructive negation using a standard SLD-resolution theorem prover. The second technique -- SOLD-resolution -- modifies the theorem prover, and leaves the existing background theory unchanged. It is shown that all abductions produced by Logical Back-propagation can also be generated by SOLD-resolution; but the reverse does not hold. The implementation using the SOLD-resolution technique -- the ALECTO system -- was applied to the problems of completing context free and context dependant grammars; and learning Event Calculus programs. It was successfully able to learn an Event Calculus program to control the navigation of a real-life robot. The Event Calculus is a formalism to represent common-sense knowledge. It follows that the discovery of some common-sense knowledge was produced with the assistance of a machine.

The ability to change one's beliefs in a rational manner is one of many facets of the abilities of an intelligent agent. Central to any investigation of belief change is the notion of an epistemic state. This dissertation is mainly concerned with three issues involving epistemic states: 1. How should an epistemic state be represented? 2. How does an agent use an epistemic state to perform belief change? 3. How does an agent arrive at a particular epistemic state? With regard to the first question, note that there are many different methods for constructing belief change operations. We argue that semantic constructions involving ordered pairs, each consisting of a set of beliefs and an ordering on the set of "possible worlds" (or equivalently, on the set of basic independent bits of information) are, in an important sense, more fundamental. Our answer to the second question provides indirect support for the use of semantic structures. We show how well-known belief change operations and related structures can be modelled semantically. Furthermore, we introduce new forms of belief change related operations and structures which are all defined, and motivated, in terms of such semantic representational formalisms. These include a framework for unifying belief revision and nonmonotonic reasoning, new versions of entrenchment orderings on beliefs, novel approaches to withdrawal operations, and an expanded view of iterated belief change. The third question is. one which has not received much attention in the belief change literature. We propose to extract extra-logical information from the formal representation of an agent's set of beliefs, which can then be used in the construction of epistemic state. his proposal is just a first approximation, although it seems to have the potential for developing into a full-fledged theory. / Computing / D.Phil.(Computer Science)

The ability to change one's beliefs in a rational manner is one of many facets of the abilities of an intelligent agent. Central to any investigation of belief change is the notion of an epistemic state. This dissertation is mainly concerned with three issues involving epistemic states: 1. How should an epistemic state be represented? 2. How does an agent use an epistemic state to perform belief change? 3. How does an agent arrive at a particular epistemic state? With regard to the first question, note that there are many different methods for constructing belief change operations. We argue that semantic constructions involving ordered pairs, each consisting of a set of beliefs and an ordering on the set of "possible worlds" (or equivalently, on the set of basic independent bits of information) are, in an important sense, more fundamental. Our answer to the second question provides indirect support for the use of semantic structures. We show how well-known belief change operations and related structures can be modelled semantically. Furthermore, we introduce new forms of belief change related operations and structures which are all defined, and motivated, in terms of such semantic representational formalisms. These include a framework for unifying belief revision and nonmonotonic reasoning, new versions of entrenchment orderings on beliefs, novel approaches to withdrawal operations, and an expanded view of iterated belief change. The third question is. one which has not received much attention in the belief change literature. We propose to extract extra-logical information from the formal representation of an agent's set of beliefs, which can then be used in the construction of epistemic state. his proposal is just a first approximation, although it seems to have the potential for developing into a full-fledged theory. / Computing / D.Phil.(Computer Science)