License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2023.15
URN: urn:nbn:de:0030-drops-179993
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17999/
Go to the corresponding LIPIcs Volume Portal

Kop, Cynthia ; Vale, Deivid

Cost-Size Semantics for Call-By-Value Higher-Order Rewriting

pdf-format:
LIPIcs-FSCD-2023-15.pdf (0.8 MB)

Abstract

Higher-order rewriting is a framework in which higher-order programs can be described by transformation rules on expressions. A computation occurs by transforming an expression into another using such rules. This step-by-step computation model induced by rewriting naturally gives rise to a notion of complexity as the number of steps needed to reduce expressions to a normal form, i.e., an expression that cannot be reduced further. The study of complexity analysis focuses on the development of automatable techniques to provide bounds to this number. In this paper, we consider a form of higher-order rewriting with a call-by-value evaluation strategy, so as to model call-by-value programs. We provide a cost-size semantics: a class of algebraic interpretations to map terms to tuples which bound both the reduction cost and the size of normal forms.

BibTeX - Entry

@InProceedings{kop_et_al:LIPIcs.FSCD.2023.15,
  author =	{Kop, Cynthia and Vale, Deivid},
  title =	{{Cost-Size Semantics for Call-By-Value Higher-Order Rewriting}},
  booktitle =	{8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)},
  pages =	{15:1--15:19},
  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/opus/volltexte/2023/17999},
  URN =		{urn:nbn:de:0030-drops-179993},
  doi =		{10.4230/LIPIcs.FSCD.2023.15},
  annote =	{Keywords: Call-by-Value Evaluation, Complexity Theory, Higher-Order Rewriting}
}

Keywords: Call-by-Value Evaluation, Complexity Theory, Higher-Order Rewriting
Collection: 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)
Issue Date: 2023
Date of publication: 28.06.2023

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