Applications of graph transformation in tools for domain-specific modeling languages

The use of domain-specific languages (DSLs) has been proposed as an approach to cost-e ectively develop families of software systems in a restricted application domain. Domain-specific languages in combination with the accumulated knowledge and experience of previous implementations, can in turn be used to generate new applications with unique sets of requirements. For this reason, DSLs are considered to be an important approach for software reuse. However, the toolset supporting a particular domain-specific language is also domain-specific and is per definition not reusable. Therefore, creating and maintaining a DSL requires additional resources that could be even larger than the savings associated with using them. As a solution, di erent tool frameworks have been proposed to simplify and reduce the cost of developments of DSLs. Developers of tool support for DSLs need to instantiate, customize or configure the framework for a particular DSL. There are di erent approaches for this. An approach is to use an application programming interface (API) and to extend the basic framework using an imperative programming language. An example of a tools which is based on this approach is Eclipse GEF. Another approach is to configure the framework using declarative languages that are independent of the underlying framework implementation. We believe this second approach can bring important benefits as this brings focus to specifying what should the tool be like instead of writing a program specifying how the tool achieves this functionality. In this thesis we explore this second approach. We use graph transformation as the basic approach to customize a domain-specific modeling (DSM) tool framework. The contributions of this thesis includes a comparison of di erent approaches for defining, representing and interchanging software modeling languages and models and a tool architecture for an open domain-specific modeling framework that e ciently integrates several model transformation components and visual editors. We also present several specific algorithms and tool components for DSM framework. These include an approach for graph query based on region operators and the star operator and an approach for reconciling models and diagrams after executing model transformation programs. We exemplify our approach with two case studies MICAS and EFCO. In these studies we show how our experimental modeling tool framework has been used to define tool environments for domain-specific languages.

Tandem-MAG-hitsauksen soveltuvuus isojen levylakanoiden valmistamiseen

Diplomityön tavoitteena oli selvittää tandem-MAG-hitsausmenetelmän soveltuvuus isojen levylakanoiden valmistamiseen. Päätavoitteena oli selvittää suurimmat saavutettavat hitsausnopeudet sekä railonvalmistukselle asetettavat vaatimukset kahdella laivanrakennusteräksellä. Tutkimuksessa käytettiin omia hitsauskokeita ja liitokset testattiin luokitusseurojen vaatimusten mukaisesti. Selvitettiin myös syntyvät hitsausmuodonmuutokset sekä edut ja rajoitukset verrattuna laserhitsaukseen. Lisäksi laadittiin ei-synergiselle pulssihitsauslaitteistolle suuntaa-antava synergiakäyrä tätä sovellusta varten hitsauskokeiden perusteella. Tandem-MAG-hitsaus osoittautui erittäin kilpailukykyiseksi hitsausmenetelmäksi sovelluksessa. Magneettisen puhalluksen havaittiin olevan merkittävä häiriötekijä tällä menetelmällä hitsattaessa.

Laajakaistaverkon topologian visualisointi

Viimeisten vuosien aikana laajakaistaoperaattoreiden laajakaistaverkot ovat nopeiden ja kiinteähintaisten laajakaistaliittymien johdosta kasvaneet suuriksi kokonaisuuksiksi. Kokonaisuuksia hallitaan erilaisilla verkonhallintatyökaluilla. Verkonhallintatyökalut sisältävät suuren määrän eri tasoista tietoa laitteista ja laitteiden välisistä suhteista. Kokonaisuuksien hahmottaminen ilman tiedoista rakennettua kuvaa on vaikeaa ja hidasta. Laajakaistaverkon topologian visualisoinnissa muodostetaan kuva laitteista ja niiden välisistä suhteista. Visualisoitua kuvaa voidaan käyttää osana verkonhallintatyökalua, jolloin käyttäjälle muodostuu nopeasti näkymä verkon laitteista ja rakenteesta eli topologiasta. Visualisoinnissa kuvan piirto-ongelma täytyy muuttaa graafin piirto-ongelmaksi. Graafin piirto-ongelmassa verkon rakennetta käsitellään graafina, joka mahdollistaa kuvan muodostamisen automaattisia piirtomenetelmiä hyväksikäyttäen. Halutunlainen ulkoasu kuvalle muodostetaan automaattisilla piirtomenetelmillä, joilla laitteiden ja laitteiden välisten suhteiden esitystapoja voidaan muuttaa. Esitystavoilla voidaan muuttaa esimerkiksi laitteiden muotoa, väriä ja kokoa. Esitystapojen lisäksi piirtomenetelmien tärkein tehtävä on laskea laitteiden sijaintien koordinaattien arvot, jotka loppujen lopuksi määräävät koko kuvan rakenteen. Koordinaattien arvot lasketaan piirtoalgoritmeilla, joista voimiin perustuvat algoritmit sopivat parhaiten laajakaistaverkkojen laitteiden sijaintien laskemiseen. Tämän diplomityön käytännön työssä toteutettiin laajakaistaverkon topologian visualisointityökalu.

Lossless Compression Methods for Multispectral Images: Development and Comparisons

Main purpose of this thesis is to introduce a new lossless compression algorithm for multispectral images. Proposed algorithm is based on reducing the band ordering problem to the problem of finding a minimum spanning tree in a weighted directed graph, where set of the graph vertices corresponds to multispectral image bands and the arcs’ weights have been computed using a newly invented adaptive linear prediction model. The adaptive prediction model is an extended unification of 2–and 4–neighbour pixel context linear prediction schemes. The algorithm provides individual prediction of each image band using the optimal prediction scheme, defined by the adaptive prediction model and the optimal predicting band suggested by minimum spanning tree. Its efficiency has been compared with respect to the best lossless compression algorithms for multispectral images. Three recently invented algorithms have been considered. Numerical results produced by these algorithms allow concluding that adaptive prediction based algorithm is the best one for lossless compression of multispectral images. Real multispectral data captured from an airplane have been used for the testing.

Computing the diameter of Coxeter groups

This thesis addresses the problem of computing the minimal and maximal diameter of the Cayley graph of Coxeter groups. We first present and assert relevant parts of polytope theory and related Coxeter theory. After this, a method of contracting the orthogonal projections of a polytope from Rd onto R2 and R3, d ¸ 3 is presented. This method is the Equality Set Projection algorithm that requires a constant number of linearprogramming problems per facet of the projection in the absence of degeneracy. The ESP algorithm allows us to compute also projected geometric diameters of high-dimensional polytopes. A representation set of projected polytopes is presented to illustrate the methods adopted in this thesis.

Suljetun jäähdytysvesiverkon mallinnus

Työssä selvitettiin Neste Oil Porvoon jalostamon tuotantolinja 2 jäähdytysvesiverkon tilaa. Jäähdytysvesiverkon hydraulinen malli päivitettiin ja verifioitiin painemittauksin. Mallia tarkennettiin säätöventtiilien mallinnuksen sekä virhelähteiden tarkastelun perusteella havaituin muutoksin. Mallin verifioinnissa havaittiin huomattavia eroja mallin ja mitattujen paineiden välillä. Tämä johti mallin tarkempaan tarkasteluun, sekä virhelähteiden ja niiden vaikutusten selvittämiseen. Putkivarusteiden mallinnusmenetelmiä, sekä mallinnusperiaatteita vertailtiin keskenään. Koska jäähdytysveden kokonaiskierto oli riittämätön, tarkasteltiin kolmea vaihtoehtoa riittävän kiertovesimäärän aikaansaamiseksi. Nykyisten kiertovesipumppujen rinnanoperointi, sekä riittävän suureksi skaalatun pumpun käyttö simuloitiin. Kolmantena tapauksena arvioitiin lämmönvaihdinkohtaisen kuristussuunnitelman vaikutus putkiston painehäviöön, sekä putkistolle sopiva kiertovesipumppu. Vaihtoehdoille laskettiin suuntaa-antavat investointi- ja käyttökustannukset. Tarkastelun perusteella riittävän suureksi skaalattu pumppu todettiin kannattavimmaksi pienen hintaeron, sekä luotettavamman jäähdytysvesikierron käyttövarmuuden vuoksi. Työssä onnistuttiin tuottamaan yleispätevää tietoa suljetun jäähdytysvesiverkon hydrauliseen mallinnukseen vaikuttavista tekijöistä, sekä niiden vaikutuksesta mallin tarkkuuteen. Selvityksen perusteella tarkasteltua mallia saatiin tarkemmaksi.

Soodakattiloiden ilmakanavien hyödyntäminen jäykistävänä rakenteena

Työssä tutkittiin soodakattiloiden ilmakanavien hyödyntämistä jäykistävänä rakenteena. Työssä käsiteltiin yksittäisiä jäykistämättömiä ja jäykistettyjä levykenttiä ja niiden lommahduskestävyyttä Eurokoodi standardin mukaisesti ja elementtimenetelmän avulla. Lisäksi käsiteltiin lommahduksen teoriaa ja levykenttien käyttäytymistä yleisellä tasolla erilaisilla kuormituksilla ja reunaehdoilla. Työn tavoitteena oli selvittää kuinka lommahdus tutkitaan Eurokoodin mukaisesti ja elementtimenetelmää hyödyntäen, kun levykentän kuormituksena on poikittainen kuormitus tason suuntaisen kuormituksen lisäksi. Työssä tutkittiin kahden eri elementtimenetelmään pohjautuvan ratkaisuvaihtoehdon käyttöä lommahduslaskennassa. Työssä kehitettiin Eurokoodin sovellettu yhteisvaikutuskaavan käyttö lineaarisen ominaisarvotehtävän ratkaisun lisänä, jossa otetaan huomioon painekuorman vaikutus levykentän lommahduksessa. Kehitettyä menetelmää sovellettiin ilmakanavan esimerkkirakenteen mitoituksessa.

Heat flux measurement inside internal combustion engine with gradient heat flux sensor.

This master’s thesis is devoted to study different heat flux measurement techniques such as differential temperature sensors, semi-infinite surface temperature methods, calorimetric sensors and gradient heat flux sensors. The possibility to use Gradient Heat Flux Sensors (GHFS) to measure heat flux in the combustion chamber of compression ignited reciprocating internal combustion engines was considered in more detail. A. Mityakov conducted an experiment, where Gradient Heat Flux Sensor was placed in four stroke diesel engine Indenor XL4D to measure heat flux in the combustion chamber. The results which were obtained from the experiment were compared with model’s numerical output. This model (a one – dimensional single zone model) was implemented with help of MathCAD and the result of this implementation is graph of heat flux in combustion chamber in relation to the crank angle. The values of heat flux throughout the cycle obtained with aid of heat flux sensor and theoretically were sufficiently similar, but not identical. Such deviation is rather common for this type of experiment.

Biomedical Event Extraction with Machine Learning

Biomedical natural language processing (BioNLP) is a subfield of natural language processing, an area of computational linguistics concerned with developing programs that work with natural language: written texts and speech. Biomedical relation extraction concerns the detection of semantic relations such as protein-protein interactions (PPI) from scientific texts. The aim is to enhance information retrieval by detecting relations between concepts, not just individual concepts as with a keyword search. In recent years, events have been proposed as a more detailed alternative for simple pairwise PPI relations. Events provide a systematic, structural representation for annotating the content of natural language texts. Events are characterized by annotated trigger words, directed and typed arguments and the ability to nest other events. For example, the sentence “Protein A causes protein B to bind protein C” can be annotated with the nested event structure CAUSE(A, BIND(B, C)). Converted to such formal representations, the information of natural language texts can be used by computational applications. Biomedical event annotations were introduced by the BioInfer and GENIA corpora, and event extraction was popularized by the BioNLP'09 Shared Task on Event Extraction. In this thesis we present a method for automated event extraction, implemented as the Turku Event Extraction System (TEES). A unified graph format is defined for representing event annotations and the problem of extracting complex event structures is decomposed into a number of independent classification tasks. These classification tasks are solved using SVM and RLS classifiers, utilizing rich feature representations built from full dependency parsing. Building on earlier work on pairwise relation extraction and using a generalized graph representation, the resulting TEES system is capable of detecting binary relations as well as complex event structures. We show that this event extraction system has good performance, reaching the first place in the BioNLP'09 Shared Task on Event Extraction. Subsequently, TEES has achieved several first ranks in the BioNLP'11 and BioNLP'13 Shared Tasks, as well as shown competitive performance in the binary relation Drug-Drug Interaction Extraction 2011 and 2013 shared tasks. The Turku Event Extraction System is published as a freely available open-source project, documenting the research in detail as well as making the method available for practical applications. In particular, in this thesis we describe the application of the event extraction method to PubMed-scale text mining, showing how the developed approach not only shows good performance, but is generalizable and applicable to large-scale real-world text mining projects. Finally, we discuss related literature, summarize the contributions of the work and present some thoughts on future directions for biomedical event extraction. This thesis includes and builds on six original research publications. The first of these introduces the analysis of dependency parses that leads to development of TEES. The entries in the three BioNLP Shared Tasks, as well as in the DDIExtraction 2011 task are covered in four publications, and the sixth one demonstrates the application of the system to PubMed-scale text mining.

Scheduling dynamic dataflow graphs with model checking

With the shift towards many-core computer architectures, dataflow programming has been proposed as one potential solution for producing software that scales to a varying number of processor cores. Programming for parallel architectures is considered difficult as the current popular programming languages are inherently sequential and introducing parallelism is typically up to the programmer. Dataflow, however, is inherently parallel, describing an application as a directed graph, where nodes represent calculations and edges represent a data dependency in form of a queue. These queues are the only allowed communication between the nodes, making the dependencies between the nodes explicit and thereby also the parallelism. Once a node have the su cient inputs available, the node can, independently of any other node, perform calculations, consume inputs, and produce outputs. Data ow models have existed for several decades and have become popular for describing signal processing applications as the graph representation is a very natural representation within this eld. Digital lters are typically described with boxes and arrows also in textbooks. Data ow is also becoming more interesting in other domains, and in principle, any application working on an information stream ts the dataflow paradigm. Such applications are, among others, network protocols, cryptography, and multimedia applications. As an example, the MPEG group standardized a dataflow language called RVC-CAL to be use within reconfigurable video coding. Describing a video coder as a data ow network instead of with conventional programming languages, makes the coder more readable as it describes how the video dataflows through the different coding tools. While dataflow provides an intuitive representation for many applications, it also introduces some new problems that need to be solved in order for data ow to be more widely used. The explicit parallelism of a dataflow program is descriptive and enables an improved utilization of available processing units, however, the independent nodes also implies that some kind of scheduling is required. The need for efficient scheduling becomes even more evident when the number of nodes is larger than the number of processing units and several nodes are running concurrently on one processor core. There exist several data ow models of computation, with different trade-offs between expressiveness and analyzability. These vary from rather restricted but statically schedulable, with minimal scheduling overhead, to dynamic where each ring requires a ring rule to evaluated. The model used in this work, namely RVC-CAL, is a very expressive language, and in the general case it requires dynamic scheduling, however, the strong encapsulation of dataflow nodes enables analysis and the scheduling overhead can be reduced by using quasi-static, or piecewise static, scheduling techniques. The scheduling problem is concerned with nding the few scheduling decisions that must be run-time, while most decisions are pre-calculated. The result is then an, as small as possible, set of static schedules that are dynamically scheduled. To identify these dynamic decisions and to find the concrete schedules, this thesis shows how quasi-static scheduling can be represented as a model checking problem. This involves identifying the relevant information to generate a minimal but complete model to be used for model checking. The model must describe everything that may affect scheduling of the application while omitting everything else in order to avoid state space explosion. This kind of simplification is necessary to make the state space analysis feasible. For the model checker to nd the actual schedules, a set of scheduling strategies are de ned which are able to produce quasi-static schedulers for a wide range of applications. The results of this work show that actor composition with quasi-static scheduling can be used to transform data ow programs to t many different computer architecture with different type and number of cores. This in turn, enables dataflow to provide a more platform independent representation as one application can be fitted to a specific processor architecture without changing the actual program representation. Instead, the program representation is in the context of design space exploration optimized by the development tools to fit the target platform. This work focuses on representing the dataflow scheduling problem as a model checking problem and is implemented as part of a compiler infrastructure. The thesis also presents experimental results as evidence of the usefulness of the approach.

Algorithmic Techniques in Gene Expression Processing. From Imputation to Visualization

The amount of biological data has grown exponentially in recent decades. Modern biotechnologies, such as microarrays and next-generation sequencing, are capable to produce massive amounts of biomedical data in a single experiment. As the amount of the data is rapidly growing there is an urgent need for reliable computational methods for analyzing and visualizing it. This thesis addresses this need by studying how to efficiently and reliably analyze and visualize high-dimensional data, especially that obtained from gene expression microarray experiments. First, we will study the ways to improve the quality of microarray data by replacing (imputing) the missing data entries with the estimated values for these entries. Missing value imputation is a method which is commonly used to make the original incomplete data complete, thus making it easier to be analyzed with statistical and computational methods. Our novel approach was to use curated external biological information as a guide for the missing value imputation. Secondly, we studied the effect of missing value imputation on the downstream data analysis methods like clustering. We compared multiple recent imputation algorithms against 8 publicly available microarray data sets. It was observed that the missing value imputation indeed is a rational way to improve the quality of biological data. The research revealed differences between the clustering results obtained with different imputation methods. On most data sets, the simple and fast k-NN imputation was good enough, but there were also needs for more advanced imputation methods, such as Bayesian Principal Component Algorithm (BPCA). Finally, we studied the visualization of biological network data. Biological interaction networks are examples of the outcome of multiple biological experiments such as using the gene microarray techniques. Such networks are typically very large and highly connected, thus there is a need for fast algorithms for producing visually pleasant layouts. A computationally efficient way to produce layouts of large biological interaction networks was developed. The algorithm uses multilevel optimization within the regular force directed graph layout algorithm.