装配加法链 (Assembly Addition Chains)

In this paper we extend the notion of Addition Chains over Z+ to a general set S. We explain how the algebraic structure of Assembly Multi-Magma over the pairs (S,BB proper subset of S) allows to define the concept of Addition Chain over S, called Assembly Addition Chains of S with Building Blocks BB. Analogously to the Z+ case, we introduce the concept of Optimal Assembly Addition Chains over S and prove lower and upper bounds for their lengths, similar to the bounds found by Schonhage for the Z+ case. In the general case the unit 1 is in set Z+ is replaced by the subset BB and the mentioned bounds for the length of an Optimal Assembly Addition Chain of O is in set S are defined in terms of the size of O (i.e. the number of Building Blocks required to construct O). The main examples of S that we consider through this papers are (i) j-Strings (Strings with an alphabeth of j letters), (ii) Colored Connected Graphs and (iii) Colored Polyominoes.

翻译：本文中，我们将正整数集Z+上的加法链概念推广至一般集合S。我们阐释了在有序对(S, BB为S的真子集)上的装配多重代数结构如何允许定义S上的加法链概念，称为具有构建块BB的S的装配加法链。类比于Z+情形，我们引入了S上的最优装配加法链概念，并证明了其长度的下界和上界，类似于Schonhage在Z+情形中发现的界。在一般情形中，集合Z+中的单位元1被子集BB取代，并且关于S中元素O的最优装配加法链长度的上述界是根据O的规模（即构造O所需的构建块数量）来定义的。本文考虑的主要S实例包括：(i) j-字符串（具有j个字母表字母的字符串），(ii) 着色连通图，以及(iii) 着色多联骨牌。