Formal Grammars
A Journal of Mathematical Research on Formal and Natural Languages

Editor-in-chief: Carlos Martín-Vide
Special issues
Introduction
Volume 7(2004)
Volume 8(2005)
Editorial board
Aims and Scope
Subscription to the Hardcopy Edition
Submission procedure


Polarizationless P Systems with Active Membranes

ARTIOM ALHAZOV, LINQIANG PAN

Abstract

The subject of this paper is the continuation of the studies of P systems with active membranes without polarizations with the label-changing capacity of some rules. Rewriting and communication rules that do not change membrane labels can be applied either sequentially or in a maximally parallel way. We consider several classes of P systems and study their generative power. Particularly interesting, P systems with only evolution rules used sequentially and changing labels compute exactly the Parikh sets of matrix languages; the universality is reached by P systems with evolution rules and communication rules used sequentially. By direct constructions, we also prove that SAT can be solved in linear time by systems with evolution rules changing labels, communication, and membrane division. Several open problems are also formulated.

Download:
PS file
PDF file
Copyright © 2004 GRLMC. All rights reserved.
Research Group on Mathematical Linguistics - Rovira i Virgili University
Webmaster