Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Computing intersections of Horn theories for reasoning with models

Eiter, Thomas ; Ibaraki, Toshihide ; Makino, Kazuhisa


Zum Volltext im pdf-Format: Dokument 1.pdf (392 KB)


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-285
URL: http://geb.uni-giessen.de/geb/volltexte/1998/28/


Universität Justus-Liebig-Universit√§t Gie√üen
Institut: Institut f√ľr Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 9803 / 1998
Sprache: Englisch
Erstellungsjahr: 1998
Publikationsdatum: 12.07.1998
Kurzfassung auf Englisch: Model­based reasoning has been proposed as an alternative form of representing and accessing logical knowledge bases. In this approach, a knowledge base is represented by a set of characteristic models. In this paper, we consider computational issues when combining logical knowledge bases, which are represented by their characteristic models; in particular, we study taking their logical intersection. We present low­order polynomial time algorithms or prove intractability for the major computation problems in the context of knowledge bases which are Horn theories. In particular, we show that a model of the intersection \Sigma of Horn theories \Sigma 1 ; : : : ; \Sigma l, represented by their characteristic models, can be found in linear time, and that some characteristic model of \Sigma can be found in polynomial time. Moreover, we present an algorithm which enumerates the models of \Sigma with polynomial delay. The analogous problem for the characteristic models is proved to be intractable, even if the possible exponential size of the output is taken into account. Furthermore, we show that approximate computation of the set of characteristic models is difficult as well. Nonetheless, we show that deduction from \Sigma is possible for a large class of queries in polynomial time, while abduction turns out to be intractable. We also consider an extension of Horn theories, and prove
negative results for the basic questions, indicating that an extension of the positive results beyond Horn theories is not immediate.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand