State hyperstructures of tree automata based on lattice-valued logic
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 1, pp. 23-42.

In this paper, an association is organized between the theory of tree automata on one hand and the hyperstructures on the other hand, over complete residuated lattices. To this end, the concept of order of the states of a complete residuated lattice-valued tree automaton (simply L-valued tree automaton) is introduced along with several equivalence relations in the set of the states of an L-valued tree automaton. We obtain two main results from this study: one of the relations can lead to the creation of Kleene’s theorem for L-valued tree automata, and the other one leads to the creation of a minimal v-valued tree automaton that accepts the same language as the given one.

DOI : 10.1051/ita/2018004
Classification : 68Q70, 68Q45, 20N25, 20N20
Mots-clés : Tree automaton, lattice-valued logic, Kleene’s theorem, hypergroup, minimization
Ghorani, Maryam 1

1 
@article{ITA_2018__52_1_23_0,
     author = {Ghorani, Maryam},
     title = {State hyperstructures of tree automata based on lattice-valued logic},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {23--42},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {1},
     year = {2018},
     doi = {10.1051/ita/2018004},
     mrnumber = {3843153},
     zbl = {1400.68129},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2018004/}
}
TY  - JOUR
AU  - Ghorani, Maryam
TI  - State hyperstructures of tree automata based on lattice-valued logic
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2018
SP  - 23
EP  - 42
VL  - 52
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2018004/
DO  - 10.1051/ita/2018004
LA  - en
ID  - ITA_2018__52_1_23_0
ER  - 
%0 Journal Article
%A Ghorani, Maryam
%T State hyperstructures of tree automata based on lattice-valued logic
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2018
%P 23-42
%V 52
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2018004/
%R 10.1051/ita/2018004
%G en
%F ITA_2018__52_1_23_0
Ghorani, Maryam. State hyperstructures of tree automata based on lattice-valued logic. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 1, pp. 23-42. doi : 10.1051/ita/2018004. http://archive.numdam.org/articles/10.1051/ita/2018004/

[1] R. Ameri and M.M. Zahedi, Hypergroup and join space induced by a fuzzy subset. Pure Math. Appl. 8 (1997) 155–168. | MR | Zbl

[2] G. Birkhof, Lattice Theory. American Mathematical Society, Providence (1984). | MR | Zbl

[3] S. Bozapalidis and O.L. Bozapalidoy, Fuzzy tree language recognizability. Fuzzy Sets Syst. 161 (2010) 716–734. | DOI | MR | Zbl

[4] J. Chvalina and L. Chvalinova, State hypergroup of automata. Acta Mat. et. Inf. Univ. Ostraviensis 4 (1996) 105–120. | MR | Zbl

[5] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, C. Loding, S. Tison and M. Tommasi, Tree Automata: technigues and Applications. Available at http://tata.gforge.inria.fr (2007).

[6] P. Corsini, Prolegomena of Hypergroup Theory. Edited by Aviani (1993). | MR | Zbl

[7] P. Corsini, Join spaces, power sets, fuzzy sets, in Proc. of the Fifth International Congress of Algebraic Hyperstructures and Their Applications (Iasi, 1993). Hadronic Press, Palm Harbor (1994) 45–52. | MR | Zbl

[8] P. Corsini and V. Leoreanu, Applications of Hyperstructure Theory. Advances in Mathematics. Kluwer Academic Publishers, Dordrecht (2003). | MR | Zbl

[9] B. Davvaz, Fuzzy Hv-groups. Fuzzy Sets Syst. 101 (1999) 191–195. | DOI | MR | Zbl

[10] B. Davvaz, Interval-valued fuzzy subhypergroups. Korean J. Comput. Appl. Math 6 (1999) 197–202. | DOI | MR | Zbl

[11] B. Davvaz, On fuzzy relations and fuzzy subhypergroups. Pure Math. Appl. 11 (2000) 51–58. | MR | Zbl

[12] W.A. Dudek, J. Zhan and B. Davvaz, On intuitionistic (S, T)-fuzzy hypergroups. Soft Comput. 12 (2008) 1229–1238. | DOI | Zbl

[13] Z. Esik and G. Liu, Fuzzy tree automata. Fuzzy Sets Syst. 158 (2007) 1450–1460. | DOI | MR | Zbl

[14] Z. Esik and W. Kuich, Formal tree series, in: Weighted Automata: Theory and Applications. J. Automat. Lang. Comb. 8 (2002) 219–285. | MR | Zbl

[15] J. Ignjatovic, M. Ciric and S. Bogdanovic, Determinization of fuzzy automata with membership values in complete residuated lattices. Inf. Sci. 178 (2008) 164–180. | DOI | MR | Zbl

[16] Y. Inagaki and T. Fukumura, On the description of fuzzy meaning of context-free language, Fuzzy sets and their applications to cognitive and decision processes, in Proc. of the US-Japan Seminar, University of California, Berkeley, CA, 1974. Academic Press, New York (1975) 301–328. | MR | Zbl

[17] F. Gécseg and M. Steinby, Tree Automata. Akademiai Kiado, Budapest, 1984. | MR | Zbl

[18] M. Ghorani, On characterization of fuzzy tree pushdown automata. To appear in: Soft Comput. DOI: (2017). | DOI | Zbl

[19] M. Ghorani, Tree automata based on complete residuated lattice-valued logic: reduction algorithm and decision problems. To appear in: Iran. J. Fuzzy Syst. DOI: (2017). | DOI | MR

[20] M. Ghorani and M.M. Zahedi, Characterization of complete residuated lattice-valued finite tree automata. Fuzzy Sets Syst. 199 (2012) 28–46. | DOI | MR | Zbl

[21] M. Ghorani and M.M. Zahedi, Alternating regular tree grammars in the framework of lattice-valued logic. Iran. J. Fuzzy Syst. 13 (2016) 71–94. | MR | Zbl

[22] M. Ghorani and M.M. Zahedi, Coding tree languages based on lattice-valued logic. Soft Comput. 21 (2017) 3815–3825. | DOI | Zbl

[23] M. Ghorani, M.M. Zahedi and R. Ameri, Algebraic properties of complete residuated lattice-valued tree automata. Soft Computing 16 (2012) 1723–1732. | DOI | Zbl

[24] M. Gori and A. Petrosino, Encoding non-deterministic fuzzy tree automata into recursive neural networks. IEEE Trans. Neur. Net. 156 (2004) 1435–1449. | DOI

[25] M. Horry and M.M. Zahedi, Hypergroups and general fuzzy automata. Iran. J. Fuzzy Syst. 6 (2009) 61–74. | MR | Zbl

[26] E.T. Lee, Fuzzy tree automata and syntactic pattern recognition. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-4 (1982) 445–449. | DOI | Zbl

[27] E.T. Lee and L.A. Zadeh, Note on fuzzy languages. Inf. Sci. 1 (1969) 421–434. | DOI | MR

[28] H.X. Lei and Y. Li, Minimization of states in automata theory based on finite lattice-ordered monoids. Inf. Sci. 177 (2007) 1413–1421. | DOI | MR | Zbl

[29] Y.M. Li, Finite automata theory with membership values in lattices. Inf. Sci. 181 (2011) 1003–1017. | DOI | MR | Zbl

[30] Y.M. Li and W. Pedrycz, Minimization of lattice finite automata and its application to the decomposition of lattice languages. Fuzzy Sets Syst. 158 (2007) 1423–1436. | DOI | MR | Zbl

[31] L. Li and D. Qiu, On the state minimization of fuzzy automata. IEEE Trans. Fuzzy Syst. 32 (2015) 434–443. | DOI

[32] F. Lin and H. Ying, Modeling and control of fuzzy discrete event systems. IEEE Trans. Syst. Man Cybern. B 32 (2002) 408–415. | DOI

[33] F. Marty, Sur une généralisation de la notion de groupe. Huitieme Congr. math. Scan. Stockholm (1934) 45–49. | JFM | Zbl

[34] Ch.G. Massouros and G.G. Massouros, On certain fundamental properties of hypergroups and fuzzy hypergroups- Mimic fuzzy hypergroups. Int. J. Risk Theory 2 (2012) 71–82.

[35] G.G. Massouros, Automata, Languages and Hypercompositional Structures. Doctoral Thesis, National Technical University of Athens (1993).

[36] G.G. Massouros, An automaton during its operation, in Proc. of the 5th International Congress on Algebraic Hyperstructures and Applications, HadronicPress (1994) 267–276. | MR | Zbl

[37] G.G. Massouros, Automata and hypermoduloids, in Proc. of the 5th International Congress on Algebraic Hyperstructures and Applications (Iasi 1993), Hadronic Press (1994) 251–266. | MR | Zbl

[38] G.G. Massouros and J. Mittas, Languages, automata and hypercompositional hyperstructures and applications, in Proc. of the 4th International Congress on Algebraic Hyperstructures and Applications (Xanthi 1990), World Scientific (1991) 137–147. | MR | Zbl

[39] S. Moghari and M.M. Zahedi, Similarity-based minimization of fuzzy tree automata. J. Appl. Math. Comput. 55 (2016) 417–436. | DOI | MR | Zbl

[40] J.N. Mordeson and D.S. Malik, Fuzzy Automata and Languages: theory and Applications. Chapman & Hall CRC, London, Boca Raton (2002). | DOI | MR | Zbl

[41] C.W. Omlin, K.K. Thornber and C.L. Giles, Fuzzy finite-state automata can be deterministically encoded in recurrent neural networks. IEEE Trans. Fuzzy Syst. 5 (1998) 76–89. | DOI

[42] W. Pedrycz and A. Gacek, Learning of fuzzy automata. Int. J. Comput. Intell. Appl. 1 (2001) 19–33. | DOI

[43] D.W. Qiu, Automata theory based on completed residuated lattice-valued logic (I). Sci. China (Series F) 44 (2001) 419–429. | MR | Zbl

[44] D.W. Qiu, Automata theory based on completed residuated lattice-valued logic (II). Sci. China (Series F) 45 (2002) 442–452. | MR | Zbl

[45] D.W. Qiu, Characterizations of fuzzy finite automata. Fuzzy Sets Syst. 141 (2004) 391–414. | DOI | MR | Zbl

[46] D.W. Qiu, Supervisory control of fuzzy discrete event systems: a formal approach. IEEE Trans. Sys. Man Cybern.-Part B 35 (2005) 72–88. | DOI

[47] D.W. Qiu, Pumping lemma in automata theory based on complete residuated lattice-valued logic: a note. Fuzzy Sets Syst. 157 (2006) 2128–38. | DOI | MR | Zbl

[48] E.S. Santos, Maximin automata. Inform. Control 12 (1968) 367–377. | MR | Zbl

[49] M.G. Thomason and P.N. Marinos, Deterministic acceptors of regular fuzzy languages. IEEE Trans. Sys. Man Cybern. 4 (1974) 228–230. | DOI | MR | Zbl

[50] W.G. Wee and K.S. Fu, A formulation of fuzzy automata and its application as a model of learning systems. IEEE Trans. Sys. Man Cybern. 5 (1969) 215–223. | Zbl

[51] L. Wu and D.W. Qiu, Automata theory based on completed residuated lattice-valued logic: reduction and minimization. Fuzzy Sets Syst. 161 (2010) 1635–1656. | DOI | MR | Zbl

[52] H.Y. Xing, D.W. Qiu and F.C. Liu, Automata theory based on complete residuated lattice-valued logic: pushdown automata. Fuzzy Sets Syst. 160 (2009) 1125–1140. | DOI | MR | Zbl

[53] H.Y. Xing, D.W. Qiu, F.C. Liu and Z.J. Fan, Equivalence in automata theory based on complete residuated lattice-valued logic. Fuzzy Sets Syst. 158 (2007) 1407–1422. | DOI | MR | Zbl

[54] L.A. Zadeh, Fuzzy sets. Inf. Control 8 (1965) 338–353. | DOI | MR | Zbl

[55] M. Zahedi, M. Bolurian and A. Hasankhani, On polygroups and fuzzy subpolygroups. J. Fuzzy Math. 3 (1995) 1–15. | MR | Zbl

Cité par Sources :