I PRIKLADNAYA MATEMATIKA
(FUNDAMENTAL AND APPLIED MATHEMATICS)
2009, VOLUME 15, NUMBER 3, PAGES 33-47
On the classification of bases in
according to the decidability
of the completeness problem for automata
D. N. Babin
View as HTML
View as gif image
The completeness problem for bases of the form , where and
is a finite
system of automaton functions, is considered.
Previously, the problem for was solved by the
author; it was also shown that there is an algorithm for determining
the completeness of the system when .
The article is concerned with the case where is the maximal (precomplete) class
The problem of completeness for systems is shown to be
undecidable if is embedded in
a Slupecki class and algorithmically decidable if contains the
preserving class of all constants.
Thus, the bases in , , can be classified according to their ability
to guarantee the decidability of the completeness problem for
Last modified: January 13, 2010