This article is cited in 6 papers

On elementary word functions obtained by bounded prefix concatenation

Sergey S. Marchenkov

Moscow State University

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.

Keywords: bounded prefix concatenation, polynomially computable function.

UDC: 519.716

Received: 14.04.2015

DOI: 10.4213/dm1334

 English version: Discrete Mathematics and Applications, 2016, 26:3, 155–163

Bibliographic databases:

• 
• 
• 
•