University of Twente Student Theses


Contextual Reasoning - Complexity Analysis and Decision Procedures -

Roelofsen, Floris (2004) Contextual Reasoning - Complexity Analysis and Decision Procedures -.

[img] PDF
Abstract:Formal accounts of contextual reasoning are of great importance for the development of sophisticated Artificial Intelligence theory and applications. This thesis’ contribution to the theory of contextual reasoning is twofold. First, it delineates the computational complexity of contextual reasoning. A first insight is obtained by translating contextual reasoning into a rather simple form of reasoning in bounded modal logic. A more direct and general understanding, as well as more refined complexity results, are established by achieving the so-called bounded model property for contextual satisfiability. Second, the thesis describes two conceptually orthogonal approaches to automatically deciding satisfiability in a contextual setting. Firstly, the bounded model property is exploited so as to encode contextual satisfiability into propositional satisfiability. This approach provides for the implementation of contextual reasoners based on existing propositional Sat solvers. Subsequently, a distributed decision procedure is proposed, which maximally exploits the potential amenity of localizing reasoning and restricting it to relevant contexts only. The latter approach is shown to be computationally superior to the former translation based procedure, and can be implemented using off-the-shelf efficient reasoning procedures.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Interaction Technology MSc (60030)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page