Abstract
Adhesive categories provide an abstract setting for the double-pushout approach to rewriting, generalising classical approaches to graph transformation. Fundamental results about parallelism and confluence, including the local Church-Rosser theorem, can be proven in adhesive categories, provided that one restricts to linear rules. We identify a class of categories, including most adhesive categories used in rewriting, where those same results can be proven in the presence of rules that are merely left-linear, i.e., rules which can merge different parts of a rewritten object. Such rules naturally emerge, e.g., when using graphical encodings for modelling the operational semantics of process calculi.
Supported by the MIUR project SisteR and the University of Padua project AVIAMO.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Baldan, P., Gadducci, F., Montanari, U.: Concurrent rewriting for graphs with equivalences. In: Baier, C., Hermanns, H. (eds.) CONCUR 2006. LNCS, vol. 4137, pp. 279–294. Springer, Heidelberg (2006)
Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Heckel, R., Löwe, M.: Algebraic approaches to graph transformation I: Basic concepts and double pushout approach. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1, pp. 163–245. World Scientific, Singapore (1997)
Corradini, A., Gadducci, F.: On term graphs as an adhesive category. In: TERMGRAPH 2004. ENTCS, vol. 127(5), pp. 43–56. Elsevier, Amsterdam (2005)
Drewes, F., Habel, A., Kreowski, H.-J.: Hyperedge replacement graph grammars. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1, pp. 95–162. World Scientific, Singapore (1997)
Ehrig, H., Ehrig, K., Prange, U., Täntzer, G.: Fundamentals of Algebraic Graph Transformation. Monographs in Theoretical Computer Science. Springer, Heidelberg (2006)
Ehrig, H., Habel, A., Padberg, J., Prange, U.: Adhesive high-level replacement categories and systems. In: Ehrig, H., Engels, G., Parisi-Presicce, F., Rozenberg, G. (eds.) ICGT 2004. LNCS, vol. 3256, pp. 144–160. Springer, Heidelberg (2004)
Ehrig, H., Habel, A., Parisi-Presicce, F.: Basic results for two types of high-level replacement systems. In: GETGRATS Closing Workshop. ENTCS, vol. 51, pp. 127–138. Elsevier, Amsterdam (2002)
Ehrig, H., König, B.: Deriving bisimulation congruences in the DPO approach to graph rewriting with borrowed contexts. Mathematical Structures in Computer Science 16(6), 1133–1163 (2006)
Ehrig, H., Kreowski, H.-J.: Parallelism of manipulations in multidimensional information structures. In: Mazurkiewicz, A. (ed.) MFCS 1976. LNCS, vol. 45, pp. 284–293. Springer, Heidelberg (1976)
Gadducci, F.: Graph rewriting for the π-calculus. Mathematical Structures in Computer Science 17(3), 407–437 (2007)
Gadducci, F., Lluch Lafuente, A.: Graphical encoding of a spatial logic for the π-calculus. In: Mossakowski, T., Montanari, U., Haveraaen, M. (eds.) CALCO 2007. LNCS, vol. 4624, pp. 209–225. Springer, Heidelberg (2007)
Gadducci, F., Monreale, G.V.: A decentralized implementation of mobile ambients. In: Ehrig, H., Heckel, R., Rozenberg, G., Taentzer, G. (eds.) ICGT 2008. LNCS, vol. 5214, pp. 115–130. Springer, Heidelberg (2008)
Habel, A., Müller, J., Plump, D.: Double-pushout graph transformation revisited. Mathematical Structures in Computer Science 11(5), 637–688 (2001)
Heindel, T.: Hereditary pushouts reconsidered. In: Ehrig, H., Rensink, A., Rozenberg, G., Schürr, A. (eds.) ICGT 2010. LNCS, vol. 6372, pp. 250–265. Springer, Heidelberg (2010)
Johnstone, P.T., Lack, S., Sobociński, P.: Quasitoposes, quasiadhesive categories and artin glueing. In: Mossakowski, T., Montanari, U., Haveraaen, M. (eds.) CALCO 2007. LNCS, vol. 4624, pp. 312–326. Springer, Heidelberg (2007)
Lack, S., Sobociński, P.: Adhesive and quasiadhesive categories. Theoretical Informatics and Applications 39(3), 511–545 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag GmbH Berlin Heidelberg
About this paper
Cite this paper
Baldan, P., Gadducci, F., Sobociński, P. (2011). Adhesivity Is Not Enough: Local Church-Rosser Revisited. In: Murlak, F., Sankowski, P. (eds) Mathematical Foundations of Computer Science 2011. MFCS 2011. Lecture Notes in Computer Science, vol 6907. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22993-0_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-22993-0_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22992-3
Online ISBN: 978-3-642-22993-0
eBook Packages: Computer ScienceComputer Science (R0)