The Experts below are selected from a list of 5025 Experts worldwide ranked by ideXlab platform
Mitsuru Ishizuka - One of the best experts on this subject based on the ideXlab platform.
-
PRICAI - Two Transformations of Clauses into Constraints and Their Properties for Cost-Based Hypothetical Reasoning
Lecture Notes in Computer Science, 2002Co-Authors: Yutaka Matsuo, Mitsuru IshizukaAbstract:This paper describes two ways to transform propositional clauses into mathematical constraints, and gives an overview of mathematical optimization approaches to inference. The first transformation, which translates constraints into linear inequalities, has been applied to cost-based abduction in the past and showed good performance. The second one, which produces nonlinear equalities, is commonly used in other representations, such as SAT. We clarify their differences and advantages, and show the radical performance transition of linear inequalities. We are mainly targeting at cost-based Hypothetical Reasoning (or abduction), but through preprocessing, the discussion has generality.
-
SL method for computing a near-optimal solution using linear and non-linear programming in cost-based Hypothetical Reasoning
Knowledge-Based Systems, 2002Co-Authors: Mitsuru Ishizuka, Yutaka MatsuoAbstract:Hypothetical Reasoning is an important framework for knowledge-based systems, however, its inference time grows exponentially with respect to problem size. In this paper, we present an understandable efficient method called slide-down and lift-up (SL) method which uses a linear programming technique for determining an initial search point and a non-linear programming technique for efficiently finding a near-optimal 0–1 solution. To escape from trapping into local optima, we have developed a new local handler, which systematically fixes a variable to a locally consistent value. Since the behavior of the SL method is illustrated visually, the simple inference mechanism of the method can be easily understood.
-
Two transformations of clauses into constraints and their properties for cost-based Hypothetical Reasoning
Lecture Notes in Computer Science, 2002Co-Authors: Yutaka Matsuo, Mitsuru IshizukaAbstract:This paper describes two ways to transform propositional clauses into mathematical constraints, and gives an overview of mathematical optimization approaches to inference. The first transformation, which translates constraints into linear inequalities, has been applied to cost-based abduction in the past and showed good performance. The second one, which produces nonlinear equalities, is commonly used in other representations, such as SAT. We clarify their differences and advantages, and show the radical performance transition of linear inequalities. We are mainly targeting at cost-based Hypothetical Reasoning (or abduction), but through preprocessing, the discussion has generality.
-
fast Hypothetical Reasoning by parallel processing
Pacific Rim International Conference on Artificial Intelligence, 2000Co-Authors: Yutaka Matsuo, Mitsuru IshizukaAbstract:Cost-based Hypothetical Reasoning is an important framework for knowledgebased systems because it is theoretically founded and useful for many practical problems. Basically, it tries to find the minimum-cost set of hypotheses that is sufficient for proving a given goal. However, since the inference time of Hypothetical Reasoning grows exponentially with respect to problem size, slow inference speed often becomes the most crucial problem in practice. We have developed a new method to efficiently find a near-optimal solution, i.e., a solution whose cost is nearly minimal. This method uses parallel software processors to search for a solution. In order to grasp the search intuitively, we emulate parallel processing on a single processor and develop efficient algorithms. We assume that each variable and each Horn-rule (constraint) is a processor and behaves as follows: a Variable processor sends a message to lower the cost of a solution and a Constraint processor sends a message to satisfy itself. Our approach is realized mathematically by the augmented Lagrangian method, an efficient parallel computation method. A Variable processor has a (prime) variable which takes the value [0,1]. A Constraint processor has also a (dual) variable which represents how strongly the constraint should be considered. The messages and updating procedures are defined by mathematical formulae. This approach has two major advantages. First, we can generalize related methods such as our earlier SL method, the breakout method or Gu's nonlinear optimization method for SAT problems. They are all variants of our approach, obtained by modifying a part of the message to be sent. Second, we can design new algorithms superior to previous algorithms such as SL method. We currently experiment with seven different algorithms of the parallel processor model, and find two algorithms are prominent as to inference time and solution cost. One algorithm is similar to the breakout method except that it considers the cost of the solution. The other is an entirely new algorithm, which adds one new processor to a problematic Horn-rule if search gets stuck in a local minimum. Using this algorithm, we can obtain solutions whose cost on average is lower than that of any other algorithm compared in our experiment.
-
the hyper system knowledge reformation for efficient first order Hypothetical Reasoning
Pacific Rim International Conference on Artificial Intelligence, 2000Co-Authors: Helmut Prendinger, Mitsuru Ishizuka, Tetsu YamamotoAbstract:We present the HYPER system that implements a new approach to knowledge compilation, where function-free first-order acyclic Horn theories are transformed to propositional logic. The compilation method integrates techniques from deductive databases (relevance Reasoning) and theory transformation via unfold/fold transformations, to obtain a compact propositional representation. The transformed theory is more compact than the ground version of the original theory in terms of significantly less and mostly shorter clauses. This form of compilation, called knowledge (base) reformation, is important since the most efficient Reasoning methods are defined for propositional theories, while knowledge is most naturally expressed in a first-order language. In particular, we will show that knowledge reformation allows low-order polynomial time inference to find a near-optimal solution in cost-based first-order Hypothetical Reasoning (or 'abduction') problems. We will also present experimental results that confirm the effectiveness of our compilation method.
Yukio Ohsawa - One of the best experts on this subject based on the ideXlab platform.
-
Networked bubbled propagation: a polynomial-time Hypothetical Reasoning method for computing near-optimal solutions
Artificial Intelligence, 1997Co-Authors: Yukio Ohsawa, Mitsuru IshizukaAbstract:Abstract Hypothetical Reasoning (abduction) is an important knowledge processing framework because of its theoretical basis and its usefulness for solving practical problems including diagnosis, design, etc. In many cases, the most probable hypotheses set for diagnosis or the least expensive one for design is desirable. Cost-based abduction, where a numerical weight is assigned to each hypothesis and an optimal solution hypotheses set with minimal sum of element hypotheses' weights is searched, deals with such problems. However, slow inference speed is its crucial problem: cost-based abduction is NP-complete. In order to achieve a tractable inference of cost-based abduction, we aim at obtaining a nearly, rather than exactly, optimal solution. For this approach, an approximate solution method exploited in mathematical programming is quite beneficial. On the other hand, from the standpoint of knowledge processing, it is also important to realize inference on a network which reflects knowledge structure. Knowledge structure is a fruitful information for an efficient inference. In this paper, we propose an inference method which works on a knowledge network, based on a mechanism similar to the pivot and complement method, an efficient approximate 0–1 integer programming method to find a near-optimal solution within a polynomial time of O(N4), where N is the number of variables or hypotheses. We reformalize this method by a new type of network on which inference is executed by propagating bubbles. This method achieves an inference time of O(N2) by executing each bubble propagation within a small sub-network, i.e., by taking advantage of the knowledge structure.
-
a polynomial time predicate logic Hypothetical Reasoning by networked bubble propagation method
AI '96 Proceedings of the 11th Biennial Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelli, 1996Co-Authors: Yukio Ohsawa, Mitsuru IshizukaAbstract:Hypothetical Reasoning is a useful knowledge-processing framework applicable to many problems including system diagnosis, design, etc. However, due to its non-monotonic inference nature, it takes exponential computation-time to find a solution hypotheses-set to prove a given goal. This is also true for cost-based Hypothetical Reasoning to find an optimal solution with minimal cost. As for the Hypothetical Reasoning expressed in propositional logic, since it is easily transformed into 0–1 integer programming problem, a polynomial-time method finding a near-optimal solution has been developed so far by employing an approximate solution method of 0–1 integer programming called the Pivot and Complement method. Also, by reforming this method, a network-based inference mechanism called Networked Bubble Propagation (NBP) has been invented by the authors, which allows even faster inference. More importantly, a network-based approach is meaningful, for its potential of being developed extending to a broader framework of knowledge processing. In this paper, we extend the NBP method to dealing with the Hypothetical Reasoning expressed with predicate logic. By constructing a series of knowledge networks, to which the NBP method is applied, in a stepwise manner according to a top-down control, we avoid the excessive expansion of the network size. As a result, we can achieve a polynomial-time inference for computing a near-optimal solution for the cost-based Hypothetical Reasoning in predicate-logic knowledge.
-
Canadian Conference on AI - A Polynomial-Time Predicate-Logic Hypothetical Reasoning by Networked Bubble Propagation Method
Lecture Notes in Computer Science, 1996Co-Authors: Yukio Ohsawa, Mitsuru IshizukaAbstract:Hypothetical Reasoning is a useful knowledge-processing framework applicable to many problems including system diagnosis, design, etc. However, due to its non-monotonic inference nature, it takes exponential computation-time to find a solution hypotheses-set to prove a given goal. This is also true for cost-based Hypothetical Reasoning to find an optimal solution with minimal cost. As for the Hypothetical Reasoning expressed in propositional logic, since it is easily transformed into 0–1 integer programming problem, a polynomial-time method finding a near-optimal solution has been developed so far by employing an approximate solution method of 0–1 integer programming called the Pivot and Complement method. Also, by reforming this method, a network-based inference mechanism called Networked Bubble Propagation (NBP) has been invented by the authors, which allows even faster inference. More importantly, a network-based approach is meaningful, for its potential of being developed extending to a broader framework of knowledge processing. In this paper, we extend the NBP method to dealing with the Hypothetical Reasoning expressed with predicate logic. By constructing a series of knowledge networks, to which the NBP method is applied, in a stepwise manner according to a top-down control, we avoid the excessive expansion of the network size. As a result, we can achieve a polynomial-time inference for computing a near-optimal solution for the cost-based Hypothetical Reasoning in predicate-logic knowledge.
-
networked bubble propagation method as a polynomial time Hypothetical Reasoning for computing near optimal solution
Systems and Computers in Japan, 1995Co-Authors: Yukio Ohsawa, Mitsuru IshizukaAbstract:Hypothetical Reasoning is important to knowledge system framework due to both its theoretical basis and its usefulness in solving practical problems including diagnosis, design, etc. One crucial problem with Hypothetical Reasoning is, however, its slow inference speed. To achieve practical or tractable speed, an approximate solution method of 0-1 integer programming named Pivot and Complement has been applied so far to a cost-based Hypothetical Reasoning, in which a numerical weight is assigned to each possible element hypothesis and an optimal solution hypothesis-set with the minimal sum of its element hypotheses' weights is searched. In this method, all described knowledge is regarded as constraints. Then, the restricted part of knowledge is transformed into inequalities to apply 0-1 integer programming. While the computational complexity of Hypothetical Reasoning is NP-complete or NP-hard, an approximate solution method of 0-1 integer programming allows polynomial inference time in the order of N 4 for finding a near-optimal solution hypothesis, where N is the number of possible element hypotheses. In this paper, in order to understand the mechanism of the foregoing method from the viewpoint of knowledge processing, it is reformalized using a new type of knowledge network. Our new networked method, name Networked Bubble Propagation is shown to have a similar (or superior) performance to the aforementioned one, i.e., the solutions it obtains are as good as those found with the Pivot and Complement method and the inference time is in the order of N 2 . This speed-up is an advantage of considering the knowledge structure of a given problem, thanks to the network.
-
networked bubble propagation method as a polynomial time Hypothetical Reasoning for computing quasi optimal solution
International Conference on Tools with Artificial Intelligence, 1993Co-Authors: Yukio Ohsawa, Mitsuru IshizukaAbstract:A Hypothetical Reasoning is an important knowledge system's framework because of its theoretical basis and its usefulness for practical problems including diagnosis, design, etc. One crucial problem with Hypothetical Reasoning is, however, its slow inference speed. The polynomial-time approximate solution method of equivalent 0-1 integer programming, i.e., pivot and complement method, has been applied to computing Hypothetical Reasoning. However, to achieve further improvement by considering the knowledge structure of a given problem, it is beneficial to have another inference method which can work in the knowledge domain rather than the mathematical programming domain. For this purpose, the above method is reformalized using a new type of network. By taking advantage of the knowledge structure, this network achieves an inference speed in the order of O(N/sup 2/) against N, where N indicates problem size.
Yutaka Matsuo - One of the best experts on this subject based on the ideXlab platform.
-
PRICAI - Two Transformations of Clauses into Constraints and Their Properties for Cost-Based Hypothetical Reasoning
Lecture Notes in Computer Science, 2002Co-Authors: Yutaka Matsuo, Mitsuru IshizukaAbstract:This paper describes two ways to transform propositional clauses into mathematical constraints, and gives an overview of mathematical optimization approaches to inference. The first transformation, which translates constraints into linear inequalities, has been applied to cost-based abduction in the past and showed good performance. The second one, which produces nonlinear equalities, is commonly used in other representations, such as SAT. We clarify their differences and advantages, and show the radical performance transition of linear inequalities. We are mainly targeting at cost-based Hypothetical Reasoning (or abduction), but through preprocessing, the discussion has generality.
-
Two transformations of clauses into constraints and their properties for cost-based Hypothetical Reasoning
Lecture Notes in Computer Science, 2002Co-Authors: Yutaka Matsuo, Mitsuru IshizukaAbstract:This paper describes two ways to transform propositional clauses into mathematical constraints, and gives an overview of mathematical optimization approaches to inference. The first transformation, which translates constraints into linear inequalities, has been applied to cost-based abduction in the past and showed good performance. The second one, which produces nonlinear equalities, is commonly used in other representations, such as SAT. We clarify their differences and advantages, and show the radical performance transition of linear inequalities. We are mainly targeting at cost-based Hypothetical Reasoning (or abduction), but through preprocessing, the discussion has generality.
-
SL method for computing a near-optimal solution using linear and non-linear programming in cost-based Hypothetical Reasoning
Knowledge-Based Systems, 2002Co-Authors: Mitsuru Ishizuka, Yutaka MatsuoAbstract:Hypothetical Reasoning is an important framework for knowledge-based systems, however, its inference time grows exponentially with respect to problem size. In this paper, we present an understandable efficient method called slide-down and lift-up (SL) method which uses a linear programming technique for determining an initial search point and a non-linear programming technique for efficiently finding a near-optimal 0–1 solution. To escape from trapping into local optima, we have developed a new local handler, which systematically fixes a variable to a locally consistent value. Since the behavior of the SL method is illustrated visually, the simple inference mechanism of the method can be easily understood.
-
fast Hypothetical Reasoning by parallel processing
Pacific Rim International Conference on Artificial Intelligence, 2000Co-Authors: Yutaka Matsuo, Mitsuru IshizukaAbstract:Cost-based Hypothetical Reasoning is an important framework for knowledgebased systems because it is theoretically founded and useful for many practical problems. Basically, it tries to find the minimum-cost set of hypotheses that is sufficient for proving a given goal. However, since the inference time of Hypothetical Reasoning grows exponentially with respect to problem size, slow inference speed often becomes the most crucial problem in practice. We have developed a new method to efficiently find a near-optimal solution, i.e., a solution whose cost is nearly minimal. This method uses parallel software processors to search for a solution. In order to grasp the search intuitively, we emulate parallel processing on a single processor and develop efficient algorithms. We assume that each variable and each Horn-rule (constraint) is a processor and behaves as follows: a Variable processor sends a message to lower the cost of a solution and a Constraint processor sends a message to satisfy itself. Our approach is realized mathematically by the augmented Lagrangian method, an efficient parallel computation method. A Variable processor has a (prime) variable which takes the value [0,1]. A Constraint processor has also a (dual) variable which represents how strongly the constraint should be considered. The messages and updating procedures are defined by mathematical formulae. This approach has two major advantages. First, we can generalize related methods such as our earlier SL method, the breakout method or Gu's nonlinear optimization method for SAT problems. They are all variants of our approach, obtained by modifying a part of the message to be sent. Second, we can design new algorithms superior to previous algorithms such as SL method. We currently experiment with seven different algorithms of the parallel processor model, and find two algorithms are prominent as to inference time and solution cost. One algorithm is similar to the breakout method except that it considers the cost of the solution. The other is an entirely new algorithm, which adds one new processor to a problematic Horn-rule if search gets stuck in a local minimum. Using this algorithm, we can obtain solutions whose cost on average is lower than that of any other algorithm compared in our experiment.
-
PRICAI - Fast Hypothetical Reasoning by parallel processing
PRICAI 2000 Topics in Artificial Intelligence, 2000Co-Authors: Yutaka Matsuo, Mitsuru IshizukaAbstract:Cost-based Hypothetical Reasoning is an important framework for knowledgebased systems because it is theoretically founded and useful for many practical problems. Basically, it tries to find the minimum-cost set of hypotheses that is sufficient for proving a given goal. However, since the inference time of Hypothetical Reasoning grows exponentially with respect to problem size, slow inference speed often becomes the most crucial problem in practice. We have developed a new method to efficiently find a near-optimal solution, i.e., a solution whose cost is nearly minimal. This method uses parallel software processors to search for a solution. In order to grasp the search intuitively, we emulate parallel processing on a single processor and develop efficient algorithms. We assume that each variable and each Horn-rule (constraint) is a processor and behaves as follows: a Variable processor sends a message to lower the cost of a solution and a Constraint processor sends a message to satisfy itself. Our approach is realized mathematically by the augmented Lagrangian method, an efficient parallel computation method. A Variable processor has a (prime) variable which takes the value [0,1]. A Constraint processor has also a (dual) variable which represents how strongly the constraint should be considered. The messages and updating procedures are defined by mathematical formulae. This approach has two major advantages. First, we can generalize related methods such as our earlier SL method, the breakout method or Gu's nonlinear optimization method for SAT problems. They are all variants of our approach, obtained by modifying a part of the message to be sent. Second, we can design new algorithms superior to previous algorithms such as SL method. We currently experiment with seven different algorithms of the parallel processor model, and find two algorithms are prominent as to inference time and solution cost. One algorithm is similar to the breakout method except that it considers the cost of the solution. The other is an entirely new algorithm, which adds one new processor to a problematic Horn-rule if search gets stuck in a local minimum. Using this algorithm, we can obtain solutions whose cost on average is lower than that of any other algorithm compared in our experiment.
Alessandro Provetti - One of the best experts on this subject based on the ideXlab platform.
-
Hypothetical Reasoning about actions from situation calculus to event calculus
Computational Intelligence, 1996Co-Authors: Alessandro ProvettiAbstract:Hypothetical Reasoning about actions is the activity of preevaluating the effect of performing actions in a changing domain; this Reasoning underlies applications of knowledge representation, such as planning and explanation generation. Action effects are often specified in the language of situation calculus, introduced by McCarthy and Hayes in 1969. More recently, the event calculus has been defined to describe actual actions, i.e., those that have occurred in the past, and their effects on the domain. Altough the two formalisms share the basic ontology of atomic actions and fluents, situation calculus cannot represent actual actions while event calculus cannot represent hypotethical actions. In this article, the language and the axioms of event calculus are extended to allow representing and Reasoning about Hypothetical actions, performed either at the present time or in the past, altough counterfactuals are not supported. Both event calculus and its extension are defined as logic programs so that theories are readily adaptable for Prolog query interpretation. For a reasonably large class of theories and queries, Prolog interpretation is shown to be sound and complete w.r.t. the main semantics for logic programs.
-
TIME - Hypothetical Reasoning from Situation Calculus to Event Calculus.
1994Co-Authors: Alessandro ProvettiAbstract:Pinto and Reiter have argued that the Sit uation Calculus improved with time han dling axioms subsumes the features of lin ear time temporal formalisms such as Event Calculus and Interval Logic In this note we nd answers to some of their re marks by showing a modi ed version of Event Calculus that seems to match Sit uation Calculus handling of Hypothetical Reasoning and projection Further consid eration on semantics and expressive power of Event Calculus put forward by Pinto and Reiter are discussed in the light of re cent proposal for an unifying semantics for languages for time and actions
-
Hypothetical Reasoning from situation calculus to event calculus
TIME, 1994Co-Authors: Alessandro ProvettiAbstract:Pinto and Reiter have argued that the Sit uation Calculus improved with time han dling axioms subsumes the features of lin ear time temporal formalisms such as Event Calculus and Interval Logic In this note we nd answers to some of their re marks by showing a modi ed version of Event Calculus that seems to match Sit uation Calculus handling of Hypothetical Reasoning and projection Further consid eration on semantics and expressive power of Event Calculus put forward by Pinto and Reiter are discussed in the light of re cent proposal for an unifying semantics for languages for time and actions
Haruhiko Kimura - One of the best experts on this subject based on the ideXlab platform.
-
A Speedup Algorithm for Repetition of Hypothetical Reasoning
Journal of Advanced Computational Intelligence and Intelligent Informatics, 2006Co-Authors: Haruhiko Kimura, Tadanobu Misawa, Koji Abe, Yasuhiro OgoshiAbstract:This paper presents performance evaluations of a speedup method for Hypothetical Reasoning to a first-order predicate logic knowledge base in the case when Reasoning is executed repeatedly replacing Hypothetical knowledge and keeping background knowledge and the goal intact. The proposed method consists of substituting hypotheses for predicate knowledge which has recursive structures, deriving bit patterns of solutions from background knowledge and the goal in advance when all the hypotheses are true, and finding actual solutions from inclusion relation with bit patterns of Hypothetical knowledge.
-
high speed consistency checking for Hypothetical Reasoning systems using inference path network
Systems and Computers in Japan, 2002Co-Authors: Haruhiko Kimura, Sadaki Hirose, Hidetaka NamboAbstract:Hypothetical Reasoning is popular in fault diagnostics and design systems, but slow Reasoning speed is its drawback. The goal of the current study is developing Hypothetical Reasoning based on inference path network, which would overcome this drawback. In Hypothetical Reasoning systems based on inference path network, there is much room for improvement regarding the computing costs of connotation processing and consistency checking. The authors of this study demonstrate improvement ideas regarding one of these problems, namely, consistency checking. First, the authors obtained necessary and sufficient conditions under which inconsistencies occur during hypothesis composition. Based on the obtained results, the authors proposed an algorithm for speeding up the process of consistency checking. Processing with this algorithm in its core consists in transforming the inference path network in such a way that inconsistencies do not occur during the hypothesis composition, under the condition of unchanged solution hypotheses. The efficiency of this algorithm was confirmed by tests. © 2002 Wiley Periodicals, Inc. Syst Comp Jpn, 33(9): 109–118, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.1157
-
High‐speed consistency checking for Hypothetical Reasoning systems using inference path network
Systems and Computers in Japan, 2002Co-Authors: Haruhiko Kimura, Sadaki Hirose, Hidetaka NamboAbstract:Hypothetical Reasoning is popular in fault diagnostics and design systems, but slow Reasoning speed is its drawback. The goal of the current study is developing Hypothetical Reasoning based on inference path network, which would overcome this drawback. In Hypothetical Reasoning systems based on inference path network, there is much room for improvement regarding the computing costs of connotation processing and consistency checking. The authors of this study demonstrate improvement ideas regarding one of these problems, namely, consistency checking. First, the authors obtained necessary and sufficient conditions under which inconsistencies occur during hypothesis composition. Based on the obtained results, the authors proposed an algorithm for speeding up the process of consistency checking. Processing with this algorithm in its core consists in transforming the inference path network in such a way that inconsistencies do not occur during the hypothesis composition, under the condition of unchanged solution hypotheses. The efficiency of this algorithm was confirmed by tests. © 2002 Wiley Periodicals, Inc. Syst Comp Jpn, 33(9): 109–118, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.1157
-
A proposal to reduce cumulative Reasoning time in Hypothetical Reasoning
Systems and Computers in Japan, 1999Co-Authors: Hideaki Nobata, Haruhiko Kimura, Sadaki HiroseAbstract:Considered in this paper is a method to reduce cumulative execution time in Hypothetical Reasoning using inference-path network. Logic-based Hypothetical Reasoning provides an efficient framework that can be applied to such areas as diagnostics and design, but in so doing, the Reasoning speed may prove insufficient. This problem seems to be solvable by using partial Hypothetical knowledge. In this case, more than one iteration with partial Hypothetical knowledge may be required to find a solution. Some existing techniques involve iterative Reasoning within the same knowledge base while varying the Hypothetical knowledge; networks are generated as necessary, and hypotheses are synthesized at each iteration. On the contrary, the method proposed in this study involves reduction of execution time by reusing the results of previous Reasoning. Specifically, the cumulative execution time is reduced by applying the concept of stage, by partially deterring inference-path generation, and by keeping the results of Hypothetical Reasoning. © 1999 Scripta Technica, Syst Comp Jpn, 30(12): 63–71, 1999
-
High speed subsumption processing for Hypothetical Reasoning using inference-path networks
Systems and Computers in Japan, 1997Co-Authors: Haruhiko Kimura, Sadaki Hirose, Kuniyasu TajimaAbstract:Although Hypothetical Reasoning is widely used in fault diagnostics and measurement systems, low processing speed is a serious drawback. The most well-known application is to a Hypothetical Reasoning system using an inference-path network. This system calls for improvement in terms of cost of subsumption processing and insistency checking. In particular, this paper deals with subsumption processing. Necessary and sufficient conditions are formulated for a subsumption to occur and these conditions are then used to propose an algorithm to accelerate subsumption processing. The algorithm is validated experimentally.