Deductive Inference for the Interiors and Exteriors of Horn Theories (2009)
Makino, Kazuhisa, Ono, Hirotaka
In this paper, we investigate the deductive inference for the interiors and exteriors of Horn knowledge bases, where the interiors and exteriors were introduced by Makino and Ibaraki to study...
Deductive Inference for the Interiors and Exteriors of Horn Theories (2008)
Makino, Kazuhisa, Ono, Hirotaka, 牧野, 和久, 小野, 廣隆, マキノ, カズヒサ, オノ, ヒロタカ
Deductive Inference for the Interiors and Exteriors of Horn Theories
Enumerating Cut Conjunctions in Graphs and Related Problems ∗ (2008)
Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino
Let G = (V, E) be an undirected graph, and let B ⊆ V ×V be a collection of vertex pairs. We give an incremental polynomial time algorithm to generate all minimal edge sets X ⊆ E such that every...
Max- and Min-Neighborhood Monopolies ∗ (2008)
Kazuhisa Makino, Masafumi Yamashita, Tiko Kameda
Given a graph G = (V, E) and a set of vertices M ⊆ V, a vertex v ∈ V is said to be controlled by M if the majority of v’s neighbors (including itself) belongs to M. M is called a monopoly in...
Enumerating spanning and connected subsets in graphs and matroids (2008)
Leonid Khachiyan, Leonid Khachiyan, Endre Boros, Endre Boros, Konrad Borys, Konrad Borys, ...
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
On the boolean connectivity problem for horn relations (2008)
Kazuhisa Makino, Kazuhisa Makino, Suguru Tamaki, Suguru Tamaki, Masaki Yamamoto, Masaki Yamamoto
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
Springer. Abduction and the Dualization Problem ⋆ (2008)
Abstract. Computing abductive explanations is an important problem, which has been studied extensively in Artificial Intelligence (AI) and related disciplines. While computing some abductive...
Generating Minimal k-Vertex Connected Spanning Subgraphs (2008)
Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino, Gabor Rudolf
Abstract. We show that minimal k-vertex connected spanning subgraphs of a given graph can be generated in incremental polynomial time for any fixed k. 1
Minimum Transversals in Posi-modular Systems ∗ (2008)
Mariko Sakashita, Kazuhisa Makino, Hiroshi Nagamochi, Satoru Fujishige
Given a system (V, f, d) on a finite set V consisting of two set functions f: 2 V → R and d: 2 V → R, we consider the problem of finding a set R ⊆ V of minimum cardinality such that f(X) ≥...
related monotone generation problems (2008)
Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino
R u t c o r
TRANSFORMATIONS ON REGULAR NONDOMINATED COTERIES AND THEIR APPLICATIONS ∗ (2008)
Abstract. A coterie under an underlying set U is a family of subsets of U such that every pair of subsets has at least one element in common, but neither is a subset of the other. A coterie C under U...
Enumerating spanning and connected subsets in graphs and matroids (2008)
Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino
We show that enumerating all minimal spanning and connected subsets of a given matroid is quasi-polynomially equivalent to the well-known hypergraph transversal problem, and thus can be solved in...
Efficient generation of All Regular (2008)
Non-dominated Coteries, Kazuhisa Makino
A coterie is a family of subsets such that every pair of subsets in it has at least one element in common but neither is a subset of the other. We introduce an operator σ, which transforms a ND...
Theoretical Computer Science, to appear. Decision Lists and Related Boolean Functions ¢¡¤£ (2008)
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
We 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 1-decision lists has...
Generating Cut Conjunctions in Graphs and Related Problems (2008)
Khachiyan, Leonid, Boros, Endre, Borys, Konrad, Elbassioni, Khaled, Gurvich, Vladimir, Makino, Kazuhisa
On Satisfiability of Partially Defined Double and Bidual Horn Functions (extended abstract) (2007)
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
Introduction A partially defined Boolean function (pdBF) is a natural generalization of the familiar concept of Boolean function, by allowing that the function value on some vectors is unknown [5]....
Abtg Wissensbasierte Systeme, Generating All Abductive, Thomas Eiter, Thomas Eiter, Kazuhisa Makino, Kazuhisa Makino
www.kr.tuwien.ac.at
NEW RESULTS ON MONOTONE DUALIZATION AND GENERATING HYPERGRAPH TRANSVERSALS (2007)
Abtg Wissensbasierte Systeme, Hypergraph Transversals, Kazuhisa Makino, Thomas Eiter, Thomas Eiter, Georg Gottlob, ...
2 and Kazuhisa Makino 3 Abstract. We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a...
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
We consider the problem of dualizing a Boolean function f given by CNF, i.e., computing a CNF for its dual f d. While this problem is not solvable in quasi-polynomial total time in general (unless...
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
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...
Discrete Applied Mathematics, 96-97:55--88, 1999. Bidual Horn Functions and Extensions (2007)
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
Partially defined Boolean functions (pdBf) (T; F), where T; F f0; 1g n are disjoint sets of true and false vectors, generalize total Boolean functions by allowing that the function values on some...
Running head: On the Dierence of Horn Theories Mailing address: (2007)
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino, Kazuhisa Makino
In this paper, we consider computing the dierence between two Horn theories. This problem may arise, for example, if we take care of a theory change in a knowledge base. In general, the dierence of...
On the Difference of Horn Theories (Extended Abstract) (2007)
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
Abstract. In this paper, we consider computing the difference between two Horn theories. This problem may arise, for example, if we take care of a theory change in a knowledge base. In general, the...
Siam Journal on Computing, 31(1):269-288, 2001. Disjunctions of Horn Theories and their Cores (2007)
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
In this paper, we study issues on disjunctions of propositional Horn theories. In particular, we consider the problems of deciding whether a disjunction of Horn theories is Horn, and, if not,...
Theoretical Computer Science, to appear. Decision Lists and Related Boolean Functions ;y (2007)
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
We 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 1-decision lists has...
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
Abstract. A partially dened Boolean function (pdBf) (T; F) generalizes a Boolean function, by allowing that the function values on some inputs are unknown, where T; F f0; 1g n are disjoint sets of...
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
Abstract. In this paper, we study issues on disjunctions of propositional Horn theories. In particular, we consider deciding whether a disjunction of Horn theories is Horn, and, if not, computing a...
(boros@rutcor.rutgers.edu). Permanent Member. (2007)
In this paper we consider four di#erent definitions for an extension of a partially defined Boolean function in which the input contains some missing bits. We show that, for many general and...
Kazuhisa Makino, Takashi Suda, Hirotaka Ono
are used as a convenient meanst explain given posit [ e examples andnegatE e examples, which is a form ofdat mining and knowledge discovery.StE#fl]b met# ods such as ID3 may providenon-monot85 [...
Springer. Abduction and the Dualization Problem (2007)
Abstract. Computing abductive explanations is an important problem, which has been studied extensively in Artificial Intelligence (AI) and related disciplines. While computing some abductive...
Daya Gaur, Daya Gaur, Kazuhisa Makino, Kazuhisa Makino
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
Enumerating disjunctions and conjunctions of paths and cuts in reliability theory (2007)
Khachiyan, Leonid, Boros, Endre, Elbassioni, Khaled, Gurvich, Vladimir, Makino, Kazuhisa
Generating Minimal k-Vertex Connected Spanning Subgraphs (2007)
Boros, Endre, Borys, Konrad, Elbassioni, Khaled, Makino, Kazuhisa, Rudolf, Gabor
Enumerating Spanning and Connected Subsets in Graphs and Matroids (2007)
Khachiyan, Leonid, Boros, Endre, Borys, Konrad, Elbassioni, Khaled, Gurvich, Vladimir, Makino, Kazuhisa
Fujishige: Minimum cost source location problems with flow requirements (2006)
Mariko Sakashita, Mariko Sakashita, Kazuhisa Makino, Kazuhisa Makino, Satoru Fujishige, Satoru Fujishige
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
COMPUTATIONAL ASPECTS OF MONOTONE DUALIZATION: A BRIEF SURVEY (2006)
Ab Wissensbasierte Systeme, Thomas Eiter, Kazuhisa Makino, Georg Gottlob, Thomas Eiter, Kazuhisa Makino, ...
Abstract.Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including Computer Science,...
Enumerating Spanning and Connected Subsets in Graphs and Matroids (2006)
Khachiyan, Leonid, Boros, Endre, Borys, Konrad, Elbassioni, Khaled, Gurvich, Vladimir, Makino, Kazuhisa, ...
We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this...
Fujishige: Minimizing a monotone concave function with laminar covering constraints (2005)
Mariko Sakashita, Mariko Sakashita, Kazuhisa Makino, Kazuhisa Makino, Satoru Fujishige, Satoru Fujishige
The METR technical reports are published as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the...
Enumerating Cut Conjunctions in Graphs and Related Problems (2005)
Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino F, ...
R u t c o r
On the Complexity of Some Enumeration Problems for Matroids (2005)
Khachiyan, Leonid, Boros, Endre, Elbassioni, Khaled, Gurvich, Vladimir, Makino, Kazuhisa
Generating Paths and Cuts in Multi-pole (Di)graphs (2004)
Boros,Endre, Elbassioni,Khaled, Gurvich,Vladimir, Khachiyan,Leonid, Makino,Kazuhisa
Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set of (source-sink) pairs of vertices of G, an important problem that arises in the computation of network...
Generating Paths and Cuts in Multi-pole (Di)graphs (2004)
Boros, Endre, Elbassioni, Khaled, Gurvich, Vladimir, Khachiyan, Leonid, Makino, Kazuhisa, Fiala, Jirí, ...
Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set of (source-sink) pairs of vertices of G, an important problem that arises in the computation of network...
New Algorithms for Enumerating All Maximal Cliques (2004)
Abstract. In this paper, we consider the problems of generating all maximal (bipartite) cliques in a given (bipartite) graph G = (V, E) with n vertices and m edges. We propose two algorithms for...
Generating Paths and Cuts in Multi-pole (Di)graphs (2004)
Boros, Endre, Elbassioni, Khaled, Gurvich, Vladimir, Khachiyan, Leonid, Makino, Kazuhisa, Fiala, Jirí, ...
Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set of (source-sink) pairs of vertices of G, an important problem that arises in the computation of network...
Generating all abductive explanations for queries on propositional Horn theories (2003)
Abstract. Abduction is a fundamental mode of reasoning, which has taken on increasing importance in Artificial Intelligence (AI) and related disciplines. Computing abductive explanations is an...
Generating all abductive explanations for queries on propositional Horn theories (2003)
Abstract. Abduction is a fundamental mode of reasoning, which has taken on increasing importance in Artificial Intelligence (AI) and related disciplines. Computing abductive explanations is an...
New Results on Monotone Dualization and Generating Hypergraph Transversals (2002)
Eiter, Thomas, Gottlob, Georg, Makino, Kazuhisa
We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in...
New results on monotone dualization and generating hypergraph transversals (2002)
Thomas Eiter, Georg Gottlob, Kazuhisa Makino
We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in...
On computing all abductive explanations (2002)
We consider the computation of all respectively a polynomial subset of the explanations of an abductive query from a Horn theory, and pay particular attention to whether the query is a positive or...
New results on monotone dualization and generating hypergraph transversals (2002)
Thomas Eiter, Georg Gottlob, Kazuhisa Makino
ac.jp This paper considers the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in...
Dual-Bounded Generating Problems: Partial And Multiple Transversals Of A Hypergraph (2001)
Endre Boros, Vladimir Gurvich, Leonid Khachiyan, KAZUHISA MAKINO
. We consider two natural generalizations of the notion of transversal to a finite hypergraph, arising in data-mining and machine learning, the so called multiple and partial transversals. We show...
Variations on Extending Partially Defined Boolean Functions with Missing Bits (2000)
Endre Boros, Toshihide Ibaraki, Kazuhisa Makino
In this paper we consider four di#erent definitions for an extension of a partially defined Boolean function in which the input contains some missing bits. We show that, for many general and...
Generating Weighted Transversals of a Hypergraph (2000)
Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino
We consider a generalization of the notion of transversal to a nite hypergraph, so called weighted transversals. Given a non-negative weight vector assigned to each hyperedge of the input hypergraph,...
Finding Small Sets of Essential Attributes in Binary Data (2000)
Endre Boros, Endre Boros, Takashi Horiyama, Takashi Horiyama, Toshihide Ibaraki, Toshihide Ibaraki, ...
.We consider the problem of nding support sets (i.e., sets of essential attributes) in a given data set, which consists of n-dimensional binary vectors of positive examples and negative examples. A...
Generating Partial and Multiple Transversals of a Hypergraph (2000)
Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino
. We consider two natural generalizations of the notion of transversal to a finite hypergraph, arising in data-mining and machine learning, the so called multiple and partial transversals. We show...
Finding essential attributes from binary data (2000)
Endre Boros, Takashi Horiyama, Toshihide Ibaraki, Kazuhisa Makino, Mutsunori Yagiura
We consider data sets that consist of n-dimensional binary vectors representing positive and negative examples for some (possibly unknown) phenomenon. A subset S of the attributes (or variables) of...
Computing intersections of Horn theories for reasoning with models (1999)
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
We consider computational issues when combining logical knowledge bases represented by their characteristic models; in particular, we study taking their logical intersection. We present efficient...
Fully Consistent Extensions of Partially Defined Boolean Functions with Missing Bits (1999)
Endre Boros, Toshihide Ibaraki, Kazuhisa Makino
. In this paper we consider four di#erent definitions for an extension of a partially defined Boolean function in which the input contains some missing bits. We show that, for many general and...
Logical Analysis of Binary Data with Missing Bits (1999)
Endre Boros, Toshihide Ibaraki, Kazuhisa Makino, F Where
We model a given pair of sets of positive and negative examples, each of which may contain missing components, as a partially defined Boolean function with missing bits (pBmb) ( T , F ), where T #...
Dual-Bounded Hypergraphs: Generating Partial and Multiple Transversals (1999)
Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino
We consider two natural generalizations of the notion of transversal to a nite hypergraph, so called multiple and partial transversals. We show that the hypergraphs of all multiple and all partial...
Interior and exterior functions of positive Boolean functions (1999)
Kazuhisa Makino, H. Ono, T. Ibaraki
The interior function and exterior function of a Boolean function f are introduced [14] in order to express its stability and robustness properties. In this paper, we investigate the complexity of...
Transformation of Regular Non-Dominated Coteries (1999)
Kazuhisa Makino, Tiko Kameda, D Satisfying Q
A coterie is a family of subsets such that every pair of subsets has at least one element in common but neither is a subset of the other. A coterie C is said to be non-dominated (ND) if there is no...
Disjunction of Horn theories and their cores (1999)
Abtg Wissensbasierte Systeme, Kazuhisa Makino, Thomas Eiter, Thomas Eiter, Toshihide Ibaraki, Toshihide Ibaraki
. In this paper, we study issues on disjunctions of propositional Horn theories. In particular, we consider deciding whether a disjunction of Horn theories is Horn, and, if not, computing a Horn core...
Decision lists and related Boolean functions (1998)
Ibaraki, Toshihide, Eiter, Thomas, Makino, Kazuhisa
We 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...
Computing intersections of Horn theories for reasoning with models (1998)
Ibaraki, Toshihide, Eiter, Thomas, Makino, Kazuhisa
Modelbased 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...
Computing intersections of Horn theories for reasoning with models (1998)
Eiter, Thomas, Ibaraki, Toshihide, Makino, Kazuhisa
Modelbased 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...
Decision lists and related Boolean functions (1998)
Eiter, Thomas, Ibaraki, Toshihide, Makino, Kazuhisa
We 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...
Functional Dependencies in Horn Theories (1998)
Toshihide Ibaraki, Alexander Kogan, Kazuhisa Makino
This paper studies functional dependencies in Horn theories, both when the theory is represented by its clausal form and when it is defined as the Horn envelope of a set of models. We provide...
Functional Dependencies in Horn Theories (1998)
Toshihide Ibaraki, Alexander Kogan, Kazuhisa Makino
This paper studies functional dependencies in Horn theories, both when the theory is represented by its clausal form and when it is defined as the Horn envelope of a set of models. We provide...
Decision Lists and Related Boolean Functions (1998)
Thomas Eiter, Thomas Eiter, Toshihide Ibaraki, Toshihide Ibaraki, Kazuhisa Makino, Kazuhisa Makino
. We 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 1-decision lists has...
Computing Intersections Of Theories For Reasoning With Models (1998)
Thomas Eiter, Thomas Eiter, Toshihide Ibaraki, Toshihide Ibaraki, Kazuhisa Makino, Kazuhisa Makino
. 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...
Decision lists and related boolean functions (1998)
Thomas Eiter, Thomas Eiter, Toshihide Ibaraki, Toshihide Ibaraki, Kazuhisa Makino, Kazuhisa Makino
Abstract. We 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 1-decision lists...
Error-Free and Best-Fit Extensions of Partially Defined Boolean Functions (1997)
Endre Boros, Toshihide Ibaraki, Kazuhisa Makino, Kazuhisa Makino
In this paper, we address a fundamental problem related to the induction of Boolean logic: Given a set of data, represented as a set of binary "true n-vectors" (or "positive...
Extensions of partially defined boolean functions with missing data (1996)
Endre Boros, Endre Boros, Toshihide Ibaraki, Toshihide Ibaraki, Kazuhisa Makino, Kazuhisa Makino
R u t c o r
Boolean Analysis of Incomplete Examples (1996)
Endre Boros, Endre Boros, Toshihide Ibaraki, Toshihide Ibaraki, Kazuhisa Makino, Kazuhisa Makino
.As a form of knowledge acquisition from data, we consider the problem of deciding whether there exists an extension of a partially defined Boolean function with missing data ( ~ T ; ~ F ), where ~ T...
On computing all abductive explanations (preliminary report (1988)
Abtg Wissensbasierte Systeme, Kazuhisa Makino, Thomas Eiter, Thomas Eiter
1 and Kazuhisa Makino 2 Abstract. We consider the computation of all respectively a polynomial subset of the explanations of an abductive query from a Horn theory, and pay particular attention to...