PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 45 | 1 |
Tytuł artykułu

Elementary Proof of Strong Normalization for Atomic F

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We give an elementary proof (in the sense that it is formalizable in Peano arithmetic) of the strong normalization of the atomic polymorphic calculus Fat (a predicative restriction of Girard’s system F).
Rocznik
Tom
45
Numer
1
Opis fizyczny
Daty
wydano
2016-03-30
Twórcy
  • Universidade de Lisboa, Faculdade de Ciências, Departamento de Matemática
  • Universidade Lusófona de Humanidades e Tecnologias, Departamento de Matemática
Bibliografia
  • [1] T. Altenkirch and T. Coquand, A finitary subsystem of the polymorphic λ-calculus, Proceedings of the 5th International Conference on Typed Lambda Calculi and Applications (TLCA 2001), Lecture Notes in Computer Science 2044 (2001), pp. 22–28.
  • A. Beckmann, Exact bounds for lenghts of reductions in typed λ-calculus, The Journal of Symbolic Logic 66(3) (2001), pp. 1277–1285.
  • F. Ferreira, A simple proof of Parsons’ theorem, Notre Dame Journal of Formal Logic 46 (2005), pp. 83–91.
  • F. Ferreira, Comments on predicative logic, Journal of Philosophical Logic 35 (2006), pp. 1–8.
  • F. Ferreira and G. Ferreira, Atomic polymorphism, The Journal of Symbolic Logic 78 (2013), pp. 260–274.
  • F. Ferreira and G. Ferreira, The faithfulness of Fat : a proof-theoretic proof, Studia Logica 103(6) (2015), pp. 1303–1311.
  • J.-Y. Girard, Y. Lafont and P. Taylor, Proofs and Types, Cambridge University Press (1989).
  • F. Joachimski and R. Matthes, Short proofs of normalization for the simplytyped lambda-calculus, permutative conversions and Gödel’s T, Archive for Mathematical Logic 42 (2003), pp. 59–87.
  • H. Schwichtenberg, An upper bound for reduction sequences in the typed λ-calculus, Archive for Mathematical Logic 30 (1991), pp. 405–408.
  • W. Tait, Intentional interpretations of functionals of finite type I, The Journal of Symbolic Logic 32 (1967), pp. 198–212.
  • W. Tait, Finitism, Journal of Philosophy 78 (1981), pp. 524–546.
  • A. S. Troelstra and H. Schwichtenberg, Basic Proof Theory, Cambridge University Press (1996).
  • A. S. Troelstra and D. van Dalen, Constructivism in Mathematics. An Introduction, volume 1, North Holland, Amsterdam (1988).
  • J. van de Pol, Two different strong normalization proofs? Computability versus functionals of finite type, Proceedings of the Second International Workshop on Higher-Order Algebra, Logic and Term Rewriting (HOA’95), Lecture Notes in Computer Science 1074 (1996), pp. 201–220.
  • F. van Raamsdonk and P. Severi, On normalization, Technical report CSR9545, Centrum voor Wiskunde en Informatica, Amsterdam (1995).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ojs-doi-10_18778_0138-0680_45_1_01
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.