Partition
=======================

Description
-----------

This example try to solve the well-known NP-complete problem of partition problem, by means of the so called simple Kernel P systems (skP systems).

Model
-----

The corresponding P-Lingua file is the following::

	@model<simple_kernel_psystems>

	k=3;

	def main()
	{
	  call partition();
	}

	def partition()
	{
	  call init_cells();  
	  call init_multisets();  
	  call init_rules();
	}

	def init_cells()
	{
	  @mu = [[]'1 []'2]'0;
	}

	def init_multisets()
	{
	  @ms(1) = S;
	  @ms(2) = A{1};
	  @ms(2) += v{i}*w{i} : 1<=i<=n;

	  /* Environment alphabet: */
	}

	def init_rules()
	{
	  /* C1 */
	  /* r1,1 */ @guard {>=+T} ? [S]'1 --> [yes]'0;
	  /* r1,2 */ @guard {>=+F} && {>=-T} ? [S]'1 --> [no]'0;

	  /* C2 */
	  /* r2,i */ [A{i}]'2 |--> [B{i},A{i+1}]'2 [A{i+1}]'2 : 1<=i<n;
	  /* r2,n */ [A{n}]'2 |--> [B{n},X]'2 [X]'2;
	  /* r2,i,j */ @guard {=+B{i}}&&{=-B{j}}&&{=+X} || {=-B{i}}&&{=+B{j}}&&{=+X} ? [v{i},v{j}]'2 --> [v]'2 : 1<=i<n, 1<=j<=n;
	  /* r2,n+1 */ [X]'2 --> [Y]'2;
	  /* r2,n+2 */ @guard (|{{>=+v{l1}}}:{1<=l1<=n}) || {<>+v*k} ? [Y]'2 --> [F]'1;
	  /* r2,n+3 */ @guard (&{{>=-v{l2}}}:{1<=l2<=n}) &&{=+v*k} ? [Y]'2 --> [T]'1;
	}

Files
-----

A first run
+++++++++++

The initial **model** presented above was **extended** to solve not only the decission problem but also the collection of possible partitions for a given instance of the problem.

.. container:: boldlink

    * `Custom application <http://www.gcn.us.es/redmine/dmsf/files/7974/download>`_, defining the needed input and output tables for partition problem.
    * `Model file <http://www.gcn.us.es/redmine/dmsf/files/7975/download>`_, P-Lingua file with the parametrized file specifying the family of P systems for solving the partition problem. The custom interface enable the user to introduce the data corresponding to each different scenario.
    * `Scenario file <http://www.gcn.us.es/redmine/dmsf/files/7973/download>`_, for a specific instance of the problem (that is, a specific graph to set the partition to).

Final results
+++++++++++++

.. image:: images/PartitionChart.png
   :align: center
   :width: 70%


The original model
++++++++++++++++++

These are the needed files for the original model:

* `App <http://www.gcn.us.es/redmine/dmsf/files/2956/download>`_, defining the needed input and output tables for partition problem.
* `Model <http://www.gcn.us.es/redmine/dmsf/files/2955/download>`_, P-Lingua file with the parametrized file specifying the family of P systems for solving the partition problem. The custom interface enable the user to introduce the data corresponding to each different scenario.
* `Scenario <http://www.gcn.us.es/redmine/dmsf/files/2954/download>`_, for a specific instance of the problem (that is, a specific graph to set the partition to).


References
----------

* `Kernel P Systems - Version I <http://www.gcn.us.es/files/11bwmc/097_gheorghe_ipate.pdf>`_ (`detailed publication info <http://www.gcn.us.es/?q=node/959>`_).
* `Solving the partition problem by using tissue-like P systems with cell division <http://www.gcn.us.es/6BWMC/volume/agustin.pdf>`_ (`detailed info <http://www.gcn.us.es/?q=node/438>`_).
* `A linear time solution to the partition problem in a cellular tissue-like model <http://openurl.ingenta.com/content?genre=article&issn=1546-1955&volume=7&issue=5&spage=884&epage=889>`_ (`detailed <http://www.gcn.us.es/?q=node/517>`_).