EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Multi types and reasonable space

Beniamino Accattoli, Ugo Dal Lago, Gabriele Vanoni

Journal of Functional Programming · 14.08.2026 · Volume 36

DOI: 10.46298/jfp.17809 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Functional Programming, online erschienen am 14.08.2026. Verfasst von Beniamino Accattoli und 2 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Accattoli, Dal Lago, and Vanoni have recently proved that the space used by the Space KAM, a variant of the Krivine abstract machine, is a reasonable space cost model for the lambda-calculus accounting for logarithmic space, solving a longstanding open problem. In this paper, we provide a new system of multi types (a variant of intersection types) and extract from multi type derivations the space used by the Space KAM, capturing into a type system the space complexity of the abstract machine. Additionally, we show how to capture also the time of the Space KAM, which is a reasonable time cost model, via minor changes to the type system.

Zitieren

APA

Accattoli, B., Lago, U. D., & Vanoni, G. (2026). Multi types and reasonable space. Journal of Functional Programming, Volume 36. https://doi.org/10.46298/jfp.17809

Vancouver

Accattoli B, Lago UD, Vanoni G. Multi types and reasonable space. Journal of Functional Programming. 2026;Volume 36. doi:10.46298/jfp.17809

BibTeX
@article{Accattoli2026,
  author = {Accattoli, Beniamino and Lago, Ugo Dal and Vanoni, Gabriele},
  title = {Multi types and reasonable space},
  journal = {Journal of Functional Programming},
  year = {2026},
  volume = {Volume 36},
  doi = {10.46298/jfp.17809}
}
Kostenlos starten →