On the branching complexity of P systems
| Title | On the branching complexity of P systems |
| Publication Type | Journal Papers |
| Year of Publication | 2006 |
| Authors | Ciobanu, G., Paun G., & Pérez-Jiménez M. J. |
| Journal Title | Fundamenta Informaticae |
| Publisher | IOS Press |
| Place Published | Amsterdam, Holanda |
| Volume | 73 |
| Pages | 27-36 |
| Abstract | We consider two complexity parameters related to the graph of reachable configurations of a given P system, namely the outdegree as a measure of the degree of non-determinism, and the indegree as a measure of the degree of confluence. These parameters can be defined for both the generative and the accepting mode of using a P system. We investigate here these parameters in what concerns hierarchies and decidability issues. We prove that all hierarchies have only two levels and that all considered decidability problems have a negative answer. |
| Keywords | decidability, descriptional complexity, Membrane computing, non-determinism |
| URL | http://portal.acm.org/citation.cfm?id=1231163 |
| Issue | 1-2 |
Research Group on Natural Computing (PAI - TIC 193)
Department of Computer Science and Artificial Intelligence
University of Seville
Webmasters: the members of the RGNC
| Follow us: |  |
 |
|
Featured News: |
|
Mario J. Pérez-Jiménez in the top 2% of scientists of the World |
|
Agustín became Full Professor |
|
Science names our most recent research project |