RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2016 Volume 28, Issue 4, Pages 91–99 (Mi dm1395)

This article is cited in 2 papers

Bounded prefix concatenation operation and finite bases with respect to the superposition

S. S. Marchenkov

Lomonosov Moscow State University

Abstract: The paper is concerned with word functions over the alphabet $\{1,2\}$. Given arbitrary one-place functions $f_1,\ldots,f_l$, the class BPC$[f_1,\ldots,f_l]$ is defined as the closure of the set of simplest word functions and the functions $f_1,\ldots,f_l$ under the operations of superposition and bounded prefix concatenation. The class BPC$[f_1,\ldots,f_l]$ is shown to have a finite basis with respect to the superposition.

Keywords: operation of bounded prefix concatenation, finite basis with respect to the superposition.

UDC: 519.716

Received: 22.03.2016

DOI: 10.4213/dm1395


 English version:
Discrete Mathematics and Applications, 2017, 27:5, 303–309

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025