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