License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2010.103
URN: urn:nbn:de:0030-drops-26475
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2647/
Go to the corresponding LIPIcs Volume Portal

Fujita, Ken-Etsu ; Schubert, Aleksy

The Undecidability of Type Related Problems in Type-free Style System F

pdf-format:
10002.FujitaKen_Etsu.2647.pdf (0.2 MB)

Abstract

We consider here a number of variations on the System F, that are predicative second-order systems whose terms are intermediate between the Curry style and Church style. The terms here contain the information on where the universal quantifier elimination and introduction in the type inference process must take place, which is similar to Church forms. However, they omit the information on which types are involved in the rules, which is similar to Curry forms. In this paper we prove the undecidability of the type-checking, type inference and typability problems for the system. Moreover, the proof works for the predicative version of the system with finitely stratified polymorphic types. The result includes the bounds on the Leivant’s level numbers for types used in the instances leading to the undecidability.

BibTeX - Entry

@InProceedings{fujita_et_al:LIPIcs:2010:2647,
  author =	{Ken-Etsu Fujita and Aleksy Schubert},
  title =	{{The Undecidability of Type Related Problems in Type-free Style System F}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  pages =	{103--118},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Christopher Lynch},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2647},
  URN =		{urn:nbn:de:0030-drops-26475},
  doi =		{10.4230/LIPIcs.RTA.2010.103},
  annote =	{Keywords: Lambda calculus and related systems, type checking, typability, partial type inference, 2nd order unification, undecidability, Curry style type system}
}

Keywords: Lambda calculus and related systems, type checking, typability, partial type inference, 2nd order unification, undecidability, Curry style type system
Collection: Proceedings of the 21st International Conference on Rewriting Techniques and Applications
Issue Date: 2010
Date of publication: 06.07.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI