Time Warps, from Algebra to Algorithms

Van Gool, Samuel; Guatto, Adrien; Metcalfe, George; Santschi, Simon (2021). Time Warps, from Algebra to Algorithms. In: Fahrenberg, Uli; Gehrke, Mai; Santocanale, Luigi; Winter, Michael (eds.) Relational and Algebraic Methods in Computer Science. Lecture Notes in Computer Science: Vol. 13027 (pp. 309-324). Switzerland: Springer 10.1007/978-3-030-88701-8_19

Text GGMS21.pdf - Accepted Version Restricted to registered users only Available under License Publisher holds Copyright. Download (375kB) | Request a copy

Graded modalities have been proposed in recent work on programming languages as a general framework for re ning type systems with intensional properties. In particular, continuous endomaps of the discrete time scale, or time warps, can be used to quantify the growth of information in the course of program execution. Time warps form a complete residuated lattice, with the residuals playing an important role in potential programming applications. In this paper, we study the algebraic structure of time warps, and prove that their equational theory is decidable, a necessary condition for their use in real-world compilers. We also describe how our universal-algebraic proof technique lends itself to a constraint-based implementation, establishing a new link between universal algebra and veri cation technology.

Interest & Impact

Downloads

4 since deposited on 25 Oct 2021
1 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item