×

Subobject transformation systems. (English) Zbl 1153.18002

Subobject Transformation Systems (STS) are presented as a new formal framework for the analysis of derivations of transformation systems based on the algebraic double-pushout (DPO). In the third section of their paper, the authors use them in order to identify some possible relations among rules. These are used to define other derived relations which are shown to coincide with those introduced in the literature for STS arising as processes of DPO rewriting systems.
An interesting and useful auxiliary graphical “Venn-diagram” like notation for reasoning about dependency relations is presented, as well as the notion of region which is, roughly, a complement of a subobject. The basic theory of regions allows the authors to prove that reasoning with the aid of the Venn-diagrams is sound.
Conditions are discussed under which two productions of an STS have to be considered as independent; several equivalent ways to characterize this relation are given. A colimit construction is also presented that builds an STS from a given derivation tree of a DPO system, generalizing the construction of the process of a linear derivation proposed in the literature.
Finally, the authors prove that the analysis of the relationships among rule occurrences in the derivation tree can be reduced faithfully to the analysis of such relationships in the generated STS.

MSC:

18B35 Preorders, orders, domains and lattices (viewed as categories)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q42 Grammars and rewriting systems
18B20 Categories of machines, automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baldan, P.: Modelling concurrent computations: from contextual Petri nets to graph grammars. PhD dissertation, Department of Computer Science, University of Pisa, March. Available as technical report no. TD-1/00 (2000)
[2] Baldan, P., Corradini, A., Heindel, T., König, B., Sobociński, P.: Processes for adhesive rewriting systems. In: Aceto, L., Ingólfsdóttir, A. (eds.) FoSSaCS, vol. 3921 of Lecture Notes in Computer Science, pp. 202–216. Springer Verlag (2006) · Zbl 1180.68165
[3] Baldan, P., Corradini, A., Montanari, U.: Concatenable graph processes: relating processes and derivation traces. In: Proc. of ICALP’98, vol. 1443 of Lecture Notes in Computer Science, pp. 283–295. Springer Verlag (1998)
[4] Baldan, P., Corradini, A., Montanari, U.: Unfolding of double-pushout graph grammars is a coreflection. In: Ehrig, G., Engels, G., Kreowski, H.J., Rozenberg, G. (eds.) Proceedings of the International Workshop on Theory and Application of Graph Transformations, vol. 1764 of Lecture Notes in Computer Science, pp. 145–163. Springer Verlag (1999)
[5] Baldan, P., König, B., Stürmer, I.: Generating test cases for code generators by unfolding graph transformation systems. In: Ehrig, H., Engels, G., Parisi-Presicce, F., Rozenberg, G. (eds.) ICGT’04, vol. 3256 of Lecture Notes in Computer Science, pp. 194–209. Springer Verlag (2004) · Zbl 1116.68477
[6] Corradini, A., Heindel, T., Hermann, F., König, B.: Sesqui-pushout rewriting. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro, L., Rozenberg, G. (eds.) ICGT’06, vol. 4178 of Lecture Notes in Computer Science, pp. 30–45. Springer Verlag (2006) · Zbl 1156.68423
[7] Corradini, A., Montanari, U., Rossi, F.: Graph processes. Fund. Inform. 26, 241–265 (1996) · Zbl 0854.68054
[8] Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Heckel, R., Löwe, M.: Algebraic approaches to graph transformation, Part I: basic concepts and double pushout approach. In: Rozenberg [21], Chapter 3 (1997)
[9] Danos, V., Krivine, J., Sobociński, P.: General reversibility. In: Express ’06, Electronic Notes in Theoretical Computer Science 175(3), pp. 75–86. Elsevier (2007) · Zbl 1277.68175
[10] Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamentals of Algebraic Graph Transformation. EATCS Monographs in Theoretical Computer Science. Springer Verlag (2006) · Zbl 1095.68047
[11] Ehrig, H., Heckel, R., Korff, M., Löwe, M., Ribeiro, L., Wagner, A., Corradini, A.: Algebraic approaches to graph transformation II: single pushout approach and comparison with double pushout approach. In: Rozenberg [21], Chapter 4 (1997)
[12] Golz, U., Reisig, W.: The non-sequential behaviour of Petri nets. Inf. Control 57, 125–147 (1983) · Zbl 0551.68050 · doi:10.1016/S0019-9958(83)80040-0
[13] Habel, A., Heckel, R., Taentzer, G.: Graph grammars with negative application conditions. Special issue of Fund. Inform. 26(3,4), 287–313 (1996) · Zbl 0854.68055
[14] Joyal, A., Street, R.: The geometry of tensor calculus. I. Adv. Math. 88, 55–112 (1991) · Zbl 0738.18005 · doi:10.1016/0001-8708(91)90003-P
[15] Kreowski, H.-J.: Manipulation von Graphmanipulationen. PhD thesis, Technische Universität Berlin (1977)
[16] Lack, S., Sobociński, P.: Adhesive and quasiadhesive categories. Theor. Inf. Appl. 39(2), 511–546 (2005) · Zbl 1078.18010 · doi:10.1051/ita:2005028
[17] Leinster, T.: Higher Operads, Higher Categories. London Mathematical Lecture Notes. Cambridge University Press (2003)
[18] Meseguer, J., Montanari, U.: Petri nets are monoids. Inform. and Comput. 88, 105–155 (1990) · Zbl 0711.68077 · doi:10.1016/0890-5401(90)90013-8
[19] Reisig, W.: Petri Nets: An Introduction. EACTS Monographs on Theoretical Computer Science. Springer Verlag (1985)
[20] Ribeiro, L.: Parallel Composition and Unfolding Semantics of Graph Grammars. PhD thesis, Technische Universität Berlin (1996)
[21] Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1: Foundations. World Scientific (1997) · Zbl 0908.68095
[22] Rozenberg, G., Engelfriet, J.: Elementary net systems. In: Reisig, W., Rozenberg, G. (eds.) Lectures on Petri Nets I: Basic Models, vol. 1491 of Lecture Notes in Computer Science, pp. 12–121. Springer Verlag (1996)
[23] Street, R.: Higher categories, strings, cubes and simplex equations. Appl. Categ. Structures. 3, 29–77 (1995) · Zbl 0827.18002 · doi:10.1007/BF00872948
[24] Winskel, G.: Event structures. In: Petri Nets: Applications and Relationships to Other Models of Concurrency, vol. 255 of Lecture Notes in Computer Science, pp. 325–392. Springer Verlag (1987)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.