Header menu link for other important links
X
On Matrix Ins-Del Systems of Small Sum-Norm
Fernau H, , Raman I.
Published in Springer International Publishing
2019
Volume: 11376 LNCS
   
Pages: 192 - 205
Abstract
A matrix ins-del system is described by a set of insertion-deletion rules presented in matrix form, which demands all rules of a matrix to be applied in the given order. These systems were introduced to model very simplistic fragments of sequential programs based on insertion and deletion as elementary operations as can be found in biocomputing. We are investigating such systems with limited resources as formalized in descriptional complexity. A traditional descriptional complexity measure of such a system is its ins-del size. Summing up the according numbers, we arrive at the sum-norm. We show that matrix ins-del systems with sum-norm 4 and (i) maximum length 3 with only one of insertion or deletion being performed under a one-sided context, or (ii) maximum length 2 with both insertion and deletion being performed under a one-sided context, can describe all recursively enumerable languages. We also show that if a matrix ins-del system of size s can describe the class of linear languages LIN, then without any additional resources, matrix ins-del systems of size s also describe the regular closure of LIN. © 2019, Springer Nature Switzerland AG.
About the journal
JournalData powered by TypesetSOFSEM 2019: Theory and Practice of Computer Science Lecture Notes in Computer Science
PublisherData powered by TypesetSpringer International Publishing
ISSN0302-9743
Open Access0