Mario PÉREZ-JIMÉNEZ, Fernando SANCHO-CAPARRINI

Verifying a P System Generating Squares

 

Abstract.

In [1], an example of a P system generating exactly all the squares of natural numbers greater than or equal to 1 is given. Only an informal proof of this result is presented. In this paper we study a similar P system (only one evolution rule is modified). A formalization of the syntax of the P system following [3] is given, and we perform the verification of this P system through soundness and completeness: (a) every successful computation generates a square greater than or equal to 1 (soundness); (b) every natural number greater or equal to 1 is the output of a successful computation of the system (completeness). Then we establish the formal verification through the study of the critical points of the computations of the P system that give to us important information to characterize the successful computations.

 

Keywords: Natural Computing, Membrane Computing, Formal Verification.