Dans cette thèse, nous étudions diverses largeurs de graphes autour de la largeur arborescente ainsi que de la largeur de clique. Nous commençons avec une étude comparative entre la largeur arborescente d’un graphe et la largeur de clique du graphe d’incidence associé, de laquelle nous extrayons des résultats algorithmiques encourageants. Puis nous présentons quelques propriétés structurelles liées à la largeur arborescente spéciale, largeur relativement récente qui est à mi-chemin entre les deux largeurs précédentes. Enfin nous nous intéressons à une notion plus générale connue sous le nom de fonction de partition sous-modulaire qui englobe, entre autres, les largeurs arborescentes « classique » et spéciale, la largeur de chemin ainsi que la largeur linéaire et les largeurs de branches de coupe et de découpe. Nous présentons alors un algorithme linéaire à paramètre fixé pour le calcul de ces différentes largeurs, lequel généralise un certain nombre de résultats propres à chacune de ces largeurs. / In this thesis, we study some width parameters on graphs, beyond tree-width and clique-width. Our first investigation is a comparative study between the tree-width of a graph and the clique-width of the associated incidence graph, from which we extract some strong algorithmic results. Then we present a few structural properties over a recently defined width called special tree-width and which takes its definition through both tree-width and clique-width. Finally, we end our journey with a more general notion named sub-modular partition fonction and which encompass both “classic” and special tree-widths, path-width, branch-width, linear-width, cut-width and carvingwidth among others. So, we introduce a fixed parameter tractable algorithm computing those widths parameters and thus we generalize a number of results specific to each of them.

During the overall development of complex engineering systems different modeling notations are employed. For example, in the domain of automotive systems system engineering models are employed quite early to capture the requirements and basic structuring of the entire system, while software engineering models are used later on to describe the concrete software architecture. Each model helps in addressing the specific design issue with appropriate notations and at a suitable level of abstraction. However, when we step forward from system design to the software design, the engineers have to ensure that all decisions captured in the system design model are correctly transferred to the software engineering model. Even worse, when changes occur later on in either model, today the consistency has to be reestablished in a cumbersome manual step. In this report, we present in an extended version of [Holger Giese, Stefan Neumann, and Stephan Hildebrandt. Model Synchronization at Work: Keeping SysML and AUTOSAR Models Consistent. In Gregor Engels, Claus Lewerentz, Wilhelm Schäfer, Andy Schürr, and B. Westfechtel, editors, Graph Transformations and Model Driven Enginering - Essays Dedicated to Manfred Nagl on the Occasion of his 65th Birthday, volume 5765 of Lecture Notes in Computer Science, pages 555–579. Springer Berlin / Heidelberg, 2010.] how model synchronization and consistency rules can be applied to automate this task and ensure that the different models are kept consistent. We also introduce a general approach for model synchronization. Besides synchronization, the approach consists of tool adapters as well as consistency rules covering the overlap between the synchronized parts of a model and the rest. We present the model synchronization algorithm based on triple graph grammars in detail and further exemplify the general approach by means of a model synchronization solution between system engineering models in SysML and software engineering models in AUTOSAR which has been developed for an industrial partner. In the appendix as extension to [19] the meta-models and all TGG rules for the SysML to AUTOSAR model synchronization are documented. / Bei der Entwicklung komplexer technischer Systeme werden verschiedene Modellierungssprachen verwendet. Zum Beispiel werden bei der Entwicklung von Systemen in der Automobilindustrie bereits früh im Entwicklungsprozess Systemmodelle verwendet, um die Anforderungen und die grobe Struktur des Gesamtsystems darzustellen. Später werden Softwaremodelle verwendet, um die konkrete Softwarearchitektur zu modellieren. Jedes Modell stellt spezifische Entwurfsaspekte mit Hilfe passender Notationen auf einem angemessenen Abstraktionsniveau dar. Wenn jedoch vom Systementwurf zum Softwareentwurf übergegangen wird, müssen die Entwicklungsingenieure sicherstellen, dass alle Entwurfsentscheidungen, die im Systemmodell enthalten sind, korrekt auf das Softwaremodell übertragen werden. Sobald danach auch noch Änderungen auftreten, muss die Konsistenz zwischen den Modellen in einem aufwändigen manuellen Schritt wiederhergestellt werden. In diesem Bericht zeigen wir, wie Modellsynchronisation und Konsistenzregeln zur Automatisierung dieses Arbeitsschrittes verwendet und die Konsistenz zwischen den Modellen sichergestellt werden können. Außerdem stellen wir einen allgemeinen Ansatz zur Modellsynchronisation vor. Neben der reinen Synchronisation umfasst unsere Lösung weiterhin Tool-Adapter, sowie Konsistenzregeln, die sowohl die Teile der Modelle abdecken, die synchronisiert werden können, als auch die restlichen Teile. Der Modellsynchronisationsalgorithmus basiert auf Tripel-Graph-Grammatiken und wird im Detail erläutert. An Hand einer konkreten Transformation zwischen SysML- und AUTOSAR-Modellen, die im Rahmen eines Industrieprojektes entwickelt wurde, wird der Ansatz demonstriert. Im Anhang des Berichts sind alle TGG-Regeln für die SysML-zu-AUTOSAR-Transformation dokumentiert.

This dissertation develops a new model transformation approach that supports engineering model integration, which is essential to support contemporary interdisciplinary system design processes. We extend traditional model transformation, which has been primarily used for software engineering, to enable model-based systems engineering (MBSE) so that the model transformation can handle more general engineering models. We identify two issues that arise when applying the traditional model transformation to general engineering modeling domains. The first is instance data integration: the traditional model transformation theory does not deal with instance data, which is essential for executing engineering models in engineering tools. The second is syntactical inconsistency: various engineering tools represent engineering models in a proprietary syntax. However, the traditional model transformation cannot handle this syntactic diversity. In order to address these two issues, we propose a new multi-layer syntactical model transformation approach. For the instance integration issue, this approach generates model transformation rules for instance data from the result of a model transformation that is developed for user model integration, which is the normal purpose of traditional model transformation. For the syntactical inconsistency issue, we introduce the concept of the complete meta-model for defining how to represent a model syntactically as well as semantically. Our approach addresses the syntactical inconsistency issue by generating necessary complete meta-models using a special type of model transformation.

The challenges in automating the design of planar mechanisms are tremendous especially in areas related to computational representation, kinematic analysis and synthesis of planar mechanisms. The challenge in computational representation relates to the development of a comprehensive methodology to completely define and manipulate the topologies of planar mechanisms while in kinematic analysis, the challenge is primarily in the development of generalized analysis routines to analyze different mechanism topologies. Combining the aforementioned challenges along with appropriate optimization algorithms to synthesize planar mechanisms for different user-defined applications presents the final challenge in the automated design of planar mechanisms. The methods presented in the literature demonstrate synthesis of standard four-bar and six-bar mechanisms with revolute and prismatic joints. But a detailed review of these methods point to the fact that they are not scalable when the topologies and the parameters of n-bar mechanisms are required to be simultaneously synthesized. Through this research, a comprehensive and scalable methodology for synthesizing different mechanism topologies and their parameters simultaneously is presented that overcomes the limitations in different challenge areas in the following ways. In representation, a graph-grammar based scheme for planar mechanisms is developed to completely describe the topology of a mechanism. Grammar rules are developed in conjunction with this representation scheme to generate different mechanism topologies in a tree-search process. In analysis, a generic kinematic analysis routine is developed to automatically analyze one-degree of freedom mechanisms consisting of revolute and prismatic joints. Two implementations of kinematic analysis have been included. The first implementation involves the use of graphical methods for position and velocity analyses and the equation method for acceleration analysis for mechanisms with a four-bar loop. The second implementation involves the use of an optimization-based method that has been developed to handle position kinematics of indeterminate mechanisms while the velocity and acceleration analyses of such mechanisms are carried out by formulating appropriate linear equations. The representation and analysis schemes are integrated to parametrically synthesize different mechanism topologies using a hybrid implementation of Particle Swarm Optimization and Nelder-Mead simplex algorithm. The hybrid implementation is able to produce better results for the problems found in the literature using a four-bar mechanism with revolute joints as well as through other higher order mechanisms from the design space. The implementation has also been tested on three new challenge problems with satisfactory results subject to computational constraints. The difficulties in the search have been studied that indicates the reasons for the lack of solution repeatability. This dissertation concludes with a discussion of the results and future directions. / text

Procedural terrain generation is a field that handles procedural, not by hand, generated realistic looking terrain for use in simulations, video games, movie special effects or art. It allows for creation of vast and far more detailed terrain than humans can create by hand. In this paper a new method for procedural terrain generation is presented. Terrain is generated in three steps. An arbitrarily shaped network oh nodes, a graph, is used as a base to design the shape and layout of terrain features. Common algorithms are used to generate custom terrain features inside the graphs sealed areas and finally the generated terrain is merged into a single piece using a new method. In this manner, more controlled and detailed terrain can be created as the layout and shape of features can be controlled. / Området terräng generering hanterar procedurellt, icke för hand, skapande utav realistisk terräng för användning inom simulationer, data spel, filmers specialeffekter och konst. I denna uppsats presenteras en ny metod för procedurell terräng generation. Terrängen genereras i tre steg. Ett godtyckligt nätverk av noder skapas, en graf, och används som grund för att designa och forma utläggningen av terrängens drag. Kända algoritmer används för att skapa dragen inuti grafens tomma ytor och slutgiltigen sys den genererade terrängen ihop till en sammanhängande helhet med en ny metod. På detta vis kan man skapa mera detaljerad och bättre styrd terräng då man både kan kontrollera dragens former och utläggning. Nyckelord: Terräng, realtid datorgrafik, digital-kartografi, graf-grammatik, Perlin