Subrecursive functions on partial sequences

DOI10.1007/S001530050122MaRDI QIDQ1306824zbMATH OpenOpenAlexFDO

Authors Karl-Heinz Niggl

Publication date 5 October 1999

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s001530050122

zbMATH Keywords

complexityfunction algebraGrzegorczyk classesGrzegorczyk hierarchyparallelismprimitive recursion over partial sequencesScott domains

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Semantics in the theory of computing (68Q55)

Review text

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.

Recommendations

• Subrecursive hierarchies on Scott domains
• A restricted computation model on Scott domains and its partial primitive recursive functionals
• scientific article; zbMATH DE number 873331

Cited in

(8)

• A restricted computation model on Scott domains and its partial primitive recursive functionals
• Non-definability of the Ackermann function with type 1 partial primitive recursion
• Subsequence summation and the m function
• scientific article; zbMATH DE number 4134024 (Why is no real title available?)
• Parallel functions in recursive program schemes
• scientific article; zbMATH DE number 3920456 (Why is no real title available?)
• scientific article; zbMATH DE number 1130215 (Why is no real title available?)
• scientific article; zbMATH DE number 873331 (Why is no real title available?)

This page was built for publication: Subrecursive functions on partial sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1306824)