ISR 2024 – Track C
About Randomized Programming and Rewriting
Lecturer
Course Description
Rewriting can be seen as an abstraction of the computational process in which the underlying configuration evolves through the process of substitution of expressions by expressions. As such, rewriting allows you to capture the fundamental concepts of program and algorithm. The latter, however, does not always enjoy a crucial property usually taken for granted, namely that of being deterministic. Indeed, many modern algorithms essentially rely on the availability of true randomness. How could one nicely express randomized algorithms? Would it be possible to capture this new computing paradigm in rewriting? What impact does all this have on the underlying theory? This course aims to provide an introduction to randomized computation, programming and rewriting, while answering the questions above.