Automatic semigroups

The area of automatic groups has been one in which significant advances have been made in recent years. While it is clear that the definition of an automatic group can easily be extended to that of an automatic semigroup, there does not seem to have been a systematic investigation of such structures. It is the purpose of this paper to make such a study.We show that certain results from the group-theoretic situation hold in this wider context, such as the solvability of the word problem in quadratic time, although others do not, such as finite presentability. There are also situations which arise in the general theory of semigroups which do not occur when considering groups; for example, we show that a semigroup S is automatic if and only if S with a zero adjoined is automatic, and also that S is automatic if and only if S with an identity adjoined is automatic. We use this last result to show that any finitely generated subsemigroup of a free semigroup is automatic.     

Program derivation in type theory: A partitioning problem

Martin-Löf's type theory is a theory in which one can write both specifications and programs. By interpreting propositions as types, predicate logic is available when formulating a specification. The rules of type theory are formulated as tactics which makes a “top down” construction of programs possible. These ideas are illustrated by a formal derivation of a program for a partitioning problem.     

Key activities for product derivation in software product lines

More and more organizations adopt software product lines to leverage extensive reuse and deliver a multitude of benefits such as increased quality and productivity and a decrease in cost and time-to-market of their software development. When compared to the vast amount of research on developing product lines, relatively little work has been dedicated to the actual use of product lines to derive individual products, i.e., the process of product derivation. Existing approaches to product derivation have been developed independently for different aims and purposes. While the definition of a general approach applicable to every domain may not be possible, it would be interesting for researchers and practitioners to know which activities are common in existing approaches, i.e., what are the key activities in product derivation. In this paper we report on how we compared two product derivation approaches developed by the authors in two different, independent research projects. Both approaches independently sought to identify product derivation activities, one through a process reference model and the other through a tool-supported derivation approach. Both approaches have been developed and validated in research industry collaborations with different companies. Through the comparison of the approaches we identify key product derivation activities. We illustrate the activities’ importance with examples from industry collaborations. To further validate the activities, we analyze three existing product derivation approaches for their support for these activities. The validation provides evidence that the identified activities are relevant to product derivation and we thus conclude that they should be considered (e.g., as a checklist) when developing or evaluating a product derivation approach.     

On Lawrence semigroups

Lawrence semigroups arise as a tool to compute Graver bases of semigroup ideals. It is known that the minimal free resolution of semigroup ideals is characterized by the reduced homologies of certain simplicial complexes.     

Finite complete rewriting systems for regular semigroups

It is proved that, given a (von Neumann) regular semigroup with finitely many left and right ideals, if every maximal subgroup is presentable by a finite complete rewriting system, then so is the semigroup. To achieve this, the following two results are proved: the property of being defined by a finite complete rewriting system is preserved when taking an ideal extension by a semigroup defined by a finite complete rewriting system; a completely 0-simple semigroup with finitely many left and right ideals admits a presentation by a finite complete rewriting system provided all of its maximal subgroups do.     

Banded matrix approach to Finite Element modelling for soft tissue simulation

Realistic deformation of computer-simulated anatomica structures is computationally intensive. As a result, simple methodologies not based in continuum mechanics have been employed for achieving real-time deformation of virtual anatomy. Since the graphical interpolations and simple spring models commonly used in these simulations are not based on the biomechanical properties of tissue structures, these quick and dirty methods typically do not represent accurately the complex deformations and force-feedback interactions that can take place during surgery. Finite Element (FE) analysis is widely regarded as the most appropriate alternative to these methods. Extensive research has been directed toward applying this method to modelling a wide range of biological structures, and a few simple FE models have been incorporated into surgical simulations. However, because of the highly computational nature of the FE method, its direct application to real-time force-feedback and visualisation of tissue deformation has not been practical for most simulations. This limitation is due primarily to the overabundance of information provided by the standard FE approaches. If the mathematics are optimised through preprocessing to yield only the information essential to the simulation task, run-time computation requirements can be reduced drastically. We are currently developing such methodologies, and have created computer demonstrations that support real-time interaction with soft tissue. To illustrate the efficacy and utility of these fast banded matrix FE methods, we present results from a skin suturing simulator which we are developing on a PC-based platform.     

PAR平台从规约出发的算法推导与自动生成

简要介绍PAR方法及其支撑平台,使用PAR方法及其平台从规约出发形式化推导并生成了两个典型的算法程序。PAR方法及其平台使用一阶谓词逻辑表示功能规约,分划与递推来进行算法形式推导,各种转换系统来自动生成算法程序。这显著地提高了算法程序的正确性和开发效率,也有助于深刻地理解算法设计思想。     

The analysis of relationships in databases for rule derivation

Owing to the rapid growth in the sizes of databases, potentially useful information may be embeded in a large amount of data. Knowledge discovery is the search for semantic relationships which exist in large databases. One of the main problems for knowledge discovery is that the number of possible relationships can be very large, thus searching for interesting relationships and reducing the search complexity are important. The relationships can be represented as rules which can be used in efficient query processing. We present a technique to analyze relationships among attribute values and to derive compact rule set. We also propose a mechanism and some heuristics to reduce the search complexity for the rule derivation process. An evaluation model is presented to evaluate the quality of the derived rules. Moreover, in real world, databases may contain uncertain data. We also propose a technique to analyze the relationships among uncertain data and derive probabilistic rules.     

荷兰国旗问题的形式化推导及其多态性实现

讨论了程序功能规约变换和算法程序的形式化技术,通过功能规约变换,可以较自然地获得问题求解的递推关系,对荷兰国旗问题的求解过程显示了形式化推导在获得高效和正确的算法程序中的作用。最后,给出了问题求解的多态性实现。     

面向对象有限元程序的研究

阐述了采用面向对象的方法和ＶＣ＋＋语言,进行结构问题有限元程序开发的过程。建立了一般线弹性体结构有限元分析类库,并与过程化语言的程序设计方法进行了分析比较,说明面向对象方法改善了有限元程序的维护性和扩充性,为开发工程计算程序提供了一种新途径。     

Finite dimensional predictors for hidden Markov chains

A continuous time Markov chain is observed in Gaussian noise. Finite dimensional normalized and unnormalized (Zakai) predictors are obtained for the state of the chain, for the number of jumps from one state to another and for the occupation time in any state.     

有限状态机设计策略

作为一个数字逻辑工程师,经常会碰到设计一个有限状态机的问题。该文讨论了FSM设计的一些注意事项和相应的VHDL编程风格。     

GPU加速有限元接触传热过程

在钢板的冲印过程中,模具的淬火效果在板料的转变中起着重要的作用。因此,本文对钢板的淬火过程建立了一个有限元模型,该模型的关键点主要是接触热传导过程,利用有限元计算机程序来计算淬火过程温度场的变化,同时通过温度测量装置来得到模具和板料的温度-时间曲线来验证计算结果。最后,采用基于GPU(图形处理单元)技术的并行计算来加快计算。     

A Mixed Finite Element Method for Elasticity in Three Dimensions

We describe a stable mixed finite element method for linear elasticity in three dimensions.     

钢筋混凝土结构有限元网格剖分的一种方法

本文将选用２分离式模型对钢筋混凝土平面结构进行有限元网格剖分,其中对混凝土结构采用四边形网格的自动剖分方法,对钢筋则采用一维杆单元的生成方法。本文所述方法能保证所产生网格的质量,有利于钢筋混凝土有限元分析。     

Design of PID controller with incomplete derivation based on ant system algorithm

A new and intelligent design method for PID controller with incomplete derivation is proposed based on the ant system algorithm (ASA). For a given control system with this kind of PlD controller, a group of optimal PID controller parameters Kp^*, Ti^*, and Td^* can be obtained by taking the overshoot, settling time, and steady-state error of the system‘s unit step response as the penfomunce indexes and by use of our improved ant system algorithm. Kp^*, Ti^*, and Td^* can be used in real-time control. This kind of controller is called the ASA-PID controller with incomplete derivation. To verify the performance of the ASA-PID controller, three different typical transfer functions were tested, and three existing typical tunmg methods of PID controller parameters,including the Ziegler-Nichols method (ZN), the genetic algnrithrn (GA), and the simulated annealing (SA), were adopted for comparison. The simulation results showed that the ASA-PID controller can be used to control different objects and has better performance compared with the ZN-PID and GA-PID controllers, and comparable performance compared with the SA-PID controller.