On bonded Indian and uniformly parallel insertion systems and their generative power

Insertion is an operation in formal language theory that generalizes the operation of concatenation of words, where its variants allow the operation in different ways. Parallel insertion is a variant of insertion that simultaneously adds words between all letters of a word and also at the right and...

Full description

Saved in:
Bibliographic Details
Main Authors: Yosman, Ahmad Firdaus, Holzer, Markus, Truthe, Bianca, Wan, Heng Fong, Turaev, Sherzod
Format: Article
Language:English
Published: Penerbit UTM Press 2017
Subjects:
Online Access:http://eprints.utm.my/id/eprint/80664/1/WanHengFong2017_OnBondedIndianandUniformlyParallelInsertion.pdf
http://eprints.utm.my/id/eprint/80664/
https://dx.doi.org/10.11113/mjfas.v13n4.753
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Insertion is an operation in formal language theory that generalizes the operation of concatenation of words, where its variants allow the operation in different ways. Parallel insertion is a variant of insertion that simultaneously adds words between all letters of a word and also at the right and left extremities. In previous research, restrictions on the applicability have been imposed leading to socalled bonded insertion systems with a sequential and a parallel variant. Motivated by the atomic behavior of chemical compounds in the process of chemical bonding, the generative power of bonded insertion systems has been investigated where a language hierarchy was obtained. In this paper, we introduce new variants of bonded parallel insertion systems, namely bonded Indian parallel insertion systems and bonded uniformly parallel insertion systems. We present some results regarding the generative power of these new systems and a language hierarchy.