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

Abstract

In this paper, we study fuzzy top-down tree automata over lattices ( $LTA s,$ for short). The purpose of this contribution is to investigate the minimization problem for $LTA s .$ We first define the concept of statewise equivalence between two $LTA s .$ Thereafter, we show the existence of the statewise minimal form for an $LTA .$ To this end, we find a statewise irreducible $LTA$ which is equivalent to a given $LTA .$ Then, we provide an algorithm to find the statewise minimal $LTA$ and by a theorem, we show that the output statewise minimal $LTA$ is statewise equivalent to the given input. Moreover, we compute the time complexity of the given algorithm. The proposed algorithm can be applied to any given $LTA$ and, unlike some minimization algorithms given in the literature, the input doesn’t need to be a complete, deterministic, or reduced lattice-valued tree automaton. Finally, we provide some examples to show the efficiency of the presented algorithm.

Keywords

Fuzzy tree automata minimization problem lattice-valued logic statewise minimal

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, +, \cdot, 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 \in 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 = {\emptyset, {a}, {b}, {a, b}},$ where ∅ ⊆ {a} , {b} ⊆ {a, b} . Then,

$L = 〈 L, \cup, \cap, \emptyset, {a, b} 〉$ is a lattice.

Example 2. Let $L = [0, 1] \subseteq R$ . Then $L = 〈 L, \lor, \land, 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) ,

X ⊆ T (F, X) ,

if n ≥ 1, σ ∈ F_n, t₁, ⋯ , t_n ∈ T (F, X) then σ (t₁, ⋯ , t_n) ∈ T (F, X) .

If X =Ø then T (F, X) is written by T (F) . Trees in T (F) are called ground trees.

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.

Fig. 1

A ground tree.

3 Minimization of

LTA

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 \in 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 \times T (F) \to L$ of $A,$ by induction on t ∈ T (F) , is defined as follows:

If t = σ ∈ F₀, then $r_{A} (q, t) = δ (q, t), \forall q \in Q,$

∀t₁, ⋯ , t_n ∈ T (F) and σ ∈ F_n, if t = σ (t₁, ⋯ , t_n) then $r_{A} (q, t) = \sum_{q_{1}, \dots, q_{n} \in Q} δ (q, (q_{1}, \dots, q_{n}), σ) \cdot \prod_{i = 1}^{n} r_{A} (q_{i}, t_{i}) .$

In fact, the fuzzy response mapping

r_{A},

shows the access level to q ∈ Q by t ∈ T (F) .

Definition 5. Let $(A, I)$ be an initialized $LTA .$ The behaviour of $(A, I)$ is defined as follows: $B (A, I) = {t \in T (F) ∣ \sum_{q \in Q} (I (q) \cdot 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], \lor, \land, 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 $\begin{matrix} δ (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 . \end{matrix}$

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

$\begin{matrix} r_{A} (q_{0}, a) = 0.5, \\ r_{A} (q_{0}, g (a)) = δ (q_{0}, q_{0}, g) \land r_{A} (q_{0}, a) = 0.5, \\ r_{A} (q_{0}, f (g (a), a)) = δ (q_{0}, (q_{0}, q_{0}), f) \land r_{A} (q_{0}, g (a)) \land r_{A} (q_{0}, a) = 0.2, \\ r_{A} (q_{1}, g (f (g (a), a))) = δ (q_{1}, q_{0}, g) \land 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) \land r_{A} (q_{1}, g (f (g (a), a))) = 0.2 . \end{matrix}$

Also, $B (A, I) = {g^{m} (a), g (t) ∣ m \geq 1, t \in 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}) \equiv (A_{2}, I_{2})$ if and only if for all q ∈ Q₁ there exists p ∈ Q₂ such that $δ_{1} (q^{'}, (q_{1}, \dots, q_{j - 1}, q, q_{j + 1}, \dots, q_{n}), σ) > 0, δ_{2} (p^{'}, (p_{1} \dots, p_{j - 1}, p, p_{j + 1}, \dots, p_{n}), σ) > 0,$ $(A_{1}, q^{'}) \equiv (A_{2}, p^{'}), \forall i (A_{1}, q_{i}) \equiv (A_{2}, p_{i}), I_{1} (q) > 0 and I_{2} (p) > 0$ and vice versa.

Let I₁ and I₂ be concentrated at q and p, respectively. Then $(A_{1}, q) \equiv (A_{2}, p)$ if and only if $δ_{1} (q^{'}, (q_{1}, \dots, q_{j - 1}, q, q_{j + 1}, \dots, q_{n}), σ) > 0, δ_{2} (p^{'}, (p_{1} \dots, p_{j - 1}, p, p_{j + 1}, \dots, p_{n}), σ) > 0,$ $(A_{1}, q^{'}) \equiv (A_{2}, p^{'}) and (A_{1}, q_{i}) \equiv (A_{2}, p_{i}), \forall i .$ Sometimes, we utilize q₁ ≡ q₂ instead of $(A, q_{1}) \equiv (A, q_{2})$ and I₁ ≡ I₂ instead of $(A, I_{1}) \equiv (A, I_{2}) .$

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) \equiv (A_{2}, p)$ and vice versa. In symbols, $A_{1} \equiv A_{2} .$

Definition 7. Two $LTA s$ $A_{1}$ and $A_{2}$ are called initial statewise equivalent if for every $I_{1} \in L^{Q_{1}},$ there exists $I_{2} \in L^{Q_{2}}$ such that $(A_{1}, I_{1}) \equiv (A_{2}, I_{2})$ and vice versa. In symbols, $A_{1} \approx 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^{'} \in 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 \equiv A^{'} .$

Proof. Let $A^{'} = (Q^{'}, F, δ^{'})$ where, Q′ = {[q] |q ∈ Q} , [q] = {p ∈ Q|q ≡ p} and define $δ^{'} : Q^{'} \times Q^{'^{n}} \times F_{n} \to L$ by: $δ^{'} ([q^{'}], ([q_{1}], \dots, [q_{j - 1}], [q], [q_{j + 1}], \dots, [q_{n}]), σ) =$ $\sum {δ (s^{'}, (s_{1}, \dots, s_{j - 1}, s, s_{j + 1}, \dots, s_{n}), σ) ∣ s_{i}, s, s^{'} \in Q, q_{i} \equiv s_{i}, q \equiv s, q^{'} \equiv s^{'}, 1 \leq i \leq n, i \neq 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 $\sum {δ (s^{'}, (s_{1}, \dots, s_{j - 1}, s, s_{j + 1}, \dots, s_{n}), σ) ∣ s_{i}, s, s^{'} \in Q, q_{i} \equiv s_{i}, 1 \leq i \leq n, i \neq j, q^{'} \equiv s^{'}, q \equiv s} =$ $\sum {δ (s^{'}, (s_{1}, \dots, s_{j - 1}, s, s_{j + 1}, \dots, s_{n}), σ) ∣ s_{i}, s, s^{'} \in Q, p_{i} \equiv s_{i} 1 \leq i \leq n, i \neq j, p^{'} \equiv s^{'}, p \equiv 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}, \dots, q_{j - 1}, q, q_{j + 1}, \dots, q_{n}), σ) > 0$ then $δ^{'} ([q^{'}], ([q_{1}], \dots, [q_{j - 1}], [q], [q_{j + 1}], \dots, [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}], \dots, [q_{j - 1}], [q], [q_{j + 1}], \dots, [q_{n}]), σ) =$ $\sum {δ (s^{'}, (s_{1}, \dots, s_{j - 1}, s, s_{j + 1}, \dots, s_{n}), σ) ∣ s^{'} \equiv q^{'}, s_{i} \equiv q_{i}, s \equiv q, s, s^{'}, s_{i} \in Q} \geq$ $δ (q^{'}, (q_{1}, \dots, q_{j - 1}, q, q_{j + 1}, \dots, q_{n}), σ) > 0 .$ Therefore: $δ^{'} ([q^{'}], ([q_{1}], \dots, [q_{j - 1}], [q], [q_{j + 1}], \dots, [q_{n}]), σ) > 0 .$ Now we show that for all [q] , [q′] , [q_i] ∈ Q′, 1 ≤ i ≤ n, i ≠ j, if $δ^{'} ([q^{'}], ([q_{1}], \dots, [q_{j - 1}], [q], [q_{j + 1}], \dots, [q_{n}]), σ) > 0$ then $δ (q^{'}, (q_{1}, \dots, q_{j - 1}, q, q_{j + 1}, \dots, 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}, \dots, s_{j - 1}, s, s_{j + 1}, \dots, 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}, \dots, q_{j - 1}, q, q_{j + 1}, \dots, q_{n}), σ) > 0 .$

Therefore we have: $A \equiv A^{'} .$

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

$δ^{'} ([q^{'}], ([q_{1}], \dots, [q_{j - 1}], [q], [q_{j + 1}], \dots, [q_{n}]), σ) > 0$ and $δ^{'} ([q^{'}], ([q_{1}], \dots, [q_{j - 1}], [p], [q_{j + 1}], \dots, [q_{n}]), σ) > 0 .$ Therefore, $δ (q^{'}, (q_{1}, \dots, q_{j - 1}, q, q_{j + 1}, \dots, q_{n}), σ) > 0$ and $δ (q^{'}, (q_{1}, \dots, q_{j - 1}, p, q_{j + 1}, \dots, 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 \approx A^{'} .$

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

Theorem 3. Let $A_{1} \equiv A_{2} .$ Then $A_{1} \approx A_{2} .$

Proof. We define $S (q) = {p \in Q_{2} | (A_{1}, q) \equiv (A_{2}, p)}$ for every q ∈ Q₁ . Obviously, $S (q) \neq Ø .$ Given I₁, define I₂ as follows: $I_{2} (q) = {\begin{matrix} 1 & if for some p \in Q_{1}, I_{1} (p) > 0 and q \in S (p) \\ 0 & o . w . \end{matrix}$ Clearly, $(A_{1}, I_{1}) \equiv (A_{2}, I_{2}) .$ Also, similarly, we can show that for every I₂, there exists I₁ such that $(A_{1}, I_{1}) \equiv (A_{2}, I_{2}) .$ Thus, $A_{1} \approx 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}^{'}, \dots, q_{n}^{'}, q^{'} \in Q^{'}$ and σ ∈ F,

$δ^{'} (q^{'}, (q_{1}^{'}, \dots, q_{j - 1}^{'}, q^{''}, q_{j + 1}^{'}, \dots, q_{n}^{'}), σ) = {\begin{matrix} δ (q^{'}, (q_{1}^{'}, \dots, q_{j - 1}^{'}, q^{''}, q_{j + 1}^{'}, \dots, q_{n}^{'}), σ) & if q^{''} \neq p, \\ δ (q^{'}, (q_{1}^{'}, \dots, q_{j - 1}^{'}, q, q_{j + 1}^{'}, \dots, q_{n}^{'}), σ) + \\ δ (q^{'}, (q_{1}^{'}, \dots, q_{j - 1}^{'}, p, q_{j + 1}^{'}, \dots, q_{n}^{'}), σ) & if q^{''} = p . \end{matrix}$ Now we prove that $A \equiv A^{'}$ . Obviously, |Q′| < |Q| and for every s ∈ Q, s ≠ q, there exists s′ ∈ Q′ such that $(A, s) \equiv (A^{'}, s^{'})$ and vice versa. Also, since $(A, q) \equiv (A, p)$ and $(A, p) \equiv (A^{'}, p)$ , we have $(A, q) \equiv (A^{'}, p)$ . Therefore, for every s ∈ Q, ther exists s′ ∈ Q′ such that $(A, s) \equiv (A^{'}, s^{'})$ and vice versa i.e. $A \equiv 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 \equiv A^{'}$ for some $A^{'}$ with |Q′| < |Q| . Thus, there exist q′ ∈ Q′ and p, q ∈ Q with p ≠ q such that $(A, q) \equiv (A^{'}, q^{'})$ and $(A, p) \equiv (A^{'}, q^{'}) .$ Hence, $(A, q) \equiv (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 \equiv 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 \approx 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^{'} \in L^{Q^{'}}$ and $I_{1}, I_{2} \in L^{Q}$ with I₁ ≠ I₂ such that $(A, I_{1}) \equiv (A^{'}, I^{'})$ and $(A, I_{2}) \equiv (A^{'}, I^{'}) .$ Therefore, $(A, I_{1}) \equiv (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 \approx 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 $\bar{H} = {(q, p) ∣ \exists a \in F_{0}, q, p \in Q, δ (q, a) \cdot δ (p, a) > 0, \forall b \in F_{0}, b \neq a, δ (q, b) + δ (p, b) = 0};$

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

$β = \bar{H} \cup {h \in H ∣ (h, α) \in 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} \equiv A^{'}$ and |Q′| < |Q_min| . Thus, there exist q′ ∈ Q′ and p, q ∈ Q_min with p ≠ q such that $(A_{\min}, q) \equiv (A^{'}, q^{'})$ and $(A_{\min}, p) \equiv (A^{'}, q^{'}) .$ Hence, $(A_{\min}, q) \equiv (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 (\sum_{n = 0}^{M} | F_{n} | | Q |^{n}) .$ So, the total time spent in Steps 3, 4 and 5 is $O (\sum_{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 (\sum_{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], \lor, \land, 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 $\begin{matrix} 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})} . \end{matrix}$ Step 2. Since δ (q₀, a) ∧ δ (q₂, a) >0, it follows that $\bar{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 $\begin{matrix} 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})} . \end{matrix}$ Step 2. Since δ (q₀, a) ∧ δ (q₃, a) >0, we have $\bar{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.

References

Abdulla

P.A.

, Bouajjani

, Holík

, Kaati

, Vojnar

, Computing simulations over tree automata, In: C.R. Ramakrishnan, J. Rehof (eds.) TACAS 2008. LNCS, 4963 93–108, Springer, Heidelberg, (2008).

Abdulla

P.A.

, Högberg

, Kaati

, Bisimulation minimization of tree automata, International Journal of Foundations of Computer Science 18(4) (2007), 699–713.

Björklund

, Cleophas

, A taxonomy of minimisation algorithms for deterministic tree automata, Journal of Universal Computer Science 22(2) (2016), 180–196.

Bozapalidis

, Bozapalidoy

O.L.

, Fuzzy tree language recognizability, Fuzzy Sets and Systems 161 (2010), 716–734.

Comon

, Dauchet

, Gilleron

, Jacquemard

, Lugiez

, Loding

, Tison

, Tommasi

, Tree Automata: Technigues and Applications, (2007). Available: http://tata.gforge.inria.fr.

Doner

J.E.

, Decidability of the weak second-order theory of two successors, Notices Amer Math Soc 12 (1965), 365–468.

Doner

J.E.

, Tree acceptors and some of their applications, Journal of Comput and Syst Sci 4 (1970), 406–451.

Drewes

, Grammatical Picture Generation-A Tree-Based Approach, Texts in Theoretical Computer Science, An EATCS Series, Springer, Berlin, (2006).

Ésik

, Liu

, Fuzzy tree automata, Fuzzy Sets and Systems 158 (2007), 1450–1460.

10.

Fallah

M.K.

, Moghari

, Nazemi

, Zahedi

M.M.

, Fuzzy ontology based document feature vector modification using fuzzy tree transducer, IEEE International Conference on Signal Image Technology and Internet Based Systems (2008), 38–44.

11.

Fülöp

, Vágvölgyi

, Minimization of deterministic top-down tree automata, Acta Cybernetica 23 (2017), 379–401.

12.

Garhwal

, Jiwari

, Conversion of fuzzy automata into fuzzy regular expressions using transitive closure, Journal of Intelligent & Fuzzy Systems 30(6) (2016), 3123–3129.

13.

Gécseg

, Steinby

, Tree Automata, Akademiai Kiado, Budapest, (1984).

14.

Gécseg

, Steinby

, Minimal ascending tree automata, Acta Cybernetica 4(1) (1978), 37–44.

15.

Ghorani

, On characterization of fuzzy tree pushdown automata, Soft Computing 23(4) (2019), 1123–1131.

16.

Ghorani

, Tree automata based on complete residuated lattice-valued logic: reduction algorithm and decision problem, Iranian Journal of Fuzzy Systems 15(7) (2018), 103–119.

17.

Ghorani

, State hyperstructures of tree automata based on lattice-valued logic, RAIROTheoretical Informatics and Applications 52(1) (2018), 23–42.

18.

Ghorani

, Zahedi

M.M.

, Characterizations of complete residuated lattice-valued finite tree automata, Fuzzy Sets and Systems 199 (2012), 28–46.

19.

Ghorani

, Zahedi

M.M.

, Alternating Regular Tree Grammars in the Framework of Lattice-Valued Logic, Iranian Journal of Fuzzy Systems 13(2) (2016), 71–94.

20.

Ghorani

, Zahedi

M.M.

, Coding tree languages based on lattice-valued logic, Soft Computing 21(14) (2017), 3815–3825.

21.

Ghorani

, Zahedi

M.M.

, Ameri

, Algebraic properties of complete residuated lattice valued tree automata, Soft Computing 16(10) (2012), 1723–1732.

22.

Gori

, Petrosino

, Encoding non-deterministic fuzzy tree automata into recursive neural networks, IEEE Trans Neur Net 156 (2004), 1435–1449.

23.

Högberg

, Maletti

, May

, Bisimulation minimisation for weighted tree automata. In: T. Harju, J. Karhumäki, A. Leistö (eds.) DLT 2007. LNCS, 4588 229–241, Springer, Heidelberg, (2007).

24.

Högberg

, Maletti

, May

, Backward and forward bisimulation minimization of tree automata, Theoretical Computer Science 410(37) (2009), 3539–3552.

25.

Inagaki

, Fukumura

, On the description of fuzzy meaning of context-free language, In: Fuzzy Sets and Their Applications to Cognitive and Decision Processes, Proc. U.S.Japan Seminar, University of California, Berkeley, CA, 1974 301–328, Academic Press, New York, (1975).

26.

Jeź

, Maletti

, Hyper-minimization for deterministic tree automata. In: N. Moreira, R. Reis (eds.) Implementation and Application of Automata, CIAA 2012, Lecture Notes inComputer Science, 7381 217–228, Springer, Berlin, Heidelberg, (2012).

27.

Knight

, Graehl

, An overview of probabilistic tree transducers for natural language processing, In: A. Gelbukh (ed.) CICLing 2005, LNCS, 3406 1–24, Springer, Heidelberg, (2005).

28.

Lee

E.T.

, Fuzzy tree automata and syntactic pattern recognition, IEEE Trans Pattern Anal Mach Intell PAMI-4 (1982), 445–449.

29.

, Qiu

, On the state minimization of fuzzy automata, IEEE Transactions on Fuzzy Systems 23 (2015), 434–443.

30.

Y.M.

, Pedrycz

, Minimization of lattice finite automata and its application to the decomposition of lattice languages, Fuzzy Sets and Systems 158 (2007), 1423–1436.

31.

Maletti

, Minimizing deterministic weighted tree automata, Inform and Comput 207(11) (2009), 1284–1299.

32.

Maletti

, A backward and a forward simulation for weighted tree automata. In: S. Bozapalidis, G. Rahonis (Eds.): CAI 2009, LNCS 5725 (2009), 288–304, Springer, Heidelberg, 2009.

33.

Martens

, Neven

, Schwentick

, Deterministic top-down tree automata: past, present, and future. In: Logic and Automata-History and Perspectives, vol 2 of Texts in Logic and Games, pp. 505–530, Amsterdam University Press, (2007).

34.

Moghari

, Zahedi

M.M.

, Similarity-based minimization of fuzzy tree automata, J Appl Math Comput 50 (2016), 417–436.

35.

Moghari

, Zahedi

M.M.

, Minimization of deterministic fuzzy tree automata, Journal of Fuzzy Set Valued Analysis 2014 (2014), 1–18.

36.

Moghari

, Zahedi

M.M.

, Ameri

, Merging states in deterministic fuzzy finite tree automata based on fuzzy similarity measure, Italian Journal of Pure and Applied Mathematics 33 (2014), 225–240.

37.

Moghari

, Zahedi

M.M.

, Ameri

, Minimization of fuzzy finite tree automata, In: Proceedings of the 6th IMTGT Conference on Mathematics, Statistics and its Applications (ICMSA2010) Universiti Tunku Abdul Rahman, Kuala Lumpur, Malaysia, (2010), 1044–1052.

38.

Mordeson

J.N.

, Malik

D.S.

, Fuzzy Automata and Languages: Theory and Applications, Chapman & Hall CRC, London, Boca Raton, (2002).

39.

Schwentick

, Automata for XMLA survey, Journal of Computer and System Sciences 73(3) (2007), 289–315.

40.

Tiwari

S.P.

, Yadav

V.K.

, Dubey

M.K.

, Minimal realization for fuzzy behaviour: A bicategory-theoretic approach, Journal of Intelligent & Fuzzy Systems 30(2) (2016), 1057–1065.

41.

Thatcher

J.W.

, Characterizing derivation trees of context free grammars through a generalization of finite automata theory, Journal of Computer and System Sciences 1 (1967), 317–322.

42.

Thatcher

J.W.

, Wright

J.B.

, Generalized finite automata theory with an application to a decision-problem of second order logic, Mathematical Systems Theory 2 (1968), 57–81.

43.

Vianu

, A web odyssey: from codd to XML. In: Proceedings of the 20th ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems (PODS), Santa Barbara, California, USA, pp. 115. ACM, New York, (2001).

44.

Wang

, Li

, Minimization of lattice multiset finite automata, Journal of Intelligent & Fuzzy Systems 35(1) (2018), 627–637.

45.

Wee

W.G.

, Fu

K.S.

, A formulation of fuzzy automata and its application as a model of learning systems, IEEE Trans Syst Man Cybern 5 (1967), 215–223.