Download or read book k Inductive invariant checking for graph transformation systems written by Dyck, Johannes and published by Universitätsverlag Potsdam. This book was released on 2017-09-15 with total page 52 pages. Available in PDF, EPUB and Kindle. Book excerpt: While offering significant expressive power, graph transformation systems often come with rather limited capabilities for automated analysis, particularly if systems with many possible initial graphs and large or infinite state spaces are concerned. One approach that tries to overcome these limitations is inductive invariant checking. However, the verification of inductive invariants often requires extensive knowledge about the system in question and faces the approach-inherent challenges of locality and lack of context. To address that, this report discusses k-inductive invariant checking for graph transformation systems as a generalization of inductive invariants. The additional context acquired by taking multiple (k) steps into account is the key difference to inductive invariant checking and is often enough to establish the desired invariants without requiring the iterative development of additional properties. To analyze possibly infinite systems in a finite fashion, we introduce a symbolic encoding for transformation traces using a restricted form of nested application conditions. As its central contribution, this report then presents a formal approach and algorithm to verify graph constraints as k-inductive invariants. We prove the approach's correctness and demonstrate its applicability by means of several examples evaluated with a prototypical implementation of our algorithm.
Download or read book Invariant Analysis for Multi Agent Graph Transformation Systems using k Induction written by Sven Schneider and published by Universitätsverlag Potsdam. This book was released on 2022-11-17 with total page 44 pages. Available in PDF, EPUB and Kindle. Book excerpt: The analysis of behavioral models such as Graph Transformation Systems (GTSs) is of central importance in model-driven engineering. However, GTSs often result in intractably large or even infinite state spaces and may be equipped with multiple or even infinitely many start graphs. To mitigate these problems, static analysis techniques based on finite symbolic representations of sets of states or paths thereof have been devised. We focus on the technique of k-induction for establishing invariants specified using graph conditions. To this end, k-induction generates symbolic paths backwards from a symbolic state representing a violation of a candidate invariant to gather information on how that violation could have been reached possibly obtaining contradictions to assumed invariants. However, GTSs where multiple agents regularly perform actions independently from each other cannot be analyzed using this technique as of now as the independence among backward steps may prevent the gathering of relevant knowledge altogether. In this paper, we extend k-induction to GTSs with multiple agents thereby supporting a wide range of additional GTSs. As a running example, we consider an unbounded number of shuttles driving on a large-scale track topology, which adjust their velocity to speed limits to avoid derailing. As central contribution, we develop pruning techniques based on causality and independence among backward steps and verify that k-induction remains sound under this adaptation as well as terminates in cases where it did not terminate before.
Download or read book Inductive invariant checking with partial negative application conditions written by Dyck, Johannes and published by Universitätsverlag Potsdam. This book was released on 2016-04-13 with total page 48 pages. Available in PDF, EPUB and Kindle. Book excerpt: Graph transformation systems are a powerful formal model to capture model transformations or systems with infinite state space, among others. However, this expressive power comes at the cost of rather limited automated analysis capabilities. The general case of unbounded many initial graphs or infinite state spaces is only supported by approaches with rather limited scalability or expressiveness. In this report we improve an existing approach for the automated verification of inductive invariants for graph transformation systems. By employing partial negative application conditions to represent and check many alternative conditions in a more compact manner, we can check examples with rules and constraints of substantially higher complexity. We also substantially extend the expressive power by supporting more complex negative application conditions and provide higher accuracy by employing advanced implication checks. The improvements are evaluated and compared with another applicable tool by considering three case studies.
Download or read book Graph Transformation written by Juan de Lara and published by Springer. This book was released on 2017-07-03 with total page 239 pages. Available in PDF, EPUB and Kindle. Book excerpt: This book constitutes the refereed proceedings of the 10th International Conference on Graph Transformation, ICGT 2017, held as part of STAF 2017, in Marburg, Germany, in July 2017. The 14 papers presented were carefully reviewed and selected from 23 submissions. The papers cover a wide range of topics including theoretical approaches to graph transformation and their verification, model-driven engineering, chemical reactions as well as various applications. They are organized in the following topical sections: foundations; graph language and parsing; analysis and verification; and model transformation and tools.
Download or read book Graph Transformation written by Russ Harmer and published by Springer Nature. This book was released on with total page 248 pages. Available in PDF, EPUB and Kindle. Book excerpt:
Download or read book Graph Transformation written by Nicolas Behr and published by Springer Nature. This book was released on 2022-06-30 with total page 216 pages. Available in PDF, EPUB and Kindle. Book excerpt: This book constitutes the refereed proceedings of the 15th International Conference on Graph Transformation, ICGT 2022, which took place Nantes, France in July 2022. The 10 full papers and 1 tool paper presented in this book were carefully reviewed and selected from 19 submissions. The conference focuses on describing new unpublished contributions in the theory and applications of graph transformation as well as tool presentation papers that demonstrate main new features and functionalities of graph-based tools.
Download or read book Automatic verification of behavior preservation at the transformation level for relational model transformation written by Dyck, Johannes and published by Universitätsverlag Potsdam. This book was released on 2017-04-26 with total page 126 pages. Available in PDF, EPUB and Kindle. Book excerpt: The correctness of model transformations is a crucial element for model-driven engineering of high quality software. In particular, behavior preservation is the most important correctness property avoiding the introduction of semantic errors during the model-driven engineering process. Behavior preservation verification techniques either show that specific properties are preserved, or more generally and complex, they show some kind of behavioral equivalence or refinement between source and target model of the transformation. Both kinds of behavior preservation verification goals have been presented with automatic tool support for the instance level, i.e. for a given source and target model specified by the model transformation. However, up until now there is no automatic verification approach available at the transformation level, i.e. for all source and target models specified by the model transformation. In this report, we extend our results presented in [27] and outline a new sophisticated approach for the automatic verification of behavior preservation captured by bisimulation resp. simulation for model transformations specified by triple graph grammars and semantic definitions given by graph transformation rules. In particular, we show that the behavior preservation problem can be reduced to invariant checking for graph transformation and that the resulting checking problem can be addressed by our own invariant checker even for a complex example where a sequence chart is transformed into communicating automata. We further discuss today's limitations of invariant checking for graph transformation and motivate further lines of future work in this direction.
Download or read book Fundamental Approaches to Software Engineering written by Reiner Hähnle and published by Springer. This book was released on 2019-04-03 with total page 446 pages. Available in PDF, EPUB and Kindle. Book excerpt: This book is Open Access under a CC BY licence. This book constitutes the proceedings of the 22nd International Conference on Fundamental Approaches to Software Engineering, FASE 2019, which took place in Prague, Czech Republic in April 2019, held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019.The 24 papers presented in this volume were carefully reviewed and selected from 94 submissions. The papers are organized in topical sections named: software verification; model-driven development and model transformation; software evolution and requirements engineering; specification, design, and implementation of particular classes of systems; and software testing.
Download or read book Metric Temporal Graph Logic over Typed Attributed Graphs written by Giese, Holger and published by Universitätsverlag Potsdam. This book was released on 2019 with total page 38 pages. Available in PDF, EPUB and Kindle. Book excerpt: Graph repair, restoring consistency of a graph, plays a prominent role in several areas of computer science and beyond: For example, in model-driven engineering, the abstract syntax of models is usually encoded using graphs. Flexible edit operations temporarily create inconsistent graphs not representing a valid model, thus requiring graph repair. Similarly, in graph databases—managing the storage and manipulation of graph data—updates may cause that a given database does not satisfy some integrity constraints, requiring also graph repair. We present a logic-based incremental approach to graph repair, generating a sound and complete (upon termination) overview of least-changing repairs. In our context, we formalize consistency by so-called graph conditions being equivalent to first-order logic on graphs. We present two kind of repair algorithms: State-based repair restores consistency independent of the graph update history, whereas deltabased (or incremental) repair takes this history explicitly into account. Technically, our algorithms rely on an existing model generation algorithm for graph conditions implemented in AutoGraph. Moreover, the delta-based approach uses the new concept of satisfaction (ST) trees for encoding if and how a graph satisfies a graph condition. We then demonstrate how to manipulate these STs incrementally with respect to a graph update.
Download or read book Graph Transformation written by Fabio Gadducci and published by Springer Nature. This book was released on 2020-06-25 with total page 346 pages. Available in PDF, EPUB and Kindle. Book excerpt: This book constitutes the refereed proceedings of the 13th International Conference on Graph Transformation, ICGT 2020, in Bergen, Norway, in June 2020.* The 16 research papers and 4 tool paper presented in this book were carefully reviewed and selected from 40 submissions. One invited paper is also included. The papers deal with the following topics: theoretical advances; application domains; and tool presentations. *The conference was held virtually due to the COVID-19 pandemic.
Download or read book Modeling and Formal Analysis of Meta Ecosystems with Dynamic Structure using Graph Transformation written by Boris Flotterer and published by Universitätsverlag Potsdam. This book was released on 2023-01-08 with total page 54 pages. Available in PDF, EPUB and Kindle. Book excerpt: The dynamics of ecosystems is of crucial importance. Various model-based approaches exist to understand and analyze their internal effects. In this paper, we model the space structure dynamics and ecological dynamics of meta-ecosystems using the formal technique of Graph Transformation (short GT). We build GT models to describe how a meta-ecosystem (modeled as a graph) can evolve over time (modeled by GT rules) and to analyze these GT models with respect to qualitative properties such as the existence of structural stabilities. As a case study, we build three GT models describing the space structure dynamics and ecological dynamics of three different savanna meta-ecosystems. The first GT model considers a savanna meta-ecosystem that is limited in space to two ecosystem patches, whereas the other two GT models consider two savanna meta-ecosystems that are unlimited in the number of ecosystem patches and only differ in one GT rule describing how the space structure of the meta-ecosystem grows. In the first two GT models, the space structure dynamics and ecological dynamics of the meta-ecosystem shows two main structural stabilities: the first one based on grassland-savanna-woodland transitions and the second one based on grassland-desert transitions. The transition between these two structural stabilities is driven by high-intensity fires affecting the tree components. In the third GT model, the GT rule for savanna regeneration induces desertification and therefore a collapse of the meta-ecosystem. We believe that GT models provide a complementary avenue to that of existing approaches to rigorously study ecological phenomena.
Download or read book Metric Temporal Graph Logic over Typed Attributed Graphs written by Holger Giese and published by Universitätsverlag Potsdam. This book was released on 2018 with total page 36 pages. Available in PDF, EPUB and Kindle. Book excerpt: Various kinds of typed attributed graphs are used to represent states of systems from a broad range of domains. For dynamic systems, established formalisms such as graph transformations provide a formal model for defining state sequences. We consider the extended case where time elapses between states and introduce a logic to reason about these sequences. With this logic we express properties on the structure and attributes of states as well as on the temporal occurrence of states that are related by their inner structure, which no formal logic over graphs accomplishes concisely so far. Firstly, we introduce graphs with history by equipping every graph element with the timestamp of its creation and, if applicable, its deletion. Secondly, we define a logic on graphs by integrating the temporal operator until into the well-established logic of nested graph conditions. Thirdly, we prove that our logic is equally expressive to nested graph conditions by providing a suitable reduction. Finally, the implementation of this reduction allows for the tool-based analysis of metric temporal properties for state sequences. Verschiedene Arten von getypten attributierten Graphen werden benutzt, um Zustände von Systemen in vielen unterschiedlichen Anwendungsbereichen zu beschreiben. Der etablierte Formalismus der Graphtransformationen bietet ein formales Model, um Zustandssequenzen für dynamische Systeme zu definieren. Wir betrachten den erweiterten Fall von solchen Sequenzen, in dem Zeit zwischen zwei verschiedenen Systemzuständen vergeht, und führen eine Logik ein, um solche Sequenzen zu beschreiben. Mit dieser Logik drücken wir zum einen Eigenschaften über die Struktur und die Attribute von Zuständen aus und beschreiben zum anderen temporale Vorkommen von Zuständen, die durch ihre innere Struktur verbunden sind. Solche Eigenschaften können bisher von keiner der existierenden Logiken auf Graphen vergleichbar darstellt werden. Erstens führen wir Graphen mit Änderungshistorie ein, indem wir jedes Graphelement mit einem Zeitstempel seiner Erzeugung und, wenn nötig, seiner Löschung versehen. Zweitens definieren wir eine Logik auf Graphen, indem wir den Temporaloperator Until in die wohl-etablierte Logik der verschachtelten Graphbedingungen integrieren. Drittens beweisen wir, dass unsere Logik gleich ausdrucksmächtig ist, wie die Logik der verschachtelten Graphbedingungen, indem wir eine passende Reduktionsoperation definieren. Zuletzt erlaubt uns die Implementierung dieser Reduktionsoperation die werkzeukbasierte Analyse von metrisch-temporallogischen Eigenschaften für Zustandssequenzen zu führen.
Download or read book Towards version control in object based systems written by Jakob Reschke and published by Universitätsverlag Potsdam. This book was released on 2018 with total page 106 pages. Available in PDF, EPUB and Kindle. Book excerpt: Version control is a widely used practice among software developers. It reduces the risk of changing their software and allows them to manage different configurations and to collaborate with others more efficiently. This is amplified by code sharing platforms such as GitHub or Bitbucket. Most version control systems track files (e.g., Git, Mercurial, and Subversion do), but some programming environments do not operate on files, but on objects instead (many Smalltalk implementations do). Users of such environments want to use version control for their objects anyway. Specialized version control systems, such as the ones available for Smalltalk systems (e.g., ENVY/Developer and Monticello), focus on a small subset of objects that can be versioned. Most of these systems concentrate on the tracking of methods, classes, and configurations of these. Other user-defined and user-built objects are either not eligible for version control at all, tracking them involves complicated workarounds, or a fixed, domain-unspecific serialization format is used that does not equally suit all kinds of objects. Moreover, these version control systems that are specific to a programming environment require their own code sharing platforms;popular, well-established platforms for file-based version control systems cannot be used or adapter solutions need to be implemented and maintained. To improve the situation for version control of arbitrary objects, a framework for tracking, converting, and storing of objects is presented in this report. It allows editions of objects to be stored in an exchangeable, existing backend version control system. The platforms of the backend version control system can thus be reused. Users and objects have control over how objects are captured for the purpose of version control. Domain-specific requirements can be implemented. The storage format (i.e. the file format, when file-based backend version control systems are used) can also vary from one object to another. Different editions of objects can be compared and sets of changes can be applied to graphs of objects. A generic way for capturing and restoring that supports most kinds of objects is described. It models each object as a collection of slots. Thus, users can begin to track their objects without first having to implement version control supplements for their own kinds of objects. The proposed architecture is evaluated using a prototype implementation that can be used to track objects in Squeak/Smalltalk with Git. The prototype improves the suboptimal standing of user objects with respect to version control described above and also simplifies some version control tasks for classes and methods as well. It also raises new problems, which are discussed in this report as well.
Download or read book Proceedings of the Fifth HPI Cloud Symposium Operating the Cloud 2017 written by Andreas Polze and published by Universitätsverlag Potsdam. This book was released on 2018 with total page 84 pages. Available in PDF, EPUB and Kindle. Book excerpt: Jedes Jahr lädt das Hasso-Plattner-Institut (HPI) Gäste aus der Industrie und der Wissenschaft zu einem kooperativen und wissenschaftlichen Symposium zum Thema Cloud Computing ein. Unser Ziel ist es, ein Forum für den Austausch von Wissen und Erfahrungen zwischen der Industrie und der Wissenschaft zu bieten. Parallel zur Veranstaltung findet der HPI Future SOC Lab Tag statt, der eine zusätzliche attraktive Umgebung für wissenschaftliche und branchenbezogene Diskussionen bietet. Das Symposium zielt darauf ab, eine Plattform für produktive Interaktionen von innovativen Ideen, Visionen und aufkommenden Technologien im Bereich von Cloud Computing zu bitten. Anlässlich dieses Symposiums fordern wir die Einreichung von Forschungsarbeiten und Erfahrungsberichte. Dieser technische Bericht umfasst eine Zusammenstellung der im Rahmen des fünften HPI Cloud Symposiums "Operating the Cloud" 2017 angenommenen Forschungspapiere. Wir danken den Autoren für spannende Vorträge und Einblicke in ihre aktuelle Arbeit und Forschung. Darüber hinaus freuen wir uns auf weitere interessante Einreichungen für das kommende Symposium im Laufe des Jahres. Every year, the Hasso Plattner Institute (HPI) invites guests from industry and academia to a collaborative scientific workshop on the topic Operating the Cloud. Our goal is to provide a forum for the exchange of knowledge and experience between industry and academia. Co-located with the event is the HPI’s Future SOC Lab day, which offers an additional attractive and conducive environment for scientific and industry related discussions. Operating the Cloud aims to be a platform for productive interactions of innovative ideas, visions, and upcoming technologies in the field of cloud operation and administration. In these proceedings, the results of the fifth HPI cloud symposium Operating the Cloud 2017 are published. We thank the authors for exciting presentations and insights into their current work and research. Moreover, we look forward to more interesting submissions for the upcoming symposium in 2018.
Download or read book Proceedings of the 7th Ph D Retreat of the HPI Research School on Service oriented Systems Engineering written by Meinel, Christoph and published by Universitätsverlag Potsdam. This book was released on 2014-10-09 with total page 218 pages. Available in PDF, EPUB and Kindle. Book excerpt: Design and Implementation of service-oriented architectures imposes a huge number of research questions from the fields of software engineering, system analysis and modeling, adaptability, and application integration. Component orientation and web services are two approaches for design and realization of complex web-based system. Both approaches allow for dynamic application adaptation as well as integration of enterprise application. Commonly used technologies, such as J2EE and .NET, form de facto standards for the realization of complex distributed systems. Evolution of component systems has lead to web services and service-based architectures. This has been manifested in a multitude of industry standards and initiatives such as XML, WSDL UDDI, SOAP, etc. All these achievements lead to a new and promising paradigm in IT systems engineering which proposes to design complex software solutions as collaboration of contractually defined software services. Service-Oriented Systems Engineering represents a symbiosis of best practices in object-orientation, component-based development, distributed computing, and business process management. It provides integration of business and IT concerns. The annual Ph.D. Retreat of the Research School provides each member the opportunity to present his/her current state of their research and to give an outline of a prospective Ph.D. thesis. Due to the interdisciplinary structure of the Research Scholl, this technical report covers a wide range of research topics. These include but are not limited to: Self-Adaptive Service-Oriented Systems, Operating System Support for Service-Oriented Systems, Architecture and Modeling of Service-Oriented Systems, Adaptive Process Management, Services Composition and Workflow Planning, Security Engineering of Service-Based IT Systems, Quantitative Analysis and Optimization of Service-Oriented Systems, Service-Oriented Systems in 3D Computer Graphics sowie Service-Oriented Geoinformatics.
Download or read book Squimera written by Tim Felgentreff and published by Universitätsverlag Potsdam. This book was released on 2017 with total page 102 pages. Available in PDF, EPUB and Kindle. Book excerpt: Software development tools that work and behave consistently across different programming languages are helpful for developers, because they do not have to familiarize themselves with new tooling whenever they decide to use a new language. Also, being able to combine multiple programming languages in a program increases reusability, as developers do not have to recreate software frameworks and libraries in the language they develop in and can reuse existing software instead. However, developers often have a broad choice with regard to tools, some of which are designed for only one specific programming language. Various Integrated Development Environments have support for multiple languages, but are usually unable to provide a consistent programming experience due to different features of language runtimes. Furthermore, common mechanisms that allow reuse of software written in other languages usually use the operating system or a network connection as the abstract layer. Tools, however, often cannot support such indirections well and are therefore less useful in debugging scenarios for example. In this report, we present a novel approach that aims to improve the programming experience with regard to working with multiple high-level programming languages. As part of this approach, we reuse the tools of a Smalltalk programming environment for other languages and build a multi-language virtual execution environment which is able to provide the same runtime capabilities for all languages. The prototype system Squimera is an implementation of our approach and demonstrates that it is possible to reuse development tools, so that they behave in the same way across all supported programming languages. In addition, it provides convenient means to reuse and even mix software libraries and frameworks written in different languages without breaking the debugging experience.
Download or read book The Font Engineering Platform written by Taeumel, Marcel and published by Universitätsverlag Potsdam. This book was released on 2019-11-14 with total page 130 pages. Available in PDF, EPUB and Kindle. Book excerpt: Creating fonts is a complex task that requires expert knowledge in a variety of domains. Often, this knowledge is not held by a single person, but spread across a number of domain experts. A central concept needed for designing fonts is the glyph, an elemental symbol representing a readable character. Required domains include designing glyph shapes, engineering rules to combine glyphs for complex scripts and checking legibility. This process is most often iterative and requires communication in all directions. This report outlines a platform that aims to enhance the means of communication, describes our prototyping process, discusses complex font rendering and editing in a live environment and an approach to generate code based on a user’s live-edits. Die Erstellung von Schriften ist eine komplexe Aufgabe, die Expertenwissen aus einer Vielzahl von Bereichen erfordert. Oftmals liegt dieses Wissen nicht bei einer einzigen Person, sondern bei einer Reihe von Fachleuten. Ein zentrales Konzept für die Gestaltung von Schriften ist der Glyph, ein elementares Symbol, das ein einzelnes lesbares Zeichen darstellt. Zu den erforderlichen Domänen gehören das Entwerfen der Glyphenformen, technische Regeln zur Kombination von Glyphen für komplexe Skripte und das Prüfen der Lesbarkeit. Dieser Prozess ist meist iterativ und erfordert ständige Kommunikation zwischen den Experten. Dieser Bericht skizziert eine Plattform, die darauf abzielt, die Kommunikationswege zu verbessern, beschreibt unseren Prototyping-Prozess, diskutiert komplexe Schriftrendering und -bearbeitung in einer Echtzeitumgebung und einen Ansatz zur Generierung von Code basierend auf direkter Manipulation eines Nutzers.
