1 Search Results for "Pautasso, Daniele"

Document
DOI: 10.4230/LIPIcs.FSCD.2023.29
A Quantitative Version of Simple Types

Authors: Daniele Pautasso and Simona Ronchi Della Rocca

Published in: LIPIcs, Volume 260, 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)

Abstract
This work introduces a quantitative version of the simple type assignment system, starting from a suitable restriction of non-idempotent intersection types. The resulting system is decidable and has the same typability power as the simple type system; thus, assigning types to terms supplies the very same qualitative information given by simple types, but at the same time can provide some interesting quantitative information. It is well known that typability for simple types is equivalent to unification; we prove a similar result for the newly introduced system. More precisely, we show that typability is equivalent to a unification problem which is a non-trivial extension of the classical one: in addition to unification rules, our typing algorithm makes use of an expansion operation that increases the cardinality of multisets whenever needed.
Cite as

Daniele Pautasso and Simona Ronchi Della Rocca. A Quantitative Version of Simple Types. In 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 260, pp. 29:1-29:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{pautasso_et_al:LIPIcs.FSCD.2023.29,
  author =	{Pautasso, Daniele and Ronchi Della Rocca, Simona},
  title =	{{A Quantitative Version of Simple Types}},
  booktitle =	{8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)},
  pages =	{29:1--29:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-277-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{260},
  editor =	{Gaboardi, Marco and van Raamsdonk, Femke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2023.29},
  URN =		{urn:nbn:de:0030-drops-180137},
  doi =		{10.4230/LIPIcs.FSCD.2023.29},
  annote =	{Keywords: \lambda-calculus, intersection types, unification}
}
  • Refine by Author
  • 1 Pautasso, Daniele
  • 1 Ronchi Della Rocca, Simona

  • Refine by Classification
  • 1 Theory of computation → Logic

  • Refine by Keyword
  • 1 intersection types
  • 1 unification
  • 1 λ-calculus

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact