In this paper, we study fuzzy top-down tree automata over lattices ( for short). The purpose of this contribution is to investigate the minimization problem for We first define the concept of statewise equivalence between two Thereafter, we show the existence of the statewise minimal form for an To this end, we find a statewise irreducible which is equivalent to a given Then, we provide an algorithm to find the statewise minimal and by a theorem, we show that the output statewise minimal 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 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.
AbdullaP.A., BouajjaniA., HolíkL., KaatiL., VojnarT., Computing simulations over tree automata, In: C.R. Ramakrishnan, J. Rehof (eds.) TACAS 2008. LNCS, 4963 93–108, Springer, Heidelberg, (2008).
2.
AbdullaP.A., HögbergJ., KaatiL., Bisimulation minimization of tree automata, International Journal of Foundations of Computer Science18(4) (2007), 699–713.
3.
BjörklundJ., CleophasL., A taxonomy of minimisation algorithms for deterministic tree automata, Journal of Universal Computer Science22(2) (2016), 180–196.
4.
BozapalidisS., BozapalidoyO.L., Fuzzy tree language recognizability, Fuzzy Sets and Systems161 (2010), 716–734.
5.
ComonH., DauchetM., GilleronR., JacquemardF., LugiezD., LodingC., TisonS., TommasiM., Tree Automata: Technigues and Applications, (2007). Available: http://tata.gforge.inria.fr.
6.
DonerJ.E., Decidability of the weak second-order theory of two successors, Notices Amer Math Soc12 (1965), 365–468.
7.
DonerJ.E., Tree acceptors and some of their applications, Journal of Comput and Syst Sci4 (1970), 406–451.
8.
DrewesF., Grammatical Picture Generation-A Tree-Based Approach, Texts in Theoretical Computer Science, An EATCS Series, Springer, Berlin, (2006).
9.
ÉsikZ., LiuG., Fuzzy tree automata, Fuzzy Sets and Systems158 (2007), 1450–1460.
10.
FallahM.K., MoghariS., NazemiE., ZahediM.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öpZ., VágvölgyiS., Minimization of deterministic top-down tree automata, Acta Cybernetica23 (2017), 379–401.
12.
GarhwalS., JiwariR., Conversion of fuzzy automata into fuzzy regular expressions using transitive closure, Journal of Intelligent & Fuzzy Systems30(6) (2016), 3123–3129.
13.
GécsegF., SteinbyM., Tree Automata, Akademiai Kiado, Budapest, (1984).
14.
GécsegF., SteinbyM., Minimal ascending tree automata, Acta Cybernetica4(1) (1978), 37–44.
15.
GhoraniM., On characterization of fuzzy tree pushdown automata, Soft Computing23(4) (2019), 1123–1131.
16.
GhoraniM., Tree automata based on complete residuated lattice-valued logic: reduction algorithm and decision problem, Iranian Journal of Fuzzy Systems15(7) (2018), 103–119.
17.
GhoraniM., State hyperstructures of tree automata based on lattice-valued logic, RAIROTheoretical Informatics and Applications52(1) (2018), 23–42.
18.
GhoraniM., ZahediM.M., Characterizations of complete residuated lattice-valued finite tree automata, Fuzzy Sets and Systems199 (2012), 28–46.
19.
GhoraniM., ZahediM.M., Alternating Regular Tree Grammars in the Framework of Lattice-Valued Logic, Iranian Journal of Fuzzy Systems13(2) (2016), 71–94.
20.
GhoraniM., ZahediM.M., Coding tree languages based on lattice-valued logic, Soft Computing21(14) (2017), 3815–3825.
21.
GhoraniM., ZahediM.M., AmeriR., Algebraic properties of complete residuated lattice valued tree automata, Soft Computing16(10) (2012), 1723–1732.
22.
GoriM., PetrosinoA., Encoding non-deterministic fuzzy tree automata into recursive neural networks, IEEE Trans Neur Net156 (2004), 1435–1449.
23.
HögbergJ., MalettiA., MayJ., 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ögbergJ., MalettiA., MayJ., Backward and forward bisimulation minimization of tree automata, Theoretical Computer Science410(37) (2009), 3539–3552.
25.
InagakiY., FukumuraT., 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źA., MalettiA., 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.
KnightK., GraehlJ., An overview of probabilistic tree transducers for natural language processing, In: A. Gelbukh (ed.) CICLing 2005, LNCS, 3406 1–24, Springer, Heidelberg, (2005).
28.
LeeE.T., Fuzzy tree automata and syntactic pattern recognition, IEEE Trans Pattern Anal Mach Intell PAMI-4 (1982), 445–449.
29.
LiL., QiuD., On the state minimization of fuzzy automata, IEEE Transactions on Fuzzy Systems23 (2015), 434–443.
30.
LiY.M., PedryczW., Minimization of lattice finite automata and its application to the decomposition of lattice languages, Fuzzy Sets and Systems158 (2007), 1423–1436.
31.
MalettiA., Minimizing deterministic weighted tree automata, Inform and Comput207(11) (2009), 1284–1299.
32.
MalettiA., 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.
MartensW., NevenF., SchwentickT., 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.
MoghariS., ZahediM.M., Similarity-based minimization of fuzzy tree automata, J Appl Math Comput50 (2016), 417–436.
35.
MoghariS., ZahediM.M., Minimization of deterministic fuzzy tree automata, Journal of Fuzzy Set Valued Analysis2014 (2014), 1–18.
36.
MoghariS., ZahediM.M., AmeriR., Merging states in deterministic fuzzy finite tree automata based on fuzzy similarity measure, Italian Journal of Pure and Applied Mathematics33 (2014), 225–240.
37.
MoghariS., ZahediM.M., AmeriR., 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.
MordesonJ.N., MalikD.S., Fuzzy Automata and Languages: Theory and Applications, Chapman & Hall CRC, London, Boca Raton, (2002).
39.
SchwentickT., Automata for XMLA survey, Journal of Computer and System Sciences73(3) (2007), 289–315.
40.
TiwariS.P., YadavV.K., DubeyM.K., Minimal realization for fuzzy behaviour: A bicategory-theoretic approach, Journal of Intelligent & Fuzzy Systems30(2) (2016), 1057–1065.
41.
ThatcherJ.W., Characterizing derivation trees of context free grammars through a generalization of finite automata theory, Journal of Computer and System Sciences1 (1967), 317–322.
42.
ThatcherJ.W., WrightJ.B., Generalized finite automata theory with an application to a decision-problem of second order logic, Mathematical Systems Theory2 (1968), 57–81.
43.
VianuV., 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.
WangY., LiY., Minimization of lattice multiset finite automata, Journal of Intelligent & Fuzzy Systems35(1) (2018), 627–637.
45.
WeeW.G., FuK.S., A formulation of fuzzy automata and its application as a model of learning systems, IEEE Trans Syst Man Cybern5 (1967), 215–223.
