Contextual P Systems

• Autorzy: Krithivasan K. , Madhu M.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

P systems; contextual grammars; insertion grammars; contextual P systems; recursively enumerable languages; kuroda normal form; pentonnen normal form; computational completeness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 49, nr 1-3
• Strony: 179--189
• Opis fizyczny: bibliogr. 9 poz.

Twórcy

autor

Krithivasan K.

autor

Madhu M.

• Theoretical Computer Science laboratory, Dep. Of Computer Science and Engineering, Indian Institute of Technology, Madras, Chennai-36, Tamil Nadu, India,

Bibliografia

• [1] Dassow, J., P2un, Gh.: Regulated Rewriting in Fornal Language Theory, Springer-Verlag, Berlin, 1989.
• [2] Dassow, J., P&un, Gh.: On the Power of Membranę Computing, Journal of Universal Computer Science, 5(2), 1999,33-49.
• [3] Kaushik, S. R., Krithivasan, K.: Some Results on Contextual Grammars, International Journal of Computer Mathematics, 73, 2000, 279-291.
• [4] Krishna, S.N.,Lakshmanan, K., Rama, R.: On the Power of P Systems with One-Sided and Erasing Contextual Rules, International Workshop on Membranę Computing (C. Martin-Vide, Gh. P5un, eds.), Curtea de Arges, Romania, August 20-25,2001.
• [5] Marcus, S.: Contextual Grammars, Rev. Roum. Math. Pures Appl., 14,1969,1525-1534.
• [6] P&un, Gh.: Marcus Contextual Grammars, Kluwer Academic Publishers, 1997.
• [7] PSun, Gh.: Computing with Membranes, Journal of Computer and System Sciences, 61(1), 2000, 108-143.
• [8] PSun, Gh., Rozenberg, G., Salomaa, A.: Membranę Computing with Extemal Output, Fundamenta Informaticae, 41(3), 2000, 259-266.
• [9] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, Springer-Yerlag, Berlin, 1997.