The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
We describe Wadge degrees of -languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is where is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
We describe Wadge degrees of ω-languages recognizable by
deterministic Turing machines. In particular, it is shown that the
ordinal corresponding to these degrees is ξω where
ξ = ω1CK is the first non-recursive ordinal known as the
Church–Kleene ordinal. This answers a question raised in [2].
We prove that there exists a structure M whose monadic second order theory is decidable, and such that the first-order theory of every expansion of M by a constant is undecidable.
Currently displaying 1 –
3 of
3