Array-rewriting P systems

TitleArray-rewriting P systems
Publication TypeJournal Papers
Year of Publication2003
AuthorsCeterchi, R., Mutyam M., Paun G., & Subramanian K. G.
Journal TitleNatural Computing
PublisherSpringer Verlag
Place PublishedAmsterdam, Netherlands

We consider array languages (sets of picturesconsisting of symbols placed in the lattice points of the 2D grid) and thepossibility to handle them with P systems. After proving binary normal formsfor array matrix grammars (which, even in the case when no appearance checking isused, are known to generate the array languages of arbitrary array grammars), weprove that the P systems with context-free rules (with three membranes and no control on the communication or the use of rules) are computationally universal, able togenerate all computable array languages. Some open problems

Keywordsarray languages, matrix grammar, Membrane computing, P system, Turing computability
ISSN Number1567-7818