Por motivos de mantenimiento se ha deshabilitado el inicio de sesión temporalmente. Rogamos disculpen las molestias.
Presentation
Event-Related Outputs of Computations in P Systems
Author/s | Cavaliere, Matteo
Freund, Rudolf Leitsch, Alexander Paun, Gheorghe |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Publication Date | 2005 |
Deposit Date | 2016-02-25 |
Published in |
|
ISBN/ISSN | 84-609-6771-9 |
Abstract | 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 ... 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. Universality is easily obtained in each case for symport/antiport P systems. 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 can be computed in this way. A general non-universality result is proved for this case - no system, of any type, can have as the length of its halting computations all sets of numbers computable by Turing machines. The general problem, of characterizing the sets of numbers computed in this way, remains open. |
Files | Size | Format | View | Description |
---|---|---|---|---|
bravol107.pdf | 194.3Kb | [PDF] | View/ | |