Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Decidability of Termination Problems for Sequential P Systems with Active Membranes
verfasst von : Michal Kováč
Erschienen in: Evolving Computability
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
Abstract
We study variants of P systems that are working in the sequential mode. Basically, they are not computationally universal, but there are possible extensions that can increase the computation power. Extensions that implement a notion of zero-checking, are often computationally universal. P systems with an ability to create new membranes are a rare exception as they are known to be computationally universal even in the sequential mode without using a dedicated zero-check operation. In this paper we show a result that seems surprising to us - the existence of an infinite computation for sequential P systems with active membranes is decidable. The standard construction of coverability tree is extended to provide an algorithm for detecting infinite loops. In addition, we show that the existence of a halting computation is undecidable as it can be reduced to reachability of register machines.