Affiliations: [a] Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran
| [b] Department of CSED, Thapar Institute of Engineering and Technology, Patiala, India
Correspondence:
[*]
Corresponding author. Maryam Ghorani, Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran. Tel.: +982332300235; E-mail: Ghorani@shahroodut.ac.ir.
Abstract: In this paper, we study fuzzy top-down tree automata over lattices (
LTAs,
for short). The purpose of this contribution is to investigate the minimization problem for
LTAs.
We first define the concept of statewise equivalence between two
LTAs.
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
