×

Pushout-complements and basic concepts of grammars in toposes. (English) Zbl 0723.18004

The author investigates pushouts in toposes by using essentially the theory of binary relations, which he called relational calculus. A characterization of pushouts is given, and also characterizations of the existence of a whole pushout starting from some part of it. For example for a composable pair of morphisms (f,g) any pair of morphisms (h,k) such that (g,k) is the pushout of (f,h) is called a pushout-complement of (f,g). The special case of the topos of directed graphs is closely examined. As an application, an embedding theorem and Church-Rosser theorem on grammars in a topos is proved.

MSC:

18B25 Topoi
68Q42 Grammars and rewriting systems
18A30 Limits and colimits (products, sums, directed limits, pushouts, fiber products, equalizers, kernels, ends and coends, etc.)
18A10 Graphs, diagram schemes, precategories
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arbib, M. A.; Manes, E. G., Arrows, Structures, and Functors, the Categorical Imperative (1975), Academic Press: Academic Press New York · Zbl 0374.18001
[2] Calenko, M. S., The structures of correspondence categories, Soviet Math. Dokl., 18, 1498-1502 (1977) · Zbl 0404.18004
[3] Calenko, M. S., Classification of correspondence categories and types of regularity for categories, Trans. Moscow Math. Soc., 1, 239-282 (1982) · Zbl 0494.18004
[4] Calenko, M. S.; Gisin, V. B.; Raikov, D. A., Ordered categories with involution, Diss. Math., 227 (1984)
[5] Ehrig, H., Introduction to the algebraic theory of graph grammars (a survey), (Lecture Notes in Computer Science, 73 (1979), Springer: Springer Berlin), 1-69
[6] Ehrig, H., Aspects of concurrency in graph grammars, (Lecture Notes in Computer Science, 153 (1983), Springer: Springer Berlin), 58-81
[7] Ehrig, H.; Habel, A.; Rosen, B. K., Concurrent transformations of relational structures, Fund. Inform., 9, 13-50 (1986) · Zbl 0592.68023
[8] Ehrig, H.; Kreowski, H.-J., Categorical approach to graphic systems and graph grammars, (Lecture Notes in Economics and Mathematical Systems, 131 (1976), Springer: Springer Berlin), 323-351
[9] Ehrig, H.; Kreowski, H.-J., Pushout-properties: an analysis of gluing constructions for graphs, Math. Nachr., 91, 135-149 (1979) · Zbl 0431.68069
[10] Ehrig, H.; Kreowski, H.-J.; Maggiolo-Schettini, A.; Rosen, B. K.; Winkowski, J., Deriving structures from structures, (Lecture Notes in Computer Science, 64 (1978), Springer: Springer Berlin), 177-190 · Zbl 0379.68055
[11] Ehrig, H.; Rosen, B. K., Decomposition of graph grammars, productions and derivations, (Lecture Notes in Computer Science, 73 (1979), Springer: Springer Berlin), 192-205
[12] Ehrig, H.; Rosen, B. K., The mathematics of record handling, (Lecture Notes in Computer Science, 52 (1977), Springer: Springer Berlin), 206-220
[13] Ehrig, H.; Stapies, J., Church-Rosser properties for graph replacement systems with unique splitting, (Lecture Notes in Computer Science, 153 (1983), Springer: Springer Berlin), 82-101 · Zbl 0522.68037
[14] Goguen, J. A.; Burstall, R. M., Introducing Institutions, (Lecture Notes in Computer Science, 164 (1984), Springer: Springer Berlin), 221-256 · Zbl 1288.03001
[15] Goguen, J. A.; Burstall, R. M., Some fundamental algebraic tools for the semantics of computation, Part 1: Comma categories, colimits, signatures and theories, Theoret. Comput. Sci., 31, 175-209 (1984) · Zbl 0566.68065
[16] Goguen, J. A.; Burstall, R. M., Some fundamental algebraic tools for the semantics of computation, Part 2: Signed and abstract theories, Theoret. Comput. Sci., 31, 263-295 (1984) · Zbl 0566.68066
[17] Goldblatt, R., Topoi, The Categorial Analysis of Logic (1979), North-Holland: North-Holland Amsterdam · Zbl 0434.03050
[18] Johnstone, P. T., Topos Theory (1977), Academic Press: Academic Press London · Zbl 0368.18001
[19] Kawahara, Y., Relations in categories with pullbacks, Mem. Fac. Sci. Kyushu Univ. Ser., A 27, 149-173 (1973) · Zbl 0261.18005
[20] Lambek, J.; Scott, P. J., Introduction to Higher Order Categorical Logic (1986), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0596.03002
[21] MacLane, S., The Categories for the Working Mathematician (1971), Springer: Springer New York
[22] Nivat, M.; Reynolds, J. C., Algebraic Methods in Semantics (1985), Cambridge University Press: Cambridge University Press London
[23] Puppe, D., Korrespondenzen in Abelschen Kategorien, Math. Ann., 148, 1-30 (1962) · Zbl 0109.25201
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.