Subrecursive functions on partial sequences (Q1306824)

The paper studies a domain-theoretical notion of primitive recursion over partial sequences in the context of Scott domains. Based on a nonmonotonic coding of partial sequences, this notion supports the concept of parallelism in the sense of Plotkin. The complexity of these functions is analyzed similar to the Grzegorczyk classes (generalizing results by Schwichtenberg/Müller and Niggl). The functions considered are characterized by a function algebra generated by continuity preserving operations starting from countable initial functions.