In this paper, a Boolean algebra approach is proposed to encode various acceptability semantics for abstract argumentation frameworks, where each semantics can be equivalently encoded into several Boolean constraint models based on Boolean matrices and a family of Boolean operations between them. Then, we show that these models can be easily translated into logic programs, and can be solved by a constraint solver over Boolean variables. In addition, we propose some querying strategies to accelerate the calculation of the grounded, stable and complete extensions. Finally, we describe an experimental study on the performance of our encodings according to different semantics and querying strategies.

This paper proposes ladder-logic programming model for sensor actuator networks. We also demonstrate optimized operations of them with central controller-based device management (CCDM) architecture. A wireless sensor actuator network consists of distributed wireless nodes, and implementing data streams and data processors onto these wireless nodes has been challenging. System programmers have to describe their instructions by a programming language, and data processors must be placed so that it optimizes, for example, total network traffic. The ladder-logic model enables the programming of them, and CCDM makes various types of optimizations feasible, including the optimization of network traffic, delivery latency, load-balancing and fault-tolerance even though these algorithms are not lightweight. In this paper, we focus on traffic reduction case, and propose two moderately complex algorithms. The experiment has shown that CCDM achieves optimizations even with such moderately complex algorithms.

An elementary formal system, EFS for short, is a kind of logic program over strings, and regarded as a set of rules to generate a language. For an EFS Γ, the language L(Γ) denotes the set of all strings generated by Γ. We consider a new form of EFS, called a restricted two-clause EFS, and denote by rEFS the set of all restricted two-clause EFSs. Then we study the learnability of rEFS in the exact learning model. The class rEFS contains the class of regular patterns, which is extensively studied in Learning Theory. Let Γ* be a target EFS in rEFS of learning. In the exact learning model, an oracle for superset queries answers "yes" for an input EFS Γ in rEFS if L(Γ) is a superset of L(Γ*), and outputs a string in L(Γ*)-L(Γ), otherwise. An oracle for membership queries answers "yes" for an input string w if w is included in L(Γ*), and answers "no", otherwise. We show that any EFS in rEFS is exactly identifiable in polynomial time using membership and superset queries. Moreover, for other types of queries, we show that there exists no polynomial time learning algorithm for rEFS by using the queries. This result indicates the hardness of learning the class rEFS in the exact learning model, in general.

In this paper, we propose an agent architecture for a combination of speculative computation and abduction. Speculative computation is a tentative computation when complete information for performing computation is not obtained. We use a default value to complement such incomplete information. Unlike usual default reasoning, the real value for the information can be obtained during the computation and the computation can be revised on the fly. In the previous work, we applied this technique to handling distributed problem solving under incomplete communication environments in the context of multi-agent systems and proposed correct procedures in abductive logic programming in terms of perfect model semantics. In the previous work, however, we regarded assumptions as defaults and used these assumptions for speculative computation. Thus, we could not perform hypothetical reasoning, that is, the original usage of abduction. In this paper, we extend our framework so that speculative computation and abduction can be both performed. As a result, our procedure becomes an extension of the abductive procedure developed by Kakas and Mancarella augmented by dynamic belief revision mechanism about outside world.

We describe a new inconsistent case which is susceptible to occur while producing consistent answer set using prioritized default logic. We define new semantics for prioritized default logic in order to solve this problem. There is a sign difference between General and Extended logic programs. Extended logic programs are formulated using classical negation, For this reason, an inconsistent answer set can sometimes be produced. For the most part, default reasoning semantics successfully resolved this problem, but a conflict could still arise in one particular case. The purpose of this paper is to present this eventuality, and revise the semantics of default logic in order to give an answer to this problem.

We study analysis of hybrid systems under incomplete knowledge. The class of hybrid systems to be considered is assumed to have the form of a rectangular hybrid automaton such that each constant in invariants and guards is given as a parameter. We develop a method based on symbolic computation that computes an approximation of the discrete behavior of the automaton. We also show an implementation on a constraint logic programming language.

We are concerned with semantic views on an extended version of SLD resolution with negation as failure (SLDNF resolution) for normal logic programs, which Eshghi and Kowalski (1989) presented by making the SLDNF resolution capable of keeping negated predicates in memory and of extracting abducible predicates. This paper deals with its formal representation in relational form, for the purpose of interpreting the normal goal as an acquisitor of negated predicates stored in memory. Some set acquired by the derivations which the normal goal evokes is defined to be a semantics of the goal, under the constraint that the set is as large as possible and does not violate consistency in model theory. The semantics is discussed with relation to the 3-valued logic model theory, where the model theory is represented by alternating fixpoint semantics (Van Gelder, 1993). For simplicity of treatment, this paper is concerned with the normal logic program in the propositional logic.

In this paper we describe collaborative constraint functional logic programming and the system called Open CFLP that supports this programming paradigm. The system solves equations by collaboration of various equational constraint solvers. The solvers include higher-order lazy narrowing calculi that serve as the interpreter of higher-order functional logic programming, and specialized solvers for solving equations over specific domains, such as a polynomial solver and a differential equation solver. The constraint solvers are distributed in an open environment such as the Internet. They act as providers of constraint solving services. The collaboration between solvers is programmed in a coordination language embedded in a host language. In Open CFLP the user can solve equations in a higher-order functional logic programming style and yet exploit solving resources in the Internet without giving low-level programs of distributions of resources or specifying details of solvers deployed in the Internet.

We present a new method for discovering knowledge from structured data which are represented by graphs in the framework of Inductive Logic Programming. A graph, or network, is widely used for representing relations between various data and expressing a small and easily understandable hypothesis. The analyzing system directly manipulating graphs is useful for knowledge discovery. Our method uses Formal Graph System (FGS) as a knowledge representation language for graph structured data. FGS is a kind of logic programming system which directly deals with graphs just like first order terms. And our method employs a refutably inductive inference algorithm as a learning algorithm. A refutably inductive inference algorithm is a special type of inductive inference algorithm with refutability of hypothesis spaces, and is suitable for knowledge discovery. We give a sufficiently large hypothesis space, the set of weakly reducing FGS programs. And we show that this hypothesis space is refutably inferable from complete data. We have designed and implemented a prototype of a knowledge discovery system KD-FGS, which is based on our method and acquires knowledge directly from graph structured data. Finally we discuss the applicability of our method for graph structured data with experimental results on some graph theoretical notions.

Inductive Logic Programming (ILP) is a study of machine learning systems that use clausal theories in first-order logic as a representation language. In this paper, we survey theoretical foundations of ILP from the viewpoints of Logic of Discovery and Machine Learning, and try to unify these two views with the support of the modern theory of Logic Programming. Firstly, we define several hypothesis construction methods in ILP and give their proof-theoretic foundations by treating them as a procedure which complets incomplete proofs. Next, we discuss the design of individual learning algorithms using these hypothesis construction methods. We review known results on learning logic programs in computational learning theory, and show that these algorithms are instances of a generic learning strategy with proof completion methods.

This paper demonstrates the necessity of special handling mechanisms for type (or sort) information when learning logic programs on the basis of background knowledge that includes type hierarchy. We have developed a novel relational learner RHB, which incorporates special operations to handle the computing of the least general generalization (lgg) of examples and the code length of logic programs with types. It is possible for previous learners, such as FOIL, GOLEM and Progol, to generate logic programs that include type information represented as is_a relations. However, this expedient has two problems: one in the computation of the code length and the other in the performance. We will illustrate that simply adding is_a relations to background knowledge as ordinary literals causes a problem in computing the code length of logic programs with is_a literals. Experimental results on artificial data show that the learning speed of FOIL exponentially slows as the number of types in the background knowledge increases. The hypotheses generated by GOLEM are about 30% less accurate than those of RHB. Furthermore, Progol is two times slower than RHB. Compared to the three learners, RHB can efficiently handle about 3000 is_a relations while still achieving a high accuracy. This indicates that type information should be specially handled when learning logic programs with types.

We introduce an ontology for transportation systems demand forecasting and its implementation into a decision support system (DSS) generator. The term ontology, as we use it here, means a collection of building blocks necessary and sufficient to construct a skeleton of a specific DSS, that is a task ontology. The ontology is specified in constraint logic, which also ensures a good support for modularity.

In the commonsense reasoning, priorities among rules are often required to be found out in order to derive the desired conclusion as a theorem of the reasoning. In this paper, first we present the bottom-up and top-down abduction procedures to compute skeptical explanations and secondly show that priorities of circumscription to infer a desired theorem can be abduced as a skeptical explanation in abduction. In our approach, the required priorities can be computed based on the procedure to compute skeptical explanations provided in this paper as well as Wakaki and Satoh's method of compiling circumscription into extended logic programs. The method, for example, enables us to automatically find the adequate priority w. r. t. the Yale Shooting Problem to express a human natural reasoning in the framework of circumscription.

In this paper we propose a new method for parallel execution of Prolog programs and present its implementation on a distributed memory parallel computer, Fujitsu AP1000. In our method a number of processes (named Prolog engines) explore different branches of a search tree (named tasks) in parallel, which is the same as OR-parallelism. Unlike OR-parallelism, the mapping between Prolog engines and tasks is statically determined like data parallelism. Each Prolog engine can decide which task is executed by the engine without communicating with the other engines. In many search problems, however, such static task mapping may cause imbalance on the processing time of each engine since the computational costs to explore branches may vary substantially. To cope with this issue, we devise a method to adjust the task imbalance by periodical exchanging how many tasks were processed for each engine. Also for reducing communication overhead in load balancing, we limit the scope of engines that exchange the load information each other. The effectiveness of our method is evaluated by measuring execution times for N Queens and the Traveling Salesman Problem on the AP1000. Using 512 processors, we obtained 355-fold speedup for N Queens and 343-fold speedup on the Traveling Salesman Problem.

In logic programming or functional programming languages, data objects, such as terms and lists, are immutable. In a basic implementation of such language, updating one element of an aggregate (contiguous data structure, such as an array) involves making a new copy of the whole aggregate. However, such copying can be expensive, and can be avoided by using a destructive update. We introduce the concept of a wrapper which enables destructive operation on an immutable object. Based on this concept, we designed the reversible functor as a solution to the aggregate update problem. We implemented the reversible functor in the existing SB-Prolog system and carried out several benchmarks. These benchmark results show its effectiveness. When using a large functor and updating it many times, the performance is improved dramatically by implementing the reversible functor. It incurs some overhead at runtime, but the amount is small and acceptable.

There have been semantics for logic programs as sets of definite clauses over sequence domains in [2],[6]. The sequence of substitutions caused by resolutions for logic programs can be captured by a fixpoint of a functional [3],[16]. In [15], a functional is regarded as a behaviour of a dataflow network, the semantics over sequence domains induces dataflow computing for logic programs. Also it may provide a transformation of logic programs to functional programs[16]. Motivated by dataflow computing constructions for logic programming, this paper deals with fixpoint semantics over sequence domains for logic programs with equations and negations. A transformation, representing deductions caused by resolutions and narrowings, is associated with a logic program with equations, modified from the operator in [18], so that it may be represented by a continuous functional over a sequence domain, and its least fixpoint is well-defined. An explicit construction of such a continuous functional of sequence variables is necessary for dataflow computing, and we should prove that the functional of sequence variables can exactly represent the transformation concerned with sets. For a general logic program, a functional is constructed over a sequence domain so that it may reflect a consistency-preserving renewal function for the pair of atom sets on the basis of the 3-valued logic approach as in [7], and [11]. It is a problem to construct the domain for the functional representing a generation of atom sets interpreted as true and negation as failure in the generation, for general logic programs. The functional is monotonic over a complete partial order and its least fixpoint is well-defined, although the least fixpoint is not always obtained by the limit of finite computing, because of the functional being not necessarily continuous.

We deal with a fixpoint semantics for normal logic programs by means of an algebraic manipulation of idempotent substitution sets. Because of the negation, the function associated with a given normal logic program, which captures the deductions caused by the program, is in general nonmonotonic, as long as we are concerned with 2-valued logic approach. The demerit of the nonmonotonic function is not to guarantee its fixpoint well, although the fixpoint is regarded as representing the whole behaviour. The stable model as in [6] is fixpoint of nonmonotonic functions, but it is referred to on the assumption of its existences. On the other hand, if we take 3-valued logic approach for normal logic programs as in [5], [9], [11], [14] we have the monotonic function to represent resolutions and negation as failure, and define its fixpoint well, if we permit the fixpoint not to be constructive because of discontinuity. Since the substituitions for variables in the program are essentially significant in the deductions for logic programming, we next focus on the representations by means of substitutions for the deductions, without usual expressions based on atomic formulas. We examine the semantics in terms of abstract interpretations among semantics as surveyed in [9], where an abstraction stands for the capability of representing another semantics. In this paper, in 3-valued logic approach and by means of the substitution manipulation, the semantics is defined to be an abstraction of the semantics in [5], [9]. To construct a semantics based on the idempotent substitution set, the algebraic manipulation of substitutions is significant, whereas the treatment in [10] for the case of definite clause sets is not available because of the restriction of substitutions to some variable domain as most general unifications.

Conceptual graph formalism is a knowledge representation language in AI based on a graphical form of logic. Although logic is the basis of the conceptual graph theory, there is a strongly felt absence of a formal treatment of conceptual graphs as a logic programming language. In this paper, we develop the notion of a conceptual graph program as a kind of graph-based order-sorted logic program. First, we define the syntax of the conceptual graph program by specifying its major syntactic elements. Then, we develop a kind of model theoretic semantics and fixpoint semantics of the conceptual graph program. Finally, we show that the two types of semantics coincide for the conceptual graph programs.

In this paper we investigate the learnability of relations in Inductive Logic Programming, by using equality theories as background knowledge. We assume that a hypothesis and an observation are respectively a definite program and a set of ground literals. The targets of our learning algorithm are relations. By using equality theories as background knowledge we introduce tree structure into definite programs. The structure enable us to narrow the search space of hypothesis. We give pairs of a hypothesis language and a knowledge language in order to discuss the learnability of relations from the view point of inductive inference and PAC learning.

This paper proposes a new environment for high-level VLSI design specification validation using "Algorithmic Debugging" and evaluates its benefits on three significant examples (a protocol processor, an 8-bit CPU, and a Prolog processor). A design is specified at a high-level using the structured analysis (SA) method, which is useful for analyzing and understanding the functionality to be realized. The specification written in SA is transformed into a logic programming language and is simulated in it. The errors (which terminate with an incorrect output in the simulation) included in the three large examples are efficiently located by answering junt a few queries from the algorithmic debugger. The number of interactions between the designer and the debugger is reduced by a factor of ten to a hundred compared to conventional simulation based validation methodologies. The correct SA specification can be automatically translated into a Register Transfer Level (RTL) specification suitable for logic synthesis. In this environment, a designer is freed from the tedious task of debugging a RTL specification, and can concentrate on the design itself. This environment promises to be an important step towards efficient high-level VLSI design specification validation.