×

zbMATH — the first resource for mathematics

Kernel P systems: from modelling to verification and testing. (English) Zbl 1390.68309
Summary: A kernel P system integrates in a coherent and elegant manner some of the most successfully used features of the P systems employed in modelling various applications. It also provides a theoretical framework for analysing these applications and a software environment for simulating and verifying them. In this paper, we illustrate the modelling capabilities of kernel P systems by showing how other classes of P systems can be represented with this formalism and providing a number of kernel P system models for a sorting algorithm and a broadcasting problem. We also show how formal verification can be used to validate that the given models work as desired. Finally, a test generation method based on automata is extended to non-deterministic kernel P systems.

MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q60 Specification and verification (program logics, model checking, etc.)
Software:
NuSMV; SPIN
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alhazov, A.; Sburlan, D., Static sorting algorithms for P systems, (Alhazov, A.; etal., Pre-Proc. 4th Workshop on Membrane Computing, Tarragona, (2003)), 17-40, GRLMC Rep. 28/03
[2] Alhazov, A.; Sburlan, D., Static sorting P systems, (Ciobanu, G.; Păun, Gh.; Pérez-Jiménez, M. J., Applications of Membrane Computing, (2006), Springer), 215-252
[3] Arulanandham, J. J., Implementing bead-sort with P systems, (Calude, C. S.; etal., Unconventional Models of Computation, Lecture Notes in Computer Science, vol. 2509, (2002)), 115-125 · Zbl 1029.68539
[4] Bakir, M. E.; Konur, S.; Gheorghe, M.; Niculescu, I.; Ipate, F., High performance simulations of kernel P systems, (Proceedings of the 2014 IEEE 16th International Conference on High Performance Computing and Communication, HPCC’14, Paris, France, (2014)), 409-412
[5] Câmpeanu, C.; Santean, N.; Yu, S., Minimal cover-automata for finite languages, (Champarnaud, J.-M.; etal., Workshop on Implementing Automata, Lecture Notes in Computer Science, vol. 1660, (1998)), 43-56 · Zbl 0959.68062
[6] Câmpeanu, C.; Santean, N.; Yu, S., Minimal cover-automata for finite languages, Theoret. Comput. Sci., 267, 1-2, 3-16, (2001) · Zbl 0984.68099
[7] Ceterchi, R.; Martín-Vide, C., P systems with communication for static sorting, (Cavaliere, M.; etal., Pre-Proc. 1st Brainstorming Week on Membrane Computing, (2003), Rovira i Virgili Univ. Tarragona), 101-117, Technical Report No. 26
[8] Ceterchi, R.; Martín-Vide, C., Dynamic P systems, (Păun, Gh.; etal., Proc. 4th Workshop on Membrane Computing, Lecture Notes in Computer Science, vol. 2597, (2003)), 146-186 · Zbl 1023.68036
[9] Ceterchi, R.; Pérez-Jiménez, M. J.; Tomescu, A. I., Simulating the bitonic sort using P systems, (Eleftherakis, G.; etal., Proc. 8th Workshop on Membrane Computing, Lecture Notes in Computer Science, vol. 4860, (2007)), 172-192 · Zbl 1137.68378
[10] Ceterchi, R.; Pérez-Jiménez, M. J.; Tomescu, A. I., Sorting omega networks simulated with P systems: optimal data layouts, (Diaz-Pernil, D.; etal., Pre-Proc. 6th Brainstorming Week on Membrane Computing, (2008), Fénix Editora, Universidad de Sevilla), 79-92
[11] Ceterchi, R.; Sburlan, D., Membrane computing and computer science, (Păun, Gh.; Rozenberg, G.; Salomaa, A., The Oxford Handbook of Membrane Computing, (2010), Oxford University Press), 553-583, Chapter 22
[12] Ceterchi, R.; Tomescu, A. I., Implementing sorting networks with spiking neural P systems, Fund. Inform., 87, 1, 35-48, (2008) · Zbl 1154.68049
[13] Chow, T. S., Testing software design modeled by finite-state machines, IEEE Trans. Softw. Eng., 4, 3, 178-187, (1978) · Zbl 0379.68039
[14] Cimatti, A.; Clarke, E.; Giunchiglia, E.; Giunchiglia, F.; Pistore, M.; Roveri, M.; Sebastiani, R.; Tacchella, A., Nusmv version 2: an open source tool for symbolic model checking, (Hunt, W. A.; etal., Proc. International Conference on Computer-Aided Verification, CAV 2002, Lecture Notes in Computer Science, vol. 2404, (2002)), 359-364 · Zbl 1010.68766
[15] (Ciobanu, G.; Păun, Gh.; Pérez-Jiménez, M. J., Applications of Membrane Computing, (2006), Springer)
[16] Dragomir, C.; Ipate, F.; Konur, S.; Lefticaru, R.; Mierlă, L., Model checking kernel P systems, (Alhazov, A.; etal., Proc. 14th International Conference on Membrane Computing, Lecture Notes in Computer Science, vol. 8340, (2013)), 151-172 · Zbl 1407.68167
[17] Gheorghe, M.; Ceterchi, R.; Ipate, F.; Konur, S., Kernel P systems modelling, testing and verification, (Leporati, A.; Zandron, C., Pre-Proc. 17th International Conference on Membrane Computing, Milan, 25-29 July, 2016, (2016)), 161-174
[18] Gheorghe, M.; Ipate, F., On testing P systems, (Corne, D. W.; etal., Proc. 9th Workshop on Membrane Computing, Lecture Notes in Computer Science, vol. 5391, (2009)), 204-216 · Zbl 1196.68090
[19] Gheorghe, M.; Ipate, F.; Dragomir, C., Kernel P systems, (Martínez-del-Amor, M. A.; etal., Pre-Proc. 10th Brainstorming Week on Membrane Computing, (2012), Fénix Editora, Universidad de Sevilla), 153-170
[20] Gheorghe, M.; Ipate, F.; Dragomir, C.; Mierlă, L.; Valencia-Cabrera, L.; García-Quismondo, M.; Pérez-Jiménez, M. J., Kernel P systems - version 1, (Valencia-Cabrera, L.; etal., Pre-Proc. 11th Brainstorming Week on Membrane Computing, (2013), Fénix Editora, Universidad de Sevilla), 97-124
[21] Gheorghe, M.; Ipate, F.; Konur, S., Kernel P systems and relationships with other classes of P systems, (Gheorghe, M.; etal., Multidisciplinary Creativity, (2015), Spandugino Publishing House), 64-76
[22] Gheorghe, M.; Ipate, F.; Lefticaru, R.; Pérez-Jiménez, M. J.; Ţurcanu, A.; Valencia-Cabrera, L.; García-Quismondo, M.; Mierlă, L., 3-COL problem modelling using simple kernel P systems, Int. J. Comput. Math., 90, 4, 816-830, (2013) · Zbl 1274.68125
[23] Gheorghe, M.; Konur, S.; Ipate, F., Kernel P systems and stochastic P systems for modelling and formal verification of genetic logic gates, (Adamatzky, A., Advances in Unconventional Computing, Emergence, Complexity and Computation Series, vol. 1: Theory, (2015), Springer), 661-676
[24] Gheorghe, M.; Konur, S.; Ipate, F.; Mierlă, L.; Bakir, M. E.; Stannett, M., An integrated model checking toolset for kernel P systems, (Rozenberg, G.; etal., Proc. 16th Conference on Membrane Computing, Lecture Notes in Computer Science, vol. 9504, (2015)), 153-170 · Zbl 06546466
[25] Gheorghe, M.; Păun, Gh.; Pérez-Jiménez, M. J.; Rozenberg, G., Research frontiers of membrane computing: open problems and research topics, Internat. J. Found. Comput. Sci., 24, 547-624, (2013) · Zbl 1292.68065
[26] Holzmann, G. J., The model checker SPIN, IEEE Trans. Softw. Eng., 23, 5, 275-295, (1997)
[27] Ipate, F., Bounded sequence testing from deterministic finite state machines, Theoret. Comput. Sci., 411, 16-18, 1770-1784, (2010) · Zbl 1192.68414
[28] Ipate, F.; Gheorghe, M., Finite state based testing of P systems, Nat. Comput., 8, 4, 833-846, (2009) · Zbl 1185.68337
[29] Körner, H., On minimizing cover automata for finite languages in O(n log n) time, (Champarnaud, J.-M.; Morel, D., Proc. 7th Conference on Implementation and Application of Automata, Lecture Notes in Computer Science, vol. 2608, (2002)), 117-127 · Zbl 1033.68064
[30] Krishna, S. N.; Gheorghe, M.; Dragomir, C., Some classes of generalised communicating P systems and simple kernel P systems, (Bonizzoni, P.; etal., Proc. 9th International Conference on Computability in Europe, Milan, 1-5 July, Lecture Notes in Computer Science, vol. 7921, (2013)), 284-293 · Zbl 1387.68114
[31] Lefticaru, R.; Macías-Ramos, L. F.; Niculescu, I. M.; Mierlă, L., Agent-based simulation of kernel P systems with division rules using FLAME, (Leporati, A.; Zandron, C., Pre-Proc. 17th International Conference on Membrane Computing, Milan, 25-29 July, 2016, (2016)), 195-216
[32] Macías-Ramos, L. F.; Song, B.; Valencia-Cabrera, L.; Pan, L.; Pérez-Jiménez, M. J., Membrane fission: a computational complexity perspective, Complexity, 21, 6, 321-334, (2016)
[33] Macías-Ramos, L. F.; Valencia-Cabrera, L.; Song, B.; Song, T.; Pan, L.; Pérez-Jiménez, M. J., A P-lingua based simulator for P systems with symport/antiport rules, Fund. Inform., 139, 2, 211-227, (2015) · Zbl 1357.68065
[34] Mauri, G.; Leporati, A.; Porreca, A. E.; Zandron, C., Recent complexity-theoretic results on P systems with active membranes, J. Logic Comput., 25, 4, 1047-1071, (2015) · Zbl 1347.68141
[35] Păun, Gh., Computing with membranes, J. Comput. System Sci., 61, 1, 108-143, (2000) · Zbl 0956.68055
[36] Păun, Gh., Membrane computing - an introduction, (2002), Springer · Zbl 1034.68037
[37] (Păun, Gh.; Rozenberg, G.; Salomaa, A., The Oxford Handbook of Membrane Computing, (2010), Oxford University Press)
[38] Sburlan, D., A static sorting algorithm for P systems with mobile catalysts, An. Ştiinţ. Univ. “Ovidius” Constanţa Ser. Mat., 11, 1, 195-205, (2003) · Zbl 1084.68521
[39] Song, B.; Pérez-Jiménez, M. J.; Pan, L., Efficient solutions to computational problems by P systems with symport/antiport rules and membrane division, Biosystems, 130, 51-58, (2015)
[40] Valencia-Cabrera, L.; Orellana-Martín, D.; Martínez-del-Amor, M. A.; Riscos-Núñez, A.; Pérez-Jiménez, M. J., Polarizationless P systems with active membranes: computational complexity aspects, J. Autom. Lang. Comb., 21, 1-2, 107-123, (2016) · Zbl 1356.68071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.