Looking for small efficient P systems

TitleLooking for small efficient P systems
Publication TypeJournal Papers
Year of Publication2011
AuthorsPérez-Jiménez, M. J., Riscos-Núñez A., Rius-Font M., & Romero-Campero F. J.
Journal TitleFundamenta Informaticae
PublisherIOS Press
Place PublishedWarsaw, Poland
Volume110
Pages295-308
Date Published09/2011
Abstract

In 1936 A. Turing showed the existence of a universal machine able to simulate any Turing machine given its description. In 1956, C. Shannon formulated for the first time the problem of finding the smallest possible universal Turing machine according to some critera to measure its size such as the number of states and symbols. Within the framework of Membrane Computing different studies have addressed this problem: small universal symport/antiport P systems (by considering the number of membranes, the weight of the rules and the number of objects as a measure of the size of the system), small universal splicing P systems (by considering the number of rules as a measure of the size of the system), and small universal spiking neural P systems (by considering the number of neurons as a measure of the size of the system). In this paper the problem of determining the smallest possible efficient P system is explicitly formulated. Efficiency within the framework of Membrane Computing refers to the capability of solving computationally hard problems (i.e. problems such that classical electronic computer cannot solve instances of medium/large size in any reasonable amount of time) in polynomial time. A descriptive measure to define precisely the notion of small P system is presented in this paper.

KeywordsMembrane computing, SAT problem, Small effcient P systems, Small universal P Systems
URLhttp://iospress.metapress.com/content/a602986l41270452/?p=a7b191063cc84e26b09025bfd0833931&pi=21
Issue1-4
Impact Factor

0.365

Ranking

88/104 - Q4

ISSN Number0169-2968
DOI10.3233/FI-2011-544