Compositions of tree series transformations

Tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (Functional) compositions of such transformations are investigated. It turns out that the class of bottom-up tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations.     

Loop transformation using nonunimodular matrices

Linear transformations are widely used to vectorize and parallelize loops. A subset of these transformations are unimodular transformations. When a unimodular transformation is used, the exact bounds of the transformed loop nest are easily computed and the steps of the loops are equal to 1. Unimodular loop transformations have been widely used since they permit the implementation of many useful loop transformations. Recently, nonunimodular transformations have been proposed to reduce communication requirements or to use the memory hierarchy efficiently. The methods used for unimodular transformations do not work in the case of nonunimodular transformations, since they do not produce the exact bounds of the transformed loop nest. In this paper, we present a method for nested loop transformation which gives the exact bounds for both unimodular and nonunimodular transformations. The basic idea is to use the Hermite Normal Form (HNF) of the transformation matrix     

Applying MDE to the (semi-)automatic development of model transformations

ContextModel transformations play a key role in any software development project based on Model-Driven Engineering principles. However, despite the inherent complexity of developing model transformations, little attention has been paid to the application of MDE principles to the development of model transformations.ObjectiveIn order to: (a) address the inherent complexity of model transformation development and (b) alleviate the problem of the diversity of the languages that are available for model transformation, this paper proposes the application of MDE principles to the development of model transformations. In particular, we have adopted the idea of handling model transformations as transformation models in order to be able to model, transform and generate model transformations.MethodThe proposal follows an MDA-based approach that entails the modeling of model transformations at different abstraction levels and the connection of these models by means of model transformations. It has been empirically validated by conducting a set of case studies following a systematic research methodology.ResultsThe proposal was supported by the introduction of MeTAGeM, a methodological and technical framework for the model-driven development of model transformations that bundles a set of Domain-Specific Languages for modeling model transformations with a set of model transformations in order to bridge these languages and (semi-)automate model transformations development.ConclusionThis paper serves to show that a semi-automatic development process for model transformations is not only desirable but feasible. This process, based on MDE principles, helps to ease the task of developing model transformations and to alleviate interoperability issues between model transformation languages.     

Nonsingular Data Transformations: Definition, Validity, and Applications

This paper describes a unifying framework for nonsingular data transformations. It shows that a wide class of existing transformations may be expressed in this framework, allowing compound transformations to be performed in one step. Validity conditions for such transformations are developed as is the form of the transformed program and data. Constructive algorithms to generate data transformations for different applications are described and applied to example programs. It is shown that they can have a significant impact on program performance and may be used in situations where traditional loop transformations are inappropriate.     

Equational tree transformations

We define an equational relation as the union of some components of the least solution of a system of equations of tree transformations in a pair of algebras. We focus on equational tree transformations which are equational relations obtained by considering the least solutions of such systems in pairs of term algebras. We characterize equational tree transformations in terms of tree transformations defined by different bimorphisms. To demonstrate the robustness of equational tree transformations, we give equational definitions of some well-known tree transformation classes for which bimorphism characterizations also exist. These are the class of alphabetic tree transformations, the class of linear and nondeleting extended top-down tree transformations, and the class of bottom-up tree transformations and its linear and linear and nondeleting subclasses. Finally, we prove that a relation is equational if and only if it is the morphic image of an equational tree transformation.     

An algorithm for constructing Darboux transformations of type I for third-order hyperbolic operators of two variables

Darboux transformations of type I are invertible Darboux transformations with explicit short formulas for inverse transformations. These transformations are invariant with respect to gauge transformations, and, for gauge transformations acting on third-order hyperbolic operators of two variables, a general-form system of generating differential invariants is known. In the paper, first-order Darboux transformations of type I for this class of operators are considered. The corresponding operator orbits are directed graphs with at most three edges originating from each vertex. In the paper, an algorithm for constructing such orbits is suggested. We have derived criteria for existence of first-order Darboux transformations of type I in terms of the generating invariants, formulas for transforming invariants, and the so-called “triangle rule” property of orbits. The corresponding implementation in the LPDO package is described. The orbits are constructed in two different forms, one of which outputs the graph in the format of the well-known built-in Maple package Graph Theory.     

Equational weighted tree transformations

We consider systems of equations of weighted tree transformations with finite support over continuous and commutative semirings. We define a weighted relation to be equational, if it is a component of the least solution of such a system of equations in a pair of algebras. In particular, we focus on equational weighted tree transformations which are equational relations obtained by considering the least solutions of such systems in pairs of term algebras. We characterize equational weighted tree transformations in terms of weighted tree transformations defined by different weighted bimorphisms. To demonstrate the robustness of equational weighted tree transformations, we give an equational definition of the class of linear and nondeleting weighted top-down tree transformations and of the class of linear and nondeleting weighted extended top-down tree transformations. Finally, we prove that a weighted relation is equational if and only if it is, roughly speaking, the morphic image of a weighted equational tree transformation.     

Canonical transformation and stabilization of generalized Hamiltonian systems

This paper introduces generalized canonical transformations for generalized Hamiltonian systems which convert a generalized Hamiltonian system into another one, and preserve the generalized Hamiltonian structure of the original. As in classical mechanics, it is expected that canonical transformations will provide new insights and fundamental tools for both analysis and synthesis of those systems. Firstly, the class of generalized canonical transformations and some of their properties are indicated. Secondly, it is shown how to stabilize the generalized Hamiltonian systems using canonical transformations. In addition, some examples illustrate how such transformations are utilized for control systems design.     

Formal foundation of consistent EMF model transformations by algebraic graph transformation

Model transformation is one of the key activities in model-driven software development. An increasingly popular technology to define modeling languages is provided by the Eclipse Modeling Framework (EMF). Several EMF model transformation approaches have been developed, focusing on different transformation aspects. To validate model transformations with respect to functional behavior and correctness, a formal foundation is needed. In this paper, we define consistent EMF model transformations as a restricted class of typed graph transformations using node type inheritance. Containment constraints of EMF model transformations are translated to a special kind of graph transformation rules such that their application leads to consistent transformation results only. Thus, consistent EMF model transformations behave like algebraic graph transformations and the rich theory of algebraic graph transformation can be applied to these EMF model transformations to show functional behavior and correctness. Furthermore, we propose parallel graph transformation as a suitable framework for modeling EMF model transformations with multi-object structures. Rules extended by multi-object structures can specify a flexible number of recurring structures. The actual number of recurring structures is dependent on the application context of such a rule. We illustrate our approach by selected refactorings of simplified statechart models. Finally, we discuss the implementation of our concepts in a tool environment for EMF model transformations.     

Adapting transformations to metamodel changes via external transformation composition

Evolution is inherent to software systemsbecause of the rapid improvement of technologies and business logic. As a software development paradigm, model driven engineering (MDE) is also affected by this problem. More concretely, being metamodels the cornerstone of MDE, their evolution impacts the rest of software artefacts involved in a development process, i.e., models and transformations. The influence over models has been tackled and partially solved in previous works. This paper focuses on the impact over transformations. We propose an approach to adapt transformations by means of external transformation composition. That is, we chain impacted transformations to particular adaptation transformations which deal with either refactoring/destruction changes or construction changes. Our approach semi-automatically generates such transformations by using the AtlanMod matching language, a DSL to define model matching strategies. To provide with a proof of concept for our proposal, we adapt transformations written in terms of object-relational database metamodels when such metamodels evolve in time.     

Inversion of Linear Space-Time Transformations in Bounded Domains

General formulas for pseudoinversion of linear integral transformations in bounded space-time domains are constructed. The input and output of transformations are given in continuous-discrete forms. The conditions of accuracy and uniqueness of the transformations are studied.     

Leveraging polynomial approximation for non-linear image transformations in real time

Applying non-linear image transformations in real time remains a challenge for cost-sensitive embedded systems today. This paper offers a method to perform such transformations efficiently using polynomial approximations. It is based on a previously published method, but is not limited to transformations with little vertical variation, such as lens distortion removal. Instead, a wider range of image transformations is supported.     

Transformations for optimizing interprocess communication and synchronization mechanisms

This paper presents source-level transformations that improve the performance of programs using synchronous and asynchronous message passing primitives, including remote call to an active process (rendezvous). It also discusses the applicability of these transformations to shared memory and distributed environments. The transformations presented reduce the need for context switching, simplify the specific form of communication, and/or reduce the complexity of the given form of communication. One additional transformation actually increases the number of processes as well as the number of context switches to improve program performance. These transformations are shown to be generalizable. Results of hand-applying the transformations to SR programs indicate reductions in execution time exceeding 90% in many cases. The transformations also apply to many commonly occurring synchronization patterns and to other concurrent programming languages such as Ada and Concurrent C. The long term goal of this effort is to include such transformations as an otpimization step, performed automatically by a compiler.This work was supported by NSF under Grant Number CCR88-10617.     

Bidirectional model transformations in QVT: semantic issues and open questions

We consider the OMG’s queries, views and transformations standard as applied to the specification of bidirectional transformations between models. We discuss what is meant by bidirectional transformations, and the model-driven development scenarios in which they are needed. We analyse the fundamental requirements on tools which support such transformations, and discuss some semantic issues which arise. In particular, we show that any transformation language sufficient to the needs of model-driven development would have to be able to express non-bijective transformations. We argue that a considerable amount of basic research is needed before suitable tools will be fully realisable, and suggest directions for this future research.     

Using affine closure to find legal reordering transformations

We present a unified framework for applying iteration reordering transformations. This framework is able to represent traditional transformations such as loop interchange, loop skewing and loop distribution as well as compositions of these transformations. Using a unified framework rather than a sequence of ad-hoc transformations makes it easier to analyze and predict the effects of these transformations. Our framework is based on the idea that all reordering transformations can be represented as a mapping from the original iteration space to a new iteration space. An optimizing compiler would use our framework by finding a mapping that both corresponds to a legal transformation and produces efficient code. We present the mapping selection problem as a search problem by decomposing it into a sequence of smaller choices. We then characterize the set of all legal mappings by defining a search tree. As part of this process we use a new operation called affine closure.     

Correct-by-construction synthesis of model transformations using transformation patterns

Model transformations are an essential part of model-based development approaches, such as Model-driven Architecture (MDA) and Model-driven Development (MDD). Model transformations are used to refine and abstract models, to re-express models in a new modelling language, and to analyse, refactor, compare and improve models. Therefore, the correctness of model transformations is critically important for successful application of model-based development: software developers should be able to rely upon the correct processing of their models by transformations in the same way that they rely upon compilers to produce correct executable versions of their programs. In this paper, we address this problem by defining standard structures for model transformation specifications and implementations, which serve as patterns and strategies for constructing a wide range of model transformations. These are incorporated into a tool-supported process which automatically synthesises implementations of model transformations from their specifications, these implementations are correct-by-construction with respect to their specifications.     

Case-based exploration of bidirectional transformations in QVT Relations

QVT Relations (QVT-R), a standard issued by the Object Management Group, is a language for the declarative specification of model transformations. This paper focuses on a particularly interesting feature of QVT-R: the declarative specification of bidirectional transformations. Rather than writing two unidirectional transformations separately, a transformation developer may provide a single relational specification which may be executed in both directions. This approach saves specification effort and ensures the consistency of forward and backward transformations. This paper explores QVT-R’s support for bidirectional model transformations through a spectrum of transformation cases. The transformation cases vary with respect to several factors such as the size of the transformation definition or the relationships between the metamodels for source and target models. The cases are solved in QVT-R, but may be applied to other bidirectional transformation languages, as well; thus, they may be used as a benchmark for comparing bidirectional transformation languages. In our work, we focus on the following research questions: functionality of bidirectional transformations in terms of relations between source and target models, solvability (which problems may be solved by a single relational specification of a bidirectional transformation), variability (does a bidirectional transformation contain varying elements, i.e., elements being specific to one direction), comprehensibility (referring to the ease of understanding and constructing QVT-R transformations), and the semantic soundness of bidirectional transformations written in QVT-R.     

软硬件划分中基于一种新的层次化控制数据流图的粒度变换

在一种控制数据流图定义的基础上,提出了面向软硬件划分中粒度选择的粒度变换方法．变换以层次化结点为中介,包括合并和展开操作,并遵循所指定的若干要求以保证变换前后的系统表示在形式和功能上的一致性．分析表明,这一变换过程简单快速,变换前后功能一致、形式统一,能很好地满足软硬件划分中粒度选择的需要．