Contextual Reasoning - Complexity Analysis and Decision Procedures -

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

[img]
Preview
PDF
4MB
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:Human Media Interaction MSc (60030)
Link to this item:http://purl.utwente.nl/essays/62562
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page