2014 | OriginalPaper | Buchkapitel
Uniform Solution to Partition Problem Using P Systems with Membrane Division
verfasst von : Yun Jiang, Zhiqiang Chen
Erschienen in: Bio-Inspired Computing - Theories and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Cell-like P systems are a class of distributed and parallel computing models inspired from the structure and the functioning of living cells. Such systems with membrane division (corresponding to the mitosis behavior of living cells) can theoretically generate exponential working space in linear time, therefore providing a possible way to solve computational hard problems in feasible time by a space-time trade-off. In this work, we construct a family of P system with membrane division to solve Partition problems, and achieve a polynomial time solution (with respect to the size of the problems). Furthermore, we prove that the systems are constructed in a uniform manner and work in a confluent way.