Using well-structured transition systems to decide divergence for catalytic P systems

摘要

P systems are a biologically inspired model introduced by Gheorghe Paun with the aim of representing the structure and the functioning of the cell. Since their introduction, several variants of P systems have been proposed and explored. We concentrate on the class of catalytic P systems without priorities associated with the rules. We show that the theory of Well-Structured Transition Systems can be used to decide the divergence problem (i.e. checking for the existence of an infinite computation) for such a class of P systems. As a corollary, we obtain an alternative proof of the nonuniversality of deterministic catalytic P systems, an open problem recently solved by Ibarra and Yen.