On the decidability of the completeness problem for special systems of automata functions

We consider systems of automaton functions of the form $M = \Phi \cup \nu $, where $ \Phi $ is a Post class and $\nu$ is a finite system of automaton functions. We prove that if $ \Phi \in\{ M,D,C,F^2\}$, then the completeness and $A$-completeness problems for the system $M$ are algorithmically decidable.
The work was supported by the Russian Foundation for Basic Research, Grant 95-01-01102.