Further Results on Contextual and Rewriting P Systems

• Autorzy: Krishna S. N. , Rama R. , Ramesh H.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we continue the study of contextual and rewriting P systems. In contextual P systems, we improve a universality result avoiding the extended feature and by using rules of small weight. In rewriting P systems, we have two (rather surprising) universality results, both of them using three membranes, for non-extended systems with replicated rewriting and with leftmost rewriting, respectively.

Słowa kluczowe

EN

P systems; contextual grammars; replicated rewriting; leftmost rewriting; recursively enumerable languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 241--253
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Krishna S. N.

• Department of Computer Science and Engineering, Indian Institute of Technology, Powai, Mumbai-76, India

autor

Rama R.

• Department of Mathematics Indian Institute of Technology, Madras Chennai-36, India

autor

Ramesh H.

• Department of Mathematics Indian Institute of Technology, Madras Chennai-36, India

Bibliografia

• [1] J. Dassow and Gh. P˘aun, Regulated Rewriting in Formal Language Theory, Springer-Verlag, 1989.
• [2] C. Ferretti, G. Mauri, Gh. P˘aun, and C. Zandron, On Three Variants of P Systems with String-Objects, Pre-Proceedings of Workshop on Membrane Computing, 63-76, Curtea de Arges, Romania, August 2001, and Theoretical Computer Science, to appear.
• [3] K. Krithivasan and M. Madhu, Contextual P Systems, Fundamenta Informaticae, 49(1-3), 2002, 179–189.
• [4] S.N. Krishna and R. Rama, P Systems with Replicated Rewriting, Journal of Automata, Languages and Combinatorics, 6(3) 2001, 345–350.
• [5] S.N. Krishna, K. Lakshmanan, and R. Rama, On the Power of P Systems with Contextual Rules, Fundamenta Informaticae, 49 (1-3), 2002, 167–178.
• [6] V. Manca, C. Martin-Vide, and Gh. Păun, On the Power of P Systems with Replicated Rewriting, Journal of Automata, Languages and Combinatorics, 6(3) 2001, 359–374.
• [7] M. Madhu, New results in Rewriting P Systems, Theoretical Computer Science, to appear.
• [8] Gh. Păun, Membrane Computing. An Introduction, Springer-Verlag, 2002.
• [9] Gh. Păun, Marcus Contextual Grammars, Kluwer Academc Publishers, 1997.
• [10] G.Rozenberg and A.Salomaa, eds., Handbook of Formal Languages (3 volumes), Springer-Verlag, 1997