18018809
Consequence-Finding Based on Ordered Linear Resolution
Since linear resolution with clause ordering is incomplete for consequence-finding, it has been used mainly for proof-finding. In this paper, we re-evaluate consequence-finding. Firstly, consequence-finding is generalized to the problem in which only interesting clauses having a certain property (called characteristic clauses) should be found. Then, we show how adding a skip rule to ordered linear resolution makes it complete for consequence-finding in this general sense. Compared with set-of-support resolution, the proposed method generates fewer clauses to find such a subset of consequences. In the propositional case, this is an elegant tool for computing the prime implicants/implicates. The importance of the results lies in their applicability to a wide class of AI problems including procedures for nonmonotonic and abductive reasoning and truth maintenance systems.
14085435
Specifying Transactions for Extended Abduction
Extended abduction introduced by Inoue and Sakama ( 1995 ) generalizes traditional abduction in the sense that it can compute negative explanations by removing hypotheses from a nonmonotonic background theory, rather than only adding them. Also, it has a mechanism of computing anti-explanations to unexplain negative observations. Such extended abduction not only enhances reasoning ability of traditional abduction but has useful applications to nonmonotonic theory change. In this paper, we study the computational aspect of extended abduction. Given a background theory written in nonmonotonic logic programming, we introduce its transaction program for computing extended abduction. A transaction program is a set of nondeterministic production rules that specify addition and deletion of abductive hypotheses. Abductive explanations are computed by the xpoint of a transaction program using a bottom-up model generation procedure. In the context of databases, a transaction program provides a declarative speci cation of database update.
18453658
Bottom-up Abduction by Model Generation
We investigate two realizations of parallel abductive reasoning systems using the model generation theorem prover MGTP. The first one, called the MGTP + MGTP method, is a co-operative problem-solving architecture in which model generation and consistency checking communicate with each other. There, parallelism is exploited by checking consistencies in parallel. However, since this system consists of two different components, the possibilities for parallelization are limited. In contrast, the other method, called the Skip method, does not separate the inference engine from consistency checking, but realizes both functions in only one MGTP that is used as a generate-and-test mechanism. In this method, multiple models can be kept in distributed memories, thus a great amount of parallelism can be obtained. We also attempt the upside-down meta-interpretation approach for abduction, in which top-down reasoning is simulated by a bottom-up reasoner.
39645731
Problem Solving with Hypothetical Reasoning
43364652
Effective SAT Planning by Speculative Computation
In recent years, SAT planning has been studied actively. In this paper, we propose a new method, called speculative computation, for accelerating the SAT planning. A SATplanner firstly translates a planning problem into the boolean satisfiability (SAT) problem, and secondly solves it by a general-purpose SAT solver. Blackbox [1], which is one of the fastest planning systems in the world, is based on this approach. Given a planning problem, Blackbox performs the following; (i) assumes that the plan length is i (initially, i = 1), (ii) translates the planning problem into a SAT problem P i, and (iii) solves P i. If P i is found to be satisfiable, the Blackbox extracts a plan of length i from the truth assignment satisfying P i. When P i is unsatisfiable, the planner increases the plan length to be i + 1, and returns to (i).
42582726
Computing Preferred Answer Sets in Answer Set Programming
Prioritized logic programs (PLPs) have a mechanism of representing priority knowledge in logic programs. The declarative semantics of a PLP is given as preferred answer sets which are used for representing nonmonotonic reasoning as well as preference abduction. From the computational viewpoint, however, its implementation issues have little been studied and no sound procedure is known for computing preferred answer sets of PLPs. In this paper, we present a sound and complete procedure to compute all preferred answer sets of a PLP in answer set programming. The procedure is based on a program transformation from a PLP to a logic program and is realized on top of any procedure for answer set programming. The proposed technique also extends PLPs to handle dynamic preference and we address its application to legal reasoning.
17773922
A formal adaption method for process descriptions
Requirement to describing software development processes in formal manners has been increased, and demand for altering and tailoring the process descriptions has been emerged. In this paper, we propose a functional language PDL (Process Description Language), designed to describe various development processes under a certain environment. To create and modify the PDL scripts easily and correctly, we propose a method of stepwise refinement from abstract scripts into concrete scripts. By this method, the abstract definitions of software process flow and product flow initially given as function definitions irk PDL, are transformed into the concrete definitions of the tool activations, message displays, and so on. We also discuss an architecture design of a software development environment (Adaptable Software Development Environment), which can be adapted in many ways for designer's requirements.
17693551
Analysis of functional programs to detect run-time garbage cells
We propose a method for detecting the generation of garbage cells by analyzing a source text written in a functional programming language which uses ordinary linked lists to implement list-type values. For a subexpression such as <italic>F</italic>(<italic>G</italic>( . . . )) in a program where the function values of <italic>F</italic> and <italic>G</italic> are of list type, if a cell <italic>c</italic> is created during the computation of <italic>G</italic> and if <italic>c</italic> does not appear in a list-type value of <italic>F</italic>, then <italic>c</italic> becomes a garbage cell at the end of the computation of <italic>F</italic>. We discuss this problem on the basis of formal languages derived from the functional program text and show some sufficient conditions that predict the generation of garbage cells. Also, we give an efficient algorithm to detect at compile time the generation of garbage cells which are linearly linked. We have implemented these algorithms in an experimental LISP system. By executing several sample programs on the system, we conclude that our method is effective in detecting the generation of garbage cells.
6398416
Analysis of the Linux Kernel Evolution Using Code Clone Coverage
Most studies of the evolution of software systems are based on the comparison of simple software metrics. In this paper, we present our preliminary investigation of the evolution of the Linux kernel using code-clone analysis and the code-clone coverage metrics. We examined 136 versions of the stable Linux kernel using a distributed extension of the code clone detection tool CCFinder. The result is shown as a heat map.