Former work by Danner et al. [2015] has formalized a method of extracting recurrences that bound the complexity of higher-order programs. However, these bounds do not offer useful information about the costs of all programs - in particular, programs with stochastic processes. Karp [1994] defines several forms of recurrences describing the cost of probabilistic algorithms; we develop languages which allow us to express recurrences of these forms. We also offer denotational semantics for these languages, and demonstrate using example recurrences given by Karp that the denotation of a recurrence is equal to its solution. These languages and denotational semantics may be tied in to the framework developed by Danner et al. to offer more useful bounds on a wider array of programs.
"},{"label":"Degree","value":["Bachelor of Arts with Departmental Honors"]},{"label":"Administrative Note","value":"2018