×

Computing the maximum bisimulation with spiking neural P systems. (English) Zbl 1330.68069

Kelemen, Jozef (ed.) et al., Computation, cooperation, and life. Essays dedicated to Gheorghe Păun on the occasion of his 60th birthday. Berlin: Springer (ISBN 978-3-642-19999-8/pbk). Lecture Notes in Computer Science 6610, 151-157 (2011).
Summary: We use spiking neural P systems to produce in linear time a partition of the nodes of a graph, which is coarser than the maximum bisimulation.
For the entire collection see [Zbl 1216.68029].

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] van Benthem, J.: Model correspondence theory. PhD thesis, Universiteit van Amsterdam, Instituut voor Logica en Grondslagenonderzo ek van Exacte Wetenschappen (1976)
[2] Milner, R.: Operational and Algebraic Semantics of Concurrent Processes. In: Handbook of Theoretical Computer Science, vol. B, Formal Models and Sematics (B), pp. 1201–1242 (1990) · Zbl 0900.68217 · doi:10.1016/B978-0-444-88074-1.50024-X
[3] Aczel, P.: Non-Well-Founded Sets. CSLI Lecture Notes, vol. 14. CSLI, Stanford (1988) · Zbl 0668.04001
[4] Clarke, E., Grumberg, O., Peled, D.: Model Checking. The MIT Press, Cambridge (1999)
[5] Kanellakis, P.C., Smolka, S.A.: CCS expressions, finite state processes, and three problems of equivalence. Information and Computation 86(1), 43–68 (1990) · Zbl 0705.68063 · doi:10.1016/0890-5401(90)90025-D
[6] Hopcroft, J.E.: An nlogn algorithm for minimizing states in a finite automaton. In: Kohavi, Z., Paz, A. (eds.) Theory of Machines and Computations, pp. 189–196. Academic Press, New York (1971) · doi:10.1016/B978-0-12-417750-5.50022-1
[7] Paige, R., Tarjan, R.E., Bonic, R.: A linear time solution to the single function coarsest partition problem. Theoretic. Comput. Sci. 40, 67–84 (1985) · Zbl 0574.68060 · doi:10.1016/0304-3975(85)90159-8
[8] Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973–989 (1987) · Zbl 0654.68072 · doi:10.1137/0216062
[9] Dovier, A., Piazza, C., Policriti, A.: An efficient algorithm for computing bisimulation equivalence. Theor. Comput. Sci. 311(1-3), 221–256 (2004) · Zbl 1070.68101 · doi:10.1016/S0304-3975(03)00361-X
[10] Rajasekaran, S., Lee, I.: Parallel Algorithms for Relational Coarsest Partition Problems. IEEE Trans. Parallel Distrib. Syst. 9(7), 687–699 (1998) · Zbl 05107450 · doi:10.1109/71.707548
[11] Saha, D.: An Incremental Bisimulation Algorithm. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol. 4855, pp. 204–215. Springer, Heidelberg (2007) · Zbl 1135.68500 · doi:10.1007/978-3-540-77050-3_17
[12] The P Systems Webpage, http://ppage.psystems.eu/
[13] Ceterchi, R., Sburlan, D.: Simulating boolean circuits with P systems. In: Martín-Vide, C., Mauri, G., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2003. LNCS, vol. 2933, pp. 104–122. Springer, Heidelberg (2004) · Zbl 1202.68187 · doi:10.1007/978-3-540-24619-0_8
[14] Ionescu, M., Sburlan, D.: Some applications of spiking neural P systems. Computing and Informatics 27(3+), 515–528 (2008) · Zbl 1389.68032
[15] Ceterchi, R., Pérez-Jiménez, M.J.: On simulating a class of parallel architectures. Int. J. Found. Comput. Sci. 17(1), 91–110 (2006) · Zbl 1088.68057 · doi:10.1142/S0129054106003711
[16] Ceterchi, R., Pérez-Jiménez, M.J., Tomescu, A.I.: Simulating the bitonic sort using P systems. In: Eleftherakis, G., Kefalas, P., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2007. LNCS, vol. 4860, pp. 172–192. Springer, Heidelberg (2007) · Zbl 1137.68378 · doi:10.1007/978-3-540-77312-2_11
[17] Ceterchi, R., Tomescu, A.I.: Implementing Sorting Networks with Spiking Neural P Systems. Fundam. Inform. 87(1), 35–48 (2008) · Zbl 1154.68049
[18] Ionescu, M., Păun, G., Yokomori, T.: Spiking Neural P Systems. Fundam. Inform. 71(2-3), 279–308 (2006) · Zbl 1110.68043
[19] Leporati, A., Zandron, C., Ferretti, C., Mauri, G.: Solving numerical NP-complete problems with spiking neural P systems. In: Eleftherakis, G., Kefalas, P., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2007. LNCS, vol. 4860, pp. 336–352. Springer, Heidelberg (2007) · Zbl 1137.68396 · doi:10.1007/978-3-540-77312-2_21
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.