EuDML | Browse

We investigate automatic presentations of ω-words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of ω-words enjoying the above...

A hierarchy of primitive recursive sequence functions

E. Fachini, A. Maggiolo-Schettini (1979)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A Turing machine oracle hierarchy. I.

Stanislav Žák (1980)

Commentationes Mathematicae Universitatis Carolinae

A Turing machine oracle hierarchy. II.

Stanislav Žák (1980)

Commentationes Mathematicae Universitatis Carolinae

Analytic determinacy and 0# A forcing-free proof of Harrington’s theorem

Ramez Sami (1999)

Fundamenta Mathematicae

We prove the following theorem: Given a⊆ω and $1 \leq α < ω_{1}^{C K}$ , if for some $η < ℵ_{1}$ and all u ∈ WO of length η, a is $Σ_{α}^{0} (u)$ , then a is $Σ_{α}^{0}$ . We use this result to give a new, forcing-free, proof of Leo Harrington’s theorem: $Σ_{1}^{1}$ -Turing-determinacy implies the existence of $0$ .

Arithmetical classification of the set of all provably recursive functions

Vítězslav Švejdar (1999)

Commentationes Mathematicae Universitatis Carolinae

The set of all indices of all functions provably recursive in any reasonable theory $T$ is shown to be recursively isomorphic to $U \times \bar{U}$ , where $U$ is $Π_{2}$ -complete set.

Displaying 1 – 14 of 14

A characterization of determinacy for Turing degree games

A Characterization of the Veblen-Schütte Functions by Means of Functionals

A classification of the ordinal recursive functions.

A conjecture of Ershov for a relative hierarchy fails near $𝒪$ .

A generalized Feiner hierarchy.

A Hierarchy of Automatic ω-Words having a Decidable MSO Theory

A hierarchy of primitive recursive sequence functions

A Turing machine oracle hierarchy. I.

A Turing machine oracle hierarchy. II.

Analytic determinacy and 0# A forcing-free proof of Harrington’s theorem

Arithmetical classification of the set of all provably recursive functions

Automatic listing of important observational statements. I

Automatic listing of important observational statements. II

Automatic listing of important observational statements. III

Currently displaying 1 – 14 of 14