basic research in computer science and software engineering at sklcs

The State Key Laboratory of Computer Science (SKLCS) is committed to basic research in computer science and software engineering. The research topics of the laboratory include: concurrency theory, theory and algorithms for real-time systems, formal specifications based on context-free grammars, semantics of programming languages, model checking, automated reasoning, logic programming, software testing, software process improvement, middleware technology, parallel algorithms and parallel software, computer graphics and human-computer interaction. This paper describes these topics in some detail and summarizes some results obtained in recent years.

constructing finite algebras with falcon

The generation of models and counterexamples is an important form of reasoning. In this paper, we give a formal account of a system, called FALCON, for constructing finite algebras from given equational axioms. The abstract algorithms, as well as some implementation details and sample applications, are presented. The generation of finite models is viewed as a constraint satisfaction problem, with ground instances of the axioms as constraints. One feature of the system is that it employs a very simple technique, called the least number heuristic, to eliminate isomorphic (partial) models, thus reducing the size of the search space. The correctness of the heuristic is proved. Some experimental data are given to show the performance and applications of the system.

语义Web中的自动推理和主动规则终止性分析

语义Web是现有Web的一个语义延伸，目标是使Web的应用具有一定的智能，能够进行更准确的信息搜索和一定的决策支持，帮助用户自动完成一些任务。语义Web的实现需要人工智能、数据库等领域的技术支持，需要对已有的技术进行改进和扩展，也需要对现有技术本身如ECA规则进行更深入的研究从而进一步将其扩展到语义Web。自动推理技术是语义Web实现的基础之一，而ECA规则可以为系统增加反应性行为能力，本文围绕自动推理和ECA规则，主要进行了如下研究：（1） 一阶逻辑推理技术对语义Web的推理支持。分析了语义Web语言需要的表达能力，对现有描述逻辑工具、一阶逻辑工具的能力进行了考察。现有的描述逻辑工具不足以处理应用所需要的更丰富的语言成分、任意的一阶逻辑规则等，而一阶逻辑自动定理证明工具和有限模型查找工具有分别都有较好的研究成果。把语义Web的推理问题化成可满足性判定问题后，本文给出了一阶逻辑定理证明器和有限模型查找器形成的并发过程进行可满足性判定的方法。这样既可以解决描述逻辑工具的不足，并可弥补定理证明器对可满足的公式推理的不完备性。（2） ECA规则(主动规则)的终止性分析。终止性是主动规则最重要的行为性质，不终止是由于主动规则的级联触发造成的，意味着定义错误。终止性检查通常是不可判定的。有效的静态分析方法是主动规则得以实际应用的保证。静态分析的关键是合适的数据库状态描述，本文给出用约束表示数据库状态的方法，通过模拟规则执行，使用约束求解进行条件计算和重复状态检查，判断主动规则集合是否终止。用约束精确表示了数据库状态，在规则处理中考虑了执行语义，从而得到更精确的终止性结论。

Fuzzy reasoning morphological operators and their optical implementation

Fuzzy-reasoning theory is widely used in industrial control. Mathematical morphology is a powerful tool to perform image processing. We apply fuzzy-reasoning theory to morphology and suggest a scheme of fuzzy-reasoning morphology, including fuzzy-reasoning dilation and erosion functions. These functions retain more fine details than the corresponding conventional morphological operators with the same structuring element. An optical implementation has been developed with area-coding and thresholding methods. (C) 1997 Optical Society of America.

Peak identification for PCDD/Fs in environmental samples at different temperature programs

A method has been developed for peak recognition of 136 polychlorinated dibenzo-p-dioxins (PCDDs) and polychlorinated dibenzofurans (PCDFs) at different temperature programs. Their retention behaviours are predicted on the basis of an identification database of retention values (A, B) of gas chromatography. By the retention times of C-13 labelled 2,3,7,8-substituted PCDD/F internal standards, the retentions of all PCDDs and PCDFs can be calculated. After comparison with the retentions of practical environmental samples, the predicted values have been proved to be very accurate. (C) 2000 Elsevier Science Ltd. All rights reserved.

A logic for default reasoning

The need to make default assumptions is frequently encountered in reasoning about incompletely specified worlds. Inferences sanctioned by default are best viewed as beliefs which may well be modified or rejected by subsequent observations. It is this property which leads to the non-monotonicity of any logic of defaults. In this paper we propose a logic for default reasoning. We then specialize our treatment to a very large class of commonly occuring defaults. For this class we develop a complete proof theory and show how to interface it with a top down resolution theorem prover. Finally, we provide criteria under which the revision of derived beliefs must be effected.

automated test case generation for the stress testing of multimedia systems

With the advancement in network bandwidth and computing power, multimedia systems have become a popular means for information delivery. However, general principles of system testing cannot be directly applied to testing of multimedia systems on account of their stringent temporal and synchronization requirements. In particular, few studies have been made on the stress testing of multimedia systems with respect to their temporal requirements under resource saturation. Stress testing is important because erroneous behavior is most likely to occur under resource saturation. This paper presents an automatable method of test case generation for the stress testing of multimedia systems. It adapts constraint solving techniques to generate test cases that lead to potential resource saturation in a multimedia system. Coverage of the test cases is defined upon the reachability graph of a multimedia system. The proposed stress testing technique is supported by tools and has been successfully applied to a real-life commercial multimedia system. Although our technique focuses on the stress testing of multimedia systems, the underlying issues and concepts are applicable to other types of real-time systems.