Keywords

1 Introduction

The art of tiling plays an important role in human civilization. A two-dimensional pattern generating model called pasting system was introduced in the literature which glues two square tiles together at the edges. Later on two isosceles right angled triangular tiles are pasted together at the gluable edges and a new pasting system called triangular tile pasting system was introduced in [3].

Petri Nets are mathematical models introduced to model dynamic systems [15]. Tokens represented by black dots are used to simulate the dynamic activity of the system. Array token Petri Nets are models which generate array languages [12]. Array Token Petri nets have applications in the following areas namely character recognition, generation and recognition of picture patterns, tiling pattern and kolam patterns. Arrays are used as token. The transitions are associated with catenation rules. Firing of transitions catenate arrays to grow in bigger size.

The area of membrane computing is a new computability model called P system introduced by Gh. Păun inspired by the functioning of living cells. Ceterchi et al. [4] proposed a theoretical model of P-system called Array Rewriting P-system for generating two-dimensional patterns. Motivated by these studies a three-dimensional pattern generating model called tetrahedral tile pasting system and tetrahedral tile pasting P system were introduced in [9] by gluing two tetrahedral tiles at the glueable edges. In the literature the studies on membrane computing generating picture languages is very limited. We have used membrane computing to generate 3D Tetrahedral picture languages, in which we can generate both rectangular and non rectangular 3D pictures like stars, triangles, rhombuses, hexagons, octagons and some kolam patterns which are some of the interesting patterns.

In this paper we introduce 3D-Array token Petri Nets generating three-dimensional tetrahedral picture languages (3D-TetATPN) and this model is compared with K-Tabled Tetrahedral Tile Pasting System (K-TTTPS), Tetrahedral Tile Pasting P System (TetTPPS), Regular Tetrahedral Array Languages (RTAL) and Basic Puzzle Tetrahedral Array Languages (BPTAL) for generative powers. The patterns generated by the Petri Nets are useful in floor design, wall design and tiling.

2 Preliminaries

In this section we recall the notion of tetrahedral tiles, K-TTTPS and TetTPPS .

Definition 1

[9] A tetrahedral tile is a polyhedral which has four vertices, four faces and six edges. Each face is an equilateral triangle. \(f_4\) is the base of the tetrahedron(Fig. 1).

Fig. 1.
figure 1

A Tetrahedron.

Full size image

We consider tetrahedral tiles of the following four types, named as

figure a

\(f_4\) is the base \(V_1 V_2 V_3\) of the tetrahedral tile.

Definition 2

[9] A K-Tabled Tetrahedral Tile Pasting System (K-TTTPS) is a 4-tuple \(M = (\varGamma , E, P, t_0)\), where \(\varGamma \) is a finite set of tetrahedral tiles of the forms A and B. E is a set of edge labels of base of tetrahedral tiles A and B. P is a finite set of tables \(\{T_1, T_2, \dots T_K\}\) where \(T_1, T_2, \dots T_K\) (\(k \ge 1\)) are finite sets of pasting rules. \(t_0\) is the axiom pattern.

A tiling pattern \(t_{i+1}\) is generated from a pattern \(t_i\) in k stages. In each stage, the rules of the table \(T_i\) (\(i = 1, 2, \dots k\)) are applied in parallel to the boundary edges of the pattern obtained in the previous stage. When all the rules in P are applied one after the other in succession the pattern \(t_{i+1}\) is generated from \(t_i\). i.e. \(t_i \Rightarrow t_{i+1}\). We write \(t_0 {\mathop {\Rightarrow }\limits ^{*}} t_j\) if \(t_0 \Rightarrow t_1 \Rightarrow t_2 \Rightarrow \cdots \Rightarrow t_j\). The collection of all patterns generated by K-TTTPS derived from the axiom \(t_0\) using the pasting rules of the system M is denoted by \(T(M) = \{t_j \in \varGamma ^{***} : t_0 {\mathop {\Rightarrow }\limits ^{*}} t_j / j \ge 0\}\), where \(\varGamma ^{***}\) represents the set of all three-dimensional tetrahedral patterns obtained by gluing tetrahedral tiles of \(\varGamma \).

The family of all three-dimensional patterns generated by K-TTTPS is denoted as \({\mathcal L}\)(K-TTTPS).

Example 1

A one-tabled Tetrahedral Tile Pasting System, generating a sequence of three-dimensional patterns whose boundaries are hexagons and stars alternatively is given below:

\(M = (\varGamma , E, P, t_0)\) where

$$\begin{aligned}&E = \{a_1, a_2, a_3, b_1, b_2, b_3\}; P = \{T_1\};\\&T_1 = \{(a_1, b_1), (a_2, b_2), (a_3, b_3), (b_1, a_1), (b_2, a_2), (b_3, a_3)\} \end{aligned}$$
figure c

The first three members of T(M) are shown in Fig. 2.

Fig. 2.
figure 2

Hexagon and Star polyhedral.

Full size image

Definition 3

[9] A Tetrahedral Tile Pasting P system (TetTPPS) \(\varPi = (\varGamma , \mu , F_1, \dots ,F_m, R_1, R_2, \dots , R_m, i_0)\) where \(\varGamma \) is a finite set of labeled tetrahedral tiles; \(\mu \) is a membrane structure with m membranes, labeled in an one-to-one way with \(1, 2, \dots m\); \(F_1, F_2, \dots F_m\) are finite sets of three-dimensional picture patterns over tiles of \(\varGamma \) associated with the m regions of \(\mu \); \(R_1, R_2, \dots , R_m\) are finite sets of pasting rules of the type \((t_i, (x_i, y_i), tar)\), \(1 \le i \le n\) associated with the m regions of \(\mu \) and \(i_0\) is the output membrane which is an elementary membrane.

The computation process in TetTPPS is defined as, to each 3D-Picture pattern present in the region of the system, the pasting rule associated with the respective region should be applied in parallel to the boundary edges of the base of the tetrahedral tile. Then the resultant tetrahedral 3D-pattern is moved (remains) to another region (in the same region) with respect to the target indicator \(in_j\) (here) associated with the pasting rule. If the target indicator is out, then the resultant tetrahedral 3D-pattern is sent immediately to the next outer region of the membrane structure.

The computation is successful only if the pasting rules of each region are applied. The computation stops if no further application of pasting rule is applicable. The result of a halting computation consists of the 3D-picture patterns composed only of tetrahedral tiles from \(\varGamma \) placed in the membrane with label \(i_0\) in the halting configuration.

The set of all such tetrahedral 3D-patterns computed or generated by a TetTPPS \(\varPi \) is denoted by TetPL(\(\varPi \)). The family of all such languages TetPL(\(\varPi \)) generated by system \(\varPi \) with at most m membranes, is denoted by TetPL\(_m\)(TetTPPS).

Example 2

Consider the Tetrahedral Tile Pasting P System, TetTPPS

$$\varPi _1 = (\varGamma , \mu = [_1 [_2 [_3 ]_3 ]_2 ]_1, F_1, F_2, F_3, R_1, R_2, R_3, 3),$$

which generates a sequence of tetrahedral 3D-picuture patterns whose boundaries are hexagons, \(\mu \) indicates that the system has three regions one within another i.e. region 1 is the ‘skin’ membrane which contains region 2, which in turn contains region 3, \(i_0 = 3\) indicates that region 3 is the output region.

figure d
figure e
$$\begin{aligned} \begin{aligned} R_1&= \left\{ (B, (a_1, b_1), here), (A, (b_1, a_1), here), (B, (a_2, b_2), here),\right. \\&\left. (A, (b_3, a_3), here), (B, (a_3, b_3), here), (A, (b_2, a_2), in)\right\} \\ R_2&= \left\{ (B, (a_1, b_1), here), (A, (b_1, a_1), here), (B(a_2, b_2), here),\right. \\&\left. (A, (b_3, a_3), here), (B, (a_3, b_3), here), (A, (b_2, a_2), in), (A, (b_2, a_2), out)\right\} \\ R_3&= \emptyset . \end{aligned} \end{aligned}$$

Beginning with the initial object \(F_1\) in region 1, the pasting rule \(R_1\) is applied, where the rules in \(R_1\) are applied in parallel to the boundary edges of the picture pattern present in region 1. Once the rule \((A, (b_2, a_2), in)\) is applied, the generated 3D-pattern is sent to the inner membrane 2, and in region 2, the rules of \(R_2\) are applied in parallel to the boundary edges of the pattern generated in region 1. If the rule \((A, (b_2, a_2), out)\) is applied, the 3D-pattern generated is sent to region 1, and the process continues. Whereas if the rule \((A, (b_2, a_2), in)\) is applied the 3D-pattern generated is sent to region 3, which is the output region, wherein it is collected in the 3D-picture pattern language formed by TetTPPS\(\varPi _1\). TetTPPS\(\varPi _1\) is the tetrahedral 3D-Picture language whose boundary is the hexagon.

3 3D-Array Token Petri Nets

In this section we recall some notions of Petri Nets. For more details we refer to [15]. Here we introduce catenation rules and firing rules for 3D-Array token Petri Nets and Tetrahedral 3D-Array token Petri Nets structure.

Definition 4

[11] A Petri Net structure is a four tuple \(C = (P, T, I, O)\) where \(P = \{P_1, P_2, \dots P_n\}\) is a finite set of places, \(n \ge 0\), \(T = \{t_1, t_2, \dots t_m\}\) is a finite set of transitions \(m \ge 0\), \(P \cap T = \emptyset \), \(T \rightarrow P^\infty \) is the input function from transitions to bags of places and \(O : T \rightarrow P^\infty \) is the output function from transitions to bags of places.

Definition 5

[11] A Petri Net marking is an assignment of tokens to the places of a Petri Net. The tokens are used to define the execution of a Petri Net. The number and position of tokens may change during the execution of a Petri Net. The marking can be defined as an n-vector \(\mu = (\mu _1, \mu _2, \mu _3, \dots \mu _n)\) where \(\mu _i\) is the number of tokens in the \(P_i\), \(i = 1, 2, \dots , n\). We can also write \(\mu (P_i) = \mu _i\).

Definition 6

[11] A Petri Net C with initial marking \(\mu \) is called a marked Petri Net. A marked Petri Net \(M = (C, \mu )\) can also be written as \(M = (P, T, I, O, \mu )\).

When a transition is fired one token is removed from its input place and one token is placed in each of its output place. For example when \(t_1\) is fired in the following figure one token from place A is removed and one token is placed in both B & C which are the output places of \(t_1\).

figure f

Now we turn our attention to define Tetrahedral 3D Array Token Petri Net.

Catenation Rules

The catenation rules which glue any two tetrahedral tiles at the glueable edges are given below:

figure g
figure h
figure i
figure j
figure k
figure l
figure m
figure n
figure o
figure p

Now let us consider the hexagonal polyhedral , which is made up of gluing A-tetrahedral and B tetrahedral tiles. This H can be catenated to A and B - tetrahedral tiles in the following manner.

figure r
figure s
figure t
figure u
figure v
figure w

Firing Rules

The transitions of the Petri Net are associated with the catenation rules of the form where \(P, Q \in \{A, B, C, D, H\}\) and is any one of the above catenation rules. When transition fires, the array in the input place gets catenated according to the catenation rule and the resultant array is placed in the output place. The transitions will be enabled as per the following conditions.

  1. (i)

    All the input places will have the same array as token.

  2. (ii)

    If there is no label for the transition then the same array will be moved to all the output places.

  3. (iii)

    If there is a label i.e a catenation rule for the transition then the array in the input place gets catenated according to the catenation rule and the resultant array is moved to all the output places.

Example 3

If the input place of transition has the tetrahedral polyhedral

figure z

as token and the transition is attached to the rule then after the firing the output places of the transition will have the tetrahedral picture

figure ab

The tetrahedral tile - B is catenated in parallel manner to all the A-tetrahedral tiles in the right up direction. The 3D-array token Petri Net diagram is given below for the above transition.

figure ac

Definition 7

A 3D Tetrahedral Tile Array Token Petri Net (3D-TetATPN) is a six tuple \(N = (\varSigma , C, \mu , S, \sigma , F)\) where \(\varSigma \) is an alphabet of tetrahedral tiles or extended tetrahedral tiles (3D-picture made up of tetrahedral tiles), C is a Petri Net structure, \(\mu \) is an initial marking of 3D-pictures made up of tetrahedral tiles or extended tetrahedral tiles kept in some places of the net, S is a set of catenation rules, \(\sigma \) is a partial mapping which attaches rules to the various transitions of the Petri Net of the form , F is a subset of the set of places of the Petri Net where the final 3D-tetrahedral picture is stored after all the firing of the various possible transitions of the Petri Net.

Definition 8

The language generated by 3D-TetATPN is the set of all 3D-tetrahedral pictures stored in the final places of the Petri Net structure and is denoted by \({\mathcal L}(N)\).

Example 4

Consider the 3D-TetATPN \(N_1 = (\varSigma , C, \mu , S, \sigma , F)\) where \(\varSigma = \{R, A, B\}\) where , \(C = (P, T, I, O)\) where \(P = \{P_1, P_2, P_3, P_4, P_5\}\), \(T = \{t_1, t_2, t_3, t_4\}\). The initial marking \(\mu \) is the rhombus polyhedral R in the place of \(P_1\).

\(\sigma \) the mapping from the set of transitions to the set of rules is shown in Fig. 3 and \(F = \{P_5\}\).

Starting with R, on firing the sequence \(t_1t_2t_3t_4\), the rhombus polyhedral is generated. The first two members of the language are shown in the following Fig. 4.

Fig. 3.
figure 3

The 3D - Array token Petri Net generating rhombus polyhedral.

Full size image
Fig. 4.
figure 4

Rhombus polyhedral.

Full size image

Example 5

Consider the 3D-TetATPN \(N_2 = (\varSigma , C, \mu , S, \sigma , F)\) where, \(\varSigma = \{H, A, B, C, D\}\), \(C = (P, T, I, O)\), \(P = \{P_1, P_2, P_3, \dots P_8\}\), \(T = \{t_1, t_2, t_3, \dots t_7\}\).

The initial marking \(\mu \) is the hexagonal polyhedral H in the place of \(P_1\).

figure ag

\(\sigma \) the mapping from the set of transitions to the set of rules is shown in Fig. 5 and \(F = \{P_8\}\)

Starting with H on firing the sequence \(t_1t_2t_3t_4\) the tetrahedral tiles B, A, D and C are catenated to H according to the catenation rules respectively and the resultant 3D-array is sent out to place \(P_5\). On firing the sequence \(t_5t_6\) Hexagonal polyhedrals are catenated to C-tetrahedral tile in parallel in the right up and right down directions and then firing \(t_7\) hexagonal polyhedrals are catenated to hexagonal polyhedrals in the right down direction in parallel and finally the resultant sequence of hexagonal polyhedral language is sent to the final place \(P_8\).

The first member of the language generated is shown in Fig. 6. In every generation the hexagonal polyhedral tile catenated is increased by one. In the first member two hexagonal polyhedral are catenated twice.

Example 6

Consider the 3D-TetATPN \(N_3 = (\varSigma , C, \mu , S, \sigma , F)\) where, \(\varSigma = \{H, A, B\}\), \(C = (P, T, I, O)\), \(P = \{P_1, P_2, P_3, \dots P_{12}\}\), \(T = \{t_1, t_2, t_3, \dots t_{12}\}\).

The initial marking \(\mu \) is the hexagonal polyhedral H in the place of \(P_1\).

figure ah

\(\sigma \) the mapping from the set of transitions to the set of rules is shown in Fig. 7 and \(F = \{P_{13}\}\).

Starting with H on firing the sequence \(t_1t_2t_3t_4t_5t_6\) the tetrahedral tiles A and B are catenated to H according to the catenation rules respectively and the resultant 3D-array is sent to place \(P_7\) on firing the sequence \(t_7t_8t_9t_{10}t_{11}t_{12}\) the tetrahedral tiles A and B are catenated according to the catenation rules and the resultant star polyhedral is generated and it is sent to place \(P_{13}\) which is the final place or the sequence of transitions \(t_7t_8t_9t_{10}t_{11}t_{12}\) can be repeated any number of times before reaching the final destination \(P_{13}\).

The first two members generated by \(N_3\) are shown in Fig. 8.

Fig. 5.
figure 5

3D-Array token Petri Net generating increasing sequence of hexagonal polyhedrals.

Full size image
Fig. 6.
figure 6

First member of the language generated by \(N_2\).

Full size image
Fig. 7.
figure 7

3D-array token Petri Net generating sequence of star polyhedrals.

Full size image
Fig. 8.
figure 8

Star polyhedrals.

Full size image

4 Comparative Results

In this section, we compare 3D-TetATPN with K-TTTPS, TetTPPS, RTAL [16] and BPTAL [16].

Theorem 1

The families of languages generated by 3D-TetATPN and K-TTTPS are incomparable but not disjoint.

Proof

The families of languages generated by K-TTTPS and 3D-TetATPN are by parallel mechanism. The constraint in K-TTTPS is that the pasting rules of the tables are applied in parallel to the pattern obtained in the previous stage. In 3D-TetATPN the catenation rules generate the family of languages where extended tetrahedral tiles are also used.

The language of star and hexagonal polyhedrals in Example 1 cannot be generated by 3D-TetATPN, since the catenation rules are applied in parallel wherever applicable.

The language of increasing sequence of hexagonal polyhedrals given in Example 5 cannot be generated by K-TTTPS, since extended tetrahedral tile, namely hexagonal polyhedral, is used in the catenation rules.

The language of rhombus given in Example 4 can be generated by both systems. A 3-TTTPS generating the family of rhombuses is given below:

Consider a three tabled Tetrahedral Tile Pasting System generating a sequence of rhombuses,

$$\begin{aligned}&E = \{a_1, a_2, a_3, b_1, b_2, b_3\}, P = \{T_1, T_2, T_3\}, T_1 = \{(a_3, b_3), (b_1, a_1)\},\\&T_2 = \{(b_2, a_2), (b_1, a_1)\} T_3 = \{(a_2, b_2)\}. \end{aligned}$$
figure aj

   \(\square \)

Theorem 2

The families of languages generated by 3D-TetATPN and TetTPPS are incomparable but not disjoint.

Proof

In 3D-TetATPN the catenation rules are applied in parallel to generate the language concerned and extended tetrahedral tiles are also used. In TetTPPS the pasting rules are applied in parallel and the target indications permits the array generated to transit within the regions.

The language of stars and hexagonal polyhedrals given in Example 2 generated by TetTPPS cannot be generated by 3D-TetATPN as the catenation rules are applied in parallel wherever applicable.

The language of increasing sequence of hexagonal polyhedrals given in Example 5 cannot be generated by TetTPPS, since extended tetrahedral tiles, namely hexagonal polyhedral, is used in the catenation rules.

The language of rhombuses given in Example 4 is generated by both systems. TetTPPS generating the language of rhombuses is given below. Consider TetTPPS \(\pi _2 = (\varGamma , \mu = [_1[_2[_3]_3]_2]_1, F_1, F_2, F_3, R_1, R_2, R_3, 3)\). \(\mu \)-indicates that the system has three regions one within the another i.e region 1 is the skin membrane which contains region 2, which in turn contains region 3, \(i_0\) = 3 indicates that region 3 is the output region.

figure ak
$$\begin{aligned}&R_1 = \{(A, (b_2, a_2), here), (B, (a_3, b_3), here), (A, (b_1, a_1), in)\}\\&R_2 = \{(B, (a_2, b_2), in), (B, (a_2, b_2), out)\}, R_3 = \emptyset . \end{aligned}$$

Beginning with the initial object \(F_1\) in region 1, the pasting rule \(R_1\) is applied, where the rules in region 1 are applied in parallel to the boundary edges of the pattern present in region 1. Once the rule \((B, (a_3, b_3), here)\) is applied, the tetrahedral tile B is catenated to A and then, when the rule \((A, (b_1, a_1), in)\) is applied, the picture pattern generated is sent to the inner region 2. In region 2, when the rule \((B, (a_2, b_2), in)\) is applied the generated picture pattern is sent to region 3, which is the output region, where there is no rule exits and the language of rhombus is collected in region 3. Whereas if the rule \((B, (a_2, b_2), out)\) is applied, the generated picture pattern is sent to region 1 and the process continues.    \(\square \)

Theorem 3

\({\mathcal L}(3D-TetATPN) - RTAL \ne \emptyset \).

Proof

We consider a tetrahedral language whose boundary is an equilateral triangle. This language cannot be generated by any Regular Tetrahedral Array Grammar (RTAG) [16]. Since the rules in RTAG are of the following forms:

figure al

Similar rules can be given for the other two tetrahedral tiles C and D, where A and B are non terminal symbols and a and b are terminal symbols. Starting with a tetrahedral tile A, RTAG can generate at most three connected tiles. So it cannot generate an equilateral triangle of the form but this language can be generated by the following 3D-TetATPN.

Consider a 3D-TetATPN \(N_4 = (\varSigma , C, \mu , S, \sigma , F)\), where \(\varSigma = \{A, B\}\), \(C = (P, T, I, O)\) where \(P = \{P_1, P_2, P_3, P_4\}\), \(T = \{t_1, t_2, t_3\}\). The initial marking \(\mu \) is the tetrahedral tile A in place \(P_1\).

figure an

\(\sigma \) the mapping from the set of transitions to the set of rules is shown in Fig. 9, \(F = \{P_4\}\) and the language generated by \(N_4\) is shown in Fig. 10.

   \(\square \)

Fig. 9.
figure 9

3D-TetATPN of the language of equilateral triangle tetrahedral.

Full size image
Fig. 10.
figure 10

Language of equilateral triangle tetrahedral.

Full size image

Theorem 4

\({\mathcal L}(3DTetATPN)\) and BPTAL are incomparable but not disjoint.

Proof

Consider a tetrahedral language whose boundary is an equilateral triangle of size 2. This language is generated by both systems Basic Puzzle Tetrahedral Array Grammar (BPTAG) [16] as well as by 3D-TetATPN.

Consider a BPTAG, where P consists of the following rules:

figure ap

The language generated by G is an equilateral triangle tetrahedral of size 2 which is shown in Fig. 11.

This language can be generated by the following 3D-TetATPN:

Consider a 3DTetATPN \(N_5 = (\varSigma , C, \mu , S, \sigma , F)\), where \(\varSigma = \{A, B\}\), \(C = (P, T, I, O)\) where \(P = \{P_1, P_2, P_3, P_4\}\), \(T = \{t_1, t_2, t_3\}\). The initial marking \(\mu \) is the tetrahedral tile A in place P1. , \(\sigma \) the mapping from the set of transitions to the set of rules is shown in Fig. 12 and \(F = \{P_4\}\)

Equilateral triangle tetrahedral of size more than 2 cannot be generated by BPTAG, whereas it can be generated by 3D-TetATPN (as in Theorem 3). On the other hand the sequence of overlapping equilateral triangle tetrahedral can be generated by the above BPTAG, whereas it cannot be generated by any 3D-TetATPN as the catenation rules are applied in parallel wherever possible.

   \(\square \)

Fig. 11.
figure 11

Equilateral triangle tetrahedral picture of size 2.

Full size image
Fig. 12.
figure 12

3D-TetATPN generating equilateral triangle tetrahedral of size 2.

Full size image

5 Conclusion

This model is found to be useful in generating interesting patterns and is compared with other recent models in terms of their generative powers. P systems are by definition distributed parallel computing devices and they can solve computationally hard problems in a feasible time. There are NP hard problems in picture languages also. We will analyze whether these problems can be studied using membrane computing. Also we propose to work on a more powerful model of 3D-TetATPN using a concept called ‘inhibitor arc’ to generate further useful patterns and closure properties of 3D-TetATPN. This is our future work.