Sesqui-Pushout Rewriting

Corradini, Andrea; Heindel, Tobias; Hermann, Frank; König, Barbara

doi:10.1007/11841883_4

No full text

Paper published in a book (Scientific congresses, symposiums and conference proceedings)

Sesqui-Pushout Rewriting

Corradini, Andrea; Heindel, Tobias; Hermann, Frank et al.

2006 • In Graph Transformation

Peer reviewed

Permalink
https://hdl.handle.net/10993/3868

DOI
10.1007/11841883_4

Files (0)Send to Details Statistics Bibliography Similar publications

Files

Full Text

No document available.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

graph transformation; single pushout approach; double pushout approach; sesqui pushout approach

Abstract :

[en] Sesqui-pushout (sqpo) rewriting – ''sesqui´´ means ``one and a half'' in Latin – is a new algebraic approach to abstract rewriting in any category. sqpo rewriting is a deterministic and conservative extension of double-pushout (dpo) rewriting, which allows to model ``deletion in unknown context'', a typical feature of single-pushout (spo) rewriting, as well as cloning. After illustrating the expressiveness of the proposed approach through a case study modelling an access control system, we discuss sufficient conditions for the existence of final pullback complements and we analyze the relationship between sqpo and the classical dpo and spo approaches.

Disciplines :

Computer science

Identifiers :

UNILU:UL-CONFERENCE-2011-188

Author, co-author :

Corradini, Andrea; Università di Pisa, Italy

Heindel, Tobias; Università di Pisa, Italy

Hermann, Frank ; Technische Universität Berlin, Germany

König, Barbara; Universität Duisburg-Essen, Germany

Language :

English

Title :

Sesqui-Pushout Rewriting

Publication date :

2006

Event name :

Third International Conference on Graph Transformation (ICGT'06)

Event place :

Natal, Brazil

Event date :

Sep. 2006

Main work title :

Graph Transformation

Publisher :

Springer Verlag

ISBN/EAN :

3-540-38870-2

Pages :

30-45

Peer reviewed :

Peer reviewed

Additional URL :

http://www.springerlink.com/content/v66287vj04077203/

Commentary :

4178 Graph Transformation

Available on ORBilu :

since 15 July 2013

Statistics

Number of views

73 (2 by Unilu)

Number of downloads

0 (0 by Unilu)

More statistics

Scopus citations^®

103

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Michel Bauderon. A uniform approach to graph rewriting: The pullback approach. In M. Nagl, editor, Graph-Theoretic Concepts in Computer Science, volume 1017 of Lecture Notes in Computer Science, pages 101-115. Springer, 1995.
Andrea Corradini, Ugo Montanari, Prancesca Rossi, Hartmut Ehrig, Reiko Heckel, and Michael Löwe. Algebraic approaches to graph transformation - part I: Basic concepts and double pushout approach. In G. Rozenberg, editor, Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1: Foundations, chapter 3. World Scientific. 1997.
Roy Dyckhoff and Walter Tholen. Exponentiable morphisms, partial products and pullback complements. Journal of Pure and Applied Algebra, 49(1-2):103-116, 1987.
Hartmut Ehrig, Annegret Habel, Hans-Jörg Kreowski, and Francesco ParisiPresicce. Parallelism and concurrency in high level replacement systems. Mathematical Structures in Computer Science, 1:361-404, 1991.
Hartmut Ehrig, Reiko Heckel, Martin Korff, Michael Löwe, Leila Ribeiro, Annika Wagner, and Andrea Corradini. Algebraic approaches to graph transformation-part II: Single pushout approach and comparison with double pushout approach. In G. Rozenberg, editor, Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1: Foundations, chapter 4. World Scientific, 1997.
Hartmut Ehrig and Michael Löwe. Categorical principles, techniques and results for high-level-replacement systems in computer science. Applied Categorical Structures. 1:21-50, 1993.
Hartmut Ehrig, Michael Pfender, and Hans-Jürgen Schneider. Graph grammars: An algebraic approach. In Proc. 14th IEEE Symp. on Switching and Automata Theory, pages 167-180, 1973.
David F. Ferriolo, D. Richard Kuhn, and Ramaswamy Chandramouli. Role-Based Access Control. Artech House computer.security series. Artech House, 2003. ISBN: 1-580-53370-1.
Robert Goldblatt. Topoi: The Categorial Analysis of Logic. Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Company, Amsterdam, The Netherlands, 1984.
Annegret Habel, Jürgen Müller, and Detlef Plump. Double-pushout graph transformation revisited. Mathematical Structures in Computer Science, 11(5):637-688, 2001.
Michael A. Harrison, Walter L. Ruzzo, and Jeffrey D. Ullman. Protection in operating systems. Commun. ACM, 19(8):461-471, 1976.
Reiko Heckel, Hartmut Ehrig, Uwe Wolter, and Andrea Corradini. Double-pullback transitions and coalgebraic loose semantics for graph transformation systems. Applied Categorical Structures, 9(1), 2001.
Wolfram Kahl. A fibred approach to rewriting -how the duality between adding and deleting cooperates with the difference between matching and rewriting. Technical Report 9702, Fakultät für Informatik. Universität der Bundeswehr München, May 1997.
Richard Kennaway. Graph Rewriting in Some Categories of Partial Morphisms. In Hartmut Ehrig. Hans-Jörg Kreowski, and Grzeġorz Rozenberg, editors, Proc. 4th. Int. Workshop on Graph Grammars and their Application to Computer Science, volume 532 of Lecture Notes in Computer Science, pages 490-504. Springer-Verlag, 1991.
Manuel Koch, Luigi V. Mancini, and Francesco Parisi-Presicce. A formal model for role-based access control using graph transformation. In Frédéric Cuppens, Yves Deswarte, Dieter Gollmann, and Michael Waidner, editors, ESORICS, volume 1895 of Lecture Notes in Computer Science, pages 122-139. Springer, 2000.
Stephen Lack and Pawel Sobociński. Adhesive and quasiadhesive categories. Theoretical Informatics and Applications, 39(2):511-546, 2005.
Michael Löwe. Algebraic approach to single-pushout graph transformation. Theoretical Computer Science, 109:181-224, 1993.
Miquel Monserrat, Francesc Rossellö, Joan Torrens, and Gabriel Valiente. Single pushout rewriting in categories of spans I: The general setting. Technical Report LSI-97-23-R, Departament de Llenguatges i Sistemes Informatics, Universitat Politècnica de Catalunya, 1997.
Edmund Robinson and Giuseppe Rosolini. Categories of partial maps. Information and Computation, 79(2):95-130, 1988.
Ravi S. Sandhu, Edward J. Coyne, Hal L. Feinstein, and Charles E. Youman. Role-based access control models. IEEE Computer, 29(2):38-47, 1996.