Ramyaa: Implicit Complexity for Corecursive functions

Implicit Complexity for Corecursive functions

Implicit complexity gives machine independent characterizations of complexity classes. These characterizations are based on "natural" principles involving restrictions of logic or programing schemes. This makes it easy to adapt these characterizations to new machine models, or data types. This talk introduces ramification - a principle which has been successful in capturing complexity classes for inductive data, such as PTIME - and explains how it can be adapted to characterize complexity classes for coinductive data.

Coinduction is the dual of induction, and though corecursive functions have been studied, complexity classes for these functions have not been studied. So, the characterizations obtained using implicit complexity techniques will add to the credence of any proposed candidate for complexity classes.