This dissertation can be essentially divided into two parts. The first, consisting of Chapters I, II, and III, studies the graph theoretic nature of complex systems. This includes the spectral properties of such systems and in particular their influence on the systems dynamics. In the second part of this dissertation, or Chapter IV, we consider a new class of one-dimensional dynamical systems or functions with an eventual negative Schwarzian derivative motivated by some maps arising in neuroscience. To aid in understanding the interplay between the graph structure of a network and its dynamics we first introduce the concept of an isospectral graph reduction in Chapter I. Mathematically, an isospectral graph transformation is a graph operation (equivalently matrix operation) that modifies the structure of a graph while preserving the eigenvalues of the graphs weighted adjacency matrix. Because of their properties such reductions can be used to study graphs (networks) modulo any specific graph structure e.g. cycles of length n, cliques of size k, nodes of minimal/maximal degree, centrality, betweenness, etc. The theory of isospectral graph reductions has also lead to improvements in the general theory of eigenvalue approximation. Specifically, such reductions can be used to improved the classical eigenvalue estimates of Gershgorin, Brauer, Brualdi, and Varga for a complex valued matrix. The details of these specific results are found in Chapter II. The theory of isospectral graph transformations is then used in Chapter III to study time-delayed dynamical systems and develop the notion of a dynamical network expansion and reduction which can be used to determine whether a network of interacting dynamical systems has a unique global attractor. In Chapter IV we consider one-dimensional dynamical systems of an interval. In the study of such systems it is often assumed that the functions involved have a negative Schwarzian derivative. Here we consider a generalization of this condition. Specifically, we consider the functions which have some iterate with a negative Schwarzian derivative and show that many known results generalize to this larger class of functions. This includes both systems with regular as well as chaotic dynamic properties.

To avoid expensive round-trips between the application layer and the database layer it is crucial that data-intensive processing and calculations happen close to where the data resides -- ideally within the database engine. However, each application has its own domain and provides domain-specific languages (DSL) as a user interface to keep interactions confined within the well-known metaphors of the respective domain. Revealing the innards of the underlying data layer by forcing users to formulate problems in terms of a general database language is often not an option. To bridge that gap, we propose an approach to transform and directly compile a DSL into a general database execution plan using graph transformations. We identify the commonalities and mismatches between different models and show which parts can be cherry-picked for direct translation. Finally, we argue that graph transformations can be used in general to translate a DSL into an executable plan for a database.

Cyber-physical systems achieve sophisticated system behavior exploring the tight interconnection of physical coupling present in classical engineering systems and information technology based coupling. A particular challenging case are systems where these cyber-physical systems are formed ad hoc according to the specific local topology, the available networking capabilities, and the goals and constraints of the subsystems captured by the information processing part. In this paper we present a formalism that permits to model the sketched class of cyber-physical systems. The ad hoc formation of tightly coupled subsystems of arbitrary size are specified using a UML-based graph transformation system approach. Differential equations are employed to define the resulting tightly coupled behavior. Together, both form hybrid graph transformation systems where the graph transformation rules define the discrete steps where the topology or modes may change, while the differential equations capture the continuous behavior in between such discrete changes. In addition, we demonstrate that automated analysis techniques known for timed graph transformation systems for inductive invariants can be extended to also cover the hybrid case for an expressive case of hybrid models where the formed tightly coupled subsystems are restricted to smaller local networks. / Cyber-physical Systeme erzielen ihr ausgefeiltes Systemverhalten durch die enge Verschränkung von physikalischer Kopplung, wie sie in Systemen der klassichen Igenieurs-Disziplinen vorkommt, und der Kopplung durch Informationstechnologie. Eine besondere Herausforderung stellen in diesem Zusammenhang Systeme dar, die durch die spontane Vernetzung einzelner Cyber-Physical-Systeme entsprechend der lokalen, topologischen Gegebenheiten, verfügbarer Netzwerkfähigkeiten und der Anforderungen und Beschränkungen der Teilsysteme, die durch den informationsverabeitenden Teil vorgegeben sind, entstehen. In diesem Bericht stellen wir einen Formalismus vor, der die Modellierung der eingangs skizzierten Systeme erlaubt. Ein auf UML aufbauender Graph-Transformations-Ansatz wird genutzt, um die spontane Bildung eng kooperierender Teilsysteme beliebiger Größe zu spezifizieren. Differentialgleichungen beschreiben das kombinierte Verhalten auf physikalischer Ebene. In Kombination ergeben diese beiden Formalismen hybride Graph-Transformations-Systeme, in denen die Graph-Transformationen diskrete Schritte und die Differentialgleichungen das kontinuierliche, physikalische Verhalten des Systems beschreiben. Zusätzlich, präsentieren wir die Erweiterung einer automatischen Analysetechnik zur Verifikation induktiver Invarianten, die bereits für zeitbehaftete Systeme bekannt ist, auf den ausdrucksstärkeren Fall der hybriden Modelle.

Contemporary systems engineering problems are becoming increasingly complex as they are handled by geographically distributed design teams, constrained by the objectives of multiple stakeholders, and inundated by large quantities of design information. According to the principles of model-based systems engineering (MBSE), engineers can effectively manage increasing complexity by replacing document-centric design methods with computerized, model-based approaches. In this thesis, modeling constructs from SysML and Modelica are integrated to improve support for MBSE. The Object Management Group has recently developed the Systems Modeling Language (OMG SysML ) to provide a comprehensive set constructs for modeling many common aspects of systems engineering problems (e.g. system requirements, structures, functions). Complementing these SysML constructs, the Modelica language has emerged as a standard for modeling the continuous dynamics (CD) of systems in terms of hybrid discrete- event and differential algebraic equation systems. The integration of SysML and Modelica is explored from three different perspectives: the definition of CD models in SysML; the use of graph transformations to automate the transformation of SysML CD models into Modelica models; and the integration of CD models and other SysML models (e.g. structural, requirements) through the depiction of simulation experiments and engineering analyses. Throughout the thesis, example models of a car suspension and a hydraulically-powered excavator are used for demonstration. The core result of this work is the provision of modeling abilities that do not exist independently in SysML or Modelica. These abilities allow systems engineers to prescribe necessary system analyses and relate them to stakeholder concerns and other system aspects. Moreover, this work provides a basis for model integration which can be generalized and re-specialized for integrating other modeling formalisms into SysML.

In simulation-based design, a key challenge is to formulate and solve analysis problems efficiently to evaluate a large variety of design alternatives. The solution of analysis problems has benefited from advancements in commercial off-the-shelf math solvers and computational capabilities. However, the formulation of analysis problems is often a costly and laborious process. Traditional simulation templates used for representing analysis problems are typically brittle with respect to variations in artifact topology and the idealization decisions taken by analysts. These templates often require manual updates and "re-wiring" of the analysis knowledge embodied in them. This makes the use of traditional simulation templates ineffective for multi-disciplinary design and optimization problems. Based on these issues, this dissertation defines a special class of problems known as variable topology multi-body (VTMB) problems that characterizes the types of variations seen in design-analysis interoperability. This research thus primarily answers the following question: How can we improve the effectiveness of the analysis problem formulation process for VTMB problems? The knowledge composition methodology (KCM) presented in this dissertation answers this question by addressing the following research gaps: (1) the lack of formalization of the knowledge used by analysts in formulating simulation templates, and (2) the inability to leverage this knowledge to define model composition methods for formulating simulation templates. KCM overcomes these gaps by providing: (1) formal representation of analysis knowledge as modular, reusable, analyst-intelligible building blocks, (2) graph transformation-based methods to automatically compose simulation templates from these building blocks based on analyst idealization decisions, and (3) meta-models for representing advanced simulation templates VTMB design models, analysis models, and the idealization relationships between them. Applications of the KCM to thermo-mechanical analysis of multi-stratum printed wiring boards and multi-component chip packages demonstrate its effectiveness handling VTMB and idealization variations with significantly enhanced formulation efficiency (from several hours in existing methods to few minutes). In addition to enhancing the effectiveness of analysis problem formulation, KCM is envisioned to provide a foundational approach to model formulation for generalized variable topology problems.

Design synthesis is a fundamental engineering task that involves the creation of structure from a desired functional specification; it involves both creating a system topology as well as sizing the system's components. Although the use of computer tools is common throughout the design process, design synthesis is often a task left to the designer. At the synthesis stage of the design process, designers have an extensive choice of design alternatives that need to be considered and evaluated. Designers can benefit from computational synthesis methods in the creative phase of the design process. Recent increases in computational power allow automated synthesis methods for rapidly generating a large number of design solutions. Combining an automated synthesis method with an evaluation framework allows for a more thorough exploration of the design space as well as for a reduction of the time and cost needed to design a system. To facilitate computational synthesis, knowledge about feasible system configurations must be captured. Since it is difficult to capture such synthesis knowledge about any possible system, a design domain must be chosen. In this thesis, the design domain is hydraulic systems. In this thesis, Model-Driven Software Development concepts are leveraged to create a framework to automate the synthesis of hydraulic systems will be presented and demonstrated. This includes the presentation of a domain specific language to describe the function and structure of hydraulic systems as well as a framework for synthesizing hydraulic systems using graph grammars to generate system topologies. Also, a method using graph grammars for generating analysis models from the described structural system representations is presented. This approach fits in the context of Model-Based Systems Engineering where a variety of formal models are used to represent knowledge about a system. It uses the Systems Modeling Language developed by The Object Management Group (OMG SysML™) as a unifying language for model definition.

Uno de los problemas más importantes que se propuso solucionar cuando apareció la Ingeniería Web fue la carencia de técnicas para la especificación de requisitos de aplicaciones Web. Aunque se han presentado diversas propuestas que proporcionan soporte metodológico al desarrollo de aplicaciones Web, la mayoría de ellas se centran básicamente en definir modelos conceptuales que permiten representar de forma abstracta una aplicación Web; las actividades relacionadas con la especificación de requisitos son vagamente tratadas por estas propuestas. Además, las técnicas tradicionales para la especificación de requisitos no proporcionan un soporte adecuado para considerar características propias de las aplicaciones Web como la Navegación. En esta tesis, se presenta una aproximación de Ingeniería de Requisitos para especificar los requisitos de las aplicaciones Web. Esta aproximación incluye mecanismos basados en la metáfora de tarea para especificar no sólo los requisitos relacionados con aspectos estructurales y de comportamiento de una aplicación Web sino también los requisitos relacionados con aspectos navegacionales. Sin embargo, una especificación de requisitos es poco útil si no somos capaces de transformarla en los artefactos software adecuados. Este es un problema clásico que la comunidad de Ingeniería del Software ha tratado de resolver desde sus inicios: cómo pasar del espacio del problema (requisitos de usuario) al espacio de la solución (diseño e implementación) siguiendo una guía metodológica clara y precisa. En esta tesis, se presenta una estrategia que, basándose en transformaciones de grafos, y estando soportada por un conjunto de herramientas, nos permite realizar de forma automática transformaciones entre especificaciones de requisitos basadas en tareas y esquemas conceptuales Web. Además, esta estrategia se ha integrado con un método de Ingeniería Web con capacidades de generación automática de código. Esta integración nos permite proporcionar un mecanis / Valderas Aranda, PJ. (2008). A requirements engineering approach for the development of web applications [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/1997 / Palancia

De nombreux domaines comme le jeu vidéo, l’architecture, l’ingénierie ou l’archéologie font désormais appel à la modélisation géométrique. Les objets à représenter sont de natures diverses, et leurs opérations de manipulation sont spécifiques. Ainsi, les modeleurs sont nombreux car tous spécialisés à leur domaine d’application. Or ils sont à la fois chers à développer, souvent peu robustes, et difficilement extensibles. Nous avons proposé dans la thèse l’approche alternative suivante :– fournir un langage dédié à la modélisation qui permet de définir les opérations quelque soit le domaine d’application ; dans ce langage, les objets sont représentés avec le modèle topologique des cartes généralisées, dont nous avons étendu la définition aux plongements ; les opérations sont elles définies par des règles de transformation de graphes, issues de la théorie des catégorie ;– garantir les opérations définies dans le langage à l’aide de conditions de cohérence ; une opération dont la définition vérifie ces conditions ne produit pas d’anomalie ;– développer un noyau de modeleur générique qui interprète ce langage ; les opérations définies sont directement appliquées dans le modeleur, sans implantation dans un langage de programmation ; l’outil assure également la vérification automatique des conditions du langage pour prévenir un utilisateur lorsqu’il propose une opération incohérente.Le langage et le modeleur développés se sont révélés performants à la fois en termes de temps de développement et en termes de temps machine. L’implantation d’une nouvelle opération par une règle ne prend que quelques minutes à l’aide des conditions du langage, au contraire de l’approche classi / Geometric modeling is now involved in many fields such as: video games, architecture, engineering and archaeology. The represented objects are very different from one field to another, and so are their modeling operations. Furthermore, many specific types of modeling software are designed for high programing costs, but with a relatively low rate of effectiveness.The following is an alternative approach:– we have conceived a dedicated language for geometric modeling that will allow us to define any operation of any field; objects in this language are defined with the topological model of generalized maps, this definition has been extended to the embedding informations; here the operations are defined as graph transformation rules which originate from the category theory;– we have ensured operation definitions with consistency conditions; these operations that satisfy those conditions do not generate anomalies; – we have designed generic modeling software to serve as an interpreter of this language; the operation definitions are directly applied without the need for more programing; the software also automatically checks the language conditions and warns the user if he designs a non-consistent operation.The provided language and software prove to be efficient, and all for a low programing cost. Designing a new operation takes only minutes thanks to the language conditions, as opposed to hours of programming and debugging with the past approach.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.