Navegar

Colección

Datos Estadísticas

Artículo

Frias, M.F.; López Pombo, C.G.; Baum, G.A.; Aguirre, N.M.; Maibaum, T.S.E. "Reasoning about static and dynamic properties in alloy: A purely relational approach" (2005) ACM Transactions on Software Engineering and Methodology. 14(4):478-526
La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We study a number of restrictions associated with the first-order relational specification language Alloy. The main shortcomings we address are: -the lack of a complete calculus for deduction in Alloy's underlying formalism, the so called relational logic, -the inappropriateness of the Alloy language for describing (and analyzing) properties regarding execution traces. The first of these points was not regarded as an important issue during the genesis of Alloy, and therefore has not been taken into account in the design of the relational logic. The second point is a consequence of the static nature of Alloy specifications, and has been partly solved by the developers of Alloy; however, their proposed solution requires a complicated and unstructured characterization of executions. We propose to overcome the first problem by translating relational logic to the equational calculus of fork algebras. Fork algebras provide a purely relational formalism close to Alloy, which possesses a complete equational deductive calculus. Regarding the second problem, we propose to extend Alloy by adding actions. These actions, unlike Alloy functions, do modify the state. Much the same as programs in dynamic logic, actions can be sequentially composed and iterated, allowing them to state properties of execution traces at an appropriate level of abstraction. Since automatic analysis is one of Alloy's main features, and this article aims to provide a deductive calculus for Alloy, we show that: -the extension hereby proposed does not sacrifice the possibility of using SAT solving techniques for automated analysis, -the complete calculus for the relational logic is straightforwardly extended to a complete calculus for the extension of Alloy. © 2005 ACM.

Registro:

Documento: Artículo
Título:Reasoning about static and dynamic properties in alloy: A purely relational approach
Autor:Frias, M.F.; López Pombo, C.G.; Baum, G.A.; Aguirre, N.M.; Maibaum, T.S.E.
Filiación:FCEyN, Universidad de Buenos Aires, CONICET, Argentina
Facultad de Informática, Universidad Nacional de La Plata, CONICET, Argentina
FCEFQyN, Universidad Nacional de Río Cuarto, CONICET, Argentina
Department of Computing and Software, McMaster University, Canada
Department of Computer Science, School of Sciences, University of Buenos Aires, Buenos Aires (1427), Argentina
Facultad de Ciencias Exactas, Universidad Nacional de La Plata, Calle 50 y 115- 1er piso, (1900), La Plata, Argentina
Departamento de Computatión, FCFQyN, Universidad de Rio Cuarto, Enlace rutas 8y36, Km 601, Rio Cuarto (5800), Córdobu, Argentina
Department of Computing and Software, McMaster University, 1280 Main Street West, Hamilton, Ont. L8S 4L7, Canada
Palabras clave:Alloy; Fork algebras; Relational specifications; Automatic analysis; Dynamic logic; Fork algebras; Relational specifications; Abstracting; Algebra; Automation; Formal logic; Logic design; Problem solving; Computer programming languages
Año:2005
Volumen:14
Número:4
Página de inicio:478
Página de fin:526
DOI: http://dx.doi.org/10.1145/1101815.1101819
Título revista:ACM Transactions on Software Engineering and Methodology
Título revista abreviado:ACM Trans. Software Eng. Methodol.
ISSN:1049331X
CODEN:ATSME
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_1049331X_v14_n4_p478_Frias

Referencias:

  • Abbial, J., (1996) The B-book: Assigning Programs to Meanings, , Cambridge University Press, New York, NY
  • Arkoudas, K., (2000) Denotational Proof Languages, , Ph.D. thesis, Massachusetts Institute of Technology
  • Aekoudas, K., Khurshid, S., Mahinov, D., Rinard, M., Integrating model checking and theorem proving for relational reasoning (2004) Proceedings of the 7th Conference on Relational Methods in Computer Science (RelMiCS)-2nd, International Workshop on Applications of Kleene Algebra, 3051, pp. 204-213. , R. Berghammer and B. Möller, Eds. Lecture Notes in Computer Science. Springer-Verlag, Malente, Germany
  • Bickford, M., Guaspari, D., Lightweight analysis of UML (1998) Tech. Rep., TM-98-0036. , Odyssey Research Associates, Ithaca, NY, November
  • Booch, G., Rumbauoh, J., Jacobson, I., (1998) The Unified Modeling Language User Guide, , Addison-Wesley Longman Publishing Co., Inc., Boston, MA
  • Burris, S., Sankappanavar, H.P., (1981) A Course in Universal Algebra, , Graduate Texts in Mathematics. Springer-Verlag, Berlin, Germany
  • Clarke, E.M., Grumberg, O., Peled, D., (2000) Model Checking, , MIT Press, Cambridge, MA
  • Cleaveland, R., Klein, M., Steffen, B., Faster model checking for the modal mu-calculus (1993) Proceedings of Computer Aided Verification (CAV), 663, pp. 410-422. , G. von Bochmann and D. K. Probst, Eds. Lecture Notes in Computer Science, Springer-Verlag, Montreal, Canada
  • Dijkstra, E.W., Scholten, C.S., (1990) Predicate Calculus and Program Semantics, , Springer-Verlag, New York, NY
  • Dowek, G., Felty, A., Herbelin, H., Huet, G., Murthy, C., Parent, C., Paulin-Mohring, C., Werner, B., The coq proof assistant user's guide (version 5.8) (1993) Tech. Rep., 154. , INRIA, Rocquencourt, France
  • Frias, M.F., (2002) Fork Algebras in Algebra, Logic and Computer Science, 2. , Advances in Logic. World Scientific Publishing Co., Singapore
  • Frias, M.F., Baum, G.A., Maibaum, T.S.E., Interpretability of first-order dynamic logic in a relational calculus (2002) Proceedings of the 6th. Conference on Relational Methods in Computer Science (RelMiCS) - TARSKI, 2561, pp. 66-80. , H. de Swart, Ed. Lecture Notes in Computer Science, Springer-Verlag, Oisterwijk, The Netherlands
  • Frias, M.F., Haeberer, A.M., Veloso, P.A.S., A finite axiomatization for fork algebras (1997) Logic Journal of the IGPL, 5 (3), pp. 311-319
  • Frias, M.F., Lopez Pombo, C.G., Baum, G.A., Aguirre, N.M., Maibaum, T.S.E., Taking alloy to the movies (2003) Proceedings of FM 2003: The 12th International FME Symposium, 2805, pp. 678-697. , K. Araki, S. Gnesi, and D. Mandrioli, Eds. Lecture Notes in Computer Science. Springer-Verlag, Pisa, Italy
  • (1993) Introduction to HOL: A Theorem Proving Environment for Higher Order Logic, , GORDON, M. J. AND MELHAM, T. P., Eds. Cambridge University Press, New York, NY
  • Harel, D., Kozen, D., Tiuryn, J., (2000) Dynamic Logic, , Foundations of Computing. MIT Press, Cambridge, MA
  • Jackson, D., Automating first-order relational logic (2000) Proceedings of the 8th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp. 130-139. , ACM Press, San Diego, California
  • Jackson, D., Alloy: A lightweight object modelling notation (2002) ACM Trans. Soft. Eng. Meth., 11 (2), pp. 256-290
  • Jackson, D., (2002) A Micromodel of Software: Lightweight Modelling and Analysis with Alloy, , MIT Laboratory for Computer Science, Cambridge, MA
  • Jackson, D., Schechter, I., Shlyahter, H., Alcoa: The alloy constraint analyzer (2000) Proceedings of the 22nd. International Conference on Software Engineering, pp. 730-733. , C. Ghezzi, M. Jazayeri, and A. L. Wolf, Eds. Association for the Computer Machinery and IEEE Computer Society, ACM Press, Limerick, Ireland
  • Jackson, D., Shlyakhter, I., Sridharan, M., A micromodularity mechanism (2001) Proceedings of the 8th European Software Engineering Conference Held Together with the 9th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp. 62-73. , ACM Press, Vienna, Austria
  • Jackson, D., Sullivan, K., COM revisited: Tool-assisted modelling of an architectural framework (2000) Proceedings of the 8th ACM SIGSOFT International Symposium on Foundations of Software Engineering: Twenty-first Century Applications, pp. 149-158. , D. S. Rosenblum, Ed. ACM Press, San Diego, CA
  • Jones, C., (1986) Systematic Software Development Using VDM, , Prentice Hall, Hertfordshire, UK
  • Lopez Pombo, C.G., Owre, S., Shankar, N., A semantic embedding of the Ag dynamic logic in PVS (2002) Tech. Rep., SRI-CSL-02-04. , Computer Science Laboratory, SRI International. July
  • Manna, Z., Anuchitanukul, A., Bjørner, N., Browne, A., Chang, E., Colon, M., De Alfaro, L., Uribe, T., STeP: The Stanford temporal prover (1994) Tech. Rep., , Stanford University, Stanford, CA
  • Mcmillan, K.L., (1993) Symbolic Model Checking, , Kluwer Academic Publishers, Norwell, MA
  • Nipkow, T., Paulson, L.C., Wenzel, M., (2002) Isabelle/HOL - A Proof Assistant for Higher-order Logic, 2283. , Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany
  • (1997) Object Constraint Language Specification, , Object Management Group, Needham, MA, version 1.1
  • Owre, S., Rushby, J.M., Shankar, N., PVS: A prototype verification system (1992) Proceedings of the 11th International Conference on Automated Deduction (CADE), 607, pp. 148-752. , D. Kapur, Ed. Lecture Notes in Artificial Intelligence, Springer-Verlag, Saratoga, NY
  • Owre, S., Rushby, J.M., Shankar, N., Stringer-Calvert, D., PVS: An experience report (1998) Proceedings of Applied Formal Methods - (FM-Trends) '98, 1641, pp. 338-345. , D. Hutter, W. Stephan, P. Traverso, and M. Ullman, Eds. Lecture Notes in Computer Science, Springer-Verlag, Boppard, Germany
  • Owre, S., Shankar, N., Abstract datatypes in PVS (1993) Tech. Rep., SRI-CSL-93-9R. , Computer Science Laboratory, SRI International. December. Subtantially revised in June 1997
  • Owre, S., Shankar, N., Rushby, J.M., Sthingeh-Calvert, D., (2001) PVS Language Reference, Version 2.4, , ed. SRI International
  • Owre, S., Shankar, N., Rushby, J.M., Stringer-Calvert, D., (2001) PVS Prover Guide, Version 2.4, , ed. Computer Science Laboratory, SRI International
  • Owre, S., Shankar, N., Rushby, J.M., Stringer-Calvert, D., (2001) PVS System Guide, Version 2.4, , ed. Computer Science Laboratory, SRI International
  • Spivey, J.M., (1988) Understanding Z: A Specification Language and Its Formal Semantics, , Cambridge University Press, New York, NY
  • Tarski, A., Givant, S., (1987) A Farmalization of Set Theory Without Variables, , American Mathematical Society Colloqium Publications, Providence, RI
  • Vardi, M.Y., Wolper, P., An automata-theoretic approach to automatic program verification (preliminary report) (1986) Proceedings of the Symposium on Logic in Computer Science '86, pp. 332-344. , A. Meyer, Ed. IEEE Computer Society, Cambridge, MA

Citas:

---------- APA ----------
Frias, M.F., López Pombo, C.G., Baum, G.A., Aguirre, N.M. & Maibaum, T.S.E. (2005) . Reasoning about static and dynamic properties in alloy: A purely relational approach. ACM Transactions on Software Engineering and Methodology, 14(4), 478-526.
http://dx.doi.org/10.1145/1101815.1101819
---------- CHICAGO ----------
Frias, M.F., López Pombo, C.G., Baum, G.A., Aguirre, N.M., Maibaum, T.S.E. "Reasoning about static and dynamic properties in alloy: A purely relational approach" . ACM Transactions on Software Engineering and Methodology 14, no. 4 (2005) : 478-526.
http://dx.doi.org/10.1145/1101815.1101819
---------- MLA ----------
Frias, M.F., López Pombo, C.G., Baum, G.A., Aguirre, N.M., Maibaum, T.S.E. "Reasoning about static and dynamic properties in alloy: A purely relational approach" . ACM Transactions on Software Engineering and Methodology, vol. 14, no. 4, 2005, pp. 478-526.
http://dx.doi.org/10.1145/1101815.1101819
---------- VANCOUVER ----------
Frias, M.F., López Pombo, C.G., Baum, G.A., Aguirre, N.M., Maibaum, T.S.E. Reasoning about static and dynamic properties in alloy: A purely relational approach. ACM Trans. Software Eng. Methodol. 2005;14(4):478-526.
http://dx.doi.org/10.1145/1101815.1101819