1,721,156 research outputs found
Graph Transformation in a Nutshell
Full text linkEven sophisticated techniques start out from simple ideas. Later, in reply to application needs or theoretical problems new concepts are introduced, often to a point where the original simple core is hardly recognizable. In Section 1.1 we will focus on the basic ideas of typed graph transformation systems, reserving a survey of the more advanced concepts for Section 1.2. This chapter provides the background for the application-oriented chapters of the book in Parts II and III. As such, the presentation is not tailored towards a specific application area. However, for illustration purposes a toy example is elaborated which motivates the use of graph transformation rules for behavioral modeling. Like throughout most of the other chapters of the book, we use a UML-like notation for graphs and rules. 1.1 The Basic Approach Modeling can be described as a two-dimensional abstraction process. The first dimension consists in building models as representations of reality. The second dimension is generalization, i.e., the extraction of concepts from concrete objets, or of rules from observed behavior. We will deal with generalization first, reserving representation issues for Sect. 1.1.2. 1.1.1 Modeling by Example It is a matter of philosophical debate if generalizations exist in reality or if, e.g., the concept of car as generalization of individual cars is part of the human perception of the world. Avoiding this discission, we will illustrate two forms of generalization by means of a simple video game of PacMan, for didactic purposes playing the role of “reality”. Later, the insights gained from this example shall be 3 4 CHAPTER 1. GRAPH TRANSFORMATION IN A NUTSHELL collect kil
Automatic Integration of Safety Invariants into Z Specifications (Extended Abstract)
No full textReiko Heckel 1 , Mirko Conrad 2 , Gottfried Egger 2 , and Jan-Juan Hiemer 2 1 Technical University Berlin, Computer Science Department, FR 6-1 Franklinstr. 28/29, D-10587 Berlin, Germany e-mail: [email protected] 2 Daimler-Benz AG Research and Technology, F3S/K Alt-Moabit 96a, D-10559 Berlin, Germany e-mail: [email protected] Abstract. This extended abstract describes a mechanism to automatically incorporate safety requirements into operational specifications written in Z. For every individual operation the global (i.e. operation independent) safety invariants are transformed into a predicate which is used to extend the original precondition of the operation. The operation constructed this way shows the same behavior as the original one whenever its post state satisfies the invariant. Otherwise it refuses to do anything. The construction of the precondition can be carried out automatically and a corresponding tool development is in progress. 1 Int..
Hoare vs Milner: Comparing Synchronizations in a Graphical Framework With Mobility
No full textAbstractWe compare the expressive power of Hoare (i.e., CSP style) and Milner (i.e., CCS style) synchronizations for defining graph transformations in a framework where edges can perform actions on adjacent nodes to synchronize their evolutions. Furthermore, nodes can be communicated and merged. We show that the expressive powers of the two synchronization models are different, but no one is greater than the other. Finally, we show that in many interesting cases the behaviour of a synchronization model can be mimicked by the other one using suitable translations for the rewritten graphs
Encoding Incremental NACs in Safe Graph Grammars using Complementation
No full textIn modelling complex systems with graph grammars (GGs), it is convenient to restrict the application of rules using attribute constraints and negative application conditions (NACs). However, having both attributes and NACs in GGs renders the behavioural analysis (e.g. unfolding) of such systems more complicated. We address this issue by an approach to encode NACs using a complementation technique. We consider the correctness of our encoding under the assumption that the grammar is safe and NACs are incremental, and outline how this result can be extended to unsafe, attributed grammar
Open Petri nets: Non-deterministic Processes and Compositionality
No full textWe introduce ranked open nets, a reactive extension of Petri
nets which generalises a basic open net model introduced in a previous
work by allowing for a refined notion of interface. The interface towards
the external environment of a ranked open net is given by a subset
of places designated as open and used for composition. Additionally, a
bound on the number of connections which are allowed on an open place
can be specified. We show that the non-deterministic process semantics
is compositional with respect to the composition operation over ranked
open nets, a result which did not hold for basic open nets
Modelling Dynamic Software Architectures using Typed Graph Grammars
No full textSeveral recent research efforts have focused on the dynamic aspects of software architectures providing suitable models and techniques for handling the run-time modification of the structure of a system. A large number of heterogeneous proposals for addressing dynamic architectures at many different levels of abstraction have been provided, such as programmable, ad-hoc, self-healing and self-repairing among others. It is then important to have a clear picture of the relations among these proposals by formulating them into a uniform framework and contrasting the different verification aspects that can be reasonably addressed by each proposal. Our work is a contribution in this line. In particular, we map several notions of dynamicity into the same formal framework in order to distill the similarities and differences among them. As a result we explain different styles of architectural dynamisms in term of graph grammars and get some better insights on the kinds of formal properties that can be naturally associated to such different specification styles. We take a simple automotive scenario as a running example to illustrate main ideas
Rule-based Model Extraction from Source Code
Full text linkAbstract. In the context of an approach for reengineering legacy software systems at the architectural level, we present in this paper a reverse engineering methodology that uses a model defined as a type graph to represent source-code subject to a code categorization process. Two alternative methods for referencing the source code are discussed: native vs. graphical. To represent the code, the native representation uses the abstract syntax tree while the graphical uses a programming language metamodel. Two options regarding the way that the graph can relate to the source code reference model are also considered: association model vs. direct link. The extraction of the program representation, complying to the type graph, is based on rules that categorize source code according to its purpose. The techniques to address this process, such as the code categorization rules, are shown together with examples.
Ten virtues of structured graphs
Full text linkThis paper extends the invited talk by the first author about the virtues
of structured graphs. The motivation behind the talk and this paper relies on our
experience on the development of ADR, a formal approach for the design of styleconformant,
reconfigurable software systems. ADR is based on hierarchical graphs
with interfaces and it has been conceived in the attempt of reconciling software architectures
and process calculi by means of graphical methods. We have tried to
write an ADR agnostic paper where we raise some drawbacks of flat, unstructured
graphs for the design and analysis of software systems and we argue that hierarchical,
structured graphs can alleviate such drawbacks
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
