Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

Analysis of Permutation Equivalence in M-adhesive Transformation Systems with Negative Application Conditions Hermann, Frank ; ; in Mathematical Structures in Computer Science (2014), 24(4-09), 1-47 M-adhesive categories provide an abstract framework for a large variety of specification frameworks for modelling distributed and concurrent systems. They extend the well-known frameworks of adhesive and ... [more ▼] M-adhesive categories provide an abstract framework for a large variety of specification frameworks for modelling distributed and concurrent systems. They extend the well-known frameworks of adhesive and weak adhesive HLR categories and integrate high-level constructs such as attribution as in the case of typed attributed graphs. In the current paper, we investigate -adhesive transformation systems including negative application conditions (NACs) for transformation rules, which are often used in applications. For such systems, we propose an original equivalence on transformation sequences, called permutation equivalence, that is coarser than the classical switch equivalence. We also present a general construction of deterministic processes for -adhesive transformation systems based on subobject transformation systems. As a main result, we show that the process obtained from a transformation sequence identifies its equivalence class of permutation-equivalent transformation sequences. Moreover, we show how the analysis of this process can be reduced to the analysis of the reachability graph of a generated Place/Transition Petri net. This net encodes the dependencies between rule applications of the transformation sequence, including the inhibiting effects of the NACs. [less ▲] Detailed reference viewed: 114 (10 UL)Transformation Systems with Incremental Negative Application Conditions ; ; Hermann, Frank et al in Recent Trends in Algebraic Development Techniques (2013) In several application areas, Graph Transformation Systems (GTSs) are equipped with Negative Application Conditions (NACs) that specify “forbidden contexts”, in which the rules shall not be applied. The ... [more ▼] In several application areas, Graph Transformation Systems (GTSs) are equipped with Negative Application Conditions (NACs) that specify “forbidden contexts”, in which the rules shall not be applied. The extension to NACs, however, introduces inhibiting effects among transformation steps that are not local in general, causing a severe problem for a concurrent semantics. In fact, the relation of sequential independence among derivation steps is not invariant under switching, as we illustrate with an example. We first show that this problem disappears if the NACs are restricted to beincremental. Next we present an algorithm that transforms a GTS with arbitrary NACs into one with incremental NACs only, able to simulate the original GTS. We also show that the two systems are actually equivalent, under certain assumptions on NACs. [less ▲] Detailed reference viewed: 123 (18 UL)On the Concurrent Semantics of Transformation Systems with Negative Application Conditions ; ; Hermann, Frank et al Report (2012) Graph Transformation Systems (GTSs) are an integrated formal speci cation framework for modelling and analysing structural and behavioural aspects of systems. The evolution of a system is modelled by the ... [more ▼] Graph Transformation Systems (GTSs) are an integrated formal speci cation framework for modelling and analysing structural and behavioural aspects of systems. The evolution of a system is modelled by the application of rules to the graphs representing its states and, since typically such rules have local e ects, GTSs are particularly suitable for modelling concurrent and distributed systems where several rules can be applied in parallel. Thus, it is no surprise that a large body of literature is dedicated to the study of the concurrent semantics of graph transformation systems. [less ▲] Detailed reference viewed: 87 (16 UL)Efficient Process Analysis of Transformation Systems Based on Petri nets Hermann, Frank ; ; et al Report (2010) In the framework of adhesive transformation systems with Negative Application Conditions (NACs), we show how the problem of computing the set of equivalent derivations to a given one can be reduced to the ... [more ▼] In the framework of adhesive transformation systems with Negative Application Conditions (NACs), we show how the problem of computing the set of equivalent derivations to a given one can be reduced to the analysis of the reachability graph of a generated Place/Transition Petri net. This net encodes the dependencies among rule applications of the derivation, including the inhibiting e ects of the NACs. We show the e ectiveness of this approach by comparing the cost of a brute force-approach with the cost of the presented analysis applied to a derivation of a simple system, showing a signi cant improvement in speed. [less ▲] Detailed reference viewed: 51 (1 UL)Efficient Analysis of Permutation Equivalence of Graph Derivations Based on Petri Nets Hermann, Frank ; ; et al in Electronic Communications of the EASST (2010), 29 Detailed reference viewed: 42 (2 UL)Subobject Transformation Systems ; Hermann, Frank ; in Applied Categorical Structures (2008), 16(3), 389--419 Subobject transformation systems STS are proposed as a novel formal framework for the analysis of derivations of transformation systems based on the algebraic, double-pushout (DPO) approach. They can be ... [more ▼] Subobject transformation systems STS are proposed as a novel formal framework for the analysis of derivations of transformation systems based on the algebraic, double-pushout (DPO) approach. They can be considered as a simplified variant of DPO rewriting, acting in the distributive lattice of subobjects of a given object of an adhesive category. This setting allows a direct analysis of all possible notions of dependency between any two productions without requiring an explicit match. In particular, several equivalent characterizations of independence of productions are proposed, as well as a local Church�Rosser theorem in the setting of STS. Finally, we show how any derivation tree in an ordinary DPO grammar leads to an STS via a suitable construction and show that relational reasoning in the resulting STS is sound and complete with respect to the independence in the original derivation tree. [less ▲] Detailed reference viewed: 81 (1 UL)Sesqui-Pushout Rewriting ; ; Hermann, Frank et al in Graph Transformation (2006) Sesqui-pushout (sqpo) rewriting – ''sesqui´´ means ``one and a half'' in Latin – is a new algebraic approach to abstract rewriting in any category. sqpo rewriting is a deterministic and conservative ... [more ▼] Sesqui-pushout (sqpo) rewriting – ''sesqui´´ means ``one and a half'' in Latin – is a new algebraic approach to abstract rewriting in any category. sqpo rewriting is a deterministic and conservative extension of double-pushout (dpo) rewriting, which allows to model ``deletion in unknown context'', a typical feature of single-pushout (spo) rewriting, as well as cloning. After illustrating the expressiveness of the proposed approach through a case study modelling an access control system, we discuss sufficient conditions for the existence of final pullback complements and we analyze the relationship between sqpo and the classical dpo and spo approaches. [less ▲] Detailed reference viewed: 90 (2 UL) |
||