Displaying similar documents to “Polynomial time bounded truth-table reducibilities to padded sets”

Function operators spanning the arithmetical and the polynomial hierarchy

Armin Hemmerling (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

A modified version of the classical -operator as well as the first value operator and the operator of inverting unary functions, applied in combination with the composition of functions and starting from the primitive recursive functions, generate all arithmetically representable functions. Moreover, the nesting levels of these operators are closely related to the stratification of the arithmetical hierarchy. The same is shown for some further function operators known from computability...