×

zbMATH — the first resource for mathematics

Quasi-varieties in abstract algebraic institutions. (English) Zbl 0622.68033
The author specializes the extremely general notion of institution introduced by J. A. Goguen and R. M. Burstall [Lect. Notes Comput. Sci. 164, 221-256 (1984; Zbl 0543.68021)] to obtain his own notion of abstract algebraic institution. It is shown that in abstract algebraic institutions quasi-varieties and strict quasi-varieties are characterized respectively as implicational and strict implicational classes. This allows the author to present characterizations of the most general algebraic institution which strongly admit initial semantics [cf. A. Tarlecki, Theor. Comput. Sci. 37, 269-304 (1985; Zbl 0608.68014)] in more standard syntactical terms. These general considerations are applied to three familiar classes of total, partial and continuous algebras.
Reviewer: H.Nishimura

MSC:
68Q65 Abstract data types; algebraic specification
68P05 Data structures
Software:
ML
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] Adamek, J.; Nelson, E.; Reiterman, J., A Birkhoff variety theorem for continuous algebras, Algebra universalis, 20, 328-350, (1985) · Zbl 0594.08005
[3] Andreka, H.; Nemeti, I., Generalization of the concept of variety and quasivariety to partial algebras through category theory, (), Warsaw · Zbl 0518.08007
[4] also Math. Inst. Hung. Acad. Sci., preprint No. 5, 1976.
[5] Andreka, H.; Nemeti, I., A general axiomatizability theorem formulated in terms of cone-injective subcategories, (), 13-35
[6] Andreka, H.; Nemeti, I., Injectivity in categories to represent all first-order formulas, Demonstratio math., 12, 717-732, (1979) · Zbl 0497.03029
[7] Banaschewski, B.; Herrlich, H., Subcategories definable by implications, Houston J. math., 2, 149-171, (1976) · Zbl 0344.18002
[8] Barwise, K.J., Axioms for abstract model theory, Ann. math. logic, 7, 221-265, (1974) · Zbl 0324.02034
[9] Birkhoff, G., On the structure of abstract algebras, (), 433-454 · Zbl 0013.00105
[10] \scs. L. Bloom, and E. G. Wagner. Many-sorted theories and their algebras, with examples from computer science, working paper at US-French Joint Symp. on the Applications of Algebra to Language Definition and Compilatation, Fontainebleau, to appear.
[11] Broy, M.; Wirsing, M., Partial abstract types, Acta inform., 18, 47-64, (1982) · Zbl 0494.68020
[12] Burmeister, P., Partial algebras—survey of a unifying approach towards a two-valued model theory for partial algebras, Algebra universalis, 15, 306-358, (1982) · Zbl 0511.03014
[13] Burstall, R.M.; Goguen, J.A., The semantics of clear, a specification language, (), 292-332 · Zbl 0456.68024
[14] R. M. Burstall, and J. A. Goguen. Algebras, theories and freeness: An introduction for computer scientists, in “Proc. 1981 Marktoberdorf NATO Summer School, Reidel.” · Zbl 0518.68009
[15] \scR. L. de Carvalho, T. S. E. Maibaum, T. H. C. Pequeno, A. A. Pereda, and P. A. S. Veloso. “A Model Theoretic Approach to the Theory of Abstract Data Types and Data Structures,” Research Report, CS-80-22, Waterloo, Ontario
[16] Chang, C.C.; Keisler, H.J., Model theory, (1973), North-Holland Amsterdam · Zbl 0276.02032
[17] Ehrig, H.; Wagner, E.G.; Thatcher, J.W., Algebraic specifications with generating constraints, (), 188-202 · Zbl 0518.68019
[18] Gogolla, M., Algebraic specifications with partially ordered sorts and declarations, (), Fb. 169 · Zbl 0544.68015
[19] Gogolla, M.; Drosten, K.; Lipeck, U.; Ehrich, H.D., Algebraic and operational semantics of specifications allowing exceptions and errors, (), Fb. 140 · Zbl 0553.68012
[20] Goguen, J.A., Abstract errors for abstract data types, () · Zbl 0373.68024
[21] Goguen, J.A., Order sorted algebras: exceptions and error sorts, coercions and overloaded operators, ()
[22] Goguen, J.A.; Burstall, R.M., Introducing institutions, (), 221-256 · Zbl 1288.03001
[23] Goguen, J.A.; Burstall, R.M., Some fundamental algebraic tools for the semantics of computation. part 1. comma categories, colimits, signatures and theories, Theor. comput. sci., 31, 175-210, (1984) · Zbl 0566.68065
[24] Goguen, J.A.; Meseguer, J.; Goguen, J.A.; Meseguer, J., Completeness of many-sorted equational logic, SIGPLAN notices, Houston J. math., 11, No. 7, 307-334, (1985) · Zbl 0602.08004
[25] Goguen, J.A.; Meseguer, J., Initiality, induction and computability, () · Zbl 0571.68004
[26] Grätzer, G., Universal algebra, (1979), Springer New York · Zbl 0182.34201
[27] Guttag, J.V., The specification and application to programming of abstract data types, () · Zbl 0395.68020
[28] Herrlich, H.; Strecker, G.E., Category theory, (1973), Allyn & Bacon Boston · Zbl 0265.18001
[29] MacLane, S., Categories for the working Mathematician, (1971), Springer-Verlag New York
[30] Mahr, B.; Markowsky, J.A., Characterizing specification languages which admit initial semantics, Theor. comput. sci., 31, 49-60, (1984) · Zbl 0536.68011
[31] Makowsky, J., Why Horn formulas matter in computer science: initial structures and generic examples, (), 374-387 · Zbl 0563.68013
[32] Meseguer, J., Varieties of chain-complete algebras, J. pure appl. algebra, 19, 347-383, (1980) · Zbl 0445.18008
[33] Milner, R., A theory of type polymorphism in programming, J. comput. system sci., 17, 348-375, (1978) · Zbl 0388.68003
[34] Nelson, E., Z-continuous algebras, (), 315-334
[35] Nemeti, I.; Sain, I., Cone-injectivity and some Birkhoff type theorems in categories, (), 535-578
[36] Reichel, H., Initially restricting algebraic theories, (), 504-514 · Zbl 0469.68026
[37] \scH. Reichel. “Introduction to Theory and Application of Partial Algebras. Part II, Structural Induction on Partial Algebras,” (P. Burmeister and H. Reichel, Eds.), Akademie-Verlag, Berlin, in press. · Zbl 0553.08002
[38] Sannella, D.T.; Tarlecki, A., Builiding specifications in an arbitrary institution, (), 337-356
[39] Tarlecki, A.; Tarlecki, A., Free constructions in algebraic institutions, (), 526-534
[40] Tarlecki, A., Abstract algebraic institutions which strongly admit initial semantics, ()
[41] Tarlecki, A., On the existence of free models in abstract algebraic institutions, Theor. comput. sci., 37, 269-304, (1985) · Zbl 0608.68014
[42] Tarlecki, A.; Wirsing, M.; Tarlecki, A.; Wirsing, M., Continuous abstract data types-basic machinery and results, (), Fundamenta informaticae, IX, 95-126, (1986) · Zbl 0624.68024
[43] Wirsing, M.; Pepper, P.; Partsch, H.; Dosch, W.; Broy, M., On hierarchies of abstract data types, Acta inform., 20, 1-33, (1983) · Zbl 0513.68015
[44] Zilles, S.N., Algebraic specification of data types, ()
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.