Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits

The problem of complexity of word assembly is studied. The complexity of a word means the minimal number of concatenation operations sufficient to obtain this word in the basis of oneletter words over a finite alphabet A ( repeated use of obtained words is permitted). Let LA ( n ) be the maximal com...

Full description

Saved in:
Bibliographic Details
Published in:Moscow University mathematics bulletin 2016-03, Vol.71 (2), p.55-60
Main Authors: Kochergin, V. V., Kochergin, D. V.
Format: Article
Language:English
Subjects:
Analysis
Mathematics
Mathematics and Statistics
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem of complexity of word assembly is studied. The complexity of a word means the minimal number of concatenation operations sufficient to obtain this word in the basis of oneletter words over a finite alphabet A ( repeated use of obtained words is permitted). Let LA ( n ) be the maximal complexity of words of length n over a finite alphabet A. In this paper we prove that Ш n ) = (l + (2 + 0 ( 1 ) ).
ISSN:0027-1322
1934-8444
DOI:10.3103/S0027132216020029