Sevilla Carpets Revisited : Enriching the Membrane Computing Toolbox

• Autorzy: Orellana-Martín D. , Graciani C. , Macías-Ramos L.-F. , Martínez-del-Amor M. A. , Riscos-Núñez A. , Romero-Jiménez A. , Valencia-Cabrera L.

Identyfikatory

DOI

10.3233/FI-2014-1096

• Języki publikacji: EN

Abstrakty

EN

Sevilla carpets have already been used to compare different solutions of the Subset Sum problem: either designed in the framework of P systems with active membranes (both in the case of membrane division and membrane creation), and in the framework of tissue-like P systems with cell division. Recently, the degree of parallelism and other descriptive complexity details have been found to be relevant when designing parallel simulators running on GPUs. We present here a new way to use the information provided by Sevilla carpets in this context, and a script that allows to generate them automatically from P-Lingua files.

Słowa kluczowe

EN

P systems; descriptive complexity; Sevilla carpets; P-Lingua; MeCoSim

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 1/2
• Strony: 153--166
• Opis fizyczny: Bibliogr. 26 poz., wykr.

Twórcy

autor

Orellana-Martín D.

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Spain

autor

Graciani C.

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Spain

autor

Macías-Ramos L.-F.

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Spain

autor

Martínez-del-Amor M. A.

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Spain

autor

Riscos-Núñez A.

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Spain

autor

Romero-Jiménez A.

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Spain

autor

Valencia-Cabrera L.

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Spain

Bibliografia

• [1] Cecilia, J.M; García, J.M; Guerrero, G.D.; Martínez-del-Amor, M.A.; Pérez-Hurtado, I.; Pérez-Jiménez, M.J. Simulation of P systems with active membranes on CUDA, Briefings in Bioinformatics, 11 (3), 2010, 313-322.
• [2] Cecilia, J.M.; García, J.M.; Guerrero, G.D.; Martínez-del-Amor, M.A.; Pérez-Jiménez, M.J.; Ujaldón, M. The GPU on the simulation of cellular computing models, Soft Computing, 16 (2), 2012, 231–246.
• [3] Ciobanu, G.; Păun, Gh.; Stefănescu, Gh. Sevilla Carpets Associated with P Systems, in M. Cavaliere, C. Martín–Vide and Gh. Păun (eds.), Proceedings of the Brainstorming Week on Membrane Computing, Tarragona, Spain, 2003, Report RGML 26/03, 135-140.
• [4] Cordón-Franco, C.; Gutiérrez-Naranjo, M.A.; Pérez-Jiménez, M.J.; Sancho-Caparrini, F. A Prolog simulator for deterministic P systems with active membranes, New Generation Computing, 22 (4), 2004, 349–363.
• [5] Díaz-Pernil, D.; Gallego-Ortiz, P.; Gutiérrez-Naranjo M.A.; Pérez-Jiménez M.J.; Riscos-Núñez A. Descriptional Complexity of Tissue-like P Systems with Cell Division. Lecture Notes in Computer Science, 5715 (2009), 168-178.
• [6] Díaz-Pernil, D.; Pérez–Hurtado, I.; Pérez-Jiménez, M.J.; Riscos-Núñez, A. A P-lingua programming environment for Membrane Computing. Lecture Notes in Computer Science, 5391 (2009), 187–203.
• [7] Graciani-Díaz, C.; Gutiérrez-Naranjo, M.A.; Pérez-Hurtado I.; Riscos- Núñez A.; Romero-Jiménez Á . (2013). A Rete-based Algorithm for Rule Selection in P Systems. International Journal of Unconventional Computing. 9(5-6), 367-384.
• [8] Gutiérrez-Naranjo, M.A.; Pérez-Jiménez, M.J.; Riscos-Núñez, A. A Fast P System for Finding a Balanced 2-Partition, Soft Computing, 9(9), (2005) 673–678.
• [9] Gutiérrez-Naranjo, M.A.; Pérez-Jiménez, M.J.; Riscos-Núñez, A. A Simulator for Confluent P Systems. In M. A. Gutiérrez-Naranjo et al (eds.), Third Brainstorming Week on Membrane Computing Fénix Editora, Sevilla, 2005, 169–184.
• [10] Gutiérrez-Naranjo, M.A.; Pérez-Jiménez, M.J.; Riscos-Núñez, A. On Descriptive Complexity of P Systems. Lecture Notes in Computer Science, 3365 (2005), 320–330.
• [11] Gutiérrez-Naranjo, M.A.; Pérez-Jiménez, M.J.; Riscos-Núñez, A. On the Degree of Parallelism in Membrane Systems. Theoretical Computer Science, 372 (2-3), (2007) 183–195.
• [12] Gutiérrez-Naranjo, M.A.; Pérez-Jiménez, M.J.; Riscos-Núñez, A. Multi-dimensional descriptional complexity of P systems. Journal of Automata, Languages and Combinatorics 12 1/2 (2007), 167–179.
• [13] Mäkinen, E. A Bibliography on Szilard Languages, Dept. of Computer and Information Sciences, University of Tampere, http://www.sis.uta.fi/cs/reports/pdf/Szilard.pdf
• [14] Martínez-del-Amor, M. A. Accelerating Membrane Systems Simulators using High Performance Computing with GPU (PhD Thesis), Universidad de Sevilla, 2013.
• [15] Martínez-del-Amor, M.A.; Pérez-Carrasco, J.; Pérez-Jiménez, M.J. Characterizing the parallel simulation of P systems on the GPU. International Journal of Unconventional Computing, 9 (5-6), 2013, 405-424.
• [16] Mateescu, A. and Salomaa, A. Aspects of Classical Language Theory, in G. Rozenberg and A. Salomaa (eds.), Handbook of Formal Languages (vol. 1), Springer-Verlag, Berlin Heidelberg, 1997.
• [17] Gh. Păun, G. Rozenberg, A. Salomaa (eds.). The Oxford Handbook of Membrane Computing, 2010.
• [18] Pérez-Hurtado, I.; Valencia, L.; Pérez-Jiménez, M.J.; Colomer, M.A.; Riscos-Núñez, A. MeCoSim: A general purpose software tool for simulating biological phenomena by means of P Systems. In K. Li, Z. Tang, R. Li, A.K. Nagar, R. Thamburaj (eds.) Proceedings 2010 IEEE Fifth International Conference on Bio-inpired Computing: Theories and Applications (BIC-TA 2010), IEEE Press, Volume 1, September 23-26, 2010, Changsha, China, ISBN 978-1-4244-6439-5, pp. 637–643.
• [19] Pérez-Jiménez, M.J.; Riscos-Núñez, A. Solving the Subset Sum Problem by Active Membranes, New Generation Computing, 23 (4), 2005, 367-384.
• [20] Pérez-Jiménez, M.J.; Riscos-Núñez, A. A Linear Solution for the Knapsack Problem Using Active Membranes. Lecture Notes in Computer Science, 2933 (2004), 250–268.
• [21] Pérez-Jiménez, M.J.; Romero-Jiménez, A.; Sancho-Caparrini, F. A Polynomial Complexity Class in P systems Using Membrane Division, in E. Csuhaj–Varjú, C. Kintala, D. Wotschke, and Gy. Vaszyl (eds.), Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, Budapest, Hungary, 2003, 284–294.
• [22] Salomaa, A. Formal Languages, Academic Press, New York, 1973.
• [23] P systems web page http://ppage.psystems.eu/
• [24] http://www.p-lingua.org
• [25] http://www.p-lingua.org/mecosim
• [26] http://sourceforge.net/p/pmcgpu