Degrees of automata transformations
Degrees of automata transformations
Using the logical framework of \textit{G. Rejna} [Degrees of automata transformations (Russian) (Moscow, 1977)] and results of H. G. Gordon on complete degrees of finite-state transformability as points of entry, the author proves several category-theoretic results on complete degrees analogous to various results by J. Myhill and by H. Rogers on category methods in recursion theory. Some proofs make good use of Zorn's lemma in effective computability.
category methods in recursion theory, Other degrees and reducibilities in computability and recursion theory, Formal languages and automata, Automata and formal grammars in connection with logical questions, Abstract and axiomatic computability and recursion theory, complete degrees
category methods in recursion theory, Other degrees and reducibilities in computability and recursion theory, Formal languages and automata, Automata and formal grammars in connection with logical questions, Abstract and axiomatic computability and recursion theory, complete degrees