Interval Probabilistic Timed Graph Transformation Systems

Author : Maria Maximova,Holger Giese,Sven Schneider
Publisher : Universitätsverlag Potsdam
Page : 64 pages
File Size : 47,9 Mb
Release : 2022-05-19
Category : Computers
ISBN : 9783869565026

Get Book

Interval Probabilistic Timed Graph Transformation Systems by Maria Maximova,Holger Giese,Sven Schneider Pdf

The formal modeling and analysis is of crucial importance for software development processes following the model based approach. We present the formalism of Interval Probabilistic Timed Graph Transformation Systems (IPTGTSs) as a high-level modeling language. This language supports structure dynamics (based on graph transformation), timed behavior (based on clocks, guards, resets, and invariants as in Timed Automata (TA)), and interval probabilistic behavior (based on Discrete Interval Probability Distributions). That is, for the probabilistic behavior, the modeler using IPTGTSs does not need to provide precise probabilities, which are often impossible to obtain, but rather provides a probability range instead from which a precise probability is chosen nondeterministically. In fact, this feature on capturing probabilistic behavior distinguishes IPTGTSs from Probabilistic Timed Graph Transformation Systems (PTGTSs) presented earlier. Following earlier work on Interval Probabilistic Timed Automata (IPTA) and PTGTSs, we also provide an analysis tool chain for IPTGTSs based on inter-formalism transformations. In particular, we provide in our tool AutoGraph a translation of IPTGTSs to IPTA and rely on a mapping of IPTA to Probabilistic Timed Automata (PTA) to allow for the usage of the Prism model checker. The tool Prism can then be used to analyze the resulting PTA w.r.t. probabilistic real-time queries asking for worst-case and best-case probabilities to reach a certain set of target states in a given amount of time.

Author : Fabio Gadducci,Timo Kehrer
Publisher : Springer Nature
Page : 311 pages
File Size : 44,9 Mb
Release : 2021-06-17
Category : Computers
ISBN : 9783030789466

Get Book

Graph Transformation by Fabio Gadducci,Timo Kehrer Pdf

This book constitutes the refereed proceedings of the 14th International Conference on Graph Transformation, ICGT 2021, which took place virtually during June 24-25, 2021. The 14 full papers and 2 tool papers presented in this book were carefully reviewed and selected from 26 submissions. They deal with the following topics: theoretical advances; application domains; and tool presentations.

Author : Maximove, Maria,Giese, Holger,Krause, Christian
Publisher : Universitätsverlag Potsdam
Page : 40 pages
File Size : 46,8 Mb
Release : 2017-11-30
Category : Electronic
ISBN : 9783869564050

Get Book

Probalistic Timed Graph Transformation Systems by Maximove, Maria,Giese, Holger,Krause, Christian Pdf

Today, software has become an intrinsic part of complex distributed embedded real-time systems. The next generation of embedded real-time systems will interconnect the today unconnected systems via complex software parts and the service-oriented paradigm. Therefore besides timed behavior and probabilistic behaviour also structure dynamics, where the architecture can be subject to changes at run-time, e.g. when dynamic binding of service end-points is employed or complex collaborations are established dynamically, is required. However, a modeling and analysis approach that combines all these necessary aspects does not exist so far. To fill the identified gap, we propose Probabilistic Timed Graph Transformation Systems (PTGTSs) as a high-level description language that supports all the necessary aspects of structure dynamics, timed behavior, and probabilistic behavior. We introduce the formal model of PTGTSs in this paper and present a mapping of models with finite state spaces to probabilistic timed automata (PTA) that allows to use the PRISM model checker to analyze PTGTS models with respect to PTCTL properties.

Author : Maria Maximova,Holger Giese,Sven Schneider
Publisher : Universitätsverlag Potsdam
Page : 60 pages
File Size : 44,9 Mb
Release : 2022-05-19
Category : Computers
ISBN : 9783869565019

Get Book

Compositional Analysis of Probabilistic Timed Graph Transformation Systems by Maria Maximova,Holger Giese,Sven Schneider Pdf

The analysis of behavioral models is of high importance for cyber-physical systems, as the systems often encompass complex behavior based on e.g. concurrent components with mutual exclusion or probabilistic failures on demand. The rule-based formalism of probabilistic timed graph transformation systems is a suitable choice when the models representing states of the system can be understood as graphs and timed and probabilistic behavior is important. However, model checking PTGTSs is limited to systems with rather small state spaces. We present an approach for the analysis of large scale systems modeled as probabilistic timed graph transformation systems by systematically decomposing their state spaces into manageable fragments. To obtain qualitative and quantitative analysis results for a large scale system, we verify that results obtained for its fragments serve as overapproximations for the corresponding results of the large scale system. Hence, our approach allows for the detection of violations of qualitative and quantitative safety properties for the large scale system under analysis. We consider a running example in which we model shuttles driving on tracks of a large scale topology and for which we verify that shuttles never collide and are unlikely to execute emergency brakes. In our evaluation, we apply an implementation of our approach to the running example.

Author : Krause, Christian,Giese, Holger
Publisher : Universitätsverlag Potsdam
Page : 54 pages
File Size : 40,9 Mb
Release : 2012
Category : Computers
ISBN : 9783869561714

Get Book

Quantitative Modeling and Analysis of Service-oriented Real-time Systems Using Interval Probabilistic Timed Automata by Krause, Christian,Giese, Holger Pdf

One of the key challenges in service-oriented systems engineering is the prediction and assurance of non-functional properties, such as the reliability and the availability of composite interorganizational services. Such systems are often characterized by a variety of inherent uncertainties, which must be addressed in the modeling and the analysis approach. The different relevant types of uncertainties can be categorized into (1) epistemic uncertainties due to incomplete knowledge and (2) randomization as explicitly used in protocols or as a result of physical processes. In this report, we study a probabilistic timed model which allows us to quantitatively reason about nonfunctional properties for a restricted class of service-oriented real-time systems using formal methods. To properly motivate the choice for the used approach, we devise a requirements catalogue for the modeling and the analysis of probabilistic real-time systems with uncertainties and provide evidence that the uncertainties of type (1) and (2) in the targeted systems have a major impact on the used models and require distinguished analysis approaches. The formal model we use in this report are Interval Probabilistic Timed Automata (IPTA). Based on the outlined requirements, we give evidence that this model provides both enough expressiveness for a realistic and modular specifiation of the targeted class of systems, and suitable formal methods for analyzing properties, such as safety and reliability properties in a quantitative manner. As technical means for the quantitative analysis, we build on probabilistic model checking, specifically on probabilistic time-bounded reachability analysis and computation of expected reachability rewards and costs. To carry out the quantitative analysis using probabilistic model checking, we developed an extension of the Prism tool for modeling and analyzing IPTA. Our extension of Prism introduces a means for modeling probabilistic uncertainty in the form of probability intervals, as required for IPTA. For analyzing IPTA, our Prism extension moreover adds support for probabilistic reachability checking and computation of expected rewards and costs. We discuss the performance of our extended version of Prism and compare the interval-based IPTA approach to models with fixed probabilities.

Author : Sven Schneider,Maria Maximova,Holger Giese
Publisher : Universitätsverlag Potsdam
Page : 44 pages
File Size : 41,9 Mb
Release : 2023-01-30
Category : Computers
ISBN : 9783869565170

Get Book

Probabilistic metric temporal graph logic by Sven Schneider,Maria Maximova,Holger Giese Pdf

Cyber-physical systems often encompass complex concurrent behavior with timing constraints and probabilistic failures on demand. The analysis whether such systems with probabilistic timed behavior adhere to a given specification is essential. When the states of the system can be represented by graphs, the rule-based formalism of Probabilistic Timed Graph Transformation Systems (PTGTSs) can be used to suitably capture structure dynamics as well as probabilistic and timed behavior of the system. The model checking support for PTGTSs w.r.t. properties specified using Probabilistic Timed Computation Tree Logic (PTCTL) has been already presented. Moreover, for timed graph-based runtime monitoring, Metric Temporal Graph Logic (MTGL) has been developed for stating metric temporal properties on identified subgraphs and their structural changes over time. In this paper, we (a) extend MTGL to the Probabilistic Metric Temporal Graph Logic (PMTGL) by allowing for the specification of probabilistic properties, (b) adapt our MTGL satisfaction checking approach to PTGTSs, and (c) combine the approaches for PTCTL model checking and MTGL satisfaction checking to obtain a Bounded Model Checking (BMC) approach for PMTGL. In our evaluation, we apply an implementation of our BMC approach in AutoGraph to a running example.

Author : Dirk Beyer
Publisher : Springer Nature
Page : 346 pages
File Size : 46,5 Mb
Release : 2024-07-01
Category : Electronic
ISBN : 9783031572593

Get Book

Fundamental Approaches to Software Engineering by Dirk Beyer Pdf

Author : Christoph Meinel,Jürgen Roland Friedrich Döllner,Mathias Weske,Andreas Polze,Robert Hirschfeld,Felix Naumann,Holger Giese,Patrick Baudisch,Tobias Friedrich,Erwin Böttinger,Christoph Lippert,Christian Dörr,Anja Lehmann,Bernhard Renard,Tilmann Rabl,Falk Uebernickel,Bert Arnrich,Katharina Hölzle
Publisher : Universitätsverlag Potsdam
Page : 160 pages
File Size : 49,6 Mb
Release : 2023-06-07
Category : Electronic
ISBN : 9783869565132

Get Book

Proceedings of the HPI Research School on Service-oriented Systems Engineering 2020 Fall Retreat by Christoph Meinel,Jürgen Roland Friedrich Döllner,Mathias Weske,Andreas Polze,Robert Hirschfeld,Felix Naumann,Holger Giese,Patrick Baudisch,Tobias Friedrich,Erwin Böttinger,Christoph Lippert,Christian Dörr,Anja Lehmann,Bernhard Renard,Tilmann Rabl,Falk Uebernickel,Bert Arnrich,Katharina Hölzle Pdf

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. 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 school, this technical report covers a wide range of topics. These include but are not limited to: Human Computer Interaction and Computer Vision as Service; Service-oriented Geovisualization Systems; Algorithm Engineering for Service-oriented Systems; Modeling and Verification of Self-adaptive Service-oriented Systems; Tools and Methods for Software Engineering in Service-oriented Systems; Security Engineering of Service-based IT Systems; Service-oriented Information Systems; Evolutionary Transition of Enterprise Applications to Service Orientation; Operating System Abstractions for Service-oriented Computing; and Services Specification, Composition, and Enactment.

Author : Paula Klinke,Silvan Verhoeven,Felix Roth,Linus Hagemann,Tarik Alnawa,Jens Lincke,Patrick Rein,Robert Hirschfeld
Publisher : Universitätsverlag Potsdam
Page : 178 pages
File Size : 40,9 Mb
Release : 2022-09-21
Category : Computers
ISBN : 9783869565217

Get Book

Tool support for collaborative creation of interactive storytelling media by Paula Klinke,Silvan Verhoeven,Felix Roth,Linus Hagemann,Tarik Alnawa,Jens Lincke,Patrick Rein,Robert Hirschfeld Pdf

Scrollytellings are an innovative form of web content. Combining the benefits of books, images, movies, and video games, they are a tool to tell compelling stories and provide excellent learning opportunities. Due to their multi-modality, creating high-quality scrollytellings is not an easy task. Different professions, such as content designers, graphics designers, and developers, need to collaborate to get the best out of the possibilities the scrollytelling format provides. Collaboration unlocks great potential. However, content designers cannot create scrollytellings directly and always need to consult with developers to implement their vision. This can result in misunderstandings. Often, the resulting scrollytelling will not match the designer’s vision sufficiently, causing unnecessary iterations. Our project partner Typeshift specializes in the creation of individualized scrollytellings for their clients. Examined existing solutions for authoring interactive content are not optimally suited for creating highly customized scrollytellings while still being able to manipulate all their elements programmatically. Based on their experience and expertise, we developed an editor to author scrollytellings in the lively.next live-programming environment. In this environment, a graphical user interface for content design is combined with powerful possibilities for programming behavior with the morphic system. The editor allows content designers to take on large parts of the creation process of scrollytellings on their own, such as creating the visible elements, animating content, and fine-tuning the scrollytelling. Hence, developers can focus on interactive elements such as simulations and games. Together with Typeshift, we evaluated the tool by recreating an existing scrollytelling and identified possible future enhancements. Our editor streamlines the creation process of scrollytellings. Content designers and developers can now both work on the same scrollytelling. Due to the editor inside of the lively.next environment, they can both work with a set of tools familiar to them and their traits. Thus, we mitigate unnecessary iterations and misunderstandings by enabling content designers to realize large parts of their vision of a scrollytelling on their own. Developers can add advanced and individual behavior. Thus, developers and content designers benefit from a clearer distribution of tasks while keeping the benefits of collaboration.

Author : Wanda Baltzer,Theresa Hradilak,Lara Pfennigschmidt,Luc Maurice Prestin,Moritz Spranger,Simon Stadlinger,Leo Wendt,Jens Lincke,Patrick Rein,Luke Church,Robert Hirschfeld
Publisher : Universitätsverlag Potsdam
Page : 338 pages
File Size : 49,6 Mb
Release : 2021-11-05
Category : Computers
ISBN : 9783869565040

Get Book

An individual-centered approach to visualize people’s opinions and demographic informationc by Wanda Baltzer,Theresa Hradilak,Lara Pfennigschmidt,Luc Maurice Prestin,Moritz Spranger,Simon Stadlinger,Leo Wendt,Jens Lincke,Patrick Rein,Luke Church,Robert Hirschfeld Pdf

The noble way to substantiate decisions that affect many people is to ask these people for their opinions. For governments that run whole countries, this means asking all citizens for their views to consider their situations and needs. Organizations such as Africa's Voices Foundation, who want to facilitate communication between decision-makers and citizens of a country, have difficulty mediating between these groups. To enable understanding, statements need to be summarized and visualized. Accomplishing these goals in a way that does justice to the citizens' voices and situations proves challenging. Standard charts do not help this cause as they fail to create empathy for the people behind their graphical abstractions. Furthermore, these charts do not create trust in the data they are representing as there is no way to see or navigate back to the underlying code and the original data. To fulfill these functions, visualizations would highly benefit from interactions to explore the displayed data, which standard charts often only limitedly provide. To help improve the understanding of people's voices, we developed and categorized 80 ideas for new visualizations, new interactions, and better connections between different charts, which we present in this report. From those ideas, we implemented 10 prototypes and two systems that integrate different visualizations. We show that this integration allows consistent appearance and behavior of visualizations. The visualizations all share the same main concept: representing each individual with a single dot. To realize this idea, we discuss technologies that efficiently allow the rendering of a large number of these dots. With these visualizations, direct interactions with representations of individuals are achievable by clicking on them or by dragging a selection around them. This direct interaction is only possible with a bidirectional connection from the visualization to the data it displays. We discuss different strategies for bidirectional mappings and the trade-offs involved. Having unified behavior across visualizations enhances exploration. For our prototypes, that includes grouping, filtering, highlighting, and coloring of dots. Our prototyping work was enabled by the development environment Lively4. We explain which parts of Lively4 facilitated our prototyping process. Finally, we evaluate our approach to domain problems and our developed visualization concepts. Our work provides inspiration and a starting point for visualization development in this domain. Our visualizations can improve communication between citizens and their government and motivate empathetic decisions. Our approach, combining low-level entities to create visualizations, provides value to an explorative and empathetic workflow. We show that the design space for visualizing this kind of data has a lot of potential and that it is possible to combine qualitative and quantitative approaches to data analysis.

Author : Christian Bartz,Ralf Krestel
Publisher : Universitätsverlag Potsdam
Page : 94 pages
File Size : 40,7 Mb
Release : 2021-11-15
Category : Computers
ISBN : 9783869565149

Get Book

Deep learning for computer vision in the art domain by Christian Bartz,Ralf Krestel Pdf

In recent years, computer vision algorithms based on machine learning have seen rapid development. In the past, research mostly focused on solving computer vision problems such as image classification or object detection on images displaying natural scenes. Nowadays other fields such as the field of cultural heritage, where an abundance of data is available, also get into the focus of research. In the line of current research endeavours, we collaborated with the Getty Research Institute which provided us with a challenging dataset, containing images of paintings and drawings. In this technical report, we present the results of the seminar "Deep Learning for Computer Vision". In this seminar, students of the Hasso Plattner Institute evaluated state-of-the-art approaches for image classification, object detection and image recognition on the dataset of the Getty Research Institute. The main challenge when applying modern computer vision methods to the available data is the availability of annotated training data, as the dataset provided by the Getty Research Institute does not contain a sufficient amount of annotated samples for the training of deep neural networks. However, throughout the report we show that it is possible to achieve satisfying to very good results, when using further publicly available datasets, such as the WikiArt dataset, for the training of machine learning models.

Author : Klara Seitz,Jens Lincke,Patrick Rein,Robert Hirschfeld
Publisher : Universitätsverlag Potsdam
Page : 108 pages
File Size : 42,5 Mb
Release : 2021-09-09
Category : Computers
ISBN : 9783869565057

Get Book

Language and tool support for 3D crochet patterns by Klara Seitz,Jens Lincke,Patrick Rein,Robert Hirschfeld Pdf

Crochet is a popular handcraft all over the world. While other techniques such as knitting or weaving have received technical support over the years through machines, crochet is still a purely manual craft. Not just the act of crochet itself is manual but also the process of creating instructions for new crochet patterns, which is barely supported by domain specific digital solutions. This leads to unstructured and often also ambiguous and erroneous pattern instructions. In this report, we propose a concept to digitally represent crochet patterns. This format incorporates crochet techniques which allows domain specific support for crochet pattern designers during the pattern creation and instruction writing process. As contributions, we present a thorough domain analysis, the concept of a graph structure used as domain specific language to specify crochet patterns and a prototype of a projectional editor using the graph as representation format of patterns and a diagramming system to visualize them in 2D and 3D. By analyzing the domain, we learned about crochet techniques and pain points of designers in their pattern creation workflow. These insights are the basis on which we defined the pattern representation. In order to evaluate our concept, we built a prototype by which the feasibility of the concept is shown and we tested the software with professional crochet designers who approved of the concept.

Author : Friedrich Schöne,Patrick Rein,Robert Hirschfeld
Publisher : Universitätsverlag Potsdam
Page : 86 pages
File Size : 54,7 Mb
Release : 2022-06-14
Category : Computers
ISBN : 9783869565033

Get Book

Fast Packrat Parsing in a Live Programming Environment by Friedrich Schöne,Patrick Rein,Robert Hirschfeld Pdf

Language developers who design domain-specific languages or new language features need a way to make fast changes to language definitions. Those fast changes require immediate feedback. Also, it should be possible to parse the developed languages quickly to handle extensive sets of code. Parsing expression grammars provides an easy to understand method for language definitions. Packrat parsing is a method to parse grammars of this kind, but this method is unable to handle left-recursion properly. Existing solutions either partially rewrite left-recursive rules and partly forbid them, or use complex extensions to packrat parsing that are hard to understand and cost-intensive. We investigated methods to make parsing as fast as possible, using easy to follow algorithms while not losing the ability to make fast changes to grammars. We focused our efforts on two approaches. One is to start from an existing technique for limited left-recursion rewriting and enhance it to work for general left-recursive grammars. The second approach is to design a grammar compilation process to find left-recursion before parsing, and in this way, reduce computational costs wherever possible and generate ready to use parser classes. Rewriting parsing expression grammars is a task that, if done in a general way, unveils a large number of cases such that any rewriting algorithm surpasses the complexity of other left-recursive parsing algorithms. Lookahead operators introduce this complexity. However, most languages have only little portions that are left-recursive and in virtually all cases, have no indirect or hidden left-recursion. This means that the distinction of left-recursive parts of grammars from components that are non-left-recursive holds great improvement potential for existing parsers. In this report, we list all the required steps for grammar rewriting to handle left-recursion, including grammar analysis, grammar rewriting itself, and syntax tree restructuring. Also, we describe the implementation of a parsing expression grammar framework in Squeak/Smalltalk and the possible interactions with the already existing parser Ohm/S. We quantitatively benchmarked this framework directing our focus on parsing time and the ability to use it in a live programming context. Compared with Ohm, we achieved massive parsing time improvements while preserving the ability to use our parser it as a live programming tool. The work is essential because, for one, we outlined the difficulties and complexity that come with grammar rewriting. Also, we removed the existing limitations that came with left-recursion by eliminating them before parsing.

Author : Hartmut Ehrig,Gregor Engels,Hans-Jörg Kreowski,Grzegorz Rozenberg
Publisher : Springer
Page : 437 pages
File Size : 47,5 Mb
Release : 2012-09-18
Category : Computers
ISBN : 9783642336546

Get Book

Graph Transformation by Hartmut Ehrig,Gregor Engels,Hans-Jörg Kreowski,Grzegorz Rozenberg Pdf

This book constitutes the proceedings of the 6th International Conference on Graph Transformations, ICGT 2012, held in Bremen, Germany, in September 2012. The 30 papers and 3 invited papers presented were carefully reviewed and selected from numerous submissions. The papers are organized in topical sections on behavioural analysis, high-level graph transformation, revisited approaches, general transformation models, structuring and verification, graph transformations in use, (meta-)model evolution and incremental approaches.

Author : Giese, Holger,Maximova, Maria,Sakizloglou, Lucas,Schneider, Sven
Publisher : Universitätsverlag Potsdam
Page : 38 pages
File Size : 41,9 Mb
Release : 2019
Category : Computers
ISBN : 9783869564630

Get Book

Metric Temporal Graph Logic over Typed Attributed Graphs by Giese, Holger,Maximova, Maria,Sakizloglou, Lucas,Schneider, Sven Pdf

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.