The Inhabitation Problem for Rank Two Intersection Types

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We prove that the inhabitation problem for rank two intersection types is decidable, but (contrary to common belief) EXPTIME-hard. The exponential time hardness is shown by reduction from the in-place acceptance problem for alternating Turing machines.
15 pages

Keywords

Logic in Computer Science

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/121214

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0701029
 http://arxiv.org/abs/cs/0701029

Collections

arXiv