Regarding execution strategies

posted Oct 29, 2012, 4:06 AM by Ciprian Dragomir

After a series of sessions of microscopic analysis on the subject, we've concluded that the kP system execution strategy should be restricted to a small array of axioms and operators. The reasons for this reduction in the specification is not just the correlated reduction in complexity but also the avoidance of conflicting situations which require torturous resolutions.

Thus, we emphasize the basic rules (syntactical but with intuitive semantics) that allow us to formulate the logic of rule execution in a compartment:

<atom> ::= "" | <r>

<alternative> ::= "{" <r1> " " <r2> " " … " " <rn> "}"

<operand> ::= <atom> | <alternative>

<iteration> ::= <operand>"*" | <operand>"^"

<exec> ::= <operand> | <iteration> | <operand> "&" <exec> | <iteration> "&" <exec>


Using the above syntax (and implicit semantics) we can assemble the following compositional strategies:


  1. S1 = r1 & r2 & r3
  2. S2 = r1 & {r2  r3} & r4
  3. S3 = {r1  r2 r3}^ & r4 & {r5 r6}*
  4. S4 = r^
  5. S5 = r* & r^


Using an XML notation, we can express a strategy by simply using of the nesting of tags. We illustrate example no 3 from the listing above:





<rule name="r1" />

<rule name="r2" />

<rule name="r3" />


<rule name="r4" />


<rule name="r5" />

<rule name="r6" />




NOTE: The above directives are considered for rewriting and communication rules only. We will further extend the specification to support rules which change the structure of a kP system. Intuitively, the same principles apply with the exception of iteration (a membrane division/link creation/destruction rule can only be applied once). 

Grammar Updates

posted Aug 13, 2012, 2:06 AM by Laurentiu Marian Mierla

Hello everyone,

I have uploaded three grammar files into the Resources section of this website:
1. kp systems-spec v3.doc, the BNF description of the kP system language, updated as follows:
- a pair of enclosing braces has been added to the constructions denoting sets (link sets, rule sets) in order to avoid a LL(*) syntax
- the execution strategy can reside only inside the enclosing braces of a rule set and is terminated with a "." symbol
- the text token has been removed, being replaces by a semantic rule accepting only an identifier or a natural
- the semantic rules denoting boolean expressions for guards have been rewritten such that to reflect the following precedence of the logical operators
"|" > "&" > "!" > "(...)"
 , where the operators with lower precedence have greater priority
- the semantic rules denoting expressions for execution strategies have been rewritten such that to reflect the following precedence of the execution strategy operators
"&" > "|" > "||" > "*" = "^" > "(...)"
 , where the operators with lower precedence have greater priority;
2. kPLingua v0.3.g, the ANTLR EBNF description of the kP system language, containing now the corresponding rewriting rules for building the AST;
3. kPLingua v0.3 Tree Grammar.g, the tree grammar file needed by ANTLR for walking the generated AST.

I currently work on populating the tree grammar file with java instructions for building the Psystem object and its corresponding membranes, rules and links, and I expect to have some final results tomorrow.

Grammar Updates

posted Aug 6, 2012, 4:48 AM by Laurentiu Marian Mierla   [ updated Aug 6, 2012, 4:51 AM ]

Please find in the Resources section of this website, the combined grammar of the two available specifications. The EBNF specification of the language can be found in the "kp systems-spec v2.doc" file, while the ANTLR version resides into the "kPLingua v0.3.g" file.

While merging the two current specifications, I have identified two important problems:
1. The current syntax is LL(*) rather than LL(k). It can be handled by ANTLR using its backtrack capability, but I suggest to review it with regard to the following specific construction:

label2 - _label1.
@ms(3)[label4] 2a 3d - label2.

, where the parser needs to analyze a variable number of lookahead symbols, until the appearance of the "-" symbol, in order match @ms(3)[label4] 2a 3d as being produced by the <link> rule and not the <statement> rule.
We can overcome this issue by considering some wrapping symbols for the constructions belonging to an instruction set (link set and rule set), as below:

@ls {
label2 - _label1.
@ms(3)[label4] 2a 3d - label2.

2. By defining the <text> token as

<text> ::= <letter_digit_underscore> {<letter_digit_underscore>}

, this will allow for constructions such as 5a to be matched as being text tokens and not as a multiset unit. Because the tokenisation process is being done before the syntactical analysis and because the <multiset-unit> rule will expect to receive a number, followed by an identifier, the <multiset-unit> matching process will fail because it actually receives a text token.

In the current merged specification I defined the text token as being

<text> ::= <text-token> | <identifier> | <natural>

<text-token> ::= <underscore> {<letter_digit_underscore>}

, until we make a decision regarding this issue.

If it is the case, I suggest to have a Skype conference tomorrow morning, if everyone is available.

According to the current grammar, the parser can match inputs as the one blow:

/* This is a comment block. Comments can also be inline using //
 * (same as in java, c# etc).
@ms(_type)[_label1] 5a 3b c 2d //introduce a new membrane instance of type _type
@ms(_1)[label2] 5t 4v 6x 6z

/* specify the links between different membranes */
label2 - _label1.
label2 - @ms(2) 4a.
@ms(3)[label4] 2a 3d - label2.

//a new membrane instance of type 1, without initial multisets

@rs(1) //define the rule set for membrane type 1
[r1] =4a & 4b: a -> b c .
[r2] >= 2c: 2c -> a 3b .
[r3] >= 3c & !2a: 'env -> 2a 3b .
[r3] !(!2a): 2a 3b -> 'env .
[r4] (!2b) & ((2a) | 2b): c -> # . //membrane dissolution
@s (r1 | r2)* & r3 & r1^ //execution strategy

//rule set without execution strategy
a -> b .
a -> # .

[r1] 2c -> c{2} a . //communication to connected membranes of type 2
[r2] a -> 2c (3a 3b){2} .
[r3] a -> @ms(3) a 2c @ms(3) a 3c # . //membrane division
[r4] 2c: a -> @ms(3) a @ms(3) a . //membrane creation
@s (r1 & r2)* & (r3 || r4) | (r3)^

Updates - MG

posted Jul 31, 2012, 5:19 AM by Marian Gheorghe

I have seen some updates, both as posts and in Resources. I would ask Laurentiu to consider the last file uploaded by Luis in Repository and check whether there are features there which are not in the ANTLR code.


kP lingua grammar v 0.2

posted Jul 30, 2012, 4:10 PM by Ciprian Dragomir

kP lingua grammar - BNF

kP lingua grammar - BNF - v 0.1 RC

posted Jul 30, 2012, 7:15 AM by Ciprian Dragomir

Please find bellow my attempt at formalising the syntax of our new language for kernel P systems. The generative style of the BNF notation also helps in detecting potential inconsistencies/ambiguities. Please don't find the comment box intimidating should you come across any oversights.

<kPsystem> ::= <comment> | <statement> <kPsystem>

<comment> ::= "/*" <text> "*/" | "//" <text> "\n"

<statement> ::= <empty> | <multiset> | <multiset-link> | <ruleset> <statement>

<multiset> ::= <multiset-instance> | <multiset-ref>
<multiset-instance> ::= "@ms(" <membrane-type> ")" <optional-label> <multiset-value>
<multiset-ref> ::= <label-ref> <optional-label> <multiset-value>

<multiset-value> ::= <empty> | <multiset-unit> <space> <multiset-value> 
<multiset-unit> ::= <optional-multiplicity> <object>

<multiset-link> := <multiset> "-" <multiset>

<ruleset> ::= "@rs" <membrane-type> <rules> <execution-strategy>
<rules> ::= <empty> | <rule> "." <rules>
<rule> ::= <optional-label> <optional-guard> <lhs> "->" <rhs>

<guard> ::= <operator> <multiset-unit> <guard> ":"
<operator> ::= "=" | "!" | ">" | "<" | ">=" | "<="

<lhs> ::= <multiset-value>
<rhs> ::= <targeted-multiset-value> <multiset-instance-set> <optional-dissolution>

<targeted-multiset-value> ::= <empty> | <multiset-unit> <target> <space> <targeted-multiset-value>
<target> ::= <empty> | "{" <membrane-type> "}" 
<multiset-instance-set> ::= <empty> | <multiset-instance> <multiset-instance-set>

<optional-dissolution> ::= <empty> | <dissolution>
<dissolution> ::= "#"

<optional-execution-strategy> ::= <empty> | <execution-strategy>
<execution-strategy> ::= "@s" <exec>
<exec> ::= <skip> | <label-ref> | <exec-binary> | <exec-unary>
<exec-binary> ::= <exec-seq> | <exec-choice> | <exec-nondeterministic>
<exec-seq> ::= <exec> "&" <exect>
<exec-choice> ::= <exec> "|" <exec>
<exec-nondeterministic> ::= <exec> "||" <exec>
<exec-unary> ::= <exec-exhaustive> | <exec-arbitrary>
<exec-exhaustive> ::= <exec> "^"
<exec-arbitrary> ::= <exec> "*"

<optional-label> ::= <empty> | <label>
<optional-multiplicity> ::= <empty> | <natural>
<natural> ::= <zero> | <non-zero-digit> <natural>
<zero> ::= "0"
<non-zero-digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

<membrane-type> ::= <text>
<label> ::= "[" <text> "]"
<label-ref> ::= <text>
<space> ::= " "
<empty> ::= ""
<skip> ::= "\>"

The execution strategy of a kernel P system

posted Jul 26, 2012, 6:28 AM by Ciprian Dragomir

kP system - Execution Strategy Specification

A kernel P system language proposal

posted Jul 25, 2012, 5:50 PM by Ciprian Dragomir   [ updated Jul 30, 2012, 2:33 AM by Laurentiu Marian Mierla ]

A few days ago, we were discussing the support of pLingua for kP systems and debating over what elements we need to include and what sort of notation should we adopt, such that: a) it doesn't conflict with the existing pLingua standards and conforms with universal elements (such as the indexed declarations) b) is coherent, intuitive, simple and succinct.

Given these preliminary goals, I drafted a compact and tidy language for our new model. It steps outside the boundaries and constraints imposed by pLingua, borrowing some notations still. I'm presenting this approach below, requesting feedback/criticism/comments. If it is considered worthwhile, then we can further develop this idea into a robust language.

Here are some insights:
- we do not declare types, they are inferred by the instance declarations (i.e. they are specified on the fly)
- the "@" signifies the introduction of an element, an instantiation, the insertion of something new; that is the process of declaring and instantiating are merged into a single statement - we can specify new membrane instances, new rule sets and new execution strategies.
- a multiset is denoted by a space separated set of objects (strings), prefixed by a number, the multiplicity. So 5a 3b c is a multiset that contains 5 as, 3 bs and one c.
- "[label_name]" applies the label "label_name" to the respective entity. Labels can be applied to membrane instances and to rules. These can later be referred using these labels like variables. Items can also be re-labelled, just as the same variable name can be applied to a new instance (i.e. the labels act as pointers). 

I will attempt to document this proposal more elaborately in the days to follow, although I am hoping there is no need for a detailed description of each statement or operator.

Demonstrating the notation on a synthetic example.

/* kP system - language draft v1.0 */

/* This is a comment block. Comments can also be inline using //
 * (same as in java, c# etc). 
@ms(1)[label1] 5a 3b c 2d  //introduce a new membrane instance of type 1
- @ms(1) 3f 4g
- @ms(1) a
- @ms(2) 4f 5g
- @ms(3) 

//tree structure declaration, we make use of the indentation to distinguish between levels
@ms(1)[label2] 5t 4v 6x 6z
- @ms(1) 2d 3c
- @ms(2) 4d
- @ms(2) 6y
- @ms(2) 6y
- @ms(3)[label3] 7b a f
- @ms(3) 4f

label3 - @ms(2) 4a
label3 - label1
+ @ms(5)[label4] 2a 3d
+ @ms(5) g
+ @ms(1) 3a 3b

//chain membranes; the + operator is equivalent to \t- (tab as indent followed by - link creation operator)
+ @ms(2) 4e r 
+ label1 
+ label4 
+ @ms(1) 2a 2b
@rs(1) //define the rule set for membrane type 1
[r1] 4a 4b: a -> b c .
[r2] >= 2c: 2c -> a 3b .
[r3] !2b & (2a | 2b): c -> # . //membrane dissolution
@s (r1 || r2)* & r3 //execution strategy

a -> b .
a -> c # .
a: - {1} . //link creation
b: \- {1} . //link destruction

[r1] 2c -> c{2} a . //communication to connected membranes of type 2
[r2] a -> 2c (3a 3b){2} .
[r3] a -> @ms(3) a 2c @ms(3) a 3c # . //membrane division
[r4] 2c: a -> @ms(3) a @ms(3) a . //membrane creation
@s (r1 & r2)* & (r3 | r4)

Off we go

posted Jul 12, 2012, 2:10 AM by Ciprian Dragomir

During our last meeting, Marian and I have identified several issues in the kP system formalism, issues which need to be addressed. In this regard, we refer to our findings in an open discussion where all opinions, comments and suggestions are welcome.


  1. Target indication / transfer modes

Under a closer inspection on the communication between kP system compartments, we concluded that the referral to cells via type only can pose certain questions about avoiding unwanted behaviour. Take for instance the case when a cell of type n creates 3 "child" cells (i.e. compartments which have a link to the cell that performed the genesis), and suppose the parent cell contains a communication rule which addresses cells of the same type n, then we have a situation where objects are just passed from one cell to another and also to themselves if the destination evaluator includes the cell itself (because the target type is the same as the sender's type. Of course this can be avoided programmatically in most cases, but should we allow for this possibility where the behaviour of the system is rather non-sensuous?

Another related matter which requires elucidation is the target selection itself. Since we use a compartment type to denote a destination, we always deal with a set of recipient membranes. Hence, we must specify the transfer mode: is it replication, is a target compartment non-deterministically chosen or is the multiset broken down into arbitrary multisets, then allocated to a cell?

  1. Execution strategy and rules which alter the system's structure

 This is another aspect which needs clarification. More precisely, we must specify how these types of rules behave, when they are interspersed with object rewriting and communication rules. How do the sigma (execution strategy) operators apply on these or if they are restricted from any such indicators (which will be the case at least for the * operator since only one structure transformation rule is permitted per step per membrane), then what is a correct execution of these rules?

  1. New specification for execution strategies

Another topic of emphasis is the inclusion of relational operators to define execution strategies. These are roughly regarded as quantifiers or rather iteration indicators over rules or sets of rules; instead of using the star operator (exhaustive execution), we can us something like <= k, =k, >k etc to denote repetition or even non-deterministic execution - if the associated strategy is "<= 1", the rule can either execute (once) or not.

Although it seems a good solution to introduce these high level  operators to express conditional iterations of rules or blocks of rules, we may face certain situations where the semantics is not as obvious and needs clarification. One example is the use of > (greater than operator): this makes perfect sense when k = 0, however if k = 5 do we evaluate whether we can execute the rule at least 5 times? This seems rather redundant if we consider the alternative  representation, using a guard. The same goes for the "=" operator. If we cannot execute k times, do we not execute at all (this requires an evaluation of left hand side resources) and if we do execute until there are enough objects, then the operator is equivalent to "<=".


  1. Decisions on syntactical additions to accommodate for kP system features

We already have means for expressing some of the new P system elements, such as guards for rules.

The aim is to discuss the options available and decide on a clear and intuitive p lingua syntax which is to become the standard modelling language.

There were suggestions of guards preceding the rules but also a general desire to keep the language consistent with previous iterations.

1-9 of 9