Functional aspects of the completeness problem for some classes of automaton functions

S. S. Marchenkov

Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 103-117

Résumé

For a closed class $Q$ of Boolean functions, $\mathcal A(Q)$ denotes the closed class of all finite-automaton functions computable by finite automata which realise a function of $Q$ in each state. It is shown that if $Q_1$, $Q_2$ are closed classes of Boolean functions, $O_1\subseteq Q_1\subset Q_2$, then the family of classes which are precomplete in $\mathcal A(Q_2)$ and contain the class $\mathcal A(Q_1)$ is of the continuum cardinality. We denote by $\mathbf C_\varphi$ the set of all functions which are defined and uniformly continuous on the Baire space $E_2^\infty$ with the modulus of continuity $\varphi$. It is established that if a closed class of functions continuous on $E_2^\infty$ can be represented in the form of a countable union of the classes $\mathbf C_{\varphi_i}$, where $\varphi_1(t)=2t$, then the family of Słupecki classes in it is of the hypercontinuum cardinality. The research was supported by the Russian Foundation for Basic Research, grant 97–01–00989.