zbMATH — the first resource for mathematics

Stratified institutions and elementary homomorphisms. (English) Zbl 1189.03038
Summary: For conventional logic institutions, when one extends the sentences to contain open sentences, their satisfaction is then parameterized. For instance, in first-order logic, satisfaction is parameterized by the valuation of unbound variables, while in modal logics it is further parameterized by possible worlds. This paper proposes a uniform treatment of such parameterization of the satisfaction relation within the abstract setting of logics as institutions by defining the new notion of stratified institutions. In this new framework, the notion of elementary model homomorphism is defined independently of an internal stratification or elementary diagrams. At this level of abstraction, a general Tarski-style study of connectives is developed. This is an abstract unified approach to the usual Boolean connectives, to quantifiers, and to modal connectives. A general theorem subsuming Tarski’s elementary chain theorem is then proved for stratified institutions with this new notion of connectives.

03B70 Logic in computer science
03C95 Abstract model theory
03G30 Categorical logic, topoi
68Q65 Abstract data types; algebraic specification
Full Text: DOI
[1] F. Barbier, Géneralisation et préservation au travers de la combinaison des logique des résultats de théorie des modèles standards liés à la structuration des spécifications algébriques, PhD thesis, Université Evry, 2005
[2] Bidoit, M.; Hennicker, R., On the integration of the observability and reachability concepts, (), 21-36 · Zbl 1077.68709
[3] Borzyszkowski, T., Higher-order logic and theorem proving for structured specifications, (), 401-418 · Zbl 0966.03010
[4] Chang, C.C.; Keisler, H.J., Model theory, (1990), North-Holland Amsterdam · Zbl 0697.03022
[5] Cîrstea, C., Institutionalising many-sorted coalgebraic modal logic, Coalgebraic methods in computer science 2002, Electronic notes in theoretical computer science, (2002) · Zbl 1270.03140
[6] R. Diaconescu, Institution-independent Model Theory, Book draft. (Ask author for current draft at Razvan.Diaconescu@imar.ro.)
[7] Diaconescu, R., Institution-independent ultraproducts, Fundamenta informaticæ, 55, 3-4, 321-348, (2003) · Zbl 1036.03055
[8] Diaconescu, R.; Futatsugi, K., Behavioural coherence in object-oriented algebraic specification, Universal computer science, 6, 1, 74-96, (2000), First version appeared as JAIST Technical Report IS-RR-98-0017F, June 1998 · Zbl 0963.68104
[9] Fiadeiro, J.L.; Costa, J.F., Mirror, mirror in my hand: A duality between specifications and models of process behaviour, Mathematical structures in computer science, 6, 4, 353-373, (1996) · Zbl 0857.68076
[10] Gabbay, D., Fibring logics, (1999), Oxford University Press · Zbl 0909.03001
[11] Goguen, J.; Burstall, R., Institutions: abstract model theory for specification and programming, Journal of the association for computing machinery, 39, 1, 95-146, (1992) · Zbl 0799.68134
[12] Goguen, J.; Diaconescu, R., Towards an algebraic semantics for the object paradigm, (), 1-34 · Zbl 0941.68637
[13] Goguen, J.; Roşu, G., Hiding more of hidden algebra, (), 1704-1719 · Zbl 0953.68094
[14] Găină, D.; Popescu, A., An institution-independent generalization of Tarski’s elementary chain theorem, Journal of logic and computation, 16, 6, 713-735, (2006) · Zbl 1123.03058
[15] Găină, D.; Popescu, A., An institution-independent proof of Robinson consistency theorem, Studia logica, 85, 1, 41-73, (2007) · Zbl 1123.03059
[16] Hennicker, R.; Bidoit, M., Observational logic, (), 263-277
[17] Y. Lamo, The Institution of Multialgebras—a general framework for algebraic software development, PhD thesis, University of Bergen, 2003
[18] Mossakowski, T.; Tarlecki, A.; Pawłowski, W., Combining and representing logical systems using model-theoretic parchments, (), 349-364 · Zbl 0907.03030
[19] Schröder, L.; Mossakowski, T.; Lüth, C., Type class polymorphism in an institutional framework, (), 234-248 · Zbl 1118.68562
[20] Sernadas, A.; Sernadas, C.; Caleiro, C., Fibring of logics as a categorical constructions, Journal of logic and computation, 9, 2, 149-179, (1999) · Zbl 0942.03064
[21] Tarlecki, A., Bits and pieces of the theory of institutions, (), 334-360
[22] Tarski, A.; Vaught, R., Arithmetical extensions of relational systems, Compositio mathematicæ, 13, 81-102, (1957) · Zbl 0091.01201
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.