A minimization algorithm for fuzzy top-down tree automata over lattices

1 Introduction

The theory of tree languages and tree automata generalizes the theory of string languages and automata. Tree automata were introduced in [6, 42]. The goal was to prove the decidability of the weak second-order theory of multiple successors. Over the past four decades, the theory of tree automata and tree languages has been developed intensively (see [5, 18–21]). A tree automaton may process input trees either bottom-up (frontier-to-root) starting at the leaves and proceeding towards the root, or top-down (root-to-frontier) starting at the root and moving towards the leaves. A significant difference with the string case where right-to-left equals left-to-right processing, is that bottom-up is not necessarily equivalent to top-down. In particular, top-down deterministic tree automata are strictly less expressive than their bottom-up counterparts and consequently form a strict subclass of the regular tree languages. Moreover, deterministic top-down tree automata do not have many of the main closure properties. For example, they are neither closed under complement nor union [5]. For more results and references on top-down deterministic tree automata, we refer the reader to [33]. Tree automata have successfully been applied as formal models for analyzing and transforming trees in applications like natural language processing, XML processing, picture generation and the processing of semi-structured documents [8, 43].

Fuzzy tree automata have been considered by many researchers. Fuzzy tree automata models are obtained from classical tree automata, top-down, or bottom-up. In such tree automata, transitions are equipped with weights which might model, e.g., resources used for the execution of transitions, length of time needed, or the reliability. Inagaki and Fukumura [25] investigated fuzzy tree automaton as a special case of weighted tree automaton that accepts formal tree series over a complete semiring. Mordeson and Malik [38] defined a fuzzy tree automaton as an acceptor of a fuzzy dendrolanguage. Esik and Liu [9] studied fuzzy tree automata with membership in a distributive lattice and, after defining a fuzzy recognizable tree language, they derived a Kleene’s theorem for fuzzy tree automata. Bozapalidis and Bozapalidoy [4] showed that linear tree homomorphisms preserve syntactic recognizability. More results on fuzzy (tree) automata can be found in [12, 44] and references therein. Since, fuzzy tree automata take values in the unit interval [0, 1], to enhance the processing ability of fuzzy tree automata, Ghorani and her co-authors [15–21] extended the membership value to a more general algebraic structure and considered tree automata based on complete residuated lattice-valued logic.

Tree automata minimization problem is of great importance both from the theoretical point of view as well as from the application point of view. From a practical perspective, it is important to reduce the state space of a system and the investigated automata to be as small as possible. Moreover, some decision problems such as intersection, equivalence, and non-emptiness are closely related to minimization problem [5]. Björklund and Cleophas [3] have proposed a taxonomy of algorithms for minimizing ranked deterministic bottom-up tree automata, and Gécseg and Steinby [14] minimized deterministic top-down tree automata. Moreover, a polynomial-time minimization algorithm for minimizing unranked top-down tree automata when they are state-separated was presented in [11]. Other algorithms for minimizing deterministic tree automata can be found in [5, 26]. Also, efficient methods to reduce the size of nondeterministic tree automata were explored in [1, 24]. Several minimization algorithms for (deterministic) weighted tree automata were considered in [23, 32]. Moghari and Zahedi [34] have proposed a minimization algorithm for deterministic fuzzy tree automata which preserves the analogy of the languages of the main fuzzy tree automaton and the minimized one. Moreover, efficient language and behavior preserving minimization algorithms for deterministic fuzzy tree automata were presented in [35]. The procedures given in [34, 35] run different algorithms, including reduction and normalization algorithms, to find a fuzzy minimal tree automaton. Other minimization algorithms for fuzzy tree automata can be found in [36–38]. Ghorani and Zahedi [18] considered the minimization of complete residuated lattice-valued (bottom-up) tree automata and presented a minimization algorithm. To use this algorithm, the input tree automaton must be complete, reduced, and deterministic. Some applications of minimization of fuzzy (tree) automata can be found in [10, 45].

In this contribution, we study fuzzy top-down tree automata over lattices ( LTA s , for short). The purpose of this paper is to study the minimization problem for LTA s . We first define the concept of equivalence between two LTA s . Thereafter, we show the existence of the statewise minimal form for an LTA . Next, we provide an algorithm to find the statewise minimal LTA , and show that the output statewise minimal LTA is statewise equivalent to the given input. Moreover, we compute the time complexity of the given algorithm. Unlike the procedures given in [34, 35], we only apply one algorithm to find a minimal tree automaton. Moreover, if we apply the minimization algorithms presented in [18, 35] to find a statewise minimal form for a given LTA , the input must be a complete, deterministic and reduced lattice-valued tree automaton, but our algorithm can find a statewise minimal LTA for any given LTA .

The content of this paper is arranged as follows: Section 2, introduces some preliminaries and basic definitions. In Section 3, we proceed with the minimization of LTA s . Finally, in Section 4 the conclusions are given.

2 Preliminaries and basic definitions

In this paper, L = 〈 L , + , · , 0 , 1 〉 means a lattice with the least and the greatest elements 0 and 1, respectively, where L is a partially ordered set with the partial order relation ≤, and for any a , b ∈ L , a + b and a · b denote the supremum and infimum of {a,b}, respectively. If A is the universe, then L A denotes the class of all fuzzy subsets of A over L , whereby a fuzzy subset of A over L we mean a fuzzy mapping from A to L .

Example 1. Let L = { ∅ , { a } , { b } , { a , b } } , where ∅ ⊆ {a} , {b} ⊆ {a, b} . Then,

L = 〈 L , ∪ , ∩ , ∅ , { a , b } 〉 is a lattice.

Example 2. Let L = [ 0 , 1 ] ⊆ R . Then L = 〈 L , ∨ , ∧ , 0 , 1 〉 is a lattice, where ∨ and ∧ are max and min , respectively.

Definition 1. [5] A ranked alphabet is a couple (F, Arity) where F is a finite set and Arity is a mapping from F into W (the set of non-negative integers). The arity of a symbol f ∈ F is Arity (f). The set of symbols of arity n is denoted by F _n  . The elements of arity 0, 1, ⋯ , n are respectively called constants, unary,..., n-ary symbols. We assume that F contains at least one constant. We use parenthesis and commas for a short declaration of symbols with arity. For instance, f (,) is a short declaration for a binary symbol f . The set T (F, X) of trees over the ranked alphabet F and the set of variables X, is the smallest set defined as follows:

F₀ ⊆ T (F, X) ,

Example 3. Let F = {a, f (,)} and X = {x} . Here f is a binary symbol and a is a constant (i.e. Arity (f) =2 and Arity (a) =0). The trees f (a, a) and f (a, f (a, a)) are ground trees. Trees can be represented graphically. For instance, the tree f (a, f (a, a)) is represented as Figure 1.

OPEN IN VIEWER

Fig. 1

A ground tree.

In this section, we consider the minimization problem and prove the decidability of the minimization problem for initialized LTA s that will be introduced soon. State minimization is a fundamental problem in tree automata theory and is of course very important in the study of fuzzy top-down tree automata. A fuzzy top-down tree automaton studied in this paper is defined as follows:

Definition 2. A fuzzy top-down tree automaton over L (or LTA , for short) is a system A = ( Q , F , δ ) , where:

(1) Q is a finite set of states,

(2) F is a ranked alphabet,

(3) ∀n ≥ 0, δ _n is a fuzzy mapping from Q × Q ⁿ  × F _n to L .

The family of fuzzy subsets δ = (δ _n ) _n≥0 is called the fuzzy transition. We will usually write δ for δ _n  .

Definition 3. An initial distribution of A is a mapping I from Q to L , i.e., I ∈ L Q . I is concentrated at q, if I (q) =1 and I (q _i ) =0 for q _i  ≠ q . Moreover, the ordered pair ( A , I ) is called an initialized LTA . If I is concentrated at q ∈ Q, we shall also write ( A , q ) for ( A , I ) .

Definition 4. The fuzzy response mapping r A : Q × T ( F ) → L of A , by induction on t ∈ T (F) , is defined as follows:

If t = σ ∈ F₀, then r A ( q , t ) = δ ( q , t ) , ∀ q ∈ Q ,

Definition 5. Let ( A , I ) be an initialized LTA . The behaviour of ( A , I ) is defined as follows: B ( A , I ) = { t ∈ T ( F ) ∣ ∑ q ∈ Q ( I ( q ) · r A ( q , t ) ) > 0 } . Also, L is called regular tree language concerning L , if there exists an initialized LTA ( A , I ) such that L = B ( A , I ) .

Example 4. Consider L = 〈 [ 0 , 1 ] , ∨ , ∧ , 0 , 1 〉 and the initialized fuzzy top-down tree automaton over L ( A , I ) defined by:

Q = {q₀, q₁, q₂} ,  F = {a, g () , f (,)} ,  I (q₀) =0.1,  I (q₁) =0.7,  I (q₂) =0.5, and δ ( q 0 , a ) = 0.5 , δ ( q 0 , q 0 , g ) = 0.8 , δ ( q 1 , q 0 , g ) = 0.9 , δ ( q 2 , q 1 , g ) = 0.6 , δ ( q 0 , ( q 0 , q 0 ) , f ) = 0.2 .

We now consider t = g (g (f (g (a) , a))) and show the access level to q₂ by t as follows:

r A ( q 0 , a ) = 0.5 , r A ( q 0 , g ( a ) ) = δ ( q 0 , q 0 , g ) ∧ r A ( q 0 , a ) = 0.5 , r A ( q 0 , f ( g ( a ) , a ) ) = δ ( q 0 , ( q 0 , q 0 ) , f ) ∧ r A ( q 0 , g ( a ) ) ∧ r A ( q 0 , a ) = 0.2 , r A ( q 1 , g ( f ( g ( a ) , a ) ) ) = δ ( q 1 , q 0 , g ) ∧ r A ( q 0 , f ( g ( a ) , a ) ) = 0.2 , r A ( q 2 , g ( g ( f ( g ( a ) , a ) ) ) ) = δ ( q 2 , q 1 , g ) ∧ r A ( q 1 , g ( f ( g ( a ) , a ) ) ) = 0.2 .

Also, B ( A , I ) = { g m ( a ) , g ( t ) ∣ m ≥ 1 , t ∈ T ( F ) } .

Let A 1 = ( Q 1 , F , δ 1 ) and A 2 = ( Q 2 , F , δ 2 ) be two LTA s . Now, we define the equivalence relation ≡ as follows:

( A 1 , I 1 ) ≡ ( A 2 , I 2 ) if and only if for all q ∈ Q₁ there exists p ∈ Q₂ such that δ 1 ( q ′ , ( q 1 , … , q j - 1 , q , q j + 1 , … , q n ) , σ ) > 0 , δ 2 ( p ′ , ( p 1 … , p j - 1 , p , p j + 1 , … , p n ) , σ ) > 0 , ( A 1 , q ′ ) ≡ ( A 2 , p ′ ) , ∀ i ( A 1 , q i ) ≡ ( A 2 , p i ) , I 1 ( q ) > 0 and I 2 ( p ) > 0 and vice versa.

Here, we focus on the decision of the minimization problem, which is defined as follows:

Given an LTA A , is there a statewise minimal LTA A min that is statewise equivalent to A ?

We note that, if we utilize the minimization algorithms presented in [18, 35] to find a statewise minimal LTA , the input LTA must be complete, deterministic, and reduced. These algorithms do not hold for any input. For example, if we consider the input as a non-deterministic tree automaton, then we can not use the algorithms presented in [18, 35] to obtain a statewise minimal LTA . Here, we are going to provide an algorithm that holds for any input LTA .

Definition 6. Two LTA s A 1 and A 2 are called statewise equivalent if for every q ∈ Q₁, there exists p ∈ Q₂ such that ( A 1 , q ) ≡ ( A 2 , p ) and vice versa. In symbols, A 1 ≡ A 2 .

Definition 7. Two LTA s A 1 and A 2 are called initial statewise equivalent if for every I 1 ∈ L Q 1 , there exists I 2 ∈ L Q 2 such that ( A 1 , I 1 ) ≡ ( A 2 , I 2 ) and vice versa. In symbols, A 1 ≈ A 2 .

Definition 8. An LTA A is called (initial) statewise minimal if it is not (initial) statewise equivalent to any fuzzy top-down tree automaton with fewer states.

Definition 9. An LTA A is called statewise irreducible if for every p, q ∈ Q, q ≡ p implies q = p .

Definition 10. An LTA A is called initial statewise irreducible if for every I and I ′ ∈ L Q , I ≡ I′ implies I = I′ .

By Theorem 1, we will show the existence of a statewise irreducible LTA which is equivalent to a given LTA .

Theorem 1. Let A = ( Q , F , δ ) be a given LTA . Then, there exists a statewise irreducible LTA A ′ such that A ≡ A ′ .

Proof. Let A ′ = ( Q ′ , F , δ ′ ) where, Q′ = {[q] |q ∈ Q} ,    [q] = {p ∈ Q|q ≡ p} and define δ ′ : Q ′ × Q ′ n × F n → L by: δ ′ ( [ q ′ ] , ( [ q 1 ] , ⋯ , [ q j - 1 ] , [ q ] , [ q j + 1 ] , ⋯ , [ q n ] ) , σ ) = ∑ { δ ( s ′ , ( s 1 , ⋯ , s j - 1 , s , s j + 1 , ⋯ , s n ) , σ ) ∣ s i , s , s ′ ∈ Q , q i ≡ s i , q ≡ s , q ′ ≡ s ′ , 1 ≤ i ≤ n , i ≠ j } . Let ([q′] , ([q₁] , ⋯ , [q_j-1] , [q] , [q_j+1] , ⋯ , [q _n ]) , σ) = ([p′] , ([p₁] , ⋯ , [p_j-1] , [p] , [p_j+1] , ⋯ , [p _n ]) , σ) . Then, q _i  ≡ p _i ,   ∀ i ∈ {1, ⋯ , j - 1, j + 1, ⋯ , n} , q′ ≡ p′ and q ≡ p . Hence ∑ { δ ( s ′ , ( s 1 , ⋯ , s j - 1 , s , s j + 1 , ⋯ , s n ) , σ ) ∣ s i , s , s ′ ∈ Q , q i ≡ s i , 1 ≤ i ≤ n , i ≠ j , q ′ ≡ s ′ , q ≡ s } = ∑ { δ ( s ′ , ( s 1 , ⋯ , s j - 1 , s , s j + 1 , ⋯ , s n ) , σ ) ∣ s i , s , s ′ ∈ Q , p i ≡ s i 1 ≤ i ≤ n , i ≠ j , p ′ ≡ s ′ , p ≡ s } . Thus, δ′ is well defined. Now, we show that for all q′, q, q _i  ∈ Q, 1 ≤ i ≤ n, i ≠ j, if δ ( q ′ , ( q 1 , … , q j - 1 , q , q j + 1 , … , q n ) , σ ) > 0 then δ ′ ( [ q ′ ] , ( [ q 1 ] , … , [ q j - 1 ] , [ q ] , [ q j + 1 ] , … , [ q n ] ) , σ ) > 0 . Let [q′] , [q] , [q _i ] ∈ Q′, 1 ≤ i ≤ n, i ≠ j,  σ ∈ F _n and δ (q′, (q₁, …, q_j-1, q, q_j+1, …, q _n ) , σ) >0 . Then δ ′ ( [ q ′ ] , ( [ q 1 ] , … , [ q j - 1 ] , [ q ] , [ q j + 1 ] , … , [ q n ] ) , σ ) = ∑ { δ ( s ′ , ( s 1 , ⋯ , s j - 1 , s , s j + 1 , ⋯ , s n ) , σ ) ∣ s ′ ≡ q ′ , s i ≡ q i , s ≡ q , s , s ′ , s i ∈ Q } ≥ δ ( q ′ , ( q 1 , … , q j - 1 , q , q j + 1 , … , q n ) , σ ) > 0 . Therefore: δ ′ ( [ q ′ ] , ( [ q 1 ] , … , [ q j - 1 ] , [ q ] , [ q j + 1 ] , … , [ q n ] ) , σ ) > 0 . Now we show that for all [q] , [q′] , [q _i ] ∈ Q′, 1 ≤ i ≤ n, i ≠ j, if δ ′ ( [ q ′ ] , ( [ q 1 ] , … , [ q j - 1 ] , [ q ] , [ q j + 1 ] , … , [ q n ] ) , σ ) > 0 then δ ( q ′ , ( q 1 , … , q j - 1 , q , q j + 1 , … , q n ) , σ ) > 0 . Let δ′ ([q′] , ([q₁] , …, [q_j-1] , [q] , [q_j+1] , …, [q _n ]) , σ) >0 for some [q] , [q′] , [q _i ] ∈ Q′, 1 ≤ i ≤ n, i ≠ j and σ ∈ F _n  . Then, there exist s, s′, s _i  ∈ Q, 1 ≤ i ≤ n, i ≠ j with s ≡ q, s′ ≡ q′ and s _i  ≡ q _i such that δ ( s ′ , ( s 1 , … , s j - 1 , s , s j + 1 , … , s n ) , σ ) > 0 . Since s ≡ q, s′ ≡ q′, s _i  ≡ q _i and δ (s′, (s₁, …, , s_j-1, s, s_j+1, …, s _n ) , σ) >0, we must have δ ( q ′ , ( q 1 , … , q j - 1 , q , q j + 1 , … , q n ) , σ ) > 0 .

Therefore we have: A ≡ A ′ .

Now, let [q] ≡ [p] and [q] , [p] ∈ Q′ . Then,

δ ′ ( [ q ′ ] , ( [ q 1 ] , … , [ q j - 1 ] , [ q ] , [ q j + 1 ] , … , [ q n ] ) , σ ) > 0 and δ ′ ( [ q ′ ] , ( [ q 1 ] , … , [ q j - 1 ] , [ p ] , [ q j + 1 ] , … , [ q n ] ) , σ ) > 0 . Therefore, δ ( q ′ , ( q 1 , … , q j - 1 , q , q j + 1 , … , q n ) , σ ) > 0 and δ ( q ′ , ( q 1 , … , q j - 1 , p , q j + 1 , … , q n ) , σ ) > 0 .

Thus, q ≡ p and so [q] = [p] . Hence, A ′ is statewise irreducible. □

Theorem 2. Let A = ( Q , F , δ ) be a given LTA . Then, there exists an initial statewise irreducible LTA A ′ such that A ≈ A ′ .

Proof. The proof is similar to the proof of Theorem 1. □

Theorem 3. Let A 1 ≡ A 2 . Then A 1 ≈ A 2 .

Proof. We define S ( q ) = { p ∈ Q 2 | ( A 1 , q ) ≡ ( A 2 , p ) } for every q ∈ Q₁ . Obviously, S ( q ) ≠ Ø . Given I₁, define I₂ as follows: I 2 ( q ) = { 1 if for some p ∈ Q 1 , I 1 ( p ) > 0 and q ∈ S ( p ) 0 o . w . Clearly, ( A 1 , I 1 ) ≡ ( A 2 , I 2 ) . Also, similarly, we can show that for every I₂, there exists I₁ such that ( A 1 , I 1 ) ≡ ( A 2 , I 2 ) . Thus, A 1 ≈ A 2 . □

From Theorem 3 we have the following corollary:

Corollary 4. If A is initial statewise minimal then A is statewise minimal.

Theorem 5. A is statewise minimal if and only if A is statewise irreducible.

Proof. Suppose that A is statewise minimal but is not statewise irreducible. Then, there exist p and q ∈ Q such that p ≠ q and p ≡ q . Define A ′ = ( Q ′ , F , δ ′ ) with Q′ = Q \ {q} and for every q 1 ′ , ⋯ , q n ′ , q ′ ∈ Q ′ and σ ∈ F,

δ ′ ( q ′ , ( q 1 ′ , ⋯ , q j - 1 ′ , q ′ ′ , q j + 1 ′ , … , q n ′ ) , σ ) = { δ ( q ′ , ( q 1 ′ , … , q j - 1 ′ , q ′ ′ , q j + 1 ′ , … , q n ′ ) , σ ) if q ′ ′ ≠ p , δ ( q ′ , ( q 1 ′ , ⋯ , q j - 1 ′ , q , q j + 1 ′ , … , q n ′ ) , σ ) + δ ( q ′ , ( q 1 ′ , ⋯ , q j - 1 ′ , p , q j + 1 ′ , … , q n ′ ) , σ ) if q ′ ′ = p . Now we prove that A ≡ A ′ . Obviously, |Q′| < |Q| and for every s ∈ Q, s ≠ q, there exists s′ ∈ Q′ such that ( A , s ) ≡ ( A ′ , s ′ ) and vice versa. Also, since ( A , q ) ≡ ( A , p ) and ( A , p ) ≡ ( A ′ , p ) , we have ( A , q ) ≡ ( A ′ , p ) . Therefore, for every s ∈ Q, ther exists s′ ∈ Q′ such that ( A , s ) ≡ ( A ′ , s ′ ) and vice versa i.e. A ≡ A ′ . Thus A is not statewise minimal, which is a contradiction.

Conversely, suppose that A is statewise irreducible but is not statewise minimal. Then, A ≡ A ′ for some A ′ with |Q′| < |Q| . Thus, there exist q′ ∈ Q′ and p, q ∈ Q with p ≠ q such that ( A , q ) ≡ ( A ′ , q ′ ) and ( A , p ) ≡ ( A ′ , q ′ ) . Hence, ( A , q ) ≡ ( A , p ) or q ≡ p . Therefore, A is not statewise irreducible which is a contradiction. Hence, the proof is completed. □

From Theorems 1 and 5 we have:

Corollary 6. Let A = ( Q , F , δ ) be an LTA . Then, there exists a statewise minimal LTA A ′ such that A ≡ A ′ .

The above corollary shows the existence of a statewise minimal form for a given LTA .

Theorem 7. If A is initial statewise irreducible, then A is initial statewise minimal.

Proof. Suppose that A is not initial statewise minimal. Then A ≈ A ′ for some A ′ such that |Q′| < |Q| . Let H and H′ denote, respectively, the collections of all initial distributions of A and A ′ . Clearly, |H′| < |H| . Thus, there exist I ′ ∈ L Q ′ and I 1 , I 2 ∈ L Q with I₁ ≠ I₂ such that ( A , I 1 ) ≡ ( A ′ , I ′ ) and ( A , I 2 ) ≡ ( A ′ , I ′ ) . Therefore, ( A , I 1 ) ≡ ( A , I 2 ) or I₁ ≡ I₂, which is a contradiction. □

Utilizing Theorems 2 and 7 we can conclude the following corollary:

Corollary 8. Let A = ( Q , F , δ ) be an LTA . Then, there exists an initial statewise minimal LTA A ′ such that A ≈ A ′ .

Now, we present Algorithm 1 the output of which is a statewise minimal LTA . In this algorithm, we construct a relation β, step by step. The obtained β in the last step is an equivalence relation on states and is denoted by ≡. In Step 2, we consider two states as equivalent states if they make an affect on the same constant symbols. In Steps 3 and 4 we extend Step 2 to symbols with arity more than zero. In Step 5 a weed-out process is applied to discard some states that are not equivalent. In the following theorem, we show that the output of Algorithm 1 is a statewise minimal LTA .

Algorithm 1 Minimization algorithm of a given LTA .

Input: A fuzzy top-down tree automaton over L , A = ( Q , F , δ ) ;

Step 1. Set H = {(q, p)∣ q, p ∈ Q} ;

Step 2. Set H ¯ = { ( q , p ) ∣ ∃ a ∈ F 0 , q , p ∈ Q , δ ( q , a ) · δ ( p , a ) > 0 , ∀ b ∈ F 0 , b ≠ a , δ ( q , b ) + δ ( p , b ) = 0 } ;

Step 3. Until no element can be added to β, repeat the following procedures:

β = H ¯ ∪ { h ∈ H ∣ ( h , α ) ∈ S } , where

S =  {((q, p) , (q′, p′))∣ q′ = p′, δ (q, (q₁, ⋯ , q_i-1, q′, q_i+1, ⋯ , q _n ) , σ) ·

δ (p, (q₁, ⋯ , q_i-1, p′, q_i+1, ⋯ , q _n ) , σ) >0 and h ∈ MARKED) } ;

and MARKED =  {(q, p) ∣ ifδ (s, (q₁, ⋯ , q_i-1, q, q_i+1, ⋯ , q _n ) , σ) > 0 then

∃r∈ Q, δ (r, (q₁, ⋯ , q_i-1, p, q_i+1, ⋯ , q _n ) , σ) >0} ;

Step 4. Until no element can be added to β, repeat the following procedures:

β = β ∪ {h ∈ H ∣ (h, α) ∈ S′} , where

S′ =  {((q, p) , (q′, p′))∣ q′ ≠ p′, (q′, p′) ∈ β, δ (q, (q₁, ⋯ , q_i-1, q′, q_i+1, ⋯ , q _n ) , σ) ·

δ (p, (q₁, ⋯ , q_i-1, p′, q_i+1, ⋯ , q _n ) , σ) >0 and h ∈ MARKED) } ;

Step 5. Until no change can occur in β, repeat the following procedures:

β = β \  {h ∣ (h, h′) ∈ Eandh′ ∉ β} , where

E =  {((q, p) , (q′, p′))∣ q′ ≠ p′, δ (q, (q₁, ⋯ , q_i-1, q′, q_i+1, ⋯ , q _n ) , σ) ·

δ (p, (q₁, ⋯ , q_i-1, p′, q_i+1, ⋯ , q _n ) , σ) >0} ;

Step 6. Set ≡ = β ;

Step 7. Set Q _min  = Q ≡ ;

Step 8. Set δ _min  ([q _t ] , ([q₁] , ⋯ , [q _n ]) , σ) = ∑ {δ (p _t , (p₁, ⋯ , p _n ) , σ) : p _t  ∈ [q _t ] , p _i  ∈ [q _i ] , i = 1, ⋯ , n} ,

where [q] = {q′∣ q′ ∈ Qandq ≡ q′} ;

Output: A min = ( Q min , F , δ min ) is the statewise minimal LTA .

Theorem 9. The output of Algorithm 1 is a statewise minimal LTA which is statewise equivalent to the given input.

Proof. Let a fuzzy top-down tree automaton over L , A = ( Q , F , δ ) be the input of Algorithm 1. We show that A min = ( Q min , F , δ min ) obtained in Algorithm 1, is a statewise minimal LTA . Assume that A min is not statewise minimal and there exists a fuzzy top-down tree automaton over L , A ′ = ( Q ′ , F , δ ′ ) with A min ≡ A ′ and |Q′| < |Q _min | . Thus, there exist q′ ∈ Q′ and p, q ∈ Q _min with p ≠ q such that ( A min , q ) ≡ ( A ′ , q ′ ) and ( A min , p ) ≡ ( A ′ , q ′ ) . Hence, ( A min , q ) ≡ ( A min , p ) or q ≡ p . Therefore, Step 3 or Step 4 is repeated and this is a contradiction. Therefore A min is a statewise minimal. □

Theorem 10. Running time of Algorithm 1 is O (|F||Q|^M+3) .

Proof. Let |Q| and |F| denote the number of states and symbols in the ranked alphabet, respectively. Also, let M be the maximal arity of the symbols in the ranked alphabet. Now, we compute the time complexity of the algorithm, step by step. It is obvious that the overall time consumed in Step 1 is O (|Q|²) and the time needed for Step 2 is O (|Q||F₀|) . For Steps 3,4 and 5, the loop can be repeated at most |Q| times. In the loops, something is tested for all pairs of states, which leads to the time O (|Q|²) . The condition that has to be checked needs to iterate through all tuples of states of length n, for each symbol of arity n . Therefore, for a pair of states q and p, to check q ≡ p, the running time is bounded by O ( ∑ n = 0 M | F n | | Q | n ) . So, the total time spent in Steps 3, 4 and 5 is O ( ∑ n = 0 M | F n | | Q | n + 3 ) . It is easy to check that the time of Step 6 is O (|Q|) and Step 7 takes O ( ∑ n = 0 M | F n | | Q | n ) . Therefore, the running time of the algorithm is O (|F||Q|^M+3) . □

Now, we give two examples to clarify Algorithm 1.

Example 5. Let L = 〈 [ 0 , 1 ] , ∨ , ∧ , 0 , 1 〉 and A = ( Q , F , δ ) be a fuzzy top-down tree automaton over L where: Q = { q 0 , q 1 , q 2 , q 3 } , F = { a , b , g ( ) , f ( , ) } and δ is as follows: δ ( q 0 , a ) = 1 , δ ( q 2 , ( q 0 , q 1 ) , f ) = 0.3 , δ ( q 2 , a ) = 0.5 , δ ( q 0 , ( q 3 , q 1 ) , f ) = 0.3 , δ ( q 3 , b ) = 0.7 , δ ( q 1 , q 2 , g ) = 0.4 , δ ( q 2 , q 1 , g ) = 0.8 , δ ( q 1 , q 0 , g ) = 0.2 , δ ( q 1 , q 1 , g ) = 0.7 . Now we apply Algorithm 1, step by step, to obtain A min .

Step 1. Set H = { ( q 0 , q 0 ) , ( q 1 , q 1 ) , ( q 2 , q 2 ) , ( q 3 , q 3 ) , ( q 0 , q 1 ) , ( q 0 , q 2 ) , ( q 0 , q 3 ) , ( q 1 , q 2 ) , ( q 1 , q 3 ) , ( q 2 , q 3 ) } . Step 2. Since δ (q₀, a) ∧ δ (q₂, a) >0, it follows that H ¯ = { ( q 0 , q 2 ) } .

Step 3. β =  {(q₀, q₂) } ; in this step there exists only one case ((q₁, q₂) , (q₁, q₁)) ∈ S but (q₁, q₂) ∉ MARKED . Therefore, no element will be added to β .

Step 4. In this step, no element will be added to β .

Step 5. In this step, since δ (q₂, (q₀, q₁) , f) ∧ δ (q₀, (q₃, q₁) , f) >0 and (q₀, q₃) ∉ β we remove {q₀, q₂} from β .

Step 6. ≡ = Ø .

Step 7. Q _min  = Q .

Step 8. δ _min  = δ .

Output. A min = ( Q min , F , δ min ) = A .

Example 6. Let l = 〈 [0,1], ∨, ∧, 0, 1 〉 and A = ( Q , F , δ ) be a fuzzy top-down tree automaton over L where: Q = { q 0 , q 1 , q 2 , q 3 } , F = { a , b , g ( ) , f ( , ) } and δ is as follows: δ ( q 0 , a ) = 1 , δ ( q 2 , ( q 0 , q 1 ) , f ) = 0.3 , δ ( q 3 , a ) = 0.5 , δ ( q 0 , ( q 3 , q 1 ) , f ) = 0.3 , δ ( q 2 , q 3 , g ) = 0.8 , δ ( q 1 , q 3 , g ) = 0.4 . Step 1. Set H = { ( q 0 , q 0 ) , ( q 1 , q 1 ) , ( q 2 , q 2 ) , ( q 3 , q 3 ) , ( q 0 , q 1 ) , ( q 0 , q 2 ) , ( q 0 , q 3 ) , ( q 1 , q 2 ) , ( q 1 , q 3 ) , ( q 2 , q 3 ) } . Step 2. Since δ (q₀, a) ∧ δ (q₃, a) >0, we have H ¯ = { ( q 0 , q 3 ) } .

Step 3. β =  {(q₀, q₃) } ; in this step there exists only one case ((q₁, q₂) , (q₃, q₃)) ∈ S but (q₁, q₂) ∉ MARKED . Therefore, no element will be added to β .

Step 4. In this step, no element will be added to β .

Step 5. In this step, no element will be removed from β .

Step 6. q₀ ≡ q₃ .

Step 7. Q _min  = {q₀, q₁, q₂} .

Step 8. δ _min is as follows: δ ( q 0 , a ) = 1 , δ ( q 2 , ( q 0 , q 1 ) , f ) = 0.3 , δ ( q 2 , q 0 , g ) = 0.8 , δ ( q 0 , ( q 0 , q 1 ) , f ) = 0.3 , δ ( q 1 , q 0 , g ) = 0.4 .

Output. A min = ( Q min , F , δ min ) is the statewise minimal form for A .

Note that if we apply the minimization algorithms presented in [18, 35] to find a statewise minimal form for a given LTA , the input must be a complete, deterministic, and reduced lattice-valued tree automaton. Since the input LTA in Example 6 is not complete, the algorithms established in [18, 35] can not obtain a statewise minimal LTA .

4 Conclusions

In this paper, we introduced some basic concepts about the minimization of initialized LTA s . Also, we showed the existence of the initial statewise minimal form for an LTA . Moreover, we presented an efficient algorithm to construct a statewise minimal LTA from for a given LTA . Moreover, we computed the time complexity of the given algorithm. The presented algorithm can be applied for all LTA , including non-deterministic and noncomplete LTA s .

However, subjects as weighted pushdown tree automata, the categorical approach of weighted tree automata, and consideration of tree automata over more general algebraic structures such as lattice monoids, have not been considered until now. So, we will deal with these subjects in subsequent works.