Contextual Reasoning. Complexity Analysis and Decision Procedures.
2004
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
1
Citations
NaN
KQI