Proving termination of GHC programs

A transformational approach for proving termination of parallel logic programs such as GHC programs is proposed. A transformation from GHC programs to term rewriting systems is developed; it exploits the fact that unifications in GHC-resolution correspond to matchings. The termination of a GHC program for a class of queries is implied by the termination of the resulting rewrite system. This approach facilitates the applicability of a wide range of termination techniques developed for rewrite systems in proving termination of GHC programs. The method consists of three steps: (a) deriving moding information from a given GHC program, (b) transforming the GHC program into a term rewriting system using the moding information, and finally (c) proving termination of the resulting rewrite system. Using this method, the termination of many benchmark GHC programs such as quick-sort, merge-sort, merge, split, fair-split and append, etc., can be proved. This is a revised and extended version of Ref. 12). The work was partially supported by the NSF Indo-US grant INT-9416687 Kapur was partially supported by NSF Grant nos. CCR-8906678 and INT-9014074. M. R. K. Krishna Rao, Ph.D.: He currently works as a senior research fellow at Griffith University, Brisbane, Australia. His current interests are in the areas of logic programming, modular aspects and noncopying implementations of term rewriting, learning logic programs from examples and conuterexamples and dynamics of mental states in rational agent architectures. He received his Ph.D in computer science from Tata Institute of Fundamental Research (TIFR), Bombay in 1993 and worked at TIFR and Max Planck Institut für Informatik, Saarbrücken until January 1997. Deepak Kapur, Ph.D.: He currently works as a professor at the State University of New York at Albany. His research interests are in the areas of automated reasoning, term rewriting, constraint solving, algebraic and geometric reasoning and its applications in computer vision, symbolic computation, formal methods, specification and verification. He obtained his Ph.D. in Computer Science from MIT in 1980. He worked at General Electric Corporate Research and Development until 1987. Prof. Kapur is the editor-in-chief of the Journal of Automated Reasoning. He also serves on the editorial boards of Journal of Logic Programming, Journal on Constraints, and Journal of Applicable Algebra in Engineering, Communication and Computer Science. R. K. Shyamasundar, Ph.D.: He currently works as a professor at Tata Institute of Fundamental Research (TIFR), Bombay. His current intersts are in the areas of logic programming, reactive and real time programming, constraint solving, formal methods, specification and verification. He received his Ph.D in computer science from Indian Institute of Science, Bangalore in 1975 and has been a faculty member at Tata Institute of Fundamental Research since then. He has been a visiting/regular faculty member at Technological University of Eindhoven, University of Utrecht, IBM TJ Watson Research Centre, Pennsylvania State University, University of Illinois at Urbana-Champaign, INRIA and ENSMP, France. He has served on (and chaired) Program Committees of many International Conferences and has been on the Editorial Committees.     

宝钢研制的全氢罩式炉控制系统分析

对宝钢研制的全氢罩式炉计算机控制系统的逻辑结构、工作原理及硬件配置进行了分析.该系统与引进的系统相比,在通讯方式、程序结构、操作分析、报警和开放性等方面都有所改进.     

Pruning Algorithms for Rule Learning

Pre-pruning and Post-pruning are two standard techniques for handling noise in decision tree learning. Pre-pruning deals with noise during learning, while post-pruning addresses this problem after an overfitting theory has been learned. We first review several adaptations of pre- and post-pruning techniques for separate-and-conquer rule learning algorithms and discuss some fundamental problems. The primary goal of this paper is to show how to solve these problems with two new algorithms that combine and integrate pre- and post-pruning.     

大变量逻辑函数最佳覆盖问题研究

逻辑函数的最佳覆盖，一直是逻辑综合领域的关键环节。尤其是大变量逻辑函数最佳覆盖，对复杂的逻辑综合更为重要，但也更加困难。本文在对逻辑覆盖算法研究的基础上，提出了适合大变量逻辑函数最佳覆盖的Beister改进算法。经过大量算题的测试表明，改进的列覆盖算法在时间复杂度和选择效果方面均优于Beister算法。     

VHDL逻辑综合及FPGA实现

运用ＶＨＤＬ语言描述了一个１２×１２位的高速补码阵列乘法器。重点是运用ＶＨＤＬ逻辑综合优化该乘法器，并进行了乘法器的ＸｉｌｉｎｘＦＰＧＡ实现、功能仿真和时序仿真。经选用ＸＣ４００５ＰＣ－８４－４芯片进行验证，证明了其正确性     

Software tools for micro-analysis of programs

The paper proposes and describes several tools enabling their user to estimate the efficiency of Pascal or C-like programs. The approach consists of generating symbolic formulas expressing the efficiency of the programs being analyzed. The formulas are applicable to a variety of compiler-machine configurations. The actual numeric values of the variables in the symbolic formula are determined using linear programming techniques. The proposed approach reduces considerably the amount of benchmarking needed to analyze programs. Several examples are presented showing the applicability of the tools. The effort necessary to implement them is considerably reduced by the combined usage of Prolog and a symbolic formula manipulation package (Maple).     

多功能半导体激光医疗仪电源的研制

根据“多功能半导体激光医疗仪”整机的要求,采用同一电源对667nm和808nm半导体激光器实施供电。为避免电源在开、关机时对半导体激光管产生浪涌冲击,电源在设计中采用了适当的逻辑功能。并可保证对667nm激光器供电时,即使打开808nm激光器供电开关,也不对808nm半导体激光器供电,反之亦然。电源设有手动、计算机两种控制方法,及恒定功率、电流两种工作方式。     

On the monotonicity of (LDL) logic programs with set

LDL is one of the recently proposed logical query languages, which incorporate set, for data and knowledge base systems. Since LDL programs can simulate negation, they are not monotonic in general. On the other hand, there are monotonic LDL programs. This paper addresses the natural question of “When are the generally nonmonotonic LDL programs monotonic?” and investigates related topics such as useful applications for monotonicity. We discuss four kinds of monotonicity, and examine two of them in depth. The first of the two, called “ω-monotonicity”, is shown to be undecidable even when limited to single-stratum programs. The second, called “uniform monotonicity”, is shown to implyω-monotonicity. We characterize the uniform monotonicity of a program (i) by a relationship between its Bancilhon-Khoshafian semantics and its LDL semantics, and (ii) with a useful property called subset completion independence. Characterization (ii) implies that uniformly monotonie programs can be evaluated more efficiently by discarding dominated facts. Finally, we provide some necessary and/or sufficient, syntactic conditions for uniform monotonicity. The conditions pinpoint (a) enumerated set terms, (b) negations of membership and inclusion, and (c) sharing of set terms as the main source for nonuniform monotonicity.     

P-channel Ge/Si Hetero-nanocrystal Based MOSFET Memory

The charge storage characteristics of P-channel Ge/Si hetero-nanocrystal based MOSFET memory has been investigated and a logical array has been constructed using this memory cell. In the case of the thickness of tunneling oxide T_ox=2nm and the dimensions of Si- and Ge-nanocrystal D_Si=D_Ge=5nm, the retention time of this device can reach ten years(~1×10~8s) while the programming and erasing time achieve the orders of microsecond and millisecond at the control gate voltage |V_g|=3V with respect to N-wells, respectively. Therefore, this novel device, as an excellent nonvolatile memory operating at room temperature, is desired to obtain application in future VLSI.     

QD-Janus: A sequential implementation of Janus in Prolog

Janus is a language designed for distributed constraint programming. This paper describes QD-Janus, a sequential implementation of Janus in Prolog. The compiler uses a number of novel analyses and optimizations to improve the performance of the system. The choice of Prolog as the target language for a compiler, although unusual, is motivated by the following: (i) the semantic gap between Janus and Prolog is much smaller than that between Janus and, say, C or machine language—this simplifies the compilation process significantly, and makes it possible to develop a system with reasonable performance fairly quickly; (ii) recent progress in Prolog implementation techniques, and the development of Prolog systems whose speeds are comparable to those of imperative languages, indicates that the translation to Prolog need not entail a significant performance loss compared to native code compilers; and (iii) compilation to Prolog can benefit immediately from a significant body of work on, and implementations of, parallel Prolog systems. Our experience indicates that translation of logic programming languages to Prolog, accompanied by the development of good program analysis and optimization tools, is an effective way to quickly develop flexible and portable implementations with good performance and low cost.