Vertex cover

Description

This example tries to solve the well-known NP-complete problem of Vertex Cover, 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>

def main()
{
  call vertex_cover();
}

def vertex_cover()
{
  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},s;
  @ms(2) += A{e{i,1},e{i,2}} : 1<=i<=ne;

  /* 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{1}]'2 [X{1}]'2;
  /* r2,n+i */ @guard {=+X{1}} ? [B{i}]'2 --> [B{i},b]'2 : 1<=i<=n;
  /* r2,2n+i */ [X{i}]'2 --> [X{i+1}]'2 : 1<=i<=2;
  /* r2,2n+3 */ @guard {>+b*k}&&{=+X{2}} ||
                                |{{=+A{i1,j1}}&&{=-B{i1}}&&{=-B{j1}}&&{=+X{2}}}:{1<=i1<n,2<=j1<=n} ?
                                [s]'2 --> []'2;
  /* r2,2n+4 */ [X{3},s]'2 --> [T]'1;
  /* r2,2n+5 */ @guard {=-s} ? [X{3}]'2 --> [F]'1;

}

Files