An LMNtal program is written as an LMNtal process that represents hierarchical graphs (consisting of atoms, links and membranes) with rewrite rules for them. An LMNtal process is a multiset (bag) of the following:

atoms\( p(X_1,\dots,X_n) \)a graph node with a symbolic name \( p \) and an ordered sequence of links \( X_i \)
cells\( \{ \textit{Process}\,\} \)
\( m\{ \textit{Process}\,\} \)
a process enclosed with a membrane (curly braces),
optionally with a membrane name \( m \)
rules\( (\textit{Head}\ \texttt{:-}\ \textit{Body}\,) \)a rewrite rule for processes, explained below

The elements of a multiset are either separated by commas (e.g., a(X), b(X)) or terminated by periods (e.g., a(X). b(X).).

Links names are written using alphanumeric tokens starting with capital letters (e.g., X, Res). The other alpha-numeric tokens are treated as atom or membrane names (e.g., foo, 123). Quoted symbols can also be used for atom or membrane names (e.g., "foo", 'bar', [:baz:]).

Since link names stand for endpoints of one-to-one links, each link name in a well-formed process must occur at most twice, and each link name in a well-formed rule must occur exactly twice. A link occurring only once in a process is called a free link. A process with no free link is called a closed process.

For instance, the first example below is a well-formed process with one free link Y, and the second and the third examples are well-formed closed processes.

plus(AX,B,Y), times(A,X,AX), a(A), b(B), x(X).
p(X,Y), p(Y,Z), p(Z,X), p(U,U).
out(X), { in(X), out(Y), { in(Y), a, b }}.

LMNtal comes with a special atom '=', called a connector, as will be described later.

Term Notation

Atoms with n links are often used to represent (n-1)-ary terms, where the nth link of the atom represents the "entry point" of the term. Since each link name occurs at most twice, we can abbreviate

\( p(s_1,\dots,s_m),\ q(t_1,\dots,t_n) \)


\( p(s_1,\dots,s_{k-1}, q(t_1,\dots,t_{n-1}),s_{k+1},\dots,s_m) \)

if \( t_n \) and \( s_k \) are the same link name. For example,


can be abbreviated to


This can be written also as


because LMNtal regards c(1,c(2,n),L0) and L0=L1, c(1,c(2,n),L1) as identical (see Connectors below) and we can use the term notation for the latter to obtain L0=c(1,c(2,n)) .

Abbreviated form is provided also for membranes. For an atom name p and a membrane, \( p(\dots, \{\dots\}, \dots) \) stands for a process \( p(\dots, X, \dots), \{\texttt{+}X, \dots\} \) .

List Notation

The Prolog list syntax can be used in LMNtal. List constructor atoms have three arguments and the name '.' . For example,

'.'(A,Tmp,X), '.'(B,Rest,Tmp), '[]'(Rest)

can be abbreviated to both of the following:

X=[A,B|Rest], Rest=[]


Binary atoms of the form X=Y are called connectors. A connector states that the two links are interconnected (in zero steps). For example, ( p(A,X,C), X=B ) is equivalent to p(A,B,C) as well as to ( p(A,B,X), C=X ) and C=p(A,B).

Connectors are typically used in the base case of a recursive definition:

( append([],Y,Res)    :- Res=Y ),
( append([A|X],Y,Res) :- Res=[A|R], append(X,Y,R)] )


The basic syntax of a rule is

\( (\textit{Head}\ \texttt{:-}\ \textit{Body}\,) \)

The enclosing parentheses can be omitted if periods are used to terminate the rule. Both of Head and Body are process templates. Head specifies processes to be rewritten and Body specifies the result of rewriting. Rules work only for the processes residing in the same membrane.

The full syntax of a rule that contains Guards will be explained in a separate section.

Process Templates

A process template is a multiset of the following:

atoms\( p(X_1,\dots,X_n) \)same as in a process
cells\( \{\textit{Template}\,\} \)
\( \{\textit{Template}\,\}/ \)
\( m\{\textit{Template}\,\} \)
\( m\{\textit{Template}\,\}/ \)
a process template enclosed with a membrane
rules\( (\textit{Head}\ \texttt{:-}\ \textit{Body}\,) \)allowed only in a Body
process contexts\( \texttt{\$}p \)
\( \texttt{\$}p\texttt{[}X_1,\dots,X_n\texttt{]} \)
\( \texttt{\$}p\texttt{[}X_1,\dots,X_n\texttt{|*}X\texttt{]} \)
matches a multiset of atoms and cells (see below)
rule contexts\( @p \)matches a multiset of rules

A cell template with a membrane name only matches a cell with the same membrane name. A cell template with '/' (the stable flag) only matches a stable cell, i.e., a cell containing no applicable rules inside it.

Process Contexts

A process context is a 'wildcard' for processes and represents a multiset of atoms and cells. The arguments \( X_1,\dots,X_n \) specify the set of free links that must exist in the matched process. The optional \( *X \) represents an arbitrary number of extra free links.

The form \( \texttt{\$}p \) is an abbreviation of \( \texttt{\$} p\texttt{[|*}X\texttt{]} \), i.e., a multiset of atoms and cells with no constraints on the occurrences of free links.

A process context must occur within a membrane in a head. Alternatively, it may either occur

  • in a head and an input position of a guard, or
  • in an output position of a guard.

Process contexts of the latter kinds are called typed process contexts; see Guards for details.

You can abbreviate

\( p(s_1,\dots,s_{k-1},X,s_{k+1},\dots,s_m),\,\texttt{\$}q\texttt{[}X\texttt{]} \)


\( p(s_1,\dots,s_{k-1},\texttt{\$}q,s_{k+1},\dots,s_m) \).

Reload   New Edit Freeze Diff Upload Copy Rename   Front page List of pages Search Recent changes Backup   Help   RSS of recent changes
Last-modified: 2019-10-25 (Fri) 14:45:30 (732d)