Bimonthly    Since 1986
ISSN 1000-9000(Print)
CN 11-2296/TP
Indexed in:
Publication Details
Edited by: Editorial Board of Journal Of Computer Science and Technology
P.O. Box 2704, Beijing 100190, P.R. China
Sponsored by: Institute of Computing Technology, CAS & China Computer Federation
Undertaken by: Institute of Computing Technology, CAS
Distributed by:
China: All Local Post Offices
Other Countries: Springer
  • Table of Content
      10 July 1999, Volume 14 Issue 4 Previous Issue    Next Issue
    For Selected: View Abstracts Toggle Thumbnails
    Approximation for- Knapsack Problemswith Multiple Constraints
    ZHANG Li'ang; ZHANG Yin;
    Journal of Computer Science and Technology, 1999, 14 (4): 289-297. 
    Abstract   PDF(229KB) ( 1264 )   Chinese Summary
    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…
    References | Related Articles | Metrics
    On the Arc Consistency Problem
    CHEN Yangjun;
    Journal of Computer Science and Technology, 1999, 14 (4): 298-308. 
    Abstract   PDF(512KB) ( 1377 )   Chinese Summary
    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…
    References | Related Articles | Metrics
    On k-Positive Satisfiability Problem
    HUANG Xiong; LI wei;
    Journal of Computer Science and Technology, 1999, 14 (4): 309-313. 
    Abstract   PDF(232KB) ( 1400 )   Chinese Summary
    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-…
    References | Related Articles | Metrics
    An Incremental Approach toAutomatic Algorithm Design
    LUAN Shangmin; LI wei;
    Journal of Computer Science and Technology, 1999, 14 (4): 314-319. 
    Abstract   PDF(271KB) ( 1290 )   Chinese Summary
    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 …
    References | Related Articles | Metrics
    Relative Properties of Frame Language
    FU maxi;
    Journal of Computer Science and Technology, 1999, 14 (4): 320-327. 
    Abstract   PDF(363KB) ( 1330 )   Chinese Summary
    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 …
    References | Related Articles | Metrics
    Topology in Process Calculus (Ⅰ):Limit Behaviour of Agents
    YING Mingsheng;
    Journal of Computer Science and Technology, 1999, 14 (4): 328-336. 
    Abstract   PDF(443KB) ( 1524 )   Chinese Summary
    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.
    References | Related Articles | Metrics
    The Sequence Modeling Method Based on ECCin Developing Program Specifications
    CAI Jiamei;
    Journal of Computer Science and Technology, 1999, 14 (4): 337-348. 
    Abstract   PDF(520KB) ( 1333 )   Chinese Summary
    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.
    References | Related Articles | Metrics
    View Creation for Queriesin Object Oriented Databases
    Rajesh Narang; K.D. Sharma;
    Journal of Computer Science and Technology, 1999, 14 (4): 349-362. 
    Abstract   PDF(613KB) ( 1434 )   Chinese Summary
    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 …
    References | Related Articles | Metrics
    A Theory of Hybrid Diagnosis
    SHEN Yidong;
    Journal of Computer Science and Technology, 1999, 14 (4): 363-371. 
    Abstract   PDF(439KB) ( 1199 )   Chinese Summary
    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…
    References | Related Articles | Metrics
    An Approach to Active Learning for Classifier Systems
    XI Haifeng; LUO Yupin; YANG Shiyuan;
    Journal of Computer Science and Technology, 1999, 14 (4): 372-378. 
    Abstract   PDF(324KB) ( 1491 )   Chinese Summary
    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 …
    References | Related Articles | Metrics
    Fault Tolerance of Reconfigurable Bi-Directional Double-Loop LANs
    WEI Hua; LUO Yupin; YANG Shiyuan;
    Journal of Computer Science and Technology, 1999, 14 (4): 379-385. 
    Abstract   PDF(325KB) ( 1347 )   Chinese Summary
    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…
    References | Related Articles | Metrics
    Isomorphic Transformations of Uncertaintiesfor Incorporating EMYCIN-Style and PROSPECTOR-Style Systems intoa Distributed Expert System
    ZHANG Cnengqi; LUO Xudong;
    Journal of Computer Science and Technology, 1999, 14 (4): 386-392. 
    Abstract   PDF(184KB) ( 1222 )   Chinese Summary
    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 …
    References | Related Articles | Metrics
    RAO Logic for Multiagent Framework
    SHI Zhongzhi; TIAN Qijia; LI Yunfeng;
    Journal of Computer Science and Technology, 1999, 14 (4): 393-400. 
    Abstract   PDF(375KB) ( 1241 )   Chinese Summary
    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…
    References | Related Articles | Metrics
    Automated Analysis of the SCR-StyleRequirements Specifications
    WU Guoqing; LIU Xiang; YING Shi; Tetsuo Tamai;
    Journal of Computer Science and Technology, 1999, 14 (4): 401-407. 
    Abstract   PDF(327KB) ( 1210 )   Chinese Summary
    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…
    References | Related Articles | Metrics
    Dynamic Checking Frameworkfor Java Beaus Semantic Constraints
    NI Bin; FENG Yulin;
    Journal of Computer Science and Technology, 1999, 14 (4): 408-413. 
    Abstract   PDF(153KB) ( 1298 )   Chinese Summary
    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 …
    References | Related Articles | Metrics
    Function Definition Language FDL andIts Implementation
    CHEN Haiming;
    Journal of Computer Science and Technology, 1999, 14 (4): 414-421. 
    Abstract   PDF(347KB) ( 1325 )   Chinese Summary
    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.
    References | Related Articles | Metrics
    Reasoning about Concurrent Actionsin Multi-Agent Systems
    FAN Xiaocong; XU Dianxiang; HOU Jianmin; ZHENG Guoliang;
    Journal of Computer Science and Technology, 1999, 14 (4): 422-428. 
    Abstract   PDF(347KB) ( 1329 )   Chinese Summary
    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.
    References | Related Articles | Metrics
    Genetic Programming with Simple Loops
    QI Yuesheng; WANG Baozhong; KANG Lishan;
    Journal of Computer Science and Technology, 1999, 14 (4): 429-433. 
    Abstract   PDF(229KB) ( 1456 )   Chinese Summary
    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.
    References | Related Articles | Metrics
  Journal Online
Just Accepted
Top Cited Papers
Top 30 Most Read
Paper Lists of Areas
Special Issues
   ScholarOne Manuscripts
   Log In

User ID:


  Forgot your password?

Enter your e-mail address to receive your account information.

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved