Sevilla Carpets

From The P-Lingua Website

Jump to: navigation, search

The evolution of a P system is usually a too complex process to be evaluated only by the classical parameters from computational complexity measure, time and space. For instance, we are often interested in other types of descriptive complexity information: size of the alphabet, number of membranes (initially in the system or obtained during the computation), number of rules, etc. Another interesting parameter, especially when running software simulations, is the number of elementary operations (applications of rules) that are performed during the computation.

A possible way to describe the complexity of the evolution of a P system is by means of Sevilla carpets. They were presented in [1] as an extension of the Szilard language, which consists of all strings of rule labels describing correct derivations in a given grammar. The original framework for Szilard language is the Chomsky hierarchy of grammars, where only one rule is used in each derivation step and, therefore, a derivation can be represented in a natural way as the string of labels corresponding to the used rules (we refer again to [1] for details).

Sevilla carpets are a Szilard-way to describe a computation in a P system, capturing via a bi-dimensional writing the fact that in each evolution step a P system can use not just a single rule, but a multiset of them. More precisely, the (Sevilla) carpet associated with a computation of a P system is a table with the time on the horizontal axis and the rules explicitly mentioned along the vertical axis; then, for each rule, in each step, a piece of information is given.


[1] G. Ciobanu, Gh. Paun, Gh. Stefanescu.
   Sevilla Carpets associated with P systems.
   In Cavaliere et al (eds) Proceedings of the Brainstorming Week on Membrane Computing. 
   Tech. rep. RGML 26/03, Univ. Rovira i Virgili, Tarragona, Spain, 2003, 135–140.


Personal tools