We describe Wadge degrees of $\omega$-languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is ${\xi }^{\omega }$ where $\xi ={\omega }_1^{\mathrm{CK}}$ 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].

A multi-head 1-way pushdown automaton with $k$ heads is a pushdown automaton with $k$ 1-way read heads on the input tape and a stack. It was previously shown that the deterministic variant of the model cannot accept all the context free languages. In this paper, we introduce a 2-tape, 2-head model namely Watson-Crick pushdown automata where the content of the second tape is determined using a complementarity relation, similar to Watson-Crick automata. We show computational powers of nondeterministic...

We exhibit a new class of grammars with the help of weightfunctions. They are characterized by decreasing the weight during the derivation process. A decision algorithm for the emptiness problem is developed. This class contains non-contextfree grammars. The corresponding language class is identical to the class of ultralinear languages.

We exhibit a new class of grammars with the help of weightfunctions. They are characterized by decreasing the weight during the derivation process. A decision algorithm for the emptiness problem is developed. This class contains non-contextfree grammars. The corresponding language class is identical to the class of ultralinear languages.

Let I be a finite set of words and ${\Rightarrow }_I^{*}$ be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let $L_I^{ϵ}$ be the set of words u such that $ϵ{\Rightarrow }_I^{*}u$. We prove that the set I is unavoidable if and only if the relation ${\Rightarrow }_I^{*}$ is a well quasi-order on the set $L_I^{ϵ}$. This result generalizes a theorem of [Ehrenfeucht et al.,Theor. Comput. Sci.27 (1983) 311–332]. Further generalizations are investigated.