Open AccessClosure properties of bonded sequential insertion-deletion systems
Author(s) -
Wan Heng Fong,
Ahmad Firdaus Yosman,
Hazzirah Izzati Mat Hassim
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1988/1/012075
Subject(s) - concatenation (mathematics) , recursively enumerable language , closure (psychology) , regular language , intersection (aeronautics) , catenation , word (group theory) , computer science , formal language , substitution (logic) , algorithm , set (abstract data type) , discrete mathematics , dna , mathematics , arithmetic , theoretical computer science , genetics , biology , programming language , automaton , engineering , geometry , economics , market economy , aerospace engineering
Through the years, formal language theory has evolved through continual interdisciplinary work in theoretical computer science, discrete mathematics and molecular biology. The combination of these areas resulted in the birth of DNA computing. Here, language generating devices that usually considered any set of letters have taken on extra restrictions or modified constructs to simulate the behavior of recombinant DNA. A type of these devices is an insertion-deletion system, where the operations of insertion and deletion of a word have been combined in a single construct. Upon appending integers to both sides of the letters in a word, bonded insertion-deletion systems were introduced to accurately depict chemical bonds in chemical compounds. Previously, it has been shown that bonded sequential insertion-deletion systems could generate up to recursively enumerable languages. However, the closure properties of these systems have yet to be determined. In this paper, it is shown that bonded sequential insertion-deletion systems are closed under union, concatenation, concatenation closure, λ-free concatenation closure, substitution and intersection with regular languages. Hence, the family of languages generated by bonded sequential insertion-deletion systems is shown to be a full abstract family of languages.