Header menu link for other important links
X
On characterizing recursively enumerable languages by insertion grammars
Kamala Krithivasan,
Published in
2005
Volume: 64
   
Issue: 1-4
Pages: 317 - 324
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.
About the journal
JournalFundamenta Informaticae
ISSN01692968
Open AccessNo
Concepts (7)
  •  related image
    Encoding (symbols)
  •  related image
    CONTEXTUAL GRAMMAR
  •  related image
    INSERTION GRAMMAR
  •  related image
    KURODA NORMAL FORM
  •  related image
    PENTTONEN NORMAL FORM
  •  related image
    Recursively enumerable languages
  •  related image
    Formal languages