Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/s10485-008-9127-6 | Applied Categorical Structures |
Keywords | Field | DocType |
Graph transformation systems,Adhesive categories,Occurrence grammars,18B35,68Q10,68Q42 | Subobject classifier,Discrete mathematics,Transformation systems,Algebraic number,Distributive lattice,Subobject,Grammar,Rewriting,Mathematics | Journal |
Volume | Issue | ISSN |
16 | 3 | 0927-2852 |
Citations | PageRank | References |
5 | 0.52 | 14 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrea Corradini | 1 | 1108 | 90.63 |
Frank Hermann | 2 | 5 | 0.52 |
Paweł Sobociński | 3 | 609 | 45.57 |