EuDML | Browse

Page 1

Displaying 1 – 3 of 3

Finite alogorithmic procedures and inductive definability.

J. Moldestad, V. Stoltenberg-Hansen (1980)

Mathematica Scandinavica

Finite models and finitely many variables

Anuj Dawar (1999)

Banach Center Publications

This paper is a survey of results on finite variable logics in finite model theory. It focusses on the common underlying techniques that unite many such results.

Function operators spanning the arithmetical and the polynomial hierarchy

Armin Hemmerling (2010)

RAIRO - Theoretical Informatics and Applications

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 and complexity theory....

Displaying 1 – 3 of 3

Finite alogorithmic procedures and inductive definability.

Finite models and finitely many variables

Function operators spanning the arithmetical and the polynomial hierarchy

Currently displaying 1 – 3 of 3