Abstract:
Since its introduction by Goguen and Burstall in 1984, the theory of institutions has been one of the most widely accepted formalizations of abstract model theory. This work was extended by a number of researchers, José Meseguer among them, who presented General Logics, an abstract framework that complements the model theoretical view of institutions by defining the categorical structures that provide a proof theory for any given logic. In this paper we intend to complete this picture by providing the notion of Satisfiability Calculus, which might be thought of as the semantical counterpart of the notion of proof calculus, that provides the formal foundations for those proof systems that use model construction techniques to prove or disprove a given formula, thus "implementing" the satisfiability relation of an institution. © IFIP International Federation for Information Processing 2013.
Registro:
Documento: |
Artículo
|
Título: | Satisfiability calculus: The semantic counterpart of a proof calculus in general logics |
Autor: | Lopez Pombo, C.G.; Castro, P.F.; Aguirre, N.M.; Maibaum, T.S.E. |
Ciudad: | Salamanca |
Filiación: | Departmento de Computación, FCEyN, Universidad de Buenos Aires, Argentina Departmento de Computación, FCEFQyN, Universidad Nacional de Río Cuarto, Argentina Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET), Argentina Department of Computing and Software, McMaster University, Canada
|
Palabras clave: | Abstract framework; Abstract model theory; Categorical structure; Formal foundation; Proof calculus; Proof system; Proof theory; Satisfiability; Algebra; Formal logic; Semantics; Calculations |
Año: | 2013
|
Volumen: | 7841 LNCS
|
Página de inicio: | 195
|
Página de fin: | 211
|
DOI: |
http://dx.doi.org/10.1007/978-3-642-37635-1_12 |
Título revista: | 21st International Workshop on Algebraic Development Techniques, WADT 2012
|
Título revista abreviado: | Lect. Notes Comput. Sci.
|
ISSN: | 03029743
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v7841LNCS_n_p195_LopezPombo |
Referencias:
- Goguen, J.A., Burstall, R.M., Introducing institutions (1984) LNCS, 164, pp. 221-256. , Clarke, E., Kozen, D. (eds.) Logic of Programs 1983. Springer, Heidelberg
- Meseguer, J., General logics (1989) Proceedings of the Logic Colloquium 1987, Granada, Spain, 129, pp. 275-329. , Ebbinghaus, H.D., Fernandez-Prida, J., Garrido, M., Lascar, D., Artalejo, M.R. (eds.) North Holland
- Fiadeiro, J.L., Maibaum, T.S.E., Generalising interpretations between theories in the context of π-institutions (1993) Proceedings of the First Imperial College Department of Computing Workshop on Theory and Formal Methods, London, UK, pp. 126-147. , Burn, G., Gay, D., Ryan, M. (eds.) Springer
- Goguen, J.A., Burstall, R.M., Institutions: Abstract model theory for specification and programming (1992) Journal of the ACM, 39 (1), pp. 95-146
- Tarlecki, A., Moving between logical systems (1996) LNCS, 1130, pp. 478-502. , Haveraaen, M., Owe, O., Dahl, O.J. (eds.) Abstract Data Types 1995 and COMPASS 1995. Springer, Heidelberg
- Sannella, D., Tarlecki, A., Specifications in an arbitrary institution (1988) Information and Computation, 76 (2-3), pp. 165-210
- Tarlecki, A., Abstract specification theory: An overview (2003) NATO Science Series, pp. 43-79. , Broy, M., Pizka, M. (eds.) Proceedings of the NATO Advanced Study Institute on Models, Algebras and Logic of Engineering Software, Marktoberdorf, Germany. IOS Press
- Mossakowski, T., Comorphism-based Grothendieck logics (2002) LNCS, 2420, pp. 593-604. , Diks, K., Rytter, W. (eds.) MFCS 2002. Springer, Heidelberg
- Mossakowski, T., Tarlecki, A., Heterogeneous logical environments for distributed specifications (2009) LNCS, 5486, pp. 266-289. , Corradini, A., Montanari, U. (eds.) WADT 2008. Springer, Heidelberg
- Diaconescu, R., Futatsugi, K., Logical foundations of CafeOBJ (2002) Theoretical Computer Science, 285 (2), pp. 289-318
- Diaconescu, R., Grothendieck institutions (2002) Applied Categorical Structures, 10 (4), pp. 383-402
- Diaconescu, R., Institution-independent Model Theory (2008) Studies in Universal Logic, 2. , Birkhäuser
- Mossakowski, T., Maeder, C., Lüttich, K., The heterogeneous tool set, HETS (2007) LNCS, 4424, pp. 519-522. , Grumberg, O., Huth, M. (eds.) TACAS 2007. Springer, Heidelberg
- Tarlecki, A., Towards heterogeneous specifications (2000) Studies in Logic and Computation, 2, pp. 337-360. , Gabbay, D., de Rijke, M. (eds.) Frontiers of Combining Systems. Research Studies Press
- Cengarle, M.V., Knapp, A., Tarlecki, A., Wirsing, M., A heterogeneous approach to UML semantics (2008) LNCS, 5065, pp. 383-402. , Degano, P., De Nicola, R., Meseguer, J. (eds.) Concurrency, Graphs and Models. Springer, Heidelberg
- Beth, E.W., (1959) The Foundations of Mathematics, , North Holland
- Beth, E.W., Semantic entailment and formal derivability (1969) The Philosophy of Mathematics, pp. 9-41. , Hintikka, J. (ed.) Oxford University Press reprinted from [34]
- Herbrand, J., Investigation in proof theory (1969) Logical Writings, pp. 44-202. , Goldfarb, W.D. (ed.) Harvard University Press translated to English from [35]
- Gentzen, G., Investigation into logical deduction (1969) The Collected Papers of Gerhard Gentzen, pp. 68-131. , Szabo, M.E. (ed.) North Holland translated to English from [36]
- Smullyan, R.M., (1995) First-order Logic, , Dover Publishing
- Robinson, J.A., A machine-oriented logic based on the resolution principle (1965) Journal of the ACM, 12 (1), pp. 23-41
- McLane, S., Categories for working mathematician (1971) Graduate Texts in Mathematics, , Springer, Berlin
- Fiadeiro, J.L., (2005) Categories for Software Engineering, , Springer
- Lopez Pombo, C.G., Castro, P., Aguirre, N.M., Maibaum, T.S.E., (2011) Satisfiability Calculus: The Semantic Counterpart of a Proof Calculus in General Logics, , Technical report, McMaster University, Centre for Software Certification
- Fitting, M., Tableau methods of proof for modal logics (1972) Notre Dame Journal of Formal Logic, 13 (2), pp. 237-247. , Lehman College
- Goguen, J.A., Rosu, G., Institution morphisms (2002) Formal Asp. Comput., 13 (3-5), pp. 274-307
- Castro, P.F., Aguirre, N.M., López Pombo, C.G., Maibaum, T.S.E., Towards managing dynamic reconfiguration of software systems in a categorical setting (2010) LNCS, 6255, pp. 306-321. , Cavalcanti, A., Deharbe, D., Gaudel, M.-C., Woodcock, J. (eds.) ICTAC 2010. Springer, Heidelberg
- Castro, P.F., Aguirre, N., López Pombo, C.G., Maibaum, T., A categorical approach to structuring and promoting Z specifications (2013) LNCS, 7684, pp. 73-91. , Pǎsǎreanu, C.S., Salaün, G. (eds.) FACS 2012. Springer, Heidelberg
- Blackburn, P., De Rijke, M., Venema, Y., Modal logic (2001) Cambridge Tracts in Theoretical Computer Science, 53. , Cambridge University Press
- Kozen, D., Kleene algebra with tests (1997) ACM Transactions on Programming Languages and Systems, 19 (3), pp. 427-443
- Clavel, M., Durán, F., Eker, S., Lincoln, P., Martí-Oliet, N., Meseguer, J., Talcott, C., All About Maude (2007) LNCS, 4350. , Springer, Heidelberg
- Jackson, D., Alloy: A lightweight object modelling notation (2002) ACM Transactions on Software Engineering and Methodology, 11 (2), pp. 256-290
- Moura, L.D., Bjørner, N., Satisfiability modulo theories: Introduction and applications (2011) Communications of the ACM, 54 (9), pp. 69-77
- Beth, E.W., Semantic entailment and formal derivability (1955) Mededlingen Van de Koninklijke Nederlandse Akademie Van Wetenschappen, Afdeling Letterkunde, 18 (13), pp. 309-342. , reprinted in [17]
- Herbrand, J., (1930) Recherches Sur la Theorie de la Demonstration, , PhD thesis, Université de Paris English translation in [18]
- Gentzen, G., Untersuchungen tiber das logische schliessen (1935) Mathematische Zeitschrijt, 39, pp. 176-210+405-431. , English translation in [19]A4 - Spanish Ministerio de Economia y Competitividad; IFIP TC1; Facultad de Informatica of Universidad Complutense de Madrid; Caja Espana-Duero Obra Social; Universidad de Salamanca; IMDEA Software Institute
Citas:
---------- APA ----------
Lopez Pombo, C.G., Castro, P.F., Aguirre, N.M. & Maibaum, T.S.E.
(2013)
. Satisfiability calculus: The semantic counterpart of a proof calculus in general logics. 21st International Workshop on Algebraic Development Techniques, WADT 2012, 7841 LNCS, 195-211.
http://dx.doi.org/10.1007/978-3-642-37635-1_12---------- CHICAGO ----------
Lopez Pombo, C.G., Castro, P.F., Aguirre, N.M., Maibaum, T.S.E.
"Satisfiability calculus: The semantic counterpart of a proof calculus in general logics"
. 21st International Workshop on Algebraic Development Techniques, WADT 2012 7841 LNCS
(2013) : 195-211.
http://dx.doi.org/10.1007/978-3-642-37635-1_12---------- MLA ----------
Lopez Pombo, C.G., Castro, P.F., Aguirre, N.M., Maibaum, T.S.E.
"Satisfiability calculus: The semantic counterpart of a proof calculus in general logics"
. 21st International Workshop on Algebraic Development Techniques, WADT 2012, vol. 7841 LNCS, 2013, pp. 195-211.
http://dx.doi.org/10.1007/978-3-642-37635-1_12---------- VANCOUVER ----------
Lopez Pombo, C.G., Castro, P.F., Aguirre, N.M., Maibaum, T.S.E. Satisfiability calculus: The semantic counterpart of a proof calculus in general logics. Lect. Notes Comput. Sci. 2013;7841 LNCS:195-211.
http://dx.doi.org/10.1007/978-3-642-37635-1_12