Artículo

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" (2013) 21st International Workshop on Algebraic Development Techniques, WADT 2012. 7841 LNCS:195-211
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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