Up-to techniques using sized types Article Swipe

PDF

Related Concepts

mathematical proof class (philosophy) computer science construct (python library) theoretical computer science order (exchange) algorithm mathematics programming language artificial intelligence geometry economics finance

Nils Anders Danielsson ·

YOU? · · 2017 · Open Access · · DOI: https://doi.org/10.1145/3158131 · OA: W2777036761

Up-to techniques are used to make it easier—or feasible—to construct, for instance, proofs of bisimilarity. This text shows how many up-to techniques can be framed as size-preserving functions , using sized types to keep track of sizes. Through a number of examples it is argued that this approach to up-to techniques is often convenient to use in practice. Some examples of functions that cannot be made size-preserving are also included, in order to illustrate the limits of the approach. On the more theoretical side a class of up-to techniques intended to capture a natural mode of use of size-preserving functions is defined. This class turns out to correspond closely to "functions below the companion", a notion recently introduced by Pous.