Home  Online Resources  Table of Contents

Journal of Logic and Computation, Volume 8, Issue 6, pp. 855-875: Abstract.

Reasoning about set constraints applied to tractable inference in intuitionistic logic

T Drakengren and P Jonsson

Department of Computer and Information Science, Linkoping University, S-581 83 Linkoping, Sweden, E-mail: {thodr,petej}@ida.liu.se

Automated reasoning about sets has received a considerable amount of interest in the literature. Techniques for such reasoning have been used in, for instance, analyses of programming languages, terminological logics and spatial reasoning. In this paper, we identify a new class of set constraints where checking satisfiability is tractable (i.e. polynomial-time). We show how to use this tractability result for constructing a new tractable fragment of intuitionistic logic. Furthermore, we prove NP-completeness of several other cases of reasoning about sets.


[ Oxford University Press]   [ Oxford Journals]   [ Comments & Feedback]   Copyright© Oxford University Press, 1998.