Yu Jin ; Bosheng Song ; Yanyan Li ; Ying Zhu - Time-free solution to independent set problem using P systems with active membranes

fi:7618 - Fundamenta Informaticae, November 18, 2021, Volume 182, Issue 3 - https://doi.org/10.3233/FI-2021-2072
Time-free solution to independent set problem using P systems with active membranes

Authors: Yu Jin ; Bosheng Song ; Yanyan Li ; Ying Zhu

Membrane computing is a branch of natural computingwhich abstracts fromthe structure and the 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 problemusing P systems with active membranes, which solve the problem independent of the execution time of the involved rules.


Volume: Volume 182, Issue 3
Published on: November 18, 2021
Accepted on: August 13, 2021
Submitted on: June 25, 2021
Keywords: Computer Science - Computational Complexity


Share

Consultation statistics

This page has been seen 7 times.
This article's PDF has been downloaded 5 times.