Time-free Solution to Independent Set Problem using P Systems with Active Membranes

• Autorzy: Nguyen Viet Dung , Pham Ba Thai , Phan Thuan Do

Identyfikatory

DOI

10.3233/FI-2021-2073

• Języki publikacji: EN

Abstrakty

EN

Membrane computing is a branch of natural computing aiming to abstract computing models from the structure and functioning of living cells. The computation models obtained in the field of membrane computing are usually called P systems. P systems have been used to solve computationally hard problems efficiently on the assumption that the execution of each rule is completed in exactly one time-unit (a global clock is assumed for timing and synchronizing the execution of rules). However, in biological reality, different biological processes take different times to be completed, which can also be influenced by many environmental factors. In this work, with this biological reality, we give a time-free solution to independent set problem using P systems with active membranes, which solve the problem independent of the execution time of the involved rules.

Słowa kluczowe

EN

permutation graph; trapezoid graph; induced matching; sweep line; disjoint set

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 182, nr 3
• Strony: 243--255
• Opis fizyczny: Bibliogr. 33 poz., rys

Twórcy

autor

Nguyen Viet Dung

• Hanoi University of Science and Technology

autor

Pham Ba Thai

• Hanoi University of Science and Technology

autor

Phan Thuan Do

• Hanoi University of Science and Technology

Bibliografia

• [1] P˘aun Gh. Computing with membranes, Journal of Computer and System Sciences, 2000. 61(1):108-143. doi:10.1006/jcss.1999.1693.
• [2] P˘aun Gh, Rozenberg G, Salomaa A. Membrane computing with external output, Fundamenta Informaticae, 2000. 41(3):313-340.
• [3] Jiang S, Wang Y, Xu J, Xu F. The computational power of cell-like P systems with Symport/Antiport rules and promoters, Fundamenta Informaticae, 2019. 164(2-3):207-225. doi:10.3233/FI-2019-1763.
• [4] Mart´ın-Vide C, P˘aun Gh, Pazos J, Rodr´ıguez-Pat´on A. Tissue P systems, Theoretical Computer Science, 2003. 296(2):295-326. doi:10.1016/S0304-3975(02)00659-X.
• [5] Song B, Huang S, Zeng X. The computational power of monodirectional tissue P systems with symport rules, Information and Computation, 2021. 104751. doi:10.1016/j.ic.2021.104751.
• [6] Song B, Li K, Zeng X. Monodirectional evolutional symport tissue P systems with promoters and cel division, IEEE Transactions on Parallel and Distributed Systems, 2021. doi:10.1109/TPDS.2021.3065397.
• [7] Song B, Zeng X, Jiang M, P´erez-Jim´enez M J. Monodirectional tissue P systems with promoters, IEEE Transactions on Cybernetics, 2021. 51(1):438-450. doi:10.1109/TCYB.2020.3003060.
• [8] Ionescu M, P˘aun Gh, Yokomori T. Spiking neural P systems, Fundamenta Informaticae, 2006. 71(2-3):279-308.
• [9] Zhang X, Zeng X, Pan L. Weighted spiking neural P systems with rules on synapses, Fundamenta Informaticae, 2014. 134(1-2):201-218.
• [10] Carandang JP,— Cabarle FG C, Adorna HN, Hernandez NH S, Mart´ınez-del-Amor M ´A. Handling nondeterminism in spiking neural P systems: Algorithms and simulations, Fundamenta Informaticae, 2019. 164(2-3):139-155. doi:10.3233/FI-2019-1759.
• [11] Lazo PPL, Cabarle FGC, Adorna HN, Yap JM C. A return to stochasticity and probability in spiking neural P systems, Journal of Membrane Computing, 2021. 134(1-2):1-13.
• [12] Pan L, P˘aun Gh. Spiking neural P systems with anti-spikes, International Journal of Computers, Communications & Control, 2009. 4(3):273-282. doi:10.15837/ijccc.2009.3.2435.
• [13] Pan L, P˘aun Gh. Spiking neural P systems: An improved normal form, Theoretical Computer Science, 2010. 411(6):906-918. doi:10.1016/j.tcs.2009.11.010.
• [14] Pan, L., P˘aun, Gh., P´erez-Jim´enez, M. J.: Spiking neural P systems with neuron division and budding, Science China Information Sciences, 54(8), 2011, 1596-1607.
• [15] Pan L, Zeng X, Zhang X. Time-free spiking neural P systems, Neural Computation, 2011. 23(5):1320-1342. doi:10.1162/NECO a 00115.
• [16] Pan L, Zeng X, Zhang X, Jiang Y. Spiking neural P systems with weighted synapses, Neural Processing Letters, 2012. 35(1):13-27. doi:10.1007/s11063-011-9201-1.
• [17] P˘aun Gh. Membrane Computing. An Introduction, Springer-Verlag, Berlin, Heidelberg, 2002.
• [18] P˘aun Gh, Rozenberg G, Salomaa A. Handbook of Membrane Computing, Oxford University Press New York, 2010. ISBN:9780199556670.
• [19] Song B, Li K, Orellana-Mart´ın D, P´erez-Jim´enez MJ, P´erez-Hurtado I. A survey of nature-inspired computing: membrane computing, ACM Computing Surveys, 2021. 54(1):1-31. doi:10.1145/3431234.
• [20] T¸ urlea A, Gheorghe M, Ipate F, Konur S. Search-based testing in membrane computing, Journal of Membrane Computing, 2019. 4(1):241-250. doi:10.1007/s41965-019-00027-w.
• [21] Zandron C. Bounding the space in P systems with active membranes, Journal of Membrane Computing, 2020. 2(2):137-145.
• [22] P˘aun Gh. P systems with active membranes: attacking NP-complete problems, Journal of Automata, Languages and Combinatorics, 2001. 6(1):75-90. doi:10.25596/jalc-2001-075.
• [23] Alhazov A, Mart´ın-Vide C, Pan L. Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes, Fundamenta Informaticae, 2003. 58(2):67-77.
• [24] Alhazov A, Pan L, P˘aun Gh. Trading polarizations for labels in P systems with active membranes, Acta Informatica, 2004. 41(2-3):111-144.
• [25] Pan L, Diaz-Pernil D, P´erez-Jim´enez MJ. Computation of Ramsey numbers by P systems with active membranes, International Journal of Foundations of Computer Science, 2011. 22(1):29-38. doi:10.1142/S0129054111007800.
• [26] Pan L, Mart´ın-Vide C. Solving multidimensional 0–1 knapsack problem by P systems with input and active membranes, Journal of Parallel and Distributed Computing, 65(12), 2005, 1578-1584.
• [27] Pan L, Mart´ın-Vide C. Further remark on P systems with active membranes and two polarizations, Journal of Parallel and Distributed Computing, 2006. 66(6):867-872.
• [28] P˘aun Gh, Suzuki Y, Tanaka H, Yokomori T. On the power of membrane division in P systems, Theoretical Computer Science, 2004. 324(1):61-85. doi:10.1016/j.tcs.2004.03.053.
• [29] Valencia-Cabrera L, P´erez-Hurtado I, Mart´ınez-del-Amor M. Simulation challenges in membrane computing, Journal of Membrane Computing, 2020, pp. 1-11. doi:10.1007/s41965-020-00056-w.
• [30] Cavaliere M, Sburlan D. Time–independent P systems, in: Lecture Notes on Computer Science, Vol. 3365, Springer–Verlag, Berlin, 2005 pp. 239-258. doi:10.1007/978-3-540-31837-8 14.
• [31] Cavaliere M. Time-Free Solutions for Hard Computational Problems, In Tenth Brainstorming Week on Membrane Computing, Sevilla, 2012, 23.
• [32] Song T, Mac´ıas-Ramos LF, Pan L, P´erez-Jim´enez MJ. Time-free solution to SAT problem using P systems with active membranes, Theoretical Computer Science, 2014. 529:61-68. doi:10.1016/j.tcs.2013.11.014.
• [33] Rozenberg G, Salomaa A. (Eds.). Handbook of Formal Languages, Vol. 1-3, Springer-Verlag, Berlin, 1997. ISBN:978-3-642-63863-3.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)