Looking for Small Efficient P Systems

• Autorzy: Pérez-Jiménez M.J. , Rius-Font M. , Riscos-Nunez A. , Romero-Campero F. J.
• Języki publikacji: EN

Abstrakty

EN

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 ofMembrane 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.

Słowa kluczowe

EN

membrane computing; small universal P Systems; small effcient P systems; SAT problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 293--308
• Opis fizyczny: Bibliogr. 13 poz., tab.

Twórcy

autor

Pérez-Jiménez M.J.

autor

Rius-Font M.

autor

Riscos-Nunez A.

autor

Romero-Campero F. J.

• Research Group on Natural Computing, Dpt. Computer Science and Artificial Intelligence, University of Sevilla, 41012 Seville, Spain,

Bibliografia

• [1] Alhazov, A., Pan, L., Pǎun, Gh. Trading polarizations for labels in P systems with active membranes. Acta Informatica, 41, (2004), 111-144.
• [2] Martın Vide, C., Pazos, J., Pǎun, Gh., Rodrıguez Patón, A. Tissue P systems. Theoretical Computer Science, 296(2003), 295-326.
• [3] Minsky, M. A 6-symbol 7-state universal Turing machines. Technical Report 54-G-027, Lincoln Laboratory, MIT, Cambridge,Massachusetts, August 1960.
• [4] Pǎun, Gh. Computing with membranes. Journal of Computer and System Sciences, 61, 1(2000), 108-143.
• [5] Pǎun, Gh. Membrane Computing. An Introduction. Springer-Verlag, Berlin (2002).
• [6] Pǎun, Gh., Pérez-Jiménez,M.J., Riscos-N´u˜nez, A. Tissue P systems with cell division. International Journal of Computers, Communications and Control, 3, 3(2008), 295-303.
• [7] Pérez-Jiménez, M.J., Riscos-N´u˜nez, A., Romero-Jiménez, A., Woods, D. Complexity: Membrane division, membrane creation. In Pǎun, Rozenberg and Salomaa (eds) The Oxford Handbook ofMembrane Computing, Oxford (U.K.), 302-336, (2010).
• [8] Pérez-Jiménez, M.J., Romero A., Sancho, F. Complexity classes in models of cellular computing with membranes. Natural Computing, 2, 3 (2003), 265-285.
• [9] Rogozhin, Y. Small universal Turing machines. Theoretical Computer Science, 168, 2 (1996), 215-240.
• [10] Shannon, C.E. A universal Turingmachine with two internal states. Automata Studies, Annals ofMathematics Studies, 34 (1956), 157-165.
• [11] Turing, A. On computable numbers with application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42 (1937), 230-265.
• [12] Watanabe, Sh. On a minimal universal Turing machine. Technical report, MCB Report, Tokyo, August 1960.
• [13] Watanabe, Sh. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the Association for Computing Machinery (ACM), 8, 4 (1961), 476-483.