IFIG Research Report
Dauerhafte URI für die Sammlung
Stöbern nach
Auflistung IFIG Research Report nach Autor:in "Ibaraki, Toshihide"
Gerade angezeigt 1 - 2 von 2
Treffer pro Seite
Sortieroptionen
Item Computing intersections of Horn theories for reasoning with models(1998) Eiter, Thomas; Ibaraki, Toshihide; Makino, KazuhisaModelbased 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 loworder 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.Item Decision lists and related Boolean functions(1998) Eiter, Thomas; Ibaraki, Toshihide; Makino, KazuhisaWe consider Boolean functions represented by decision lists, and study their relationships to other classes of Boolean functions. It turns out that the elementary class of 1decision lists has interesting relationships to independently defined classes such as disguised Horn functions, readonce functions, nested differences of concepts, threshold functions, and 2monotonic functions. In particular, 1decision lists coincide with fragments of the mentioned classes. We further investigate the recognition problem for this class, as well as the extension problem in the context of partially defined Boolean functions (pdBfs). We show that finding an extension of a given pdBf in the class of 1decision lists is possible in linear time. This improves on previous results. Moreover, we present an algorithm for enumerating all such extensions with polynomial delay.