FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

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

On the classification of bases in $P$_k according to the decidability of the completeness problem for automata

D. N. Babin

Abstract

View as HTML     View as gif image

The completeness problem for bases of the form $$F È n, where $$F Í P_k 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] = P_k. The article is concerned with the case where $[$F] is the maximal (precomplete) class in $P$_k. 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 $P$_k, $k$³ 3, can be classified according to their ability to guarantee the decidability of the completeness problem for automaton functions.

Location: http://mech.math.msu.su/~fpm/eng/k09/k093/k09305h.htm
Last modified: January 13, 2010