TY - JOUR
T1 - On the power of enzymatic numerical P systems
AU - Vasile, Cristian Ioan
AU - Pavel, Ana Brânduşa
AU - Dumitrache, Ioan
AU - Pǎun, Gheorghe
N1 - Funding Information:
The work of Gh. Păun was supported by Proyecto de Excelencia con Investigador de Reconocida Valía, de la Junta de Andalucía, grant P08—TIC 04200. Part of this work was supported by the Sectorial Operational Program Human Resources Development (SOP HRD), financed from the European Social Fund and by the Romanian Government under the contract number SOP HRD/107/1.5/S/82514. Useful remarks by two anonymous referees are gratefully acknowledged.
PY - 2012/9
Y1 - 2012/9
N2 - We study the computing power of a class of numerical P systems introduced in the framework of autonomous robot control, namely enzymatic numerical P systems. Three ways of using the evolution programs are investigated: sequential, all-parallel and one-parallel (with the same variable used in all programs or in only one, respectively); moreover, both deterministic and non-deterministic systems are considered. The Turing universality of some of the obtained classes of numerical P systems is proved (for polynomials with the smallest possible degree, one, also introducing a new proof technique in this area, namely starting the universality proof from the characterization of computable sets of numbers by means of register machines). The power of many other classes remains to be investigated.
AB - We study the computing power of a class of numerical P systems introduced in the framework of autonomous robot control, namely enzymatic numerical P systems. Three ways of using the evolution programs are investigated: sequential, all-parallel and one-parallel (with the same variable used in all programs or in only one, respectively); moreover, both deterministic and non-deterministic systems are considered. The Turing universality of some of the obtained classes of numerical P systems is proved (for polynomials with the smallest possible degree, one, also introducing a new proof technique in this area, namely starting the universality proof from the characterization of computable sets of numbers by means of register machines). The power of many other classes remains to be investigated.
UR - http://www.scopus.com/inward/record.url?scp=84866463865&partnerID=8YFLogxK
U2 - 10.1007/s00236-012-0166-y
DO - 10.1007/s00236-012-0166-y
M3 - Article
AN - SCOPUS:84866463865
SN - 0001-5903
VL - 49
SP - 395
EP - 412
JO - Acta Informatica
JF - Acta Informatica
IS - 6
ER -