Formal Veri cation of P Systems with Active Membranes through Model Checking - Florentin Ipate; Raluca Lefticaru; Ignacio Pérez-Hurtado; Mario J. Pérez-Jiménez; Cristina Tudose (2011)
Formal verification of P systems using model checking has attracted a significant amount of research in recent years. However, up to now only P systems with static structure have been considered. This paper makes significant advances in this area by considering P systems with active membranes, in particular P systems with division rules. The paper presents a theoretical framework for addressing this problem and reports on a complex case study involving a well-known NP-complete problem solved using P systems with membrane division rules. This is implemented in Promela and non trivial properties are verified using Spin.