Abstract
In this paper we present a mathematical framework tailored for reasoning about specification/program refinements. The proposed framework uses formal concepts coming from Institution Theory and Category Theory, such as theories and morphisms, to capture the notion of specification/program refinement. The main benefits of the proposed mathematical theory are its generality and compositionality, that is, it is based on abstract concepts that can be used to reason about refinements in different formal settings (such as Z, B, VDM, Alloy, statecharts and others), as well as it heavily relies upon the notion of component, thus enabling modular reasoning over the process of specification/program refinement.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
\(\mathbf {Sign}^{op}\) denotes the dual category of Sign, obtained by reversing arrows. This is so since reducts and translations go in different directions.
- 2.
In [23] this definition is stronger and the authors require that the sets of traces of both terms have to be the same, here we focus on refinement, and since that we only require an inclusion between the corresponding set of traces.
- 3.
Note that this is straightforward to prove for standard cospans when we have a finitely cocomplete category.
References
Abrial, J.-R.: The B-Book. Cambridge University Press, Cambridge (1996)
Back, R.J., von Wright, J.: Refinement Calculus: A Systematic Introduction. Springer, New York (1998)
Barr, M., Wells, C.: Category Theory for Computer Science. Centre de Recherches Mathématiques, Université de Montréal, Montreal (1999)
Bird, R., de Moor, O.: Algebra of Programming. Prentice-Hall, Upper Saddle River (1997)
Borceux, F.: Handbook of Categorical Algebra. Basic Category Theory, Encyclopedia of Mathematics and its Applications, vol. 1. Cambridge University Press, Cambridge (1994)
Cavalcanti, A.L.C.: A Refinement calculus for Z. Ph.D. thesis, Oxford University Computing Laboratory, Oxford, UK (1997)
Castro, P., Aguirre, N., Lopez Pombo, C., Maibaum, T.: Categorical foundations for structured specifications in Z. Form. Asp. Comput. 27(5–6), 831–865 (2015)
Diaconescu, R.: Grothendieck institutions. Appl. Categ. Struct. 10(4), 383–402 (2002)
Diaconescu, R.: Institution-Independent Model Theory. Birkhäuser Verlag, Basel (2008)
Fiadeiro, J.: Categories for Software Engineering. Springer, Heidelberg (2004)
Fiadeiro, J., Sernadas, A.: Structuring theories on consequence. In: Sannella, D., Tarlecki, A. (eds.) ADT 1987. LNCS, vol. 332, pp. 44–72. Springer, Heidelberg (1988). doi:10.1007/3-540-50325-0_3
Fischer, C.: Combining CSP and Z. Technical report, University of Oldenburg (1996)
Goguen, J., Burstall, R.: Institutions: abstract model theory for specification and programming. J. ACM 39(1), 95–146 (1992). ACM Press
He, J., Hoare, C.A.R., Sanders, J.W.: Data refinement refined resume. In: Robinet, B., Wilhelm, R. (eds.) ESOP 1986. LNCS, vol. 213, pp. 187–196. Springer, Heidelberg (1986). doi:10.1007/3-540-16442-1_14
Hoare, C.A.R.: Communicating Sequential Processes. Prentice Hall International, Upper Saddle River (1985)
Hoare, C.A.R., He, J.: Unifying Theories of Programming. Prentice Hall International Series in Computer Science. Prentice-Hall, Upper Saddle River (1998)
Jackson, D.: Data Abstractions. Logic, Language, and Analysis. MIT Press, Cambridge (2006)
Johnson, M., Naumann, D., Power, J.: Category theoretic models of data refinement. Electr. Notes Theor. Comput. Sci. 225, 21–38 (2009)
Jones, C.B.: Systematic Software Development Using VDM, 2nd edn. Prentice Hall, New York (1990)
Lack, S., Sobociński, P.: Adhesive categories. In: Walukiewicz, I. (ed.) FoSSaCS 2004. LNCS, vol. 2987, pp. 273–288. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24727-2_20
Lopes, A., Fiadeiro, J.: Superposition: composition vs refinement of non-deterministic, action-based systems. Form. Asp. Comput. 16(1), 5–18 (2004). Springer
Mossakowski, T.: Heterogeneus specification and the heterogeneous tool set. Habilitation thesis (2005)
Mossakowski, T., Roggenbach, M.: Structured CSP – a process algebra as an institution. In: Fiadeiro, J.L., Schobbens, P.-Y. (eds.) WADT 2006. LNCS, vol. 4409, pp. 92–110. Springer, Heidelberg (2007). doi:10.1007/978-3-540-71998-4_6
Morgan, C.C.: Programming from Specifications. Prentice-Hall, Upper Saddle River (1990)
Rodrigues, C., Martins, M., Madeira, A., Barbosa, L.: Refinement by interpretation in \(\pi \)-institutions. In: Proceedings of the 15th International Refinement Workshop (2011)
Spivey, J.M.: The Z Notation: A Reference Manual. Prentice Hall, Upper Saddle River (1992)
Tarlecki, A.: Moving between logical systems. In: Haveraaen, M., Owe, O., Dahl, O.-J. (eds.) ADT/COMPASS -1995. LNCS, vol. 1130, pp. 478–502. Springer, Heidelberg (1996). doi:10.1007/3-540-61629-2_59
Woodcock, J., Cavalcanti, A.L.C.: The semantics of Circus. In: Bert, D., Bowen, J.P., Henson, M.C., Robinson, K. (eds.) ZB 2002. LNCS, vol. 2272, pp. 184–203. Springer, Heidelberg (2002). doi:10.1007/3-540-45648-1_10
Woodcock, J., Davies, J.: Using Z: Specification, Refinement, and Proof. Prentice Hall, Upper Saddle River (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Castro, P.F., Aguirre, N. (2016). Algebraic Foundations for Specification Refinements. In: Ribeiro, L., Lecomte, T. (eds) Formal Methods: Foundations and Applications. SBMF 2016. Lecture Notes in Computer Science(), vol 10090. Springer, Cham. https://doi.org/10.1007/978-3-319-49815-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-49815-7_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49814-0
Online ISBN: 978-3-319-49815-7
eBook Packages: Computer ScienceComputer Science (R0)