Article collection "Mathematical Problems of Cybernetics" №1, Moscow, 1988
Authors:Vetrennikova E.V.
Construction of the simplest universal bounded-deterministic function
Abstract:
In the present article we consider the issues of completeness for functions that are computed by finite automata, also known as bounded-deterministic functions. The systems, that consist of a single function are an important class of complete bounded-deterministic functions systems. Such bounded-deterministic functions are known as universal. We construct an example of the simplest universal bounded-deterministic function, whose input and output values belong to a finite set: 0,1,...,k-1 (k ≥2).
Keywords:
bounded-deterministic function, finite automaton, complete function systems