Event-Related Outputs of Computations in P Systems

Matteo Cavaliere, Rudolf Freund, Alexander Leitsch, Gheorghe Paun

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

We briefly investigate the idea to consider as the result of a computation in a P system the number of steps elapsed between two events produced during the computation. Specifically, we first consider the case when the result of a computation is defined in terms of events related to using rules, introducing objects, or meeting objects. In each case, symport/antiport P systems are computationally complete, i.e., they can generate any recursively enumerable set of natural numbers. Then, we address the case when the number computed by a system is the length of a computation itself. We obtain a few results both for catalytic multiset-rewriting and for symport/antiport systems (in each case, also with using membrane dissolution) showing that non-semilinear sets of vectors of natural numbers can be computed in that way. Moreover, we prove a general result showing that for no type of systems we can obtain computational completeness when considering the length sets of halting computations. The general problem, of characterizing the sets of natural numbers computed in this way, remains open.
Original languageEnglish
Pages (from-to)263-278
Number of pages16
JournalJournal of Automata, Languages and Combinatorics
Issue number3
Publication statusPublished - 2006


Dive into the research topics of 'Event-Related Outputs of Computations in P Systems'. Together they form a unique fingerprint.

Cite this