On the classification of Post automaton bases by the decidability of the A-completeness property for definite automata
Dmitriy N. Zhuk · Discrete Mathematics and Applications · 2010
We consider systems of the form M = F ∪ ν, where F is some Post class and ν 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.