KIAM Main page Web Library  •  Publication Searh  Русский 

Article collection "Mathematical Problems of Cybernetics" №8, Moscow, 1999
Authors: Kochergin V.V.
On the multiplicative complexity of binary words with a given number of units
The multiplicative complexity of a binary word α is the length m of the shortest chain of binary words τ−1 = 0, τ0 = 1, τ1, . . . , τm = α, where each τi can be written as a concatenation of two previous words: τi = τj τk, −1 ≤ j, k < i. Let l(k, n) denote the largest multiplicative complexity taken over all binary words of length n with k ones. Some interesting links between l(k, n) and the smallest possible number of multiplications to compute k-tuples of powers xn1,..., xnk are established. The main result of the paper is the asymptotic formula l(k,n) = (1 + o(1))(log n + log Cnk / loglog Cnk) as n→∞.
word chain, concatenation circuit, circuit complexity, Shannon function
Publication language: russian,  pages: 14 (p. 63-76)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Kochergin Vadim Vasil'evich,  ,  Механико-математический факультет МГУ, Кафедра дискретной математики, Институт теоретических проблем микромира им. Н. Н. Боголюбова МГУ