On the Power of P Systems with Contextual Rules

• Autorzy: Krishna S.N. , Lakshmanan K. , Rama R.
• Języki publikacji: EN

Abstrakty

EN

We consider P Systems with string objects which evolve by means of one-sided contextual rules and erasing contextual rules. The generative power of these systems with three or less than three membranes is investigated. We show that systems with three membranes characterize the family of recursively enumerable languages. When the string replication is used in one-sided contextual rules, these systems are able of solving NP-complete problems in linear time: this is exemplified with SAT and HPP.

Słowa kluczowe

EN

P systems; one-sided contextual rules; erasing contextual rules; recursively enumerable; NP-completeness

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

Twórcy

autor

Krishna S.N.

autor

Lakshmanan K.

autor

Rama R.

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

Bibliografia

• [1] J. Castenallos, Gh.PSun, A.Rodriguez-Paton, P Systems with worm objects, Proceedings of IEEE Conference SPIRE’2000, La Coruna, Spain, 64-74.
• [2] S.N. Krishna, K. Lakshmanan, R. Rama, Hybrid P Systems, Romanian Journal of Infromation Science and Technology, 4, 1-2(2001).
• [3] S.N. Krishna, R. Rama, P Systems with replicated rewriting, Journal of automata, Languages and Combinatorics, to appear.
• [4] M. Madhu, K. Krithivasan, Contextual P Systems, Pre-Proceedings of Workshop on Membranę Computing, Curtea de Arge§, Romania, August 2001, Technical Report 17/01 of Research Group on Mathematical Linguistics, Rovira i Yirgili University, Tarragona, Spain, 2001, 169-180.
• [5] S. Marcus, Contextual grammars, Rev. Roum. Pures. Appl., 14 (1969), 1525-1534.
• [6] C. Martin-Vide, A. Mateescu, Gh. P3un, Hybrid grammars: The Chomsky-Marcus case, Bulletin of EATCS, 64(1998), 159-165.
• [7] M. Margenstem, C. Martin-Vide, Gh. Pfiun, Computing with membranes: Variants with an enhanced membranę handling, Proc. 7th Intern. Meeting on DNA Based Computers, (N. Jonoska, N.C. Seeman, eds.), Tampa, Florida, USA, 2001, 53-62.
• [8] C. Martin-Vide, Gh. P3un, String-objects in P Systems, Proc. Algebraic Systems, Format Languages and Computations Workshop, Kyoto, 2000, RIMS Kokyuroku, Kyoto Univ. 2000.
• [9] Gh. P5un, Marcus Contextual Grammars, Kluwer Academic Publ., Dordrecht, Boston, London, 1997.
• [10] Gh. Pdun, Computing with membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108-143.
• [11] Gh. PSun, P systems with active membranes: Attacking NP-complete problems, Journal of Automata, Lan¬guages and Combinatorics, 6 (2001), 75-90.
• [12] G. Rozenberg, A. Salomaa, eds., Handbook of Formal Languages, 3 volumes, Springer-Yerlag, Berlin, 1997.