String Assembling Systems: Origins and Directions
摘要
String assembling systems are biologically inspired mechanisms that generate strings from copies out of a finite set of assembly units. The underlying mechanism is based on piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. Since their introduction in 2011, several variants have been studied from various viewpoints. Although string assembling systems are a simple concept, their generative behavior can be already very complex and leads to undecidable problems on these devices such as, for example, emptiness, finiteness, universality, equivalence, etc. Here we tour a fragment of the literature on generative capacities, decidability problems, and other properties of string assembling systems. The capacities of different variants are compared to study the impact of the resources given to the variants. The results discussed obviously lack completeness, as one falls short of exhausting all the details considered in the literature.