×

zbMATH — the first resource for mathematics

Some fundamental algebraic tools for the semantics of computation. III: Indexed categories. (English) Zbl 0755.18004
From the authors’ abstract and introduction: “For each many-sorted algebraic signature \(\Sigma\), there is a category \(\text{Alg}(\Sigma)\) of \(\Sigma\)-algebras, and a signature morphism \(\sigma: \Sigma\to\Sigma'\) induces a functor \(\text{Alg}(\sigma): \text{Alg}(\Sigma')\to\text{Alg}(\Sigma)\), which we call a \(\sigma\)- reduct. Thus, there is a functor \(\text{Alg}: \text{Alg\;Sig}^{op}\to\text{Cat}\) from the (index) category of signatures to the category of categories.” The authors therefore study “strict” indexed categories which appear to be “a useful tool for the working computer scientist. An indexed category gives rise to a single flattened category as a disjoint union of its component categories plus some additional morphisms. Similarly, an indexed functor (which is a uniform family of functors between the components categories) induces a flattened functor between the corresponding flattened categories. Under certain assumptions, flattened categories are (co)complete if all their components are, and flattened functors have left adjoints if all their components do.”
[The present Part III is entirely independent of Parts I and II (to appear)].

MSC:
18D30 Fibered categories
68Q55 Semantics in the theory of computing
08C05 Categories of algebras
08A70 Applications of universal algebra in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arbib, M.A.; Manes, E.G., Arrows, structures and functors: the categorical imperative, (1975), Academic Press New York · Zbl 0374.18001
[2] Barr, M.; Wells, C., The formal description of data types using sketches, () · Zbl 0644.68030
[3] Beierle, C.; Voss, A., Implementation specifications, (), 39-53, Informatik Fachberichte 116
[4] Benabou, J., Fibred categories and the foundations of naive category theory, J. symbolic logic, 50, 10-37, (1985) · Zbl 0564.18001
[5] Burstall, R.M.; Goguen, J.A., Putting theories together to make specifications, Proc. fifth internat. conf. on artificial intelligence, 1045-1058, (1977)
[6] Burstall, R.M.; Goguen, J.A., The semantics of clear, a specification language, (), 292-332 · Zbl 0456.68024
[7] Burstall, R.M.; Goguen, J.A., Algebras, theories and freeness: an introduction for computer scientists, (), 329-350 · Zbl 0518.68009
[8] Ehrich, H.-D., On the theory of specification, implementation and parameterisation of abstract data types, J. assoc. comput. Mach., 29, 206-227, (1982) · Zbl 0478.68020
[9] Ehrig, H.; Kreowski, H.-J.; Maggiolo-Schettini, A.; Winkowski, J., Transformation of structures: an algebraic approach, Math. systems theory, 14, 305-334, (1981) · Zbl 0491.68035
[10] Ehrig, H.; Mahr, B., Fundamentals of algebraic specification I: equations and initial algebra semantics, () · Zbl 0557.68013
[11] Goguen, J.A., Mathematical representation of hierarchically organised systems, (), 112-128
[12] Goguen, J.A., A categorical manifesto, (), also submitted for publication · Zbl 0747.18001
[13] Goguen, J.A., What is unification? — a categorical view of substitution, equation and solution, (), Technical report SRI-CSL-88-2R2, 217-261, (1988), SRI International, Computer Science Lab
[14] Goguen, J.A.; Burstall, R.M., CAT, a system for the structured elaboration of correct programs from structured specifications, () · Zbl 0456.68024
[15] Goguen, J.A.; Burstall, R.M., Some fundamental algebraic tools for the semantics of computation, part 1: comma categories, colimits, structures 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] Goguen, J.A.; Burstall, R.M.; Goguen, J.A.; Burstall, R.M., Earlier version: introducing institutions, (), 221-256 · Zbl 1288.03001
[18] Goguen, J.A.; Burstall, R.M., A study in the foundations of programming methodology: specifications, institutions, charters and parchments, (), 313-333 · Zbl 0615.68002
[19] Goguen, J.A.; Ginali, S.; Klir, G., A categorical approach to general systems theory, Applied general systems research, 257-270, (1978)
[20] Goguen, J.A.; Thatcher, J.W.; Wagner, E.G.; Goguen, J.A.; Thatcher, J.W.; Wagner, E.G., An initial algebra approach to the specification, correctness and implementation of abstract data types, (), 80-149, (1976) · Zbl 0333.93002
[21] Gray, J.W., Fibred and cofibred categories, (), 21-83 · Zbl 0192.10701
[22] Gray, J.W., Categories aspects of data type constructors, Theoret. comput. sci., 50, 103-135, (1987) · Zbl 0629.68014
[23] Grothendieck, A.; Grothendieck, A., Catégories fibrées et descente, (), 145-194
[24] Herrlich, H.; Strecker, G.E., Category theory, (1973), Allen & Bacon Rockleigh · Zbl 0265.18001
[25] Johnstone, P.T.; Paré, R., Indexed categories and their applications, () · Zbl 0372.00009
[26] Kamin, S.; Archer, M., Partial implementation of abstract data types: a dissenting view of errors, (), 317-336
[27] MacLane, S., Categories for the working Mathematician, (1971), Springer Berlin
[28] ()
[29] Mayoh, B., Galleries and institutions, ()
[30] Moggi, E., Computational lambda-calculus and monads, () · Zbl 0716.03007
[31] Moggi, E., A category-theoretic account of program modules, () · Zbl 0747.18009
[32] Sannella, D.T.; Tarlecki, A.; Sannella, D.T.; Tarlecki, A., Full version: specifications in an arbitrary institution, (), Inform. and comput., 76, 165-210, (1988) · Zbl 0654.68017
[33] Sannella, D.T.; Tarlecki, A., On observational equivalence and algebraic specifications, (), 34, 308-322, (1987), Extended abstract in
[34] Sannella, D.T.; Tarlecki, A., Extended ML: an institution independent framework for formal program development, (), 364-389
[35] Sannella, D.T.; Tarlecki, A., Towards formal development of programs from algebraic specifications: implementations revisited, (), 25, 96-110, (1988), Extended abstract in
[36] Tarlecki, A., On the existence of free models in abstract algebraic institutions, Theoret. comput. sci., 37, 269-301, (1985) · Zbl 0608.68014
[37] Tarlecki, A., Bits and pieces of the theory of institutions, (), 334-363
[38] Tarlecki, A., Quasi-varieties in abstract algebraic institutions, J. comput. system sci., 33, 333-360, (1986) · Zbl 0622.68033
[39] Taylor, P., Recursive domains, indexed category theory and polymorphism, ()
[40] Thatcher, J.W.; Wagner, E.G.; Wright, J.B., Data type specification: parameterisation and the power of specification techniques, Transactions on programming languages and systems, 4, 711-732, (1982) · Zbl 0495.68020
[41] Wand, M., Final algebra semantics and data type extensions, J. comput. system sci., 19, 27-44, (1979) · Zbl 0418.68020
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.