in this paper, the approximation for four kinds of knapsack prob- lems with multiple constraints is studied: 0/1 Multiple Constraint Knapsack Problem(0/1 MCKP), Integer Multiple Constraint Knapsack Problem (Integer MCKP), 0/1k-Constraillt Knapsack Problem (0/1 k-CKP) and Integer k-Constraint KnapsackProblem (Integer k-CKP). The following results are obtained:1) Unless NP = co - R, no polynomial time algorithm approximates 0/1 MCKPor Integer MCKP within a factor k(1/2)- for any > 0; unless NP = P, nopolynom…

In this paper, we propose a new arc consistency algorithm, AC-8,which requires less computation time and space than AC-6 and AC-7. The main ideaof the optimization is the divide-and-conquer strategy, thereby decomposing an arcconsistency problem into a series of smaller ones and trying to solve them in sequence.In this way, not only the space complexity but also the time complexity can be reduced. The reason for this is that due to the ahead of time performed inconsistencypropagation (in the sense that some…

An algorithm for solving the satisfiability problem is presented. It isproceed that this algorithm solves 2-SAT and Horn-SAT in linear time and k-positiveSAT (in which every clause contains at most k positive literals) ill time O(F.),where F is the length of input F, n is the number of atoms occurring in F, and k isthe greatest real number satisfying the equation x = 2-. Compared with previousresults, this nontrivial upper bound on time complexity could only be obtained fork-SAT, which is a subproblem of k-…

This paper presents an incremental approach to automatic algorithm design, which can be described by algebraic specifications precisely and conveniently. The definitions of selection operator and extension operator which can bedefined by strategy relations and transformations are given in order to model theprocess of finding the solution of a problem. Also discussed is its object-orientedimplementation. The functional specification and the design specification for an algorithm are given in one framework so …

The paper discusses semalltics of encodings in logical frameworkswhere equalities in object calculi are represented by families of types as the case inELF. The notion of Leibniz equality in a category is introduced. Two morphisms ina category are Leibniz equal if they are seen so by an internal category. The usualcategorical properties are then relativized to r-properties by requiring mediatingmorphisms to be unique up to some Leibniz equality. Using these terminologies,it is shown, by an example, that the …

This paper introduces the modifications on actions of a topologyon names of actions and the simplest topology on agents induced by a topology onnames of actions and shows that the limit behaviour of some agents is compatiblewith transitional semantics.

This article discusses the developing process of the version sequencesof specifications and the formal expressions of various reconstructions including theexpansion and revision of the version at each stage. The author suggests using ECC(Extended Calculus of Construction) to describe the specifications of formal systemand using functional language ML to implement this developing process.

A view in object oriented databases corresponds to virtual schemawith restructured generalization and decomposition hierarchies. Numbers of viewcreation methodologies have been proposed. A major drawback of existing method-ologies is that they do not maintain the closure property. That is, the result of aquery does not have the same semantics as embodied in the object oriented datamodel. Therefore, this paper presents a view creation methodology that derives aclass in response to a user's query, integrates …

This paper establishes a formal model for hybrid diagnosis, novelfeatures including: (1) It provides a unified theoretical framework for utilizing de-vice models and heuristics in diagnosis, which naturally integrates all the importantcomponents of diagnosis - the structural and behavioral description of devices, faultmodes, the lower and upper fault bounds, fault possibilities and heuristic rules -into a diagnostic system. Device models predict outputs from inputs, heuristic rulesinfer the possibilities of…

In this paper, the active learning mechanism is proposed to beused in classifier systems to cope with complex problems: an intelligent agent leavesits own signals in the environment and later collects and employs them to assistits learning process. Principles and components of the mechanism are outlined,followed by the introduction of its preliminary implementation in an actual system.An experiment with the system in a dynamic problem is then introduced, togetherwith discussions over its results. The paper …

Double-loop is a very popular structure in loop network topology. Areconfigurable hi-directional double--loop structure is recently developed. It has a newstructure which is different from any existing double-loop structure and no previousmethods can be used to evaluate its fault tolerance which is demanded for all freshideas. This paper provides an easy approach to offset this deficiency. A network issegmented first based on its block connection and then analyzed in a recursive way.The calculation using th…

In the past, expert systems exploited mainly the EMYCIN modeland the PROSPECTOR model to deal with uncertainties. In other words, a lot ofstand-alone expert systems which use these two models are available. If we can usethe Internet to couple them together, their performance will be improved throughcooperation. This is because the problem-solving ability of expert systems is greatlyimproved by the way of cooperation among different expert systems in a distributedexpert system. Cooperation between different …

In this paper, we deal with how agents reason about knowledgeof others in multiagent system. We first present a knowledge representation frame-work called reasoning about others (RAO) which is designed specifically to representconcepts and rules used in reasoning about knowledge of others. From a class ofsentences usually taken by people in daily life to reason about others, a rule calledposition exchange principle (PEP) is abstracted. PEP is described as an axiomscheme in RAO and regarded as a basic rule f…

The SCR (Software Cost Reduction) requirements method is aneffective method for specifying software system requirements. This paper presents aformal model analyzing SCR-style requirements. The analysis model mainly appliesstate translation rules, semantic computing rules and attributes to define formal se-mantics of a tabular notation in the SCR requirements method, and may be used toanalyze requirements specifications to be specified by the SCR requirements method.Using a simple example, this paper introdu…

Java Beans is a standard for software components. For checkingthe consistency of the Java Beaus semantic constraints with its implementation,this paper proposes a formal Java Beaus Description Language (JBDL) to specifycomponent semantic constraints. The JBDL logic is based on many sorted firstorder logic and Computation Tree Logic (CTL), with extension of some facilities inspecifying object oriented features. A framework for dynamic checking Java Beaussemantic constraines in JBDL form is described in this …

A Function Definition Language (FDL) is presented. Though de-signed for describing specifications, FDL is also a general-purpose functional pro-gramming language. It uses context-free language as data type, supports patternmatching definition of functions, offers several function definition forms, and is exe-cutable. It is shown that FDL has strong expressiveness, is easy to use and describesalgorithms concisely and naturally. An interpreter of FDL is introduced. Experi-ments and discussion are included.

Concurrence is an important research area in collaborative problemsolving. This paper offers a formal definition for cooperative sequences in multi-agentsystems, discusses the different categories of concurrent actions, and proposes somerules for situation revision and an algorithm used to generate resulting situations.An example is also given to show how to solve concurrent problems occurring inmulti-agent systems.

A kind of loop function LoopN in Genetic Programming (GP) isproposed. Different from other forms of loop function, such as While-Do and Repeat-Until, LoopN takes only one argument as its loop body and makes its loop bodysimply run N times, so infinite loops will never happen. The problem of how to avoidtoo many layers of loops in Genetic Programming is also solved. The advantage ofLoopN in GP is shown by the computational results in solving the mower problem.