Type
Text
Type
Dissertation
Advisor
Michael Kifer. Yanhong A. Liu. | David S. Warren | Christopher A. Welty.
Date
2011-05-01
Keywords
Deductive Databases, Dynamic Knowledge Bases, Logic Programming, Programming Languages | Computer Science
Department
Department of Computer Science
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/71600
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
Transaction Logic is an extension of classical predicate calculus for representing declarative and procedural knowledge in logic programming, databases, and artificial intelligence. Since it provides a logical foundation for the phenomenon of state changes, it has been successful in areas as diverse as workflows, planning, reasoning about actions, Web services, security policies, active databases and more. Although a number of implementations of Transaction Logic exist, none is logically complete due to the time and space complexity of such implementations. In the first part of this thesis, we describe an approach for performing actions in the logic, which has better complexity and termination properties via a logically complete tabling evaluation strategy. Then we describe a series of optimizations, which make this algorithm practical and analyze their performance on a set of benchmarks. Our performance evaluation study shows that the tabling algorithm can scale well both in time and space. In the second part of the thesis, we extend Transaction Logic in the direction of defeasible reasoning, which has a number of interesting applications, including specification of defaults in action theories and heuristics for directed search in planning. In this setting we show that heuristics expressed as defeasible actions can significantly reduce the search space and thus the execution time and space requirements.
Recommended Citation
Fodor, Paul, "Practical Reasoning with Transaction Logic Programming for Knowledge Base Dynamics" (2011). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 805.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/805