Watson-Crick finite automata of small size and variants of string assembling systems

Abstract We investigate the relationship of languages characterized by variants of string assembling systems and by Watson-Crick finite automata with a small number of states. Besides the general variant, we consider so-called free, and pure string assembling systems and compare their language generating power to Watson-Crick finite automata having one state (also called stateless) and two or three states in their state sets. We also study restricted variants of models that describe unary languages.