Assembly Addition Chains
By: Leroy Cronin, Juan Carlos Morales Parra, Keith Y. Patarroyo
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.
Similar Papers
How Concise are Chains of co-Büchi Automata?
Formal Languages and Automata Theory
Makes computer programs smaller and faster.
Additive systems for $\mathbb{Z}$ are undecidable
Combinatorics
Finds unique number sums for all whole numbers.
Duality on group algebras over finite chain rings: applications to additive group codes
Information Theory
Makes computer codes more efficient for sending data.