Affiliations: International Institute of Information Technology,
Hyderabad, Gachibowli, Hyderabad-19, India. madhu_mutyam@iiit.ac.in | Department of Computer Science and Engineering, Indian
Institute of Technology Madras, Chennai-36, India. kamala@iitm.ernet.in | Department of Computer Science, New York University,
NY, USA. siddhart@cs.nyu.edu
Note: [] Address for correspondence: International Institute of
Information Technology, Hyderabad, Gachibowli, Hyderabad-19, India
Abstract: Insertion grammars have been introduced in [1] and their
computational power has been studied in several places. In [7] it is proved
that insertion grammars with weight at least 7 can characterize recursively
enumerable languages (modulo a weak coding and an inverse morphism), and the
question was formulated whether or not this result can be improved. In this
paper, we come up with a positive answer to this question, by decreasing the
weight of the insertion grammar used to 5. We also give a characterization of
recursively enumerable languages in terms of right quotients of insertion
languages.
Keywords: Insertion grammar, contextual grammar, recursively enumerable languages, Penttonen normal form, Kuroda normal form
