Header menu link for other important links
X
Parikh Images of Matrix Ins-Del Systems
Fernau H,
Published in Springer International Publishing
2017
Volume: 10185 LNCS
   
Pages: 201 - 215
Abstract
Matrix insertion-deletion systems combine the idea of matrix control (as established in regulated rewriting) with that of insertion and deletion (as opposed to replacements). We study families of multisets that can be described as Parikh images of languages generated by this type of systems, focusing on aspects of descriptional complexity. We show that the Parikh images of matrix insertion-deletion systems having length 2 matrices and context-free insertion/deletion contain only semilinear languages and when the matrices length increased to 3, they contain non-semilinear languages. We also characterize the hierarchy of family of languages that is formed with these systems having small sizes. We also introduce a new class, namely, monotone strict context-free matrix ins-del systems and analyze the results connecting with families of context-sensitive languages and Parikh images of regular and context-free matrix languages. © Springer International Publishing AG 2017.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science Theory and Applications of Models of Computation
PublisherData powered by TypesetSpringer International Publishing
ISSN0302-9743
Open Access0