Graph Grammars for the Specification of Concurrent Systems
Abstract
Graph grammars have origined from generalizing Chomsky grammars from Strings to Graphs. They visually support intuition, have a solid theoretical foundation, and provide a formal, implementation independent means for the description of discretely evolving computations and their formal and tractable analysis. In this paper we present the outline of a case study of specifying a telephone system and report on the resulting semantical and analytical issues.
Keywords:
graph grammars, system specification, concurrency
References
A. Corradini, Concurrent computing: from Petri nets to graph grammars, Eletronic Notes in Theoretical Computer Science 2 (1995), 245-260, Proc. of the SEGRAGRA'95 Workshop on Graph Rewriting and Computation.
H. Ehrig, R. Heckel, M. Korff, M. Löwe, L. Ribeiro, A. Wagner, and A. Corradini, Algebraic approaches to graph transformation II: Single pushout approach and comparison with double pushout approach, Handbook of Graph Grammars, Volume 1: Foundations, World Scientific, 1996, to appear.
H. Ehrig, Introduction to the algebraic theory of graph grammars, 1st Graph Grammar Workshop, Lecture Notes in Computer Science 73 (V. Claus, H, Ehrig, and G. Rozenberg, eds.), Springer Verlag, 1979, pp. 1-69.
M, Korff, Generalized graph structure grammars with applications to concurrent object-oriented systems, Ph.D. thesis, TU Berlin, 1996.
M. Korff and L. Ribeiro, Formal relationship between graph grammars and Petri nets, Lecture Notes in Computer Science 1073 (1996), 288-303.
M.Löwe, Algebraic approach to single-pushout graph transformation, Theoretical Computer Science 109 (1993), 181-224.
L. Ribeiro, Parallel composition and unfolding semantics of graph grammars, Ph.D. thesis, Technical University of Berlin, Germany, 1996.
L. Ribeiro, A telephone system's specification using graph grammars, Tech. Report 96-23, Technical University of Berlin, 1996.
G. Winskel, Event structures, Proc. of the Advanced Course on Petri Nets, Springer Verlag, 1987, Lecture Notes in Computer Science 255, pp. 325-392.
H. Ehrig, R. Heckel, M. Korff, M. Löwe, L. Ribeiro, A. Wagner, and A. Corradini, Algebraic approaches to graph transformation II: Single pushout approach and comparison with double pushout approach, Handbook of Graph Grammars, Volume 1: Foundations, World Scientific, 1996, to appear.
H. Ehrig, Introduction to the algebraic theory of graph grammars, 1st Graph Grammar Workshop, Lecture Notes in Computer Science 73 (V. Claus, H, Ehrig, and G. Rozenberg, eds.), Springer Verlag, 1979, pp. 1-69.
M, Korff, Generalized graph structure grammars with applications to concurrent object-oriented systems, Ph.D. thesis, TU Berlin, 1996.
M. Korff and L. Ribeiro, Formal relationship between graph grammars and Petri nets, Lecture Notes in Computer Science 1073 (1996), 288-303.
M.Löwe, Algebraic approach to single-pushout graph transformation, Theoretical Computer Science 109 (1993), 181-224.
L. Ribeiro, Parallel composition and unfolding semantics of graph grammars, Ph.D. thesis, Technical University of Berlin, Germany, 1996.
L. Ribeiro, A telephone system's specification using graph grammars, Tech. Report 96-23, Technical University of Berlin, 1996.
G. Winskel, Event structures, Proc. of the Advanced Course on Petri Nets, Springer Verlag, 1987, Lecture Notes in Computer Science 255, pp. 325-392.
Published
1997-10-15
How to Cite
RIBEIRO, Leila; KORFF, Martin.
Graph Grammars for the Specification of Concurrent Systems. In: BRAZILIAN SYMPOSIUM ON SOFTWARE ENGINEERING (SBES), 11. , 1997, Recife/PE.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1997
.
p. 199-214.
ISSN 2833-0633.
DOI: https://doi.org/10.5753/sbes.1997.24049.
