Abstract:
We consider systems of the form $M=F\cup\nu$, where $F$ is some Post class and $\nu$ is a finite system of definite automata. We divide the Post classes into those for which the problem of $A$-completeness of such systems of definite automata is algorithmically decidable and those for which the problem of $A$-completeness is algorithmically undecidable.