This article is cited in 1 paper

On completeness and $A$-completeness of $S$-sets of determinate functions containing all one-place determinate $S$-functions

M. A. Podkolzina


Abstract: We consider the problem on completeness of sets of $S$-functions, the determinate functions such that the automaton calculating them realises in each state functions which emanate no value. We assume that each set of $S$-functions whose completeness is checked in this paper contains all $S$-functions depending on at most one variable. We describe all $A$-precomplete classes of such sets. It is shown that there exists an algorithm recognising $A$-completeness of $S$-sets of one-place determinate functions containing all one-place determinate $S$-functions.

UDC: 519.7

Received: 17.09.2008

DOI: 10.4213/dm1047

 English version: Discrete Mathematics and Applications, 2009, 19:3, 263–276

Bibliographic databases:

• 
• 
•