Bi-immunity over different size alphabets

Autor:	Ludwig Staiger, Ziyuan Gao, Frank Stephan, Sanjay Jain, Karen Frilya Celine, Cristian S. Calude
Rok vydání:	2021
Předmět:	Discrete mathematics General Computer Science Bounded function Recursive functions Natural number Alphabet Constant (mathematics) Turing computer Computer Science::Formal Languages and Automata Theory Theoretical Computer Science computer.programming_language Mathematics
Zdroj:	Theoretical Computer Science. 894:31-49
ISSN:	0304-3975
Popis:	In this paper we study various notions of bi-immunity over alphabets with b ≥ 2 elements and recursive transformations between sequences on different alphabets which preserve them. Furthermore, we extend the study from sequences bounded by a constant to sequences over the alphabet of all natural numbers, which may or may not be bounded by a recursive function, and relate them to the Turing degrees in which they can occur.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::1e35f85bb2a94ea386ad5a17fe16e4b1 https://doi.org/10.1016/j.tcs.2021.09.005 Zobrazit plný text záznamu Full Text from ScienceDirect