Abstract
NLC and ESM are two types of graph rewriting based on node replacement and embedding. Their embedding mechanisms are quite different, and no unifying framework for them was known so far. It is demonstrated that Local Action Systems provide such a framework. Since rewriting in an NLC grammar is not confluent, this leads to the notion of an ordered LAS processes: a process equipped with a complete order on the local actions. It is shown that NLC graph rewriting can be described in terms of these ordered processes, and that the order can be omitted if the sets of available local actions satisfy a simple algebraic property. ESM graph rewriting fits into this unordered version of the theory.
Partially supported by the EC TMR Network GETGRATS (General Theory of Graph Transformation Systems) and Esprit Working Group APPLIGRAPH through Universitaire Instelling Antwerpen.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Corradini, A., Montanari, U., Rossi, F.: Graph Processes. Fundamenta Informaticae 26, 241–265 (1996)
Engelfriet, J., Rozenberg, G.: Node Replacement Graph Grammars. In: Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1, pp. 1–94. World Scientific, Singapore (1997)
Janssens, D.: Actor Grammars and Local Actions. In: Handbook of Graph Grammars and Computing by Graph Transformation, vol. 3. World Scientific, Singapore (1999)
Janssens, D.: ESM Systems and the Composition of Their Computations. In: Ehrig, H., Schneider, H.-J. (eds.) Dagstuhl Seminar 1993. LNCS, vol. 776, pp. 203–217. Springer, Heidelberg (1994)
Janssens, D., Mens, T.: Abstract semantics for ESM systems. Fundamenta Informaticae 26, 315–339 (1996)
Janssens, D., Rozenberg, G.: On the Structure of Node Label Controlled Graph Languages. Information Sciences 20, 191–216 (1980)
Pratt, V.R.: Modelling Concurrency with Partial Orders. J. of Parallel Programming 15, 33–71 (1987)
Winskel, G.: Events in Computation, Ph. D. Thesis, Comp. Sci. Dept., University of Edinburgh (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Verlinden, N., Janssens, D. (2000). A Framework for NLC and ESM: Local Action Systems. In: Ehrig, H., Engels, G., Kreowski, HJ., Rozenberg, G. (eds) Theory and Application of Graph Transformations. TAGT 1998. Lecture Notes in Computer Science, vol 1764. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-46464-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-46464-8_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67203-6
Online ISBN: 978-3-540-46464-8
eBook Packages: Springer Book Archive