On elementary word functions obtained by bounded prefix concatenation
Sergey Seraphimovich Marchenkov · Discrete Mathematics and Applications · 2016
Abstract The operation of bounded prefix concatenation (BPC) is introduced on the set of word functions in the alphabet {1, 2}. The class BPC of polynomially computable functions is defined on the basis of this operation and the superposition operation. The class BPC is shown to contain a number of word functions and to be closed with respect to certain known operations. A certain type of two-tape nonerasing Turing machines is introduced, functions from the class BPC are shown to be computable on machines of this type in polynomial time.