Not available / text

Thesis (Ph. D.)--University of Texas at Austin, 2003. / Vita. Includes bibliographical references. Available also from UMI Company.

This dissertation conducts an investigation into nonmonotonic reasoning---forms of reasoning which allow defeasible inferences arrived at in the absence of complete information, and which, when additional information is acquired, may need to be revoked. In contrast to the mathematical notion of consequence which is based on proof---mathematical proofs, once established, are beyond reproach, no matter what additional information is acquired---nonmonotonic forms of reasoning are often employed in Artificial Intelligence, where generally only incomplete information is available, and often 'working' inferences need to be made; e.g. default inferences. The platform on which this analysis of nonmonotonic reasoning is carried out is conditional logic; a relative of modal logic. This thesis explores notions of consequence formulated in conditional logic, and explores its possible-worlds semantics, and its connection to nonmonotonic consequence relations. In particular, the notion of default consequence is explored, receiving the interpretation that something is inferred to be true by default if it holds in a `majority' of possible worlds. A number of accounts of majority-based reasoning appear in the literature. However, it is argued that some of the more well known accounts have counter-intuitive properties. An alternative definition of `majorities' is furnished, and both modal and conditional formulations of this form of inference are given and compared---favourably---with similar approaches in the literature. A second, traditional problem of reasoning in Artificial Intelligence is tackled in this thesis: reasoning about action. The treatment presented is again based on conditional logic, but also incorporates an account of dynamic logic. The semantics proposed approaches the frame problem from a different perspective; the familiar `minimal change' approach is generalised to an account based on the principle known as Occam's Razor. The conditional introduced proves to be a valuable contribution to the account given---which again is compared, and contrasted with other approaches in the literature---accommodating a causal approach to the problem of correctly determining the indirect effects of an action.

This dissertation conducts an investigation into nonmonotonic reasoning---forms of reasoning which allow defeasible inferences arrived at in the absence of complete information, and which, when additional information is acquired, may need to be revoked. In contrast to the mathematical notion of consequence which is based on proof---mathematical proofs, once established, are beyond reproach, no matter what additional information is acquired---nonmonotonic forms of reasoning are often employed in Artificial Intelligence, where generally only incomplete information is available, and often 'working' inferences need to be made; e.g. default inferences. The platform on which this analysis of nonmonotonic reasoning is carried out is conditional logic; a relative of modal logic. This thesis explores notions of consequence formulated in conditional logic, and explores its possible-worlds semantics, and its connection to nonmonotonic consequence relations. In particular, the notion of default consequence is explored, receiving the interpretation that something is inferred to be true by default if it holds in a `majority' of possible worlds. A number of accounts of majority-based reasoning appear in the literature. However, it is argued that some of the more well known accounts have counter-intuitive properties. An alternative definition of `majorities' is furnished, and both modal and conditional formulations of this form of inference are given and compared---favourably---with similar approaches in the literature. A second, traditional problem of reasoning in Artificial Intelligence is tackled in this thesis: reasoning about action. The treatment presented is again based on conditional logic, but also incorporates an account of dynamic logic. The semantics proposed approaches the frame problem from a different perspective; the familiar `minimal change' approach is generalised to an account based on the principle known as Occam's Razor. The conditional introduced proves to be a valuable contribution to the account given---which again is compared, and contrasted with other approaches in the literature---accommodating a causal approach to the problem of correctly determining the indirect effects of an action.

Typescript. Includes vita and abstract. Includes bibliographical references (leaves 132-136) Also available online in Scholars' Bank; and in ProQuest, free to University of Oregon users.

This thesis is an investigation into the foundations of reasoning with default rules as presented by Reiter in his seminal 1980 article: `A Logic for Default Reasoning'. In being such, it opens up with a critical appraisal of the logical underpinnings of Reiter's presentation of the main elements of reasoning with default rules. More precisely, following Reiter's presentation, it discusses the concept of a default rule in comparison with that of a rule of inference, the concept of an extension in comparison with that of a theory, and the concept of `being a consequence of' for reasoning with default rules. Contrary to the commonly perceived view, the argument put forth is that such a context does not provide sensible logical foundation for reasoning with default rules. As a result, this thesis argues for an alternative interpretation to what is captured by default rules, what is captured by extensions, and what `being a consequence of' for reasoning with default rules amounts to. In particular, it proposes to treat default rules as premiss-like objects standing for assertions made tentatively, to treat extensions as interpretation structures of a syntactical kind, and to bring the concept of `being a consequence of' for reasoning with default rules into the foreground by formulating a suitable notion of an entailment relation and its ensuing logical system. Accounting for the fact that in any logical system it is important to have at hand mechanisms for formulating proofs and for structuring large theories, this thesis presents a tableaux based proof calculus for reasoning with default rules and it explores some mappings notions related to the structuring of default presentations, i.e., presentations in the context of reasoning with default rules. / Thesis / Doctor of Philosophy (PhD) / This thesis is an investigation into the foundations of reasoning with default rules as presented by Reiter in his seminal 1980 article: `A Logic for Default Reasoning'. A first very general problem definition for this Ph.D. thesis is raised by the following question: Can reasoning with default rules, as presented in Reiter's seminal 1980 article: `A Logic for Default Reasoning', be understood as a logic for non-monotonic reasoning? This thesis presents a rationale for the formulation of such a question and a possible answer for it. On the more technical side, this thesis presents a proof calculus for a particular formulation of a logic for reasoning with default rules, as well as some mapping concepts for structuring presentations defined on this logic.

The aim of this thesis is to study the role played by negation in databases and to develop data models that can handle inconsistent and incomplete information. We develop models that also allow incompleteness through disjunctive information under both the CWA and the OWA in relational databases. In the area of logic programming, extended logic programs allow explicit representation of negative information. As a result, a number of extended logic programs have an inconsistent semantics. We present a translation of extended logic programs to normal logic programs that is more tolerant to inconsistencies. Extended logic programs have also been used widely in order to compute the repairs of an inconsistent database. We present some preliminary ideas on how source information can be incorporated into the repair program in order to produce a subset of the set of all repairs based on a preference for certain sources over others.

Not available / text

Thesis (Ph. D.)--University of Texas at Austin, 2005. / Supervisor: Vladimir Lifschitz. Vita. Includes bibliographical references.

xii, 136 p. : ill. A print copy of this thesis is available through the UO Libraries. Search the library catalog for the location and call number. / Many algorithms are known to work well in practice on a variety of different problem instances. Reusing existing algorithms for problems besides the one that they were designed to solve is often quite valuable. This is accomplished by transforming an instance of the new problem into an input for the algorithm and transforming the output of the algorithm into the correct answer for the new problem. To capitalize on the efficiency of the algorithm, it is essential that these transformations are efficient. Clearly not all problems will have efficient transformations to a particular algorithm so there are limitations on the scope of an algorithm. There is no previous study of which I am aware on determining the capability of an algorithm in terms of the complexity of problems that it can be used to solve. Two examples of this concept will be presented in proving the exact capability of the most well known algorithms for solving Satisfiability (SAT) and for solving Quantified Boolean Formula (QBF). The most well known algorithm for solving SAT is called DPLL. It has been well studied and is continuously being optimized in an effort to develop faster SAT solvers. The amount of work being done on optimizing DPLL makes it a good candidate for solving other problems. The notion of algorithm capability proved useful in applying DPLL to two areas of AI: Planning and Nonmonotonic Reasoning. Planning is PSPACE Complete in general, but NP Complete when restricted to problems that have polynomial length plans. Trying to optimize the plan length or introducing preferences increases the complexity of the problem. Despite the fact that these problems are harder than SAT, they are with in the scope of what DPLL can handle. Most problems in nonmonotonic reasoning are also harder than SAT. Despite this fact, DPLL is a candidate solution for nonmonotonic logics. The complexity of nonmonotonic reasoning in general is beyond the scope of what DPLL can handle. By knowing the capability of DPLL, one can analyze subsets of nonmonotonic reasoning that it can be used to solve. For example, DPLL is capable of solving the problem of model checking in normal default logic. Again, this problem is harder than SAT, but can still be solved with a single call to a SAT solver. The idea of algorithm capability led to the fascinating discovery that SAT solvers can solve problems that are harder than SAT. / Advisers: Matthew Ginsberg, Christopher Wilson