×

A graph structure over the category of sets and partial functions. (English) Zbl 0779.68055

The framework of the paper is graph grammars and graph rewritings using category theory. The structure of a directed graph is a function from the set \(E\) of edges to the product set \(V\times V\) of the source vertices set and destination vertices set. Ehrig characterized the graph grammar and rewriting rules using two pushout squares and pushout complements in the category of graphs. Löwe and Ehrig also formulated graph rewriting using a single pushout in the category of graphs based on sets and partial functions. In Raoult and Kennaway’s approach the graph is a function from the vertex set \(V\) to the set \(V^{\ast}\) of finite strings of vertices. Graph rewriting is defined by a single pushout square using partial functions. The present paper generalizes Raoult’s method. The considered graph structure is a function \(V\rightarrow TV\) from a vertex set \(V\) to \(TV\), where \(T\) is an endofunctor on the category Pfn of sets and partial functions (in the case \(TV=V^{\ast}\) the structure is the same as Raoult’s one). An existence theorem of pushouts is proved in this general setting avoiding many conditional checks and case divisions by using the relational calculus. It turns out that Raoult’s result lacks one condition.

MSC:

68Q42 Grammars and rewriting systems
18B05 Categories of sets, characterizations
PDFBibTeX XMLCite
Full Text: Numdam EuDML

References:

[1] M.S. Calenko . The structures of correspondence categories . Soviet Math. Dokl. , 18 ( 1977 ), 1498 - 1502 . Zbl 0404.18004 · Zbl 0404.18004
[2] M.S. Calenko , V.B. Gisin , and D.A. Raikov . Ordered categories with involution. Dissertations Mathematics , 227 ( 1984 ). MR 759814 | Zbl 0539.18005 · Zbl 0539.18005
[3] H. Ehrig , M. Korff , and M. Löwe . Tutorial introduction to the algebraic approach of graph grammars based on double and single pushouts. Lecture Notes in Computer Science , 532 ( 1990 ), 24 - 37 . Zbl 0765.68089 · Zbl 0765.68089
[4] H. Ehrig, M. Nagl, G. Rozenberg, and A. Rosenfeld, editors. Graph-grammars and their application to computer science, volume 291 of Lecture Notes in Computer Science . Springer-Verlag , 1986 . MR 943166 | Zbl 0636.00013 · Zbl 0636.00013
[5] Y. Kawahara . Relations in categories with pullbacks . Mem. Fac. Sci. Kyushu University , Ser. A27 ( 1973 ), 149 - 173 . MR 390017 | Zbl 0261.18005 · Zbl 0261.18005 · doi:10.2206/kyushumfs.27.149
[6] Y. Kawahara . Applications of relational calculus to computer mathematics. Bull. of Informatics and Cybernetics , 23 ( 1988 ), 67 - 78 . MR 937100 | Zbl 0645.68086 · Zbl 0645.68086
[7] Y. Kawahara . Pushout-complements and basic concepts of grammars in toposes. Theoretical Computer Science , 77 ( 1990 ), 267 - 289 . MR 1083139 | Zbl 0723.18004 · Zbl 0723.18004 · doi:10.1016/0304-3975(90)90171-D
[8] Y. Kawahara and Y. Mizoguchi . Categorical assertion semantics in toposes . Advances Softw. Sci. and Tech. , in press.
[9] R. Kennaway . On ”On graph rewritings”. Theoretical Computer Science , 52 ( 1987 ), 37 - 58 . MR 918112 | Zbl 0636.68028 · Zbl 0636.68028 · doi:10.1016/0304-3975(87)90079-X
[10] R. Kennaway . Graph rewriting in some categories of partial morphisms. Lecture Notes in Computer Science , 532 ( 1990 ), 490 - 504 . MR 1431290 | Zbl 0765.68065 · Zbl 0765.68065
[11] M. Löwe and H. Ehrig . Algebraic approach to graph transformation based on single pushout derivations. Lecture Notes in Computer Science , 484 ( 1990 ), 338 - 353 . MR 1114594 | Zbl 0768.68069 · Zbl 0768.68069
[12] Y. Mizoguchi and Y. Kawahara . Graph rewritings without gluing conditions . RIFIS Tech. Report CS-42, Kyushu University , 1991 .
[13] J.C. Raoult . On graph rewritings. Theoretical Computer Science , 32 ( 1984 ), 1 - 24 . MR 761158 | Zbl 0551.68065 · Zbl 0551.68065 · doi:10.1016/0304-3975(84)90021-5
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.