递归程序变换及其实验

递归程序变换是软件自动化研究中程序变换途径的一种方法。本文介绍了递归程序等价变换的一系列模式以及根据递归程序变换基本思想而构造的人-机交互实验系统XDPTS的梗概。     

关于递归程序变换模式的设计方法

本文提出递归程序变换模式的一般设计方法，并以具体示例说明之。此外，还对递归程序变换的有关问题作了讨论。     

关于并行递归程序等价变换的若干研究

一般而言,要把并行递归程序转化为等价的尾递归程序(它直接对应于循环迭代程序)是十分困难的。本文指出,具有某种性质的两类(分别称为α类和β类)并行递归程序可以转化为等价的尾递归程序,从而具有较高的时空运行效率。     

Mathematica在横向程序变换中的应用

本文讨论用Ｍａｔｈｅｍａｔｉｃａ的两大核心工作机制即模式匹配和规则来实现横向程序变换,以两类不同的递归程序变换的抽象模式为例,本文设计了相应的Ｍａｔｈｅｍａｔｉｃａ程序包将非尾递归的程序变换成为相应的尾递归形式,然后利用Ｍａｔｈｅｍａｔｉｃａ３．０提供的ＭａｔｈＬｉｎｋ机制,在ＶＢ５．０的环境下实现它们的应用。     

递归程序变换成非递归程序的方法

本文讨论将高级语言编写的递归程序自动地变换成非递归程序的变换规则和变换算法。     

形式推导支持的递归程序向非递归程序的转换

本文提出一种递归消除的方法,适于一类基于递归数据结构的程序。该方法将递归程序作为初始规约,以求解过程的状态变迁序列作迭代模式;通过数据展开和变换实现初始规约向基于序列描述规约的变换,继而用PAR形式推导出序列规约的递推关系,并以之为核心近乎机械地构造出非递归算法。树和图的两个算法实例说明了本方法的有效性。     

几种递归变换的改进模式

递归变换是程序自动设计中的一个研究课题。文[3,4]分别提出了几种递归变换,其可用条件中都包括单位元.我们基于文[8]的思想,讨论了对文[3,4]中几种变换的改进。     

Unity和Gamma之间的程序变换：一个实例研究

Ｇａｍｍａ，Ｕｎｉｔｙ都是面向问题描述的编程模型。文中我们提出了一种从Ｕｎｉｔｙ到Ｇａｍｍａ的语义等价的程序变换方法，进而我们证明，Ｇａｍｍａ比相应的Ｕｎｉｔｙ有更强的表达能力。同时，也提出了逆转换方法，把这些方法运用到排序问题中的实验结果表明，用转换机制以及把Ｕｎｉｔｙ作为Ｇａｍｍａ的实现层来编写有效的程序是一种可行的方法。     

支持软件开发的变换方法

一、变换的意义 变换方法是指一个较为抽象的定义被重复地变换和细化,通过更加具体形式,直至一个目标系统的生成。其基本目标是实现一个程序到另一个程序的等价转换。近几年来,程序变换一直是计算机研     

算法程序变换研究与进展

开发算法程序是计算机科学领域中最具挑战性的问题之一。为了提高算法程序的可靠性和生产效率，人们正在追求其开发的自动化。算法程序变换是实现算法程序开发自动化的重要途径，已成为程序设计方法学和软件自动化领域中的重要课题，目前已取得很大进展。本文介绍了算法程序变换的相关概念，给出了算法程序变换的分类，并从方法学、语言、算法设计能力、支撑工具及其适用领域等方面分析和比较了几个有代表性的算法程序变换研究项目，讨论了当前研究的不足以及今后的研究方向。     

关于非线性有限自动机的弱可逆性

根据ＲＲ变换所得方程是否有解或至多一解可判定有限自动机Ｍ是否为弱逆或弱可逆。本文证明了这些充分条件与某类映射为满射或单射是等价的，从而减少了判定所需的工作量。本文还讨论了它们同时也是判定Ｍ为弱逆或弱可逆的必要条件的情形。     

Linear time transformations between combinatorial problems

Besides showing the existence of NP-complete problems, Cook's theorem and subsequent developments have resulted in a large number of polynomial-time transformations between combinatorial problems. For both theoretical and practical reasons it is important to pursue these transformations, especially low-order ones. In this paper, two linear classes are displayed: it is shown that satisfiability, 3-colourability and set-splitting are linear-time equivalent. It is also shown that bipartite matching and path-connectivity are linear-time equivalent. The computational model on which these results are based is a 1-tape transducer.     

Transformational approach to program concretization

This paper focuses on the problem of program concretization by applying correctness-preserving transformations of annotated programs. According to the approach presented, a general-purpose program can be annotated by known information about a specific context of its applications and correctly transformed into a specialized program which is equivalent to the original one on the context-defined ranges of inputs and outputs and is better than it by quality criteria given by the context. Tools for program concretizations via annotated program transformations are considered.     

Equivalent Transformations of Program Schemes for “Entangling” Programs

By entangling program, we mean its equivalent transformation that complicates understanding the program's logic. Conventionally, equivalent transformations of programs are designed on the basis of their schemes. The problem of constructing schemes that can be used for designing equivalent transformations is discussed. A general approach to solving this problem is presented. An example of its application to ALGOL-like programs without procedures is described in the case when program schemes are constructed from the program's algebraic models.     

奇异控制正则化及刚度移置法

基于结构力学中子结构链与 LQ 离散时间控制的模拟关系,本文给出了代数里卡提方程的两种等价表达形式,利用其中的势能列式提出了刚度移置法.采用刚度移置法及适当的变换导出了奇异控制问题的里卡提方程.     

Homography and Fundamental Matrix Estimation from Region Matches Using an Affine Error Metric

Matching a pair of affine invariant regions between images results in estimation of the affine transformation between the regions. However, the parameters of the affine transformations are rarely used directly for matching images, mainly due to the lack of an appropriate error metric of the distance between them. In this paper we derive a novel metric for measuring the distance between affine transformations: Given an image region, we show that minimization of this metric is equivalent to the minimization of the mean squared distance between affine transformations of a point, sampled uniformly on the image region. Moreover, the metric of the distance between affine transformations is equivalent to the l ₂ norm of a linear transformation of the difference between the six parameters of the affine transformations. We employ the metric for estimating homographies and for estimating the fundamental matrix between images. We show that both homography estimation and fundamental matrix estimation methods, based on the proposed metric, are superior to current linear estimation methods as they provide better accuracy without increasing the computational complexity.     

H∞ type problem for sampled-data control systems-asolution via minimum energy characterization

This paper aims at deriving a solution for H_∞ type problem for sampled-data control systems. The solution is given in terms of an equivalent discrete-time H_∞ problem. The reduction procedure is viewed and characterized from the viewpoint of minimum energy principle and J-unitary transformations     

Query parallelization methods for DBMS

The paper proposes an approach to improving the efficiency of query processing in DBMS. The approach is based on equivalent transformations and parallelization of queries, extending the ideas of macropipelined and data-flow execution to the class of DBMS queries. High computational efficiency is achieved.Translated from Kibernetika, No. 1, pp. 56–63, January–February, 1990.     

Studies in the theory of algebraic models of programs with procedures

Algebraic models of programs with procedures extend algebraic models of programs that are free of procedures (simple models of programs). A specific feature of both types of models is that they are built for some formalization of software programs. Models of programs are intended for studying functional equivalence of formalized programs and constructing wide sets of equivalent transformations of programs. Two basic problems in the theory of algebraic models of programs are the equivalence problem and the problem of building complete systems of equivalent transformations. An increasing interest in models of programs with procedures is due to the abundance of results obtained for simple models of programs. The most suitable model of programs with procedures is a gateway model. A remarkable feature of these models is that every such model is induced by some simple model of programs. This paper gives a survey of the latest results obtained for gateway models of programs.