2009, VOLUME 15, NUMBER 3, PAGES 33-47

On the classification of bases in Pk 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 F È n, where F Í Pk and n is a finite system of automaton functions, is considered. Previously, the problem for k=2 was solved by the author; it was also shown that there is an algorithm for determining the completeness of the system F È n when [F] = Pk. The article is concerned with the case where [F] is the maximal (precomplete) class in Pk. The problem of completeness for systems F È n is shown to be undecidable if F is embedded in a Slupecki class and algorithmically decidable if F contains the preserving class of all constants. Thus, the bases in Pk, k ³ 3, can be classified according to their ability to guarantee the decidability of the completeness problem for automaton functions.

Main page Contents of the journal News Search

Last modified: January 13, 2010