Artículo

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:

The Propositional Logic of Proofs (LP) is a modal logic in which the modality □A is revisited as [[t]]A, t being an expression that bears witness to the validity of A. It enjoys arithmetical soundness and completeness, can realize all S4 theorems and is capable of reflecting its own proofs (⊢A implies ⊢[[t]]A, for some t). A presentation of first-order LP has recently been proposed, FOLP, which enjoys arithmetical soundness and has an exact provability semantics. A key notion in this presentation is how free variables are dealt with in a formula of the form [[t]]A(i). We revisit this notion in the setting of a Natural Deduction presentation and propose a Curry-Howard correspondence for FOLP. A term assignment is provided and a proof of strong normalization is given. © The Author, 2016.

Registro:

Documento: Artículo
Título:The first-order hypothetical logic of proofs
Autor:Steren, G.; Bonelli, E.
Filiación:Depto. de Computación, FCEyN, UBA, Argentina
Depto. de Ciencia y Tecnología, UNQ, Argentina
CONICET, Argentina
Palabras clave:Curry howard isomorphism; First-order logic of proofs; Lambda calculus; Natural deduction; Calculations; Computer circuits; Differentiation (calculus); Semantics; Curry-Howard correspondence; Curry-Howard isomorphism; First order logic; Lambda calculus; Natural deduction; Provability semantics; Soundness and completeness; Strong normalization; Formal logic
Año:2017
Volumen:27
Número:4
Página de inicio:1023
Página de fin:1066
DOI: http://dx.doi.org/10.1093/logcom/exv090
Título revista:Journal of Logic and Computation
Título revista abreviado:J Logic Comput
ISSN:0955792X
CODEN:JLCOE
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0955792X_v27_n4_p1023_Steren

Referencias:

  • Artëmov, S.N., Explicit provability and constructive semantics (2001) Bulletin of Symbolic Logic, 7, pp. 1-36
  • Artemov, S., Justification logic (2008) Logics in Artificial Intelligence, Vol. 5293 of Lecture Notes in Computer Science, pp. 1-4. , S. Hlldobler, C. Lutz and H. Wansing, eds, Springer
  • Artëmov, S.N., (1995) Operational Modal Logic, , Technical Report, Cornell University
  • Artëmov, S.N., The logic of justification (2008) The Review of Symbolic Logic, 1, pp. 477-513
  • Artëmov, S.N., Bonelli, E., The intensional lambda calculus (2007) LFCS, pp. 12-25. , Springer
  • Abadi, M., Fournet, C., Access control based on execution history (2003) Proceedings of the 10th Annual Network and Distributed System Security Symposium, pp. 107-121. , The Internet Society
  • Artëmov, S.N., Iemhoff, R., The basic intuitionistic logic of proofs (2007) Journal of Symbolic Logic, 72, pp. 439-451
  • Artëmov, S.N., Yavorskaya, T., On first order logic of proofs (2001) Moscow Mathematical Journal, 1, pp. 475-490. , (Sidon)
  • Artëmov, S.N., Yavorskaya, T., (2011) First-order Logic of Proofs, , (Sidon). Technical Report TR-2011005, CUNY Ph.D. Program in Computer Science
  • Bavera, F., Bonelli, E., Justification logic and history based computation (2010) ICTAC, pp. 337-351. , Springer
  • Bavera, F., Bonelli, E., Justification logic and audited computation (2015) Journal of Logic and Computation
  • Banerjee, A., Naumann, D.A., History-based access control and secure information flow (2005) Construction and Analysis of Safe, Secure, and Interoperable Smart Devices, International Workshop (CASSIS 2004), Revised Selected Papers, Vol. 3362 of Lecture Notes in Computer Science, pp. 27-48. , Springer
  • Bonelli, E., Feller, F., Justification logic as a foundation for certifying mobile computation (2012) Annals of Pure and Applied Logic, 163, pp. 935-950
  • Bonelli, E., Steren, G., Hypothetical logic of proofs (2014) Logica Universalis, 8, pp. 103-140
  • Blackburn, P., Van Benthem, J., Modal logic: A semantic perspective (2006) Handbook of Modal Logic, 3, pp. 1-84
  • Dashkov, E., Arithmetical completeness of the intuitionistic logic of proofs (2011) Journal of Logic and Computation, 21, pp. 665-682
  • Davies, R., Pfenning, F., Ajudgmental reconstruction of modal logic (2001) Mathematical Structures in Computer Science, 11, pp. 511-540
  • Davies, R., Pfenning, F., A modal analysis of staged computation (1996) POPL, pp. 258-270
  • Davies, R., Pfenning, F., A modal analysis of staged computation (2001) Journal of ACM, 48, pp. 555-604
  • Dijkstra, E.W., (1976) A Discipline of Programming, 4. , Prentice-Hall Englewood Cliffs
  • Fitting, M., Possible world semantics for first-order logic of proofs (2014) Annals of Pure and Applied Logic, 165, pp. 225-240
  • Geuvers, H., Jojgov, G.I., Open proofs and open terms: A basis for interactive logic (2002) Computer Science Logic, 16th International Workshop, CSL 2002, 11th Annual Conference of the EACSL, pp. 537-552. , Edinburgh, Scotland, UK, September 22-25, 2002, Proceedings, Vol. 2471 of Lecture Notes in Computer Science, J. C. Bradfield, ed., Springer
  • Gödel, K., Eine interpretation des intuitionistischen aussagenkalküls (1933) Ergebnisse Eines Mathematischen Kolloquiums, 4, pp. 39-40
  • Jia, L., Walker, D., Modal proofs as distributed programs (2004) Programming Languages and Systems, Vol. 2986 of Lecture Notes in Computer Science, pp. 219-233. , D. Schmidt, ed., Springer
  • Kramer, S., (2012) A Logic of Interactive Proofs (Formal Theory of Knowledge Transfer), , arXiv preprint arXiv:1201.3667
  • Kramer, S., Logic of negation-complete interactive proofs (formal theory of epistemic deciders) (2014) Electronic Notes in Theoretical Computer Science, 300, pp. 47-70
  • Lévy, J.-J., (1978) Réductions Correctes et Optimales dans le Lambda-calcul, , PhD Thesis, Paris 7
  • Martin-Löf, P., (1984) An Intuitionistic Theory of Types, , Bibliopolis
  • Martini, S., Masini, A., A computational interpretation of modal proofs (1996) Proof Theory of Modal Logic, pp. 213-241. , H. Wansing, ed., Springer
  • Moody, J., Logical mobility and locality types (2005) Logic Based Program Synthesis and Transformation, Vol. 3573 of Lecture Notes in Computer Science, pp. 69-84. , S. Etalle, ed., Springer
  • Moody, J., (2003) Modal Logic As A Basis for Distributed Computation, , Technical Report, Carnegie Mellon University
  • Miller, D., Tiu, A., Aproof theory for generic judgments (2005) ACM Transactions on Computational Logic, 6, pp. 749-783
  • Murphy, T., Crary, K., Harper, R., Pfenning, F., A symmetric modal lambda calculus for distributed computing (2004) Logic in Computer Science, 2004. Proceedings of the 19th Annual IEEE Symposium on, pp. 286-295. , IEEE
  • McKinsey, J.C.C., Tarski, A., Some theorems about the sentential calculi of lewis and heyting (1948) The Journal of Symbolic Logic, 13, pp. 1-15
  • Nanevski, A., Pfenning, F., Pientka, B., Contextual modal type theory (2008) ACM Transactions on Computational Logic, 9, pp. 1-49
  • Orlov, I.E., The logic of compatibility of propositions (1925) Matematicheskii Sbornik, 35, pp. 263-286
  • Parigot, M., λμ-calculus: An algorithmic interpretation of classical natural deduction (1992) Logic Programming and Automated Reasoning, Vol. 624 of Lecture Notes in Computer Science, pp. 190-201. , A. Voronkov, ed., Springer
  • Parigot, M., Proofs of strong normalisation for second order classical natural deduction (1997) The Journal of Symbolic Logic, 62, pp. 1461-1479
  • Pfenning, F., Wong, H.-C., On a modal λ-calculus for s4 (1995) Electronic Notes in Theoretical Computer Science, 1, pp. 515-534
  • Pientka, B., Beluga: Programming with dependent types, contextual data, and contexts (2010) Functional and Logic Programming, pp. 1-12. , M. Blume, N. Kobayashi and G. Vidal, eds, Springer
  • Rangan, P.V., An axiomatic basis of trust in distributed systems (1988) Security and Privacy, 1988. Proceedings, 1988 IEEE Symposium on, pp. 204-211. , IEEE
  • Saurin, A., On the relations between the syntactic theories of lambda-mu-calculi (2008) Computer Science Logic, 22nd International Workshop, CSL 2008, 17th Annual Conference of the EACSL, 5213, pp. 154-168. , Bertinoro, Italy, September 16-19, 2008. Proceedings, of Lecture Notes in Computer Science, M. Kaminski and S. Martini, eds, Springer
  • Saurin, A., Typing streams in the λμ-calculus (2010) ACM Transactions on Computational Logic (TOCL), 11, p. 28
  • Solovay, R.M., Provability interpretations of modal logic (1976) Israel Journal of Mathematics, 25, pp. 287-304
  • Sørensen, M.H., Urzyczyn, P., (2006) Lectures on the Curry-Howard Isomorphism, Vol. 149 of Studies in Logic and the Foundations of Mathematics, , Elsevier Science
  • Yavorsky, R.E., On arithmetical completeness of first-order logics of provability (2000) Advances in Modal Logic 3, Papers from the Third Conference on 'Advances in Modal Logic', Held in Leipzig (Germany) in October 2000, pp. 1-16. , F. Wolter, H. Wansing, M. de Rijke and M. Zakharyaschev, eds, World Scientific
  • Yavorsky, R.E., Provability logics with quantifiers on proofs (2001) Annals of Pure and Applied Logic, 113, pp. 373-387

Citas:

---------- APA ----------
Steren, G. & Bonelli, E. (2017) . The first-order hypothetical logic of proofs. Journal of Logic and Computation, 27(4), 1023-1066.
http://dx.doi.org/10.1093/logcom/exv090
---------- CHICAGO ----------
Steren, G., Bonelli, E. "The first-order hypothetical logic of proofs" . Journal of Logic and Computation 27, no. 4 (2017) : 1023-1066.
http://dx.doi.org/10.1093/logcom/exv090
---------- MLA ----------
Steren, G., Bonelli, E. "The first-order hypothetical logic of proofs" . Journal of Logic and Computation, vol. 27, no. 4, 2017, pp. 1023-1066.
http://dx.doi.org/10.1093/logcom/exv090
---------- VANCOUVER ----------
Steren, G., Bonelli, E. The first-order hypothetical logic of proofs. J Logic Comput. 2017;27(4):1023-1066.
http://dx.doi.org/10.1093/logcom/exv090