Sticker systems over permutation groups - Mohd Sebry, Nurul Afidah; Sarmin, Nor Haniza; Fong, Wan Heng; Turaev, Sherzod (IDOSI Publications, 2013)
Sticker systems were first introduced as a language generating device based on the operation of sticking. A new molecule is produced from the starting axiom, which is prolonged to the left or to the right using given single stranded strings or dominoes. For each sticker operation, an element of a group (called valence) will be associated with the axioms and dominoes and then the value of the group operation of the newly produced string is computed. Valence grammars were introduced as grammars with regulated rewriting using permutation groups and groups as control mechanisms. The definition for valence grammar is later extended to valence H systems which associate integer numbers with strings and the values associated with the result of newly produced strings are computed. A complete double stranded molecule is considered to be valid if the computation of the associated element produces the identity element. However, the converse is not true. Using the idea from the definition of valence H system and extended valence H system, the concept of valence sticker system over permutation groups is introduced in this research and the computational power of the language produced is also investigated.