Ramyaa, PURPLE (Pure Pointer Language) - some extensions
PURPLE (Pure Pointer Language) - some extensions
Many logspace algorithms are naturally described as programs that operate on a structured input (e.g. a graph), that store in memory only a constant number of pointers (e.g. to graph nodes). Algorithms that use pointers abstractly, without pointer arithmetic, (pure pointer algorithms) are useful for studying the nature of logspace-computation. The pure pointer language PURPLE was introduced by Hofmann and Schoepp to study such algorithms, and they showed that though the class of PURPLE programs was more powerful than existing pointer algorithms, it is strictly less than Logspace. In this talk, we present some extensions to PURPLE.