Array generating fuzzy petri nets and rectangular picture languages

Abstract

A two dimensional language is a collection of two dimensional words, which are rectangular array of symbols made up of finite alphabets. Fuzzy Petri nets are the generalization of classical Petri nets designed to deal with imprecise and ambiguous data which usually occurs in knowledge based systems, image processing, etc. They have been widely used to represent fuzzy production rules and fuzzy rule-based reasoning. In this paper, a new model called array token fuzzy Petri net to generate two dimensional fuzzy regular languages has been introduced. Array token fuzzy Petri nets are used to deal with impreciseness and uncertainties occurring in two dimensional regular languages. Furthermore, proved that for every two dimensional fuzzy regular grammar there exists an array token fuzzy Petri net that generates the same two dimensional fuzzy regular language and also establish some closure properties of the languages generated by array token fuzzy Petri net.

Keywords

Array grammars array token petri nets fuzzy petri nets fuzzy languages picture languages

1 Introduction

A formal language (one dimensional) is a set of sequence of symbols over some finite alphabet. The advances and applications of formal languages in various fields such as pattern matching, lexical analyzer, syntax, biology, etc., can be found in [1 –4]. An extension of one dimensional languages called two dimensional languages (picture languages) were introduced and studied by many researchers [5 –10]. A two dimensional language is a collection of two dimensional words (pictures, matrices and arrays). The Siromoney matrix model, introduced in [8] is one of the simplest model to describe picture languages and its extension of array grammars and array automata are extremely useful models for generating two dimensional picture languages among the various classes of two dimensional languages. Also, in [8], the closure properties of matrix languages and its application in generating a wide class of pictures have been studied. The advantages of this model are discussed in [9, 10]. Some of the major and useful devices to generate one dimensional and two dimensional languages are formal grammars (regular, context-free and context-sensitive), Petri nets, L-systems and automata [8 , 11–15].

In recent years, there is an increasing interest in studying and analyzing the relation between formal grammars and Petri nets, which are more applicable and effective devices to generate the formal languages. Formal grammars, generally called as grammars, are precise descriptions of formal languages, that is a grammar is a set of rules for rewriting strings to produce a language and the rewriting begins from a start symbol [1, 2]. Petri nets are dynamic graphs with two disjoint sets of nodes namely, places represented by circles and transitions represented by rectangles [15]. The collection of firing sequences of transitions produced by the Petri net is of primary importance in many applications. Among the different varieties of Petri nets structures, one of the Petri net structure called labelled Petri net was introduced in [13]. Their extensions and applications have been studied in many papers [15 –17]. In [18], another version of labelled Petri net called string token Petri net has been introduced and studied by representing the labels of transitions with grammar rules and tokens by strings over some alphabet.

Zadeh introduced the concept of fuzzy sets to deal with real life problems having uncertainties, vagueness and imprecise data [19]. In [20], fuzzy Petri nets were introduced to reduce the behaviour of uncertainty problems, which arises in decision making of industrial models. Later, various extensions of fuzzy Petri nets have been initiated and studied [21 –23]. In [24], Zadeh and Lee initiated fuzzy languages generated by fuzzy grammars to reduce the vagueness occurring in formal languages. Fuzzy languages have received a lot of attention since the late seventies. The concept of fuzzy languages are used in script recognition, lexical analysis, pattern matching, etc. [25 –27]. In [28], the generative tools such as fuzzy L-system, fuzzy grammar and fuzzy Petri nets were discussed and some properties of fuzzy languages have been studied. The fuzzy Petri net introduced in [28] is a labelled fuzzy Petri net where the transitions of Petri net are labelled by symbols over some alphabet associated with their membership values. In [29], a new model called regular string token fuzzy Petri nets has been introduced by labelling the transitions with rewriting rules of fuzzy grammars. Also, studied the relation between fuzzy grammars and fuzzy Petri nets and the closure properties such as union, concatenation, kleene closure, reversal, homomorphism and inverse homomorphism of the languages generated by the regular string token fuzzy Petri nets have been discussed. Recently, two dimensional fuzzy regular languages (2-FRL) generated by two dimensional fuzzy right-linear grammars have been studied in [30], where the basic concepts of fuzzy languages are extended to the picture languages [8]. The equivalence between two dimensional fuzzy right-linear (2-FRLG) grammar and two dimensional fuzzy finite automata have been studied. The closure properties of 2-FRLs have been discussed and also studied the application of 2-FRLG in generation of kolam patterns with fuzzy colors.

Motivated by the above works, in this paper, a new class of fuzzy Petri net called array token fuzzy Petri net is introduced by labelling the transitions of fuzzy Petri net with production rules of two dimensional fuzzy grammar. The properties of fuzzy Petri nets from the aspect of two dimensional fuzzy regular grammars with 2-FRLs are studied.

The organization of this paper is given as follows: The basic notion and definitions of array token Petri net, two dimensional languages and 2-FRL are recalled in Section 2. In Section 3, fuzzy evolution rules and array token fuzzy Petri net are defined. Also, proved that for every two dimensional fuzzy regular language there exists an array token fuzzy Petri net that accepts the same language. The closure properties of 2-FRLs generated by array token fuzzy Petri net are defined and discussed in Section 4. In Section 5, the conclusion and the direction of future studies of this concept has been summarized.

2 Preliminaries

This section recalls the definitions of array token Petri nets of two dimensional languages and 2-FRLs [12, 30]. The terms and notion of formal languages and formal grammars can be referred from the standard textbooks [1, 2]. The basic definitions and properties of fuzzy languages, fuzzy automata and fuzzy grammars can be recalled from [24, 25].

“Notation Let Σ be a finite collection of input symbols then Σ^** represents the collection of all matrices over Σ including Λ (empty array). Σ⁺⁺ = Σ^** - {Λ}, Σ_* represents the vertical strings over Σ and Σ₊ = Σ_* - {Λ} and Σ^* represents the horizontal strings over Σ and Σ⁺ = Σ^* - {Λ}. "

Definition 2.1. [12] An array token Petri net (ATPN) is a 6-tuple N = (P, T, C, A, R, M₀), where

P represents the collection of finite places,

T represents the collection of finite transitions,

C represents the collection of symbols (colours) and C_AY represents the collection of all rectangular arrays over the collection C which are considered as tokens,

A ⊆ (T × P) ∪ (P × T) represents the collection of arcs,

R (t) represents the collection of evolution rules labelled with the transitions in T,

M₀ represents the initial marking, which is a function defined on P, for p ∈ P, M₀ (p) ∈ [C_AY] _MS.

Definition 2.2. [12] A language L is an M-type ATPN language if there exists N = (P, T, C, A, R, M₀), and a collection of final places F such that $\begin{matrix} L = & {w / w \in M (p); where M is a reachable \\ marking of N and p is in F} . \end{matrix}$

Definition 2.3. [30] “ A two dimensional fuzzy right - linear grammar (2-FRLG) is a 2-tuple G = (G_h, G_v), where G_h and G_v are fuzzy right-linear grammars. Now, G_h = (V_h, I_h, P_h, S_h), in which

V_h represents the collection of finite horizontal non-terminals,

I_h represents the collection of finite intermediates,

S_h represents the finite fuzzy subset of start symbols from V_h,

P_h represents the collection of finite fuzzy horizontal production rules of the form α→ρxβ or α→ρx, where ρ ∈ (0, 1] is the grade of membership of the production rules, $α, β \in V_{h}, x \in I_{h}^{*}$ and V_h∩ I_h = ∅. and

G_{v} = ⋃_{i = 1}^{k} G_{v_{i}}

where, G_{v
_i} = (V_{v
_i}, I_v, P_{v
_i}, S_i),

i = 1, 2, … , k, in which

V_{v
_i} represents the collection of finite vertical non-terminals such that V_{v
_i}∩ V_{v
_j} = ∅ for i ≠ j,

I_v represents the collection of finite terminals,

S_i ∈ V_{v
_i} represents the fuzzy start symbol and

P_{v
_i} represents the collection of finite fuzzy vertical production rules of the form A→σcB or A→σc, A, B ∈ V_{v
_i} and c ∈ I_v, where σ ∈ (0, 1] is membership grade of the production rules.

Derivation of a matrix from the given 2-FRLG, the degree of membership of the matrix and the 2-FRL generated by G are given in [30].

Let L_M, L_{M
₁} and L_{M
₂} be 2-FRLs over Σ^**. Then the Union of L_{M
₁} and L_{M
₂}, the column concatenation (or vertical concatenation) of L_{M
₁} and L_{M
₂} and the column star of L_M can be recalled from [30].

The reflection about the base, reflection about the right most vertical, half-turn and conjugate of a given two dimensional word are explained in [9].

Definition 2.4. [31] The solidity of a basic color can be reduced by mixing the color with white color. These colors are called fuzzy colors and the quantity of the white color mixed with a color determines the grade of membership of them. That is, if q (0 ≤ q ≤ 1) units of a color (say c) are mixed with 1 - q units of white color then the membership value of the color c is q and the resultant fuzzy color is denoted by (c, q). This is known as a standard mixture [31].

For example, if red is a basic color then a “fuzzy red” (say light red) color may be obtained by mixing 0.6 units of red color with 0.4 units of white color.

3 Array token fuzzy petri nets and two dimensional fuzzy regular languages

In this section, the definition of array token fuzzy Petri net and fuzzy evolution rules are given. Also, given the generation of 2-FRL generated by regular array token fuzzy Petri net. Moreover, it is proven that for every 2-FRL there exists a regular array token fuzzy Petri net.

Definition 3.1. Fuzzy evolution rules (FER) for array token fuzzy Petri net are as follows:

Reflexive rule: There is no change in the horizontal string.

Insertion (left/right) rule: λ→1a, an empty string (λ) is replaced by a string over V. It can be done in either leftmost (represented by λ→1a (l)) or rightmost (represented by λ→1a (r)) side of the string.

Deletion (left/right) rule: a→0λ, a string over V is replaced by an empty string. It can be done in either leftmost (represented by a→0λ (l)) or rightmost (a→0λ (r)) side of the string.

Substitution rule: X→ρb, ρ ∈ [0, 1], a string over V is replaced by another string over V.

The vertical fuzzy evolution rules for each symbol to generate the array are given below:

Reflexive rule: There is no change in the vertical string.

Upper insertion rule: A_i λ→1a (u), an empty symbol (λ) is replaced above by a symbol over V.

Lower insertion rule: A_i λ→1a (l), an empty symbol (λ) is replaced below by a symbol over V.

Substitution rule: A_i λ→ρa_i (s) represents the substitution of all A_i with symbols a_i.

where X, A_i ∈ V, a, b, a_i ∈ V^* and λ is the empty string.

Definition 3.2. An array token fuzzy Petri net (ATFPN) is a 9-tuple $N^{f} = (P, T, V, A, F, R_{h} (t), R_{v} (t), M_{0}, M_{F})$ where

P = {p_i : i = 1, 2, …, n} - the finite collection of places,

T = T_h ∪ T_v, in which

T_h = {t_j : j isapositiveinteger} is a finite collection of transitions labelled by horizontal fuzzy evolution rules and T_v = {t_k : k isapositiveinteger} is a finite collection of tupled transitions, where each transition of every tuple is labelled by the vertical fuzzy evolution rules,

V - the finite non-empty collection of symbols consists of terminals represented by lower case letters ({a, b, c, …, z}), non-terminals represented by upper case letters ({A, B, C, …, Z}) and the intermediates are represented by

({S₁, S₂, …, S_n}),

A ⊆ (T × P) ∪ (P × T) - the collection of arcs (flow relation) and an arc from any p (place) to t (transition) is denoted by p ↦ t (similarly t ↦ p denotes an arc from transition to place).

F ⊆ P - the collection of final places, which contains only array of terminals,

$R_{h} (t)$ - the collection of horizontal fuzzy evolution rules labelled by the transition t_j of T_h, used to derive horizontal strings of intermediates for the two dimensional words,

$R_{v} (t)$ - the collection of vertical fuzzy evolution rules labelled with each transition t_j of T_v, used to derive vertical strings (columns) the two dimensional words,

M₀ : P → (astringover V) - the fuzzy initial marking,

M_F : P → (anarrayofterminalsover V) - the collection of final markings (also called as reachable markings).

where, P∪ T ≠ ∅ and P∩ T = ∅.

Definition 3.3. A state or marking in an ATFPN is changed according to the following transition (firing) rules to replicate the dynamic system’s behavior.

(i) A transition (say t) labelled by the horizontal fuzzy evolution rule is called an enabled transition, if the tokens of every input place (say p) of a transition t posses a string, which appears in the left side expression of the horizontal fuzzy evolution rule labelled with t.

A tuple of transitions (say (t₁, t₂, …, t_n)) each labelled by the vertical fuzzy evolution rules is called an enabled transition, if tupled token of every input place (say p) of a transition (t₁, t₂, …, t_n) posses strings, all of which appears in the left side expression of the vertical fuzzy evolution rules labelled with each transition of (t₁, t₂, …, t_n).

(ii) A transition t and (t₁, t₂, …, t_n) can be fired, if they are enabled (depending on whether the event actually takes place).

(iii) The token (say y) is removed from all input place (say p) of a transition (say t) and altered as the string token z in the output place of t, if the enabled transition t is fired. Also, each vertical string (say α_i : i ranges from 1 to the number of columns in the two dimensional word) in the tupled token is removed from the input place of the tupled transition (say (t₁, t₂, …, t_n) and altered as the vertical string $α_{i}^{'}$ in the output place of (t₁, t₂, …, t_n), if the enabled transition (t₁, t₂, …, t_n) is fired.

The generation of two dimensional word from the given ATFPN is described as follows:

(i) The horizontal string of intermediates (say δ = S₁S₂ … S_n) is generated with the firing of Transitions Labelled By the horizontal fuzzy evolution rules from the fuzzy initial marking (say S) and is represented by $S | \overset{*}{- -} δ$ . The membership value of the string δ is obtained by $⋁_{S \in M_{0}} (d (S) \land d (S | \overset{*}{- -} δ))$ , where d (S) is the membership value of the string S to be an initial marking. $d (S | \overset{*}{- -} δ) = sup min {ρ_{1}, ρ_{2}, do ts, ρ_{n}}; ρ_{i} \in [0, 1], i = 1, 2, \dots n$ is the membership value of the i^th transition fired and the supremum is the taken over all possible firing sequences from S to δ.

(ii) The horizontal string (S₁S₂ … S_n) obtained in the place (say p) is considered as tuples S₁, S₂, …, S_n and each element of the tuple is considered as an initial marking in the place p to generate the columns of the two dimensional word.

(iii) Finally, each column of the two dimensional word is generated simultaneously by firing of tupled transitions labelled with the vertical fuzzy evolution rules. The membership value of each column (vertical string of terminals α_i ; i represents the number of columns in the two dimensional word) is obtained by $d (S_{i}) \land d (S_{i} | \overset{*}{- -} α_{i})$ , where d (S_i) represents the membership value of the string S_i to be an initial marking and similarly $d (S_{i} | \overset{*}{- -} α_{i})$ is obtained as above.

Note that $| \overset{★}{- -}$ is the transitive closure of $| - -$ and in some cases the vertical evolution rules are labelled repeatedly to different transitions to generate the two dimensional word simultaneously.

Definition 3.4. A two dimensional word W of terminals is generated by the ATFPN 𝒩^f, if there exists a sequence of horizontal and vertical transitions fired from the fuzzy initial marking to the final marking of the two dimensional word W. The membership value of the word is denoted by d (W) (also, d_𝒩^f (W)) and is obtained by $\begin{matrix} d_{N^{f}} (W) & = max_{S \in M_{0}} {min {(d (S) \land d (S | \overset{★}{- -} δ)), \\ {⋁_{i = 1}^{k} (d (S_{i}) \land d (S_{i} | \overset{★}{- -} α_{i}))}}} > 0 . \end{matrix}$

Definition 3.5. An ATFPN is termed as a regular array token fuzzy Petri net (RATFPN) when the horizontal fuzzy evolution rules and the vertical fuzzy evolution rules are same as horizontal and vertical fuzzy production rules respectively as given in 2-FRLG.

The 2-FRL generated by the RATFPN 𝒩^f is the collection of all two dimensional words of terminals generated by the RATFPN 𝒩^f and it is denoted by L_M (𝒩^f).

Example 3.1. Consider the RATFPN 𝒩^f that generates the 2-FRL L_M, which consists of m × n ; m ≥ 2, n ≥ 3 matrices with membership value 0.4, where as one in-between column is completely filled by zero and all other columns are filled by one. Let $N^{f} = (P, T, V, A, F, R_{h} (t), R_{v} (t), M_{0}, M_{f})$ , in which

$\begin{matrix} P = {p_{1}, p_{2}, p_{3}, p_{4}, p_{5}, p_{6}}, \\ T = {t_{1}, t_{2}, t_{3}, t_{4}, t_{5}, t_{6}, t_{7}, t_{8}, t_{9}}, \\ V = {S, S_{1}, S_{2}, H, D}, \\ A = {p_{1} \mapsto t_{1}, t_{1} \mapsto p_{2}, p_{2} \mapsto t_{2}, t_{2} \mapsto p_{2}, p_{2} \mapsto t_{3}, \\ t_{3} \mapsto p_{3}, p_{3} \mapsto t_{4}, t_{4} \mapsto p_{3}, p_{3} \mapsto t_{5}, t_{5} \mapsto p_{4}, \\ p_{4} \mapsto (t_{6}, t_{8}), (t_{6}, t_{8}) \mapsto p_{4}, p_{4} \mapsto (t_{7}, t_{8}), \\ (t_{7}, t_{8}) \mapsto p_{5}}, \\ F = {p_{5}}, \end{matrix}$

$\begin{matrix} R_{h} (t) = {t_{1} : S \overset{0.9}{\to} S_{1} H, t_{2} : H \overset{0.7}{\to} S_{1} H, \\ t_{3} : H \overset{0.8}{\to} S_{2} D, t_{4} : D \overset{0.7}{\to} S_{2} H, \\ t_{5} : H \overset{0.6}{\to} S_{1}}, \\ R_{v} (t) = {t_{6} : S_{1} \overset{0.5}{\to} 1 S_{1}, t_{7} : S_{1} \overset{0.4}{\to} 1, \\ t_{8} : S_{2} \overset{0.5}{\to} 0 S_{2}, t_{9} : S_{2} \overset{0.4}{\to} 0}, \\ M_{0} - initial marking and M_{F} - final marking . \end{matrix}$ The RATFPN 𝒩^f is shown in Fig. 1.

Fig. 1

RATFPN 𝒩^f of Example 3.1.

Consider a 3 × 3 matrix W in L_M (𝒩^f), where the central column is filled by zero and all other entries are filled by one. The generation process of W is shown below:

$S | \frac{0.9}{t_{1}} S_{1} H | \frac{0.8}{t_{3}} S_{1} S_{2} D | \frac{0.6}{t_{5}} S_{1} S_{2} S_{1} | \frac{(0.5, 0.5)}{(t_{6}, t_{8})} \begin{matrix} 1 & 0 & 1 \\ S_{1} & S_{2} & S_{1} \end{matrix}$ $| \frac{(0.5, 0.5)}{(t_{6}, t_{8})} \begin{matrix} 1 & 0 & 1 \\ 1 & 0 & 1 \\ S_{1} & S_{2} & S_{1} \end{matrix} ∥ | \frac{(0.5, 0.5)}{(t_{7}, t_{9})} \begin{matrix} 1 & 0 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 1 \end{matrix}$

The membership value of the horizontal string of intermediates δ = S₁S₂S₂ with d (S) =0.6 is

$d (S | \overset{*}{- -} S_{1} S_{2} S_{1}) = min (0.9, 0.8, 0.6)$

= 0.6.

The membership value of the vertical string α₁ = 111 with d (S₁) =0.7 is $d (S_{1} | \overset{*}{- -} 111) = min (0.5, 0.5, 0.4)$ = 0.4.

Similarly for α₂ = 000 with d (S₂) =0.7 is

$d (S_{2} | \overset{*}{- -} 000) = min (0.5, 0.5, 0.4)$ = 0.4.

Now, $d (S) \land d (S | \overset{*}{- -} δ) = 0.6 \land 0.6 = 0.6$ .

$d (S_{1}) \land d (S_{1} | \overset{*}{- -} α_{1}) = 0.7 \land 0.4 = 0.4$ .

$d (S_{2}) \land d (S_{2} | \overset{*}{- -} α_{2}) = 0.8 \land 0.4 = 0.4$ .

Since, by definition 3.4, $\begin{matrix} d_{N^{f}} (W) & = max_{S \in M_{0}} {min {(d (S) \land d (S | \overset{★}{- -} δ)), \\ {⋁_{i = 1}^{k} (d (S_{i}) \land d (S_{i} | \overset{★}{- -} α_{i}))}}} > 0 . \end{matrix}$

Therefore, d_𝒩^f (W) = max {min {0.6, ⋁ (0.4, 0.4)}} = 0.4 > 0.

Theorem 3.1. For every 2-FRL L_M (G) generated by the two dimensional fuzzy regular grammar G = (G_h, G_v) there exists a RATFPN 𝒩^f such that

L_M (𝒩^f) = L_M (G).

Proof. Let G = (G_h, G_v) be the two dimensional fuzzy regular grammar, where G_h = (V_h, I_h, P_h, S_h) and $G_{v} = ⋃_{i = 1}^{n} G_{v_{i}} = (V_{v_{i}}, I_{v}, P_{v_{i}}, S_{i})$ as described in Definition 2.3. Let L_M (G) be the 2-FRLs generated by G.

Construct the Petri Net

$N^{f} = (P, T, V, A, F, R_{h} (t), R_{v} (t), M_{0}, M_{F})$ such that L_M (G) = L_M (𝒩^f) from the given two dimensional fuzzy regular grammar G as follows:

V = V_h ∪ I_h ∪ I_v ∪ V_{v
_i} ; i = 1, 2, …, n, M₀ is collection of fuzzy initial markings corresponding to each fuzzy start variable S ∈ S_h of G_h and S_i ∈ G_{v
_i} ; i = 1, 2, …, n. For each A→ρaB ∈ P_h put $t_{j} : A \to ρ aB; j \in ℕ$ in R_h (t) and for each A→ρa ∈ P_h put $t_{k} : A \to ρ a; k \in ℕ$ in $R_{h} (t)$ . For every A_i→ρ_ia_iB_i ∈ P_{v
_i} put $t_{m} : A_{i} \to ρ_{i} a_{i} B_{i}; m \in ℕ$ in $R_{v} (t)$ and for every A_i→ρ_ia_iB_i ∈ P_{v
_i} put $t_{l} : A_{i} \to ρ_{i} a_{i}; l \in ℕ$ in $R_{v} (t)$ . T = T_h ∪ T_v, where T_h is the collection of transitions labelled by the horizontal fuzzy evolution rules $R_{h} (t)$ and T_v is the collection of transitions labelled by the vertical fuzzy evolution rules $R_{v} (t)$ . M_F is collection of final markings. P is the collection of all places and A is the collection of all arcs from transitions to places and places to transitions. Now, it is easily verifiable that each W ∈ L_M (𝒩^f) for every W ∈ L_M (G). The construction is also illustrated in flow chart given in Fig. 2.

Fig. 2

Construction of RATFPN 𝒩^f from 2-FRLG G.

Example 3.2. Consider the 2-FRL $\begin{matrix} L_{M} (G) = & {Geometric patterns of different size with \\ membership value 0.5 for all sizes} \end{matrix}$

The 2-FRLG G that generates L_M (G) is described in Example 5.1 given in [30]. An example of geometric pattern is shown Fig. 3. By Theorem 3.1, let us construct RATFPN 𝒩^f such that

Fig. 3

Geometric pattern.

$N^{f} = (P, T, V, A, F, R_{h} (t), R_{v} (t), M_{0}, M_{F})$ , which generates the same 2-FRL, where,

P = {p₁, p₂, p₃, p₄, p₅},

T = {t₁, t₂, t₃, t₄, t₅, t₆, t₇, t₈, t₉, t₁₀, t₁₁, t₁₂},

V = V_h ∪ I_h ∪ I_v ∪ V_{v
_i}

= {S₀, A, B, S₁, S₂, a, c, d, e, f, g, C, D, E, F},

A = {Collectionofallarcs},

F = {p₅},

For each horizontal fuzzy production rule P_h of G, the horizontal fuzzy evaluation rules $R_{h} (t)$ is obtained by $R_{h} (t) = {t_{1} : S_{0} \to 0.8 S_{1} A, t_{2} : A \to 0.7 S_{2} B, t_{3} : B \to 0.7 S_{1} A, t_{4} : B \to 0.7 S_{1}}$ ,

For each vertical fuzzy production rule P_{v
_i} of G, the vertical fuzzy evaluation rules $R_{v} (t)$ is obtained by $R_{v} (t) = {t_{5} : S_{1} \to 0.5 aC, t_{6} : S_{2} \to 0.8 fE, t_{7} : C \to 0.6 cD, t_{8} : E \to 0.7 gF, t_{9} : D \to 0.5 dC, t_{10} : F \to 0.8 fE, t_{11} : D \to 0.5 e, t_{12} : F \to 0.8 f}$ ,

M₀ is the collection of fuzzy initial marking obtained from S₀, S₁ and S₂ along with their membership values of G and M_F is the final marking in place p₅.

The constructed RATFPN 𝒩^f is shown in Fig. 4.

Fig. 4

RATFPN 𝒩^f.

Functional Comparison between RATFPN and RATPN:

In the sense of functional comparison, the evolution rules of RATFPN are in the form of regular fuzzy production rules whereas RATPN has evolution rules of the form of regular production rules.

In this paper, one such functioning of RATFPN has been described in the form of generation of geometric kolam pattern with fuzzy colors, which has been explained detail in Example 3.2. Whereas in RATPN each fuzzy color is treated as different new color and should be given as new inputs to generate the colored patterns. The advantage of RATFPN is to resolve the issues of vagueness occurring in two dimensional regular languages.

4 Closure properties of two dimensional fuzzy regular languages

In this section, the closure properties of 2-FRLs generated by RATFPNs have been introduced and discussed.

Definition 4.1. The row concatenation(or horizontal concatenation) of L_{M
₁} and L_{M
₂} is a 2-FRL denoted by L_{M
₁} ⊖ L_{M
₂} and defined as: Let X be a m × n matrix over the input Σ be a row concatenation of a prefix m′ × n′ matrix X₁ and a suffix m″ × n″ matrix X₂ when n = n′ = n″. i.e. If X = X₁ ⊖ X₂, then $d_{L_{M_{1}} ⊖ L_{M_{2}}} (X) = sup_{X_{1}} min (d_{L_{M_{1}}} (X_{1}), d_{L_{M_{2}}} (X_{2})),$ the supremum being taken over all X₁ of X. By replacing ∨ and ∧ for supremum and minimum, d_{L_{M
₁}⊖L_{M
₂}} (X) can also be written as $d_{L_{M_{1}}} ⊖ d_{L_{M_{2}}} = ⋁_{X_{1}} (d_{L_{M_{1}}} \land d_{L_{M_{2}}})$

The row star of L_M is 2-FRL denoted by $L_{M}^{*}$ and defined by $\begin{matrix} L_{M}^{*} = & ⋃_{i} L_{M}^{i} \cup {Λ} \\ = & {Λ} \cup L_{M}^{1} \cup L_{M}^{2} \cup \dots \cup L_{M}^{i} . \end{matrix}$

Theorem 4.1. The 2-FRLs generated by the RATFPN are closed under union, column concatenation, column star (kleene closure), row concatenation and row star (kleene closure).

Proof. Let L_{M
₁} and L_{M
₂} be two 2-FRLs generated by a RATFPN

$N_{1}^{f} = (P_{1}, T_{1}, V_{1}, A_{1}, F_{1} R_{h}^{1} (t), R_{v}^{1} (t), M_{0_{1}}, M_{F_{1}})$ such that $L_{M_{1}} = L_{M_{1}} (N_{1}^{f})$ and a RATFPN $N_{2}^{f} = (P_{2}, T_{2}, V_{2}, A_{2}, F_{2}, R_{h}^{2} (t), R_{v}^{2} (t), M_{0_{2}}, M_{F_{2}})$ such that $L_{M_{2}} = L_{M_{2}} (N_{2}^{f})$ .

(i) The construction of the RATFPN

$N^{f} = (P, T, V, A, F, R_{h} (t), R_{v} (t), M_{0}, M_{F})$ that generates the 2-FRL L_{M
₁} ∪ L_{M
₂} such that $L_{M} (N^{f}) = L_{M_{1}} (N_{1}^{f}) \cup L_{M_{2}} (N_{2}^{f})$ is done by the following three steps. First, the array tokens S₁ and S₂ are removed from the start places say p_{S
₁} and p_{S
₂} of the RATFPNs $N_{1}^{f}$ and $N_{2}^{f}$ respectively. In the second step, a new place p_S is constructed with S as token in it and consider this as an initial marking with membership value one. Finally, add the transition labelled, t_α with new substitution rule S→ρS₁, whose input and output place as p_S and p_{S
₁} respectively and where ρ is membership value of S₁ to be an initial marking of $N_{1}^{f}$ . Also, add another transition labelled, t_β with insertion rule S→σS₂, whose input and output place as p_S and p_{S
₂} respectively and where σ is membership value of S₂ to be an initial marking of $N_{2}^{f}$ . Once the process gets started, either $N_{1}^{f}$ or $N_{2}^{f}$ continues to operate usually, after firing of the transitions t_α and t_β. The membership value of the array is obtained by taking maximum of its membership value in $L_{M_{1}} (N_{1}^{f})$ and $L_{M_{2}} (N_{2}^{f})$ .

The same procedure can be extended to 2-FRLs L_{M
₁}, L_{M
₂}, …, L_{M
_n}.

(ii) The construction of the RAT

$N^{f} = (P, T, V, A, F, R_{h} (t), R_{v} (t), M_{0}, M_{F})$ that generates the 2-FRL L_{M
₁} ○ | L_{M
₂} such that

$L_{M} (N^{f}) = L_{M_{1}} (N_{1}^{f}) ○ | L_{M_{2}} (N_{2}^{f})$ is described as follows: Once the horizontal string of intermediates generated in a place (say p′) by $N_{1}^{f}$ , add a transition t_α with right insertion rule λ→1S₂ whose input and output place as p′ and the start place of $N_{2}^{f}$ respectively. Now, the horizontal string of intermediates generated by both $N_{1}^{f}$ and $N_{2}^{f}$ is considered as tuples in the place say p″. The concatenated array in the 2-FRL L_M (𝒩^f) is generated from the place p″, by using the vertical fuzzy evolution rules of the nets $N_{1}^{f}$ and $N_{2}^{f}$ .

The same procedure can be extended to 2-FRLs L_{M
₁}, L_{M
₂}, …, L_{M
_n}.

(iii) The construction of the RATFPN

$N^{f} = (P, T, V, A, F, R_{h} (t), R_{v} (t), M_{0}, M_{F})$ that generates the 2-FRL $L_{M_{1}}^{*} (N_{1}^{f})$ such that $L_{M} (N^{f}) = L_{M_{1}}^{*} (N_{1}^{f})$ is described as follows: Once the horizontal string of intermediates generated in a place (say p′) by $N_{1}^{f}$ , add a transition t_α with right insertion rule λ→1S₁ whose input and output place as p′ and the start place of $N_{1}^{f}$ respectively. Now, the horizontal string of intermediates of $N_{1}^{f}$ can be generated by any number of times in the place say p″. Finally, the horizontal string of intermediates obtained at p″ is considered as tuples and the array in the 2-FRL $L_{M_{1}}^{*} (N_{1}^{f})$ is generated from the place p″, by using the vertical fuzzy evolution rules of the net $N_{1}^{f}$ .

The 2-FRL generated by RATFPN is closed under row concatenation and row star can be proved in a similar way.

Definition 4.2. If X is a matrix as given below, then the reflection about the right-most vertical, reflection about the base, half-turn are represented by R_v (X), R_h (X) and H (X) respectively and they are defined as follows. $X = \begin{matrix} u_{11} & \dots & u_{1 n} \\ \dots & \dots & \dots \\ u_{m 1} & \dots & u_{mn} \end{matrix}$ $R_{v} (X) = \begin{matrix} u_{1 n} & \dots & u_{11} \\ \dots & \dots & \dots \\ ∥ u_{mn} & \dots & u_{m 1} \end{matrix}$

$R_{h} (X) = \begin{matrix} u_{m 1} & \dots & u_{mn} \\ \dots & \dots & \dots \\ u_{11} & \dots & u_{1 n} \end{matrix}$ $H (X) = \begin{matrix} u_{mn} & \dots & u_{m 1} \\ \dots & \dots & \dots \\ u_{1 n} & \dots & u_{11} \end{matrix}$

The half-turn of a 2-FRL L_M is denoted by H (L_M) and is defined by H (L_M) = {H (X)/X ∈ L_M} . The reflection about the right-most vertical and reflection about the base of the 2-FRL are defined in a similar way.

Definition 4.3. Let X be an m × n matrix over Σ = {u, v}. Then the conjugate of X is denoted by C (X) and is defined by replacing every u in the matrix X by v and every v in the matrix X by u and the conjugate of the 2-FRL L_M is denoted by C (L_M) and is given by the collection {C (X)/X ∈ L_M}.

Theorem 4.2. The class of 2-FRL generated by the RATFPN are closed under reflection about right-most vertical, reflection about base, conjugation and half-turn.

Proof. The closure of reflection about base of 2-FRL generated by RATFPN is shown below.

Let L_M (𝒩^f) be the 2-FRL generated by RATFPN $N^{f} = (P, T, V, A, F, R_{h} (t), R_{v} (t), M_{0}, M_{F})$ . Construct another RATFPN

$N^{f^{'}} = (P^{'}, T^{'}, V^{'}, A^{'}, F^{'}, R_{h}^{'} (t), R_{v}^{'} (t), M_{0}^{'}, M_{F}^{'})$ such that

P′ = P; T′ = T; V′ = V; A′ = A; F′ = F; $R_{h}^{'} (t) = R_{h} (t)$ ; $M_{0}^{'} = M_{0}$ ; $M_{F}^{'} = M_{F}$ and $R_{v} (t)$ is defined as follows:

$R_{v}^{'} (t) = {\begin{matrix} B \to σ aA & if A \to σ aB in R_{v} (t) \\ A \to σ a & if A \to σ a in R_{v} (t) \end{matrix}$ where A, B, a ∈ V. By the above construction of $N_{f}^{'}$ , the set of all horizontal strings generated by the RATFPN $N_{f}^{'}$ is same as the set of all horizontal strings generated by 𝒩_f. Therefore, it is clear to see that, if L_M (𝒩_f) is a 2-FRL generated by 𝒩_f then $L_{M} (N_{f}^{'})$ is also a 2-FRL, which is the reflection about base of the 2-FRL L_M (𝒩_f) generated 𝒩_f.

Hence, if L_M is a 2-FRL then its reflection about base R_h (L_M) is also a 2-FRL. i.e., The class of 2-FRLs is closed under reflection about the base.

The other closure properties can be similarly proved.

5 Conclusion

In this paper, the regular array token fuzzy Petri net to generate two dimensional fuzzy regular language has been introduced and established that, for every two dimensional fuzzy regular language there exists array token fuzzy Petri net. Also, exemplified the generation of geometric pattern by regular array token fuzzy Petri net. Some of the closure properties of languages generated by regular array token fuzzy Petri net such as union, column concatenation, column closure and reflection about base, etc., has been discussed. The future work is to extend the array token fuzzy Petri nets to the Chomsky hierarchy of two dimensional fuzzy languages, tetrahedral and hexagonal picture languages. Further, the application of array token fuzzy Petri nets can be carried out in the direction of fuzzy lexical analyzer, image processing and approximate pattern matching.

References

Hopcroft

J.E.

, Motwani

and Ullman

J.D.

, Introduction to Automata Theory Languages, and Computation, JPearson Education Ltd., 3rd ed (2014).

Linz

, An introduction to formal languages and automata, Jones & Bartlett Learning (2006).

Nidhi Kalra and Ajay Kumar , State grammar and deep pushdown automata for biological sequences of nucleic acids, Current Bioinformatics 11(4) (2016), 470–479.

Khoussainov

and Nerode

, Automata theory and its applications, Springer Science & Business Media 21 (2012).

Fernau

, Paramasivan

, Schmid

M.L.

and Thomas

D.G.

, Simple picture processing based on finite automata and regular grammars, Journal of Computer and System Sciences 95 (2018), 232–258.

Siromoney

, Advances in array languages, In: International Workshop on Graph Grammars and Their Application to Computer Science, Springer, 1986, pp. 549–563.

Smith

T.J.

, Two-dimensional automata, Tech. rep., 2019-637, Queen’s University, Kingston, 2019.

Stromoney

, Siromoney

and Krithivasan

, Abstract families of matrices and picture languages, Computer Graphics and Image Processing 1(3) (1972), 284–307.

Siromoney

, Siromoney

and Krithivasan

, Picture languages with array rewriting rules, Information and Control 22(5) (1973), 447–470.

10.

Siromoney

, Advances in array languages, in: InternationalWorkshop on Graph Grammars and Their Application to Computer Science, Springer, Berlin, Heidelberg, 1986, pp. 549–563.

11.

Kalyani

, Raman

T.T.

, Thomas

D.G.

, Bhuvaneswari

and Ravichandran

, Triangular Array Token Petri Net and P System, In International Conference on Membrane Computing, Springer, Cham (2020), pp. 78–93.

12.

Immanuel

and Usha

, Array token petri nets and 2d grammars, In: International Conference on Mathematical Computer Engineering-ICMCE, 2013, pp. 722–727.

13.

Jantzen

and Zetzsche

, Labeled step sequences in petri nets, In: International Conference on Applications and Theory of Petri Nets, Springer, 2008, pp. 270–287.

14.

Lindenmayer

, Developmental Systems without Cellular Interactions, their languages and Grammars, J. Theoret. Biol. 30 (1971), 455–484.

15.

Peterson

J.L.

, Petri net theory and the modeling of systems, Prentice Hall PTR, 1981.

16.

Al-Ajeli

and Parker

, Fault diagnosis in labelled Petri nets: a Fourier-Motzkin based approach, Automatica 132 (2021).

17.

Yin

and Lafortune

, On the decidability and complexity of diagnosability for labeled Petri Nets, IIEEE Trans. Automat. Control 62 (2017), 5931–5938.

18.

Shirley Gloria

D.K.

, Devi

and Nirmala

, Regular string-token petri nets, Malaya Journal of Mathematik 8(2) (2020), 445–449.

19.

Zadeh

L.A.

, Fuzzy sets, Information and Control 8 (1965), 338–353.

20.

Looney

C.G.

, Fuzzy petri nets for rule-based decision making, IEEE Transactions on Systems, Man, and Cybernetics 18(1) (1988), 178–183.

21.

Jiang

, Zhou

K.Q.

, Sarkheyli-H”agele

and Zain

A.M.

, Modeling, reasoning, and application of fuzzy petri net model: a survey, Artificial Intelligence Review (2022), 1–39.

22.

Zhang

, Tian

, Fathollahi-Fard

A.M.

, Wang

, Wu

and Li

, Interval-valued intuitionistic uncertain linguistic cloud petri net and its application to risk assessment for subway fire accident, IEEE Trans. Autom. Sci. Eng. 19 (2022), 163–177.

23.

Zhou

K.-Q.

and Zain

A.M.

, Fuzzy Petri Nets and industrial applications: a review, Artif. Intell. Rev. 45 (2016), 405–446.

24.

Lee

E.T.

and Zadeh

L.A.

, Note on fuzzy languages, Information Sciences 1 (1969), 421–434.

25.

Mordeson

J.N.

and Malik

D.S.

, Fuzzy automata and languages: theory and applications, CRC Press (2002).

26.

Ajay Kumar , Nidhi Kalra and Sunita Garhwal , Error tolerance for the recognition of faulty strings in a regulated grammar using fuzzy sets, Sādhanā 43(8) (2018), 1–12.

27.

Nidhi Kalra and Ajay Kumar , Fuzzy state grammar and fuzzy deep pushdown automaton, Journal of Intelligent & Fuzzy Systems 31(1) (2016), 249–258.

28.

Moraga

, Some properties of fuzzy languages, In: Computational Intelligence, Theory and Applications, Springer, 2006, pp. 367–374.

29.

Kaspar

A.J.

and Sheena

D.K.

, Christy, Regular string token fuzzy Petri nets, Journal of Mathematics and Computer Science 30(2) (2023), 89–100.

30.

John Kaspar

, Sheena Christy

D.K.

, Masilamani

and Thomas

D.G.

, Two dimensional fuzzy regular languages. Fuzzy Sets and Systems, Fuzzy Sets and Systems 442(2022), 309–330.

31.

Samanta

, Pramanik

and Pal

, Fuzzy colouring of fuzzy graphs, Afrika Matematika 27(1) (2016), 37–50.