You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Isomorphism Between Two Vector General Fuzzy Automata

Article type: Research Article

Authors: Shamsizadeh, Marzieh1 | Movahednia, Ehsan1 | De la Sen, Manuel2; ∗

Affiliations: [1] Department of Mathematics, Behbahan Khatam Alanbia University of Technology, Khouzestan, Iran | [2] Department of Electricity and Electronics, Institute of Research and Development of Processes, University of Basque Country, Campus of Leioa (Bizkaia), 48080 Bilbao, Spain

Correspondence: [∗] Corresponding author.

Keywords: fuzzy automata, linear automata, vector automata, general fuzzy automata, Similar

DOI: 10.15388/23-INFOR514

Journal: Informatica, vol. 34, no. 3, pp. 617-633, 2023

Received July 2022
|
Accepted March 2023
|
Published: 2023
Get PDF open access

Abstract

In this paper, at first, we define the notion of general fuzzy automaton over a field; we call this automaton vector general fuzzy automaton (VGFA). Moreover, we present the concept of max-min vector general fuzzy automaton. We show that if two max-min VGFA are similar, they constitute an isomorphism. After that, we prove that if two VGFA constitute an isomorphism with threshold α, they are equivalent with threshold α, where α∈[0,1]. Also, some examples are given to clarify these new notions.

1Introduction

Theoretical computer science is the mathematical study of models of computation. As such, it originated in the 1930s, well before the existence of modern computers, in the work of the logicians Church, Godel, Kleene, Post, and Turing. This early work has had a profound influence on the practical and theoretical development of computer science. Not only has the Turing machine model proved essential for theory, but the work of these pioneers presaged many aspects of computational practice that are now commonplace and whose intellectual antecedents are typically unknown to users. Control theory is a branch of mathematics that deals with the behaviour of dynamical systems studied in terms of inputs and outputs.

Automata theory is one of the longest-established areas in computer science. Standard applications of automata theory include pattern matching, syntax analysis, and formal verification. In recent years, novel applications of automata-theoretic concepts have emerged from numerous sciences, like biology, physics, cognitive sciences, control, linguistics, and biology. For more information, see Aceto et al. (2007), Cassandras and Lafortune (2009), Shamsizadeh et al. (2020), Dovier et al. (2004), Even (1965), Roggenbach and Majster-Cederbaum (2000), Shamsizadeh et al. (2016), Shamsizadeh and Zahedi (2019). Directable automata were introduced in Starke (1969), and also definite automata by Kleene (1956). Wee (1967) and Santos (1968) have introduced the idea of fuzzy automata. Accordingly, fuzzy finite automata have been applied in many areas, such as learning systems, the model of computing with words, pattern recognition, lattice-valued fuzzy finite automata, and clinical monitoring, and also used as models of machine learning systems (Ying, 2002; Li and Shi, 2000). In general, fuzzy automata have provided an attractive systematic way of generalizing discrete applications (Cattaneo et al., 1997; Doostfatemeh and Kremer, 2003; Reiter, 2002; Srivastava and Tiwari, 2002). Moreover, fuzzy automata developed capabilities that are hardly achievable by other tools (Ying, 2002).

Several researchers have contributed to the growth of the fuzzy automata theory. Among these works, the work of Jin and his coworkers (Jin et al., 2013) is directed towards the algebraic study of fuzzy automata based on Po-monoids; the work of Abolpour and Zahedi (Abolpour et al., 2020; Abolpour and Zahedi, 2017) is directed towards the use of categorical concepts in the study of general fuzzy automata with membership values in different lattice structures; the work of Qiu (2001, 2002) is directed towards the algebraic, topological and categorical study of fuzzy automata theory based on residuated lattices; the work of Peeva (1988, 1991) relates to the study of minimizing the states of fuzzy automata and its application to study pattern recognition; the work of Pal and their coworkers (Pal et al., 2019) is directed towards the study of fuzzy automaton based on the residuated and co-residuated lattice, the work of Shamsizadeh and coworkers (Shamsizadeh et al., 2021; Raisi Sarbizhan et al., 2022; Shamsizadeh and Zahedi, 2022; Shamsizadeh, 2022) is directed towards the study of fuzzy automaton based on graph theory and multiset theory and neutrosophic sets; Ghorani, Moghari and coworkers (Ghorani and Moghari, 2022; Ghorani et al., 2022) study fuzzy tree automata based on lattice-valued.

In this paper, we define the notion of general fuzzy automaton over a field. We call this automaton vector general fuzzy automaton (VGFA). Moreover, we present the concept of max-min vector general L-fuzzy automaton. VGFA are used for generation of linear codes, detection and correction of errors, construction of testing sequence, and generation of pseudo-random sequences of numbers. They are also used in experiments that require Monte Carlo methods, in the protection of data stored in computer systems and radio location. We show that if two max-min VGFA are similar, then they constitute an isomorphism. After that, we prove that if two VGFA constitute an isomorphism with threshold α, they are equivalent with threshold α, where α∈[0,1]. Also, some examples are given to clarify these new notions.

2Preliminaries

In this section, we review some notions which are needed in the next section.

Definition 1

Definition 1(Mordeson and Malik, 2002).

A fuzzy finite state machine (ffsm) is a triple M=(Q,X,υ), where Q is a finite set of states, X is a set of input symbols and υ:Q×X×Q→[0,1] is a fuzzy transition function.

As usual, X∗ denotes the set of all words of elements of X of finite length, including the empty word Λ in X∗ and |x| denotes the length of x, for any x∈X∗.

Definition 2

Definition 2(Zahedi et al., 2008).

A fuzzy finite state automaton (FFA) is a six-tuple denoted by F˜=(Q,X,R,Z,δ,ω), where:

  • • Q={q1,q2,…,qn} is a finite set of states,

  • • X={a1,a2,…,am} is a finite set of input symbols,

  • • R is the start state of F˜,

  • • Z={b1,b2,…,bk} is a finite set of output symbols,

  • • δ:Q×X×Q→[0,1] is the fuzzy transition function which is used to map a state (current state) into another state (next state) upon an input symbol, attributing a value in the interval [0,1],

  • • ω:Q→Z is the output function.

In an FFA, as can be seen, associated with each fuzzy transition a membership value in [0,1]. We call this membership value, the value of the transition.

Definition 3

Definition 3(Doostfatemeh and Kremer, 2005).

A general fuzzy automaton (GFA) F˜ is an eight-tuple machine denoted by F˜=(Q,X,R˜,Z,δ˜,ω,F1,F2), where:

  • • Q={q1,q2,…,qn} is a finite set of states,

  • • X={a1,a2,…,am} is a finite set of input symbols,

  • • R˜⊆P˜(Q) is the set of fuzzy start states,

  • • Z={b1,b2,…,bk} is a finite set of output symbols,

  • • δ˜:(Q×[0,1])×X×Q→[0,1] is the augmented transition function,

  • • ω:Q→Z is the output function,

  • • F1:[0,1]×[0,1]→[0,1] is called the membership assignment function. The function F1(μ,δ), as is seen, is motivated by two parameters μ and δ, where μ is the membership value of a predecessor and δ is the value of a transition. In this definition, the process that takes place upon the transition from state qi to qj on an input ak is represented as

    μt+1(qj)=δ˜((qi,μt(qi)),ak,qj)=F1(μt(qi),δ(qi,ak,qj)).
    Which means that membership value (MV) of the state qj at time t+1 is computed by function F1 using both the membership value of qi at time t and the membership value of the transition. There are many options which can be used for the function F1(μ,δ). It can be, for example, max{μ,δ},min{μ,δ},μ+δ2 or any other applicable mathematical function.

  • • F2:[0,1]∗→[0,1] is called the multi-membership resolution function. The multi-membership resolution function resolves the multi-membership active states and assigns a single non-membership value to them.

    [0,1]∗ is the set of elements in [0, 1]. The multi-membership resolution function F2 is a function which specifies the strategy that resolves the multi-membership active states and assigns a single mv to them.

Definition 4

Definition 4(Bag and Samanta, 2003).

Let U be a linear space over a field F. A fuzzy subset N of U×R is called a fuzzy norm on U if and only if for every x,u∈U and c∈F,

  • 1. For every t∈R with t⩽0, N(x,t)=0,

  • 2. For every t∈R, t>0, N(x,t)=1 if and only if x=0,

  • 3. For every t∈R, t>0, N(cx,t)=N(x,t|c|) if c≠0,

  • 4. For every s,t∈R, x,u∈U, N(x+u,s+t)⩾min{N(x,s),N(u,t)},

  • 5. N(x,.) is a non-decreasing function of R and limt→∞N(x,t)=1.

The pair (U,N) will be referred to as a fuzzy normed linear space.

Example 1

Example 1(Bag and Samanta, 2003).

Let (U,‖‖) be a normed linear space. Define

(1)
N(x,t)=tt+‖x‖,whent(>0)∈R,∀x∈U,0,whent(⩽0)∈R,∀x∈U.
Then (U,N) is a fuzzy normed linear space.

Example 2

Example 2(Bag and Samanta, 2003).

Let (U,‖‖) be a normed linear space. Define

(2)
N(x,t)=0,ift⩽‖x‖,1,ift>‖x‖.
Then (U,N) is a fuzzy normed linear space.

3Vector General Fuzzy Automaton

Definition 5.

Let F be a field and n∈N0. By Fn we denote the vector space of column vectors of dimension n over F. A vector general fuzzy automaton (VGFA) is an automaton F˜v=(Q,X,R˜,Z,δ˜,ω˜,F1,F2,F3,F4) with the following properties:

  • (i) There exists a field F and integers k,m,r∈N0, such that

    • 1. Q=Fk is a nonempty finite set of states, Q={u1,u2,u3,…}, where u1=(u1(1),u1(2),…,u1(k))∈Fk,

    • 2. X=Fm is a finite set of input symbols, X={a1,a2,a3,…}, where a1=(a1(1),a1(2),…,a1(m))∈Fm,

    • 3. R˜⊆P(Q˜) is the set of L-fuzzy start symbols,

    • 4. Z=Fr is a finite set of output symbols, Z={z1,z2,z3,…}, where z1=(z1(1),z1(2),…,z1(r))∈Fr;

  • (ii) There exist a k×k matrix A, a k×m matrix B, and a r×k matrix C, all over F, such that

    • 1. δ˜:(Q×[0,1])×X×Q→[0,1] is the augmented transition function, where δ(u,a,Au+Ba)∈Δ.

    • 2. ω˜:(Q×[0,1])×Z→[0,1] is the augmented output function.

    • 3. F1:[0,1]×[0,1]→[0,1] is called the membership assignment function. The function F1(μ,δ), as is seen, is motivated by two parameters μ and δ, where μ is the membership value of a predecessor and δ is the value of a transition. In this definition, the process that takes place upon the transition from state ui to uj on an input ak is represented as

      μt+1(uj)=δ˜((ui,μt(ui)),ak,uj)=F1(μt(ui),δ(ui,ak,uj)).
      Which means that membership value (MV) of the state uj at time t+1 is computed by function F1 using both the membership value of ui at time t and the membership value of the transition. There are many options which can be used for the function F1(μ,δ). For example, it can be max{μ,δ}, min{μ,δ}, μ+δ2 or any other applicable mathematical function.

    • 4. F2:[0,1]×[0,1]→[0,1] is called the membership assignment output function. F2(μ,ω) as is seen, is motivated by two parameters μ and ω, where μ is the membership value of present state and ω is the membership value of an output function. Then

      ω˜((u,μti(u)),z)=F2(μti(u),ω(u,z)).
      Notice that ω(u,z)>0 if and only if z=Cu.

    • 5. F3:[0,1]∗→[0,1] is called the multi-membership resolution function. The multi-membership resolution function resolves the multi-membership active states and assigns a single membership value to them.

    • 6. F4:[0,1]∗→[0,1] is called the multi-membership resolution output function. The multi-membership resolution output function resolves the output multi-membership active state and assigns a single output membership value to it.

We let the set of all transitions of F˜v is denoted by Δ. Now, suppose that Qact(ti) be the set of all active states at time ti, for all i⩾0. We have Qact(t0)=R˜ and

Qact(ti)={(Au+Ba,μti(Au+Ba))|∃u∈Qact(ti−1),∃a∈X,δ(u,a,Au+Ba)∈Δ},
where Δ={δ(u,a,Au+Ba)|u∈Q,a∈X} for every i⩾1. Since Qact(ti) is a fuzzy set, to show that a state u belongs to Qact(ti) and T is a subset of Qact(ti), we write u∈Domain(Qact(ti)). Hereafter, we denote these notations by
u∈Qact(ti)andT⊆Qact(ti).

The combination of the operations of functions F1 and F3 on a multi-membership state uj leads to the multi-membership resolution algorithm. By using (Doostfatemeh and Kremer, 2005; Shamsizadeh and Zahedi, 2015) we have the following algorithms.

Algorithm: Multi-membership resolution for transition function:

If there are several simultaneous transitions to the active state uj at time t+1, then the following algorithm will assign a unified membership value to that.

  • Step 1. Input: δ1(ui,ak,uj), μt(ui), i,j=1,2,…,m, and k=1,2,…,l,

  • Step 2. For i,j=1,2,…,m, and k=1,2,…,l, compute δ˜1((ui,μt(ui)),ak,uj)=F1(μt(ui),δ1(ui,ak,uj)),

  • Step 3. For j=1,2,…,m, μt+1(uj)=(F3)n−1(x1,x2,…,xn), where n is the number of simultaneous transitions to the active state uj at time t+1 and xr=F1(μt(ui),δ1(ui,ak,uj)), 1⩽r⩽n,

  • Step 4. Output: for j=1,2,…,m, print: μt+1(uj).

Algorithm: Multi-membership resolution for output function:

If there are several simultaneous outputs to the active state ui at time t, the following algorithm will assign a unified membership value to it.

  • Step 1. Input: ω1(ui,zk), μt(ui), i=1,2,…,m, k=1,2,…,l,

  • Step 2. For i=1,2,…,m, k=1,2,…,l, compute:

    ω˜1((ui,μt(ui)),zk)=F2(μt(ui),ω1(ui,zk)),

  • Step 3. For i=1,2,…,m, ω1t(ui)=F4n−1(x1,x2,…,xn), where n is the number of simultaneous outputs to the active state ui at time t, xr=F2(μt(ui),ω1(ui,zj)), 1⩽r⩽n,

  • Step 4. Output: for i=1,2,…,m, print: ω1t(ui).

Remark 1.

For every u∈Q, such that u∉R˜, we have μt0(u)=0 and q∈R˜ implies that μt0(q)>0.

Definition 6.

We shall often want to refer to a finite non-empty set Fm as a vector alphabet. If Fm is a vector alphabet, let Fm+ consist of all finite sequences

(3)
(a1(1),a1(2),…,a1(m)).(a2(1),a2(2),…,a2(m)),…,(ak(1),ak(2),…,ak(m)),
where (ai(1),ai(2),…,ai(m))∈Fm and 1⩽i⩽k.

The multiplication given by (3) then corresponds to just a simple position:

(a1(1),a1(2),…,a1(m)).(a2(1),a2(2),…,a2(m))=(a1(1)a2(1),a1(2)a2(2),…,a1(m)a2(m)).

Definition 7.

Let F˜v=(Q,X,R˜,Z,δ˜,ω˜,F1,F2,F3,F4) be a VGFA. We define the max-min vector general fuzzy automaton F˜v∗=(Q,X,R˜,Z,δ˜∗,ω˜,F1,F2,F3,F4), such that δ˜∗:Qact×X∗×Q→[0,1]×[0,1], where Qact={Qact(t0),Qact(t1),Qact(t2),…} and for every i⩾0,

(4)
δ˜∗((u1,μti(u1)),Λ,u2)=1,ifu1=u2,0,otherwise.

Also, for every i⩾0, δ˜∗((u1,μti(u1)),ai+1,u2)=δ˜((u1,μti(u1)),ai+1,u2) and recursively,

(5)
δ˜∗((u1,μt0(u1)),a1a2…an−1,un)=∨{δ˜((u1,μt0(u1)),a1,u2)∧δ˜((u2,μt1(u2)),a2,u3)∧⋯∧δ˜((un−1,μtn−2(un−1)),an−1,un)|u2∈Qact(t1),…,un−1∈Qact(tn−1)},
in which ai∈X for every 1⩽i⩽n−1, and assume that ai+1 is the entered input at time ti, for every 0⩽i⩽n−2.

Actually, the fact that the VGFA acts in discrete time we will also use the notation

(6)
ut+1=Aut+Bat,
(7)
ωut=Cut,
where ut∈Qact(t), at∈X, ωqt∈Z for t∈N0.

Notice that when we want to consider a word, we can write it as enumeration. If we have

w=(a1,a2,…,ak)(b1,b2,…,bk)(b1,b2,…,bk)(c1,c2,…,ck),
for use of equation (6), we consider w as follows:
(a1,a2,…,ak)=σ1,(b1,b2,…,bk)=σ2,(b1,b2,…,bk)=σ3,(c1,c2,…,ck)=σ4.

Since field F and matrices A, B and C entirely characterize the vector general fuzzy automaton (VGFA), we shall also denote automaton by 13-tuple machine (F,Q,X,A,B,C,R˜,Z,δ˜,ω˜,F1,F2,F3,F4).

Example 3.

Let L be a bounded lattice as in Fig. 1. Let F˜v=(F,Q,X,A,B,C,R˜,Z,δ˜,ω˜,F1,F2,F3,F4) be a VGFA defined over field F=Q2 of integers modulo 2, such that A=[0110], B=[11], C=[01], Q={[00],[11],[01],[10]}, X={[0],[1]}, R˜=([00],1), Z={[0],[1]} and δ, ω are defined as follows:

δ01,0,10=α,δ01,1,01=α,δ00,0,00=β,δ00,1,11=β,δ10,0,01=γ,δ10,1,10=γ,δ11,0,11=α,δ11,1,00=α,ω01,1=γ,ω10,0=η,ω00,0=β,ω11,1=γ.
If we choose F1=∧ and F2=∨ and μt0([00])=1, we have
μt100=F1(μt000,δ00,0,00=1∧β=β,μt111=F1(μt000,δ00,1,11=1∧β=β,μt200=F1(μt100,δ00,0,00∨F1μt111,δ11,1,00=(β∧β)∨(β∧α)=β∨α=β,μt211=F1(μt100,δ00,1,11∨F1(μt111,δ11,0,11=(β∧β)∨(β∧α)=β∨α=β.
Notice that there exists no μt1([10]), since δ([00],0,[10]) does not belong to Δ. By choosing a different Matrices A and B, it is possible to obtain μt1([10]) and μt1([01]). Now, we have
ω˜t100,μt100,0=F2μt100,ω00,0=β∧β=β,ω˜t111,μt111,1=F2μt111,ω11,1=β∧γ=η.
The diagram of VGFA is presented on Fig. 2.
Fig. 1

The bounded lattice L of Example 3.

The bounded lattice L of Example 3.

Fig. 2

The vector general fuzzy automaton F˜v of Example 3.

The vector general fuzzy automaton F˜v of Example 3.

4Equivalence and Isomorphism for Vector General Fuzzy Automata

Theorem 1.

Let a VGFA F˜v=(F,Q,X,A,B,C,R˜,Z,δ˜,ω˜,F1,F2,F3,F4) be given. Then the following properties hold:

  • 1. ut=Atu0+∑i=0t−1At−i−1Bai, for every t∈N,

  • 2. ωt=CAtu0, for every t∈N0.

Proof.

1. We prove the claim by induction on t. If t=1, then we have

Au0+∑i=00A1−i−1Bai=Au0+A0Ba0=Au0+Ba0=u1.
Now, suppose the claim holds for t=n, so we have un=Anu0+∑i=0n−1An−i−1Bai. Let t=n+1. Then
un+1=Aun+Ban=A(Anu0+∑i=0n−1An−i−1Bai)+Ban=An+1u0+A∑i=0n−1An−i−1Bai+Ban=An+1u0+∑i=0nAn−iBai.
2. By induction on t, it is omitted.  □

Definition 8.

Let F˜vi=(F,Qi,X,Ai,Bi,Ci,R˜i,Z,δ˜i,ω˜i,F1,F2,F3,F4) where i=1,2, be two VGFAs. We say that F˜v1 is similar to F˜v2 if there exists a nonsingular matrix P, such that

  • i. u∈R˜1 if and only if Pu∈R˜2,

  • ii. A2=PA1P−1,

  • iii. B2=PB1,

  • iv. C2=C1P−1.

Definition 9.

Let F be a field. Let F˜vi=(Qi,X,Ai,Bi,Ci,R˜i,Z,δ˜i,ω˜i,F1,F2,F3,F4) where i=1,2, be two VGFAs. A homomorphism from F˜v1 onto F˜v2 with threshold α, is a function φ from Q1 onto Q2 such that for every u,u′∈Q1 and a∈X and z∈Z the following conditions hold:

  • I. μt0(u)>α if and only if μt0(φ(u))>α,

  • II. δ1(u,a,u′)>α if and only if δ2(φ(u),a,φ(u′))>α.

    Actually, I and II show that δ˜1((u,μt(u)),a,u′)>α if and only if

    δ˜2((φ(u),μt(φ(u))),a,φ(u′))>α.

  • III. ω˜1((u,μti(u)),z)>α implies that ω˜2((φ(u),μti(φ(u))),z)>α.

    We say that φ constitutes an isomorphism with threshold α if φ constitutes an a homomorphism with threshold α that is one-to-one and ω˜1((u,μti(u)),z)>α if and only if ω˜2((φ(u),μti(φ(u))),z)>α.

If φ constitutes an isomorphism with threshold 0, then we say that φ constitutes an isomorphism.

Theorem 2.

Let F˜vi=(F,Qi,X,Ai,Bi,Ci,R˜i,Z,δ˜i,ω˜i,F1,F2,F3,F4) where i=1,2, be two VGFAs. If F˜v1 is similar to F˜v2, then F˜v1 and F˜v2 constitute an isomorphism.

Proof.

Let P be a nonsingular matrix such that A2=PA1P−1, B=PB1, C2=C1P−1. Let φ:Q1→Q2 be a map such that φ(u)=Pu, for every u∈Fk. It is clear that φ is well defined. Now, let φ(u1)=φ(u2), for every u1,u2∈Q1. Then Pu1=Pu2. Since P is a nonsingular matrix, then u1=u2. Therefore, φ is one-one. Hence, φ is bijection. Now, let μt0(u)>0, where u∈Fk. Then u∈R˜1. Since φ(u)=Pu and by considering Definition 8 we have Pu∈R˜2, so φ(Pu)>0. Suppose that μt0(φ(u))>0 thus, φ(u)∈R˜2. By using Definition 8, we have μt0(u)>0 and u∈R˜1. Let δ1(u,a,u′)>0. Then by Definition 5, we have δ1(u,a,u′)∈Δ. It implies that u′=A1u+B1a. Therefore,

φ(u′)=Pu′=P(A1u+B1a)=PA1u+PB1a=PA1P−1Pu+PB1a=(PA1P−1)Pu+PB1a=A2φ(u)+B2a.
By Definition 5, δ2(φ(u),a,A2φ(u)+B2a)=δ2(φ(u),a,φ(u′))∈Δ, hence, δ2(φ(u),a,φ(u′))>0. Now, let δ2(v,a,v′)>0, where v,v′∈Q2. Then there exists u,u′∈Q1, such that φ(u)=v and φ(u′)=v′. So,
δ2(v,a,v′)=δ2(φ(u),a,φ(u′))>0⟹δ2(Pu,a,Pu′)>0⟹δ2(Pu,a,Pu′)∈Δ⟹Pu′=A2Pu+B2a⟹Pu′=PA1P−1Pu+PB1a⟹Pu′=PA1u+PB1a⟹u′=A1u+B1a⟹δ(u,a,u′)∈Δ⟹δ(u,a,u′)>0.
We show that δ1((u,μt0(u)),a,u′)>0 if and only if δ2((φ(u),μt0(φ(u))),a,φ(u′))>0. Let ω˜1((u,μti(u)),z)>0. Then μti(u)>0 and ω1(u,z)>0. By Definition 5, we have z=C1u. By considering Definition 8, we have z=C1u=C2Pu=C2φ(u). Thus, ω2(φ(u),z)>0. Also, we have μti(u)>0 if and only if μti(φ(u))>0. Therefore, ω˜2((φ(u),μti(φ(u))),z)>0. The opposite can be proved in a similar way.  □

The opposite of Theorem 2 is not true because there exist isomorphic VGFA which are not similar. As an illustration, let us give the following example.

Example 4.

Let L be a bounded lattice as in Fig. 1, Q7 be a field and

F˜v1=(Q7,{[0],[1],[2],…,[6]},{[0]},[3],[0],[2],{[0],μt0)([0])=α},[1],δ˜1,ω1,F1,F2,F3,F4),
and
F˜v2=(Q7,{[0],[1],[2],…,[6]},{[0]},[5],[0],[2],{[0],μt0)([0])=α},[1],δ˜2,ω2,F1,F2,F3,F4),
where α∈[0,1]. Also, let φ:Q1→Q2 be a map such that φ([m])=[m] and δ1([u],[0],[3][u])=α, for every [u]∈Q1 and δ2([u],[0],[5][u])=α, for every [u]∈Q2, and suppose that ωi([u],[2][u])=α, for every [u]∈Q1=Q2 and i=1,2. It is clear that F˜v1 and F˜v2 are isomorphic but not similar because the matrix [3] is not similar to matrix [5] over the field Q7 of integers modulo 7.

Definition 10.

Let F˜=(F,Q,X,A,B,C,R˜,Z,δ˜,ω˜,F1,F2,F3,F4) be a max-min VGFA. The language with threshold α, α∈[0,1], recognized by F˜, is a subset of Fm∗ defined by

Lc(F˜)={x∈Fm∗|δ˜∗((u,μt0(u)),x,v)∧ω˜((v,μt0+|x|(v)),z)>α,for someu,v∈Fk,z∈Z,fori=1,…,n}.

Definition 11.

Two max-min VGFAs F˜v1 and F˜v2 are called equivalent with threshold α if Lα(F1)=Lα(F2), where α∈[0,1].

Theorem 3.

Let F˜v1 and F˜v2 be two max-min VGFAs. Let F˜v1 and F˜v2 be isomorphic with threshold α, where α∈[0,1]. Then they are equivalent with threshold α.

Proof.

Let F˜vi=(F,Qi,X,Ai,Bi,Ci,R˜i,Z,δ˜i,ω˜i,F1,F2,F3,F4), i=1,2, be two max-min VGFAs and φ:Q1→Q2 be a homomorphism. Now, let a1a2…ak=x∈L(F˜v1). Then there exist u,v∈Fk and z∈Fr, such that δ˜1∗((u,μt0(u)),x,v)∧ω˜1((v,μt0+|x|(v)),z)>α, where α∈[0,1]. So, δ˜1∗((u,μt0(u)),x,v)>α and ω˜1((v,μt0+|x|(v)),z)>α. Then there exists u1,u2,…,uk−1∈Q1, such that

μt0(u)>α,δ1(u,a1,u1)>α,…,δ1(uk−1,ak,v)>α,ω(v,b)>α.
By Definition 9, we have
μt0(φ(u))>α,δ2(φ(u),a1,φ(u1))>α,…,δ2(φ(uk−1),ak,φ(v))>α,ω(φ(v),z)>α.
It is implied that x∈L(F˜v2). Therefore, L(F˜v1)⊆L(F˜v2). In a similar way L(F˜v2)⊆L(F˜v1). Hence, L(F˜v1)=L(F˜v2).  □

5General Fuzzy Automaton on Fuzzy Normed Linear Space

Definition 12.

Let F be a field and n∈N0. By Fn we denote the vector space of column vectors of dimension n over F. A general automaton on fuzzy normed linear space (or simply fuzzy norm general automata (FNGA)) is an automaton F˜n=(Q,X,I,Z,δ˜,ω˜,N1,N2,∨,∨) with the following properties:

  • (i) There exist a field F and integers k,m,r∈N0, such that

    • 1. Q=Fk is a nonempty finite set of states, Q={u1,u2,u3,…}, where u1=(u1(1),u1(2),…,u1(k))∈Fk,

    • 2. X=Fm is a finite set of input symbols, X={a1,a2,a3,…}, where a1=(a1(1),a1(2),…,a1(m))∈Fm,

    • 3. I⊆Q is the set of start symbols,

    • 4. Z=Fr is a finite set of output symbols, Z={z1,z2,z3,…}, where z1=(z1(1),z1(2),…,z1(r))∈Fr;

  • (ii) There exist a k×k matrix A, a k×m matrix B, and a r×k matrix C, all over F such that

    • 1. δ˜:(Q×R)×X×Q→[0,1] is the augmented transition function, where δ(u,a,Au+Ba)∈R, δ(u,Λ,Au+BΛ)=0, and R is set of real number,

    • 2. ω˜:(Q×R)×Z→[0,1] is the augmented output function,

    • 3. N1:U×R→[0,1] is called the membership assignment function. In this definition, the process that takes place upon the transition from state ui to uj on an input a∈X is represented as follows:

      μt+1(uj)=δ˜((ui,μt(ui)),a,uj)=N1a(Aui+Ba,μt(ui)),
      where N1 is a fuzzy normed linear space and U is a linear space over a fileld F,

    • 4. N2:U×R→[0,1] is called the membership assignment output function. N2(μ,ω), as it seems, is motivated by two parameters μ and ω, where μ is the membership value of present state and ω is the membership value of an output function. Then

      ω˜((u,μti(u)),z)=N2(Cu,μti(u)).

We let the set of all transitions of F˜v be denoted by Δ. Now, suppose that Qact(ti) is the set of all active states at time ti, for all i⩾0. We have Qact(t0)=I and

Qact(ti)={(Au+Ba,μti(Au+Ba))|∃u∈Qact(ti−1),∃a∈X,δ(u,a,Au+Ba)∈Δ},
where Δ={δ(u,a,Au+Ba)|u∈Q,a∈X} for every i⩾1. Qact(ti),i>0 is a fuzzy set.

Remark 2.

For every u∈Q, such that u∉I, we have μt0(u)=0 and q∈I implies that μt0(q)>0.

Definition 13.

Let F˜n=(Q,X,I,Z,δ˜,ω˜,N1,N2,∨,∨) be a FNGA. We define the max-min fuzzy norm general automaton F˜n∗=(Q,X,I,Z,δ˜∗,ω˜,N1,N2,∨,∨), such that δ˜∗:Qact×X∗×Q→[0,1], where Qact={Qact(t0),Qact(t1),Qact(t2),…} and for every i⩾0,

(8)
δ˜∗((u1,μti(u)),Λ,u2)=1,ifu2=Au1+BΛ,0,otherwise.

Also, for every i⩾0, δ˜∗((u1,μti(u1)),ai+1,u2)=δ˜((u1,μti(u1)),ai+1,u2) and recursively,

(9)
δ˜∗((u1,μt0(u1)),a1a2…an−1,un)=∨{δ˜((u1,μt0(u1)),a1,u2)∧δ˜((u2,μt1(u2)),a2,u3)∧⋯∧δ˜((un−1,μtn−2(un−1)),an−1,un)|u2∈Qact(t1),…,un−1∈Qact(tn−1)},
in which ai∈X, for every 1⩽i⩽n−1, and assume that ai+1 is the entered input at time ti, for every 0⩽i⩽n−2.

Example 5.

Let F˜v=(F,Q,X,A,B,C,R˜,Z,δ˜,ω˜,N1,N2,∨,∨) be an FNGA defined over field F=Q2 of integers modulo 2 such that A=[0110], B=[11], C=01, Q={[00],[11],[01],[10]}, X={[0],[1]},R˜=([00],1), and Z={[0],[1]}. Let μt0([00])=9. If we consider N1a as Example 1, and N2 as Example 1, then we have:

μt100=N1[0]00,μt000=11+0=1,μt111=N1[1]11,μt000=11+2=0.414,μt200=N1[0]00,μt100∨N1[1]00,μt111=11+0∨0.4140.414+0=1∨1=1,μt211=N1[1]11,μt100∨N1[0]11,μt111=11+2∨(0.4140.414+2)=0.414.
Now, we have
ω˜00,μt100,0=N20,μt100=1,ω˜11,μt111,1=N21,μt111=0.

6Conclusion

General fuzzy automaton over a field are used for generation of linear codes, detection and correction of errors, construction of testing sequence, and generation of pseudo-random sequences of numbers. They are also used in experiments that require Mote Carlo methods, in the protection of data stored in computer systems and radio-location.

In the recent study, we defined the notion of general fuzzy automaton and max-min general fuzzy automaton over a field; we call this automaton vector general fuzzy automaton. Moreover, we presented the concept of max-min vector general fuzzy automaton. We proved that if two max-min VGFA are similar, they constitute an isomorphism. Moreover, we showed that if two VGFA constitute an isomorphism with threshold α, they are equivalent with threshold α, where α∈[0,1]. Also, we presented a general automaton on fuzzy normed linear space.

Further, we try to present a connection between VGFA and similar automata. Also, we try to present fuzzy finite tree automaton over a fuzzy normed linear space.

References

1 

Abolpour, K., Zahedi, M. ((2017) ). General fuzzy automata based on complete residuated lattice-valued. Iranian Journal of Fuzzy Systems, 14: (5), 103–121.

2 

Abolpour, K., Zahedi, M., Shamsizadeh, M. ((2020) ). BL-general fuzzy automata and minimal realization: based on the associated categories. Iranian Journal of Fuzzy Systems, 17: (1), 155–169.

3 

Aceto, L., Ingólfsdóttir, A., Larsen, K.G., Srba, J. ((2007) ). Reactive Systems: Modelling, Specification and Verification. Cambridge University Press.

4 

Bag, T., Samanta, S. ((2003) ). Finite dimensional fuzzy normed linear spaces. Journal of Fuzzy Mathematics, 11: (3), 687–706.

5 

Cassandras, C., Lafortune, S. ((2009) ). Introduction to Discrete Event Systems, Number 1. Springer Science & Business Media, Berlin/Heidelberg, Germany.

6 

Cattaneo, G., Flocchini, P., Mauri, G., Vogliotti, C.Q., Santoro, N. ((1997) ). Cellular automata in fuzzy backgrounds. Physica D: Nonlinear Phenomena, 105: (1–3), 105–120.

7 

Doostfatemeh, M., Kremer, S.C. ((2003) ). A fuzzy finite-state automaton that unifies a number of other popular computational paradigms. In: Proceedings of the Artificial Neural Networks in Engineering Conference (ANNIE 03’), pp. 441–446.

8 

Doostfatemeh, M., Kremer, S.C. ((2005) ). New directions in fuzzy automata. International Journal of Approximate Reasoning, 38: (2), 175–214.

9 

Dovier, A., Piazza, C., Policriti, A. ((2004) ). An efficient algorithm for computing bisimulation equivalence. Theoretical Computer Science, 311: (1-3), 221–256.

10 

Even, S. ((1965) ). On information lossless automata of finite order. IEEE Transactions on Electronic Computers, 14: (4), 561–569.

11 

Ghorani, M., Moghari, S. ((2022) ). Decidability of the minimization of fuzzy tree automata with membership values in complete lattices. Journal of Applied Mathematics and Computing, 68: (1), 461–478.

12 

Ghorani, M., Garhwal, S., Moghari, S. ((2022) ). Lattice-valued tree pushdown automata: pumping lemma and closure properties. International Journal of Approximate Reasoning, 142: , 301–323.

13 

Jin, J., Li, Q., Li, Y. ((2013) ). Algebraic properties of L-fuzzy finite automata. Information Sciences, 234: , 182–202.

14 

Kleene, S.C. ((1956) ). Representation of events in nerve nets and finite automata. In: Shannon, C.E., McCarthy, J. (Eds.), Automata Studies, Vol. 34: . Princeton University Press, Princeton, pp. 3–42. https://doi.org/10.1515/9781400882618-002.

15 

Li, Y.-M., Shi, Z.-K. ((2000) ). Remarks on uninorm aggregation operators. Fuzzy Sets and Systems, 114: (3), 377–380.

16 

Mordeson, J.N., Malik, D.S. ((2002) ). Fuzzy Automata and Languages: Theory and Applications. CRC Press.

17 

Pal, P., Tiwari, S., Verma, R. ((2019) ). Different operators in automata theory based on residuated and co-residuated lattices. New Mathematics and Natural Computation, 15: (01), 169–190.

18 

Peeva, K. ((1991) ). Fuzzy acceptors for syntactic pattern recognition. International Journal of Approximate Reasoning, 5: (3), 291–306.

19 

Peeva, K.G. ((1988) ). Behaviour, reduction and minimization of finite L-automata. Fuzzy Sets and Systems, 28: (2), 171–181.

20 

Qiu, D. ((2001) ). Automata theory based on complete residuated lattice-valued logic. Science in China Series: Information Sciences, 44: , 419–429.

21 

Qiu, D. ((2002) ). Automata theory based on complete residuated lattice-valued logic (II). Science in China Series F: Information Sciences, 45: , 442–452.

22 

Raisi Sarbizhan, E., Mehdi Zahedi, M., Shamsizadeh, M. (2022). L-graph automata and some applications. The Computer Journal, bxac035. https://doi.org/10.1093/comjnl/bxac035.

23 

Reiter, C.A. ((2002) ). Fuzzy automata and life. Complexity, 7: (3), 19–29.

24 

Roggenbach, M., Majster-Cederbaum, M. ((2000) ). Towards a unified view of bisimulation: a comparative study. Theoretical Computer Science, 238: (1–2), 81–130.

25 

Santos, E.S. ((1968) ). Maximin automata. Information and Control, 13: (4), 363–377.

26 

Shamsizadeh, M. ((2022) ). Single valued neutrosophic general machine. Neutrosophic Sets and Systems, 49: (1), 33.

27 

Shamsizadeh, M., Zahedi, M. ((2015) ). Minimal intuitionistic general L-fuzzy automata. Italian Journal of Pure and Applied Mathematics, 35: , 155–186.

28 

Shamsizadeh, M., Zahedi, M.M. ((2019) ). Bisimulation of type 2 for BL-general fuzzy automata. Soft Computing, 23: (20), 9843–9852.

29 

Shamsizadeh, M., Zahedi, M.M. ((2022) ). On reduced fuzzy multiset finite automata. Soft Computing, 26: (24), 13381–13390.

30 

Shamsizadeh, M., Zahedi, M., Abolpour, K. ((2016) ). Bisimulation for BL-general fuzzy automata. Iranian Journal of Fuzzy Systems, 13: (4), 35–50.

31 

Shamsizadeh, M., Zahedi, M., Abolpour, K. (2020). Reduction of BL-general L-fuzzy automata. Iranian Journal of Mathematical Sciences and Informatics.

32 

Shamsizadeh, M., Zahedi, M., Golmohamadian, M., Abolpour, K. ((2021) ). Zero-forcing finite automata. International Journal of Industrial Mathematics, 13: (4), 477–488.

33 

Srivastava, A.K., Tiwari, S. ((2002) ). A topology for fuzzy automata. In: Advances in Soft Computing—AFSS 2002: 2002 AFSS International Conference on Fuzzy Systems Calcutta, India, February 3–6, 2002 Proceedings. Springer, pp. 485–490.

34 

Starke, P. ((1969) ). Abstrakte Automaten. VEB Deutscher Verlag der Wissenschaften, Berlin.

35 

Wee, W.G. (1967). On Generalizations of Adaptive Algorithms and Application of the Fuzzy Sets Concept to Pattern Classification. Thesis, Purdue University.

36 

Ying, M. ((2002) ). A formal model of computing with words. IEEE Transactions on Fuzzy Systems, 10: (5), 640–652.

37 

Zahedi, M., Horry, M., Abolpor, K. ((2008) ). Bifuzzy (General) topology on max-min general fuzzy automata. Advanced in Fuzzy Mathematics, 3: (1), 51–68.

Show more