Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: kuroda normal form

Sortuj według:

Ogranicz wyniki do:

On Characterizing Recursively Enumerable Languages by Insertion Grammars

Mutyam M., Krithivasan K., Reddy A. S.

Fundamenta Informaticae

2005

Vol. 64, nr 1-4

317--324

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.

Contextual P Systems

Krithivasan K., Madhu M.

Fundamenta Informaticae

2002

Vol. 49, nr 1-3

179-189

Generally, in P systems with string-objects one uses the Chomsky way of rewriting for processing the objects. In this paper we consider the contextual way of handling string-objects in P systems. We introduce some variants of contextual grammars and prove that contextual P systems with rules corresponding to these variants are more powerful than ordinary contextual grammars and their variants. We also show that one-sided contextual P systems with right-sided erased contexts and insertion contextual P systems with right-sided erased contexts are computationally complete.