Synthesizing Fuzzy Tree Automata
RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 6

Fuzzy tree automata are mathematical devices for modeling and analyzing vaguely defined tree structures. The behavior of a fuzzy tree automaton generates a fuzzy tree language by mapping a set of regular trees on a ranked alphabet to fuzzy membership values. It calculates the membership grade of trees using a set of rules that process their structural characteristics. This paper deals with constructing fuzzy tree automata models that their behavior satisfies a set of given logical propositions (called properties) on the structure of trees. Our goal is uncertainty modeling by synthesizing fuzzy tree automata whose behavior is described by fuzzy linguistic variables. In this regard, we first provide several patterns and heuristic tricks and techniques for constructing fuzzy tree automata that satisfy simple properties. Then, we develop a method for modeling complex propositional formulas based on the conversion of a logical formula into a computation tree, as well as a step-by-step combination of models.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ita/2022005
Classification : 68T37, 68Q45
Keywords: Uncertainty modeling, synthesizing fuzzy tree automata, vaguely defined fuzzy tree languages 
@article{ITA_2022__56_1_A6_0,
     author = {Moghari, Somaye},
     title = {Synthesizing {Fuzzy} {Tree} {Automata}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     doi = {10.1051/ita/2022005},
     mrnumber = {4442403},
     zbl = {1497.68275},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2022005/}
}
TY  - JOUR
AU  - Moghari, Somaye
TI  - Synthesizing Fuzzy Tree Automata
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2022
VL  - 56
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2022005/
DO  - 10.1051/ita/2022005
LA  - en
ID  - ITA_2022__56_1_A6_0
ER  - 
%0 Journal Article
%A Moghari, Somaye
%T Synthesizing Fuzzy Tree Automata
%J RAIRO. Theoretical Informatics and Applications
%D 2022
%V 56
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2022005/
%R 10.1051/ita/2022005
%G en
%F ITA_2022__56_1_A6_0
Moghari, Somaye. Synthesizing Fuzzy Tree Automata. RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 6. doi: 10.1051/ita/2022005

[1] R. Bača, M. Krátkỳ, I. Holubová, M. Nečaskỳ, T. Skopal, M. Svoboda and S. Sakr Structural XML query processing. ACM Comput. Surv. 50 (2017) 1–41. | DOI

[2] T. Ballard, H. Palada, M. Griffin and A. Neal An integrated approach to testing dynamic, multilevel theory: using computational models to connect theory, model, and data. Org. Res. Methods 24 (2021) 251–284. | DOI

[3] S. Borgwardt and R. P. Naloza Reasoning in fuzzy description logics using automata. Fuzzy Sets Syst. 298 (2016) 22–43. | MR | Zbl | DOI

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

[5] S. Chehida, A. Baouya, S. Bensalem and M. Bozga Learning and analysis of sensors behavior in loT systems using statistical model checking. Softw. Quality J. (2021) 1–22. Available from: | DOI

[6] K. C. Clarke, Mathematical Foundations of Cellular Automata and Complexity Theory, in The Mathematics of Urban Morphology. Springer (2019) 163–170.

[7] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, C. Loding, S. Tison and M. Tommasi, Tree automata: techniques and applications (2007). Preprint | HAL

[8] Y. Du and P. Zhu Fuzzy approximations of fuzzy relational structures. Int. J. Approx. Reas. 98 (2018) 1–10. | MR | Zbl | DOI

[9] Z. Esik and L. Guangwu Fuzzy tree automata. Fuzzy Sets Syst. 158 (2007) 1450–1460. | MR | Zbl | DOI

[10] M. K. Fallah, S. Moghari, E. Nazemi and M. M. Zahedi, Fuzzy ontology based document feature vector modification using fuzzy tree transducer, in Proceedings of the 2008 IEEE International Conference on Signal Image Technology and Internet Based Systems (2008) 38–44. | DOI

[11] A.-J. Fougères and E. Ostrosi Fuzzy engineering design semantics elaboration and application. Soft Comput. Lett. 3 (2021) 100025. | DOI

[12] H. Frenkel, O. Grumberg and S. Sheinvald An automata-theoretic approach to model-checking systems and specifications over infinite data domains. J. Autom. Reas. 63 (2019) 1077–1101. | MR | Zbl | DOI

[13] M. Ghorani, S. Garhwal and S. Moghari Lattice-valued tree pushdown automata: pumping lemma and closure properties. Int. J. Approx. Reas. 142 (2022) 307–323. | MR | Zbl | DOI

[14] M. Ghorani and S. Moghari Decidability of the minimization of fuzzy tree automata with membership values in complete lattices. J. Appl. Math. Comput. 68 (2022) 461–478. | MR | Zbl | DOI

[15] E. González-Caballero, R. A. Espin-Andrade, W. Pedrycz, L. Martinez and L. A. Guerrero-Ramos, Continuous linguistic variables and their applications to data mining and time series prediction. Int. J. Fuzzy Syst. (2021) 1–22.

[16] P. Grzegorzewski Metrics and orders in space of fuzzy numbers. Fuzzy Sets Syst. 97 (1998) 83–94. | MR | Zbl | DOI

[17] M. Hachicha and J. Darmont, A survey of XML tree patterns. IEEE Trans. Knowl. Data Eng. 25 (2011) 29–46. | DOI

[18] J. He, X. Li, Y. Yao, Y. Hong and Z. Jinbao Mining transition rules of cellular automata for simulating urban expansion by using the deep learning techniques. Int. J. Geogr. Inf. Sci. 32 (2018) 2076–2097. | DOI

[19] M. He and S. Kazi, Data structures for categorical path counting queries, in 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), Schloss Dagstuhl-Leibniz-Zentrum fur Informatik (2021). | MR | Zbl

[20] J. E. Hopcroft, Introduction to automata theory, languages, and computation. Pearson Education India (2008).

[21] F. Howar and B. Steffen, Active automata learning in practice, in Machine Learning for Dynamic Software Analysis: Potentials and Limits. Springer (2018) 123–148.

[22] X. Ji, L. Wang, H. Xue and Y. Gao Decision-making method of qualitative and quantitative comprehensive evaluation of talents based on probability hesitation fuzzy language. Math. Probl. Eng. 2021 (2021) 8903427.

[23] K. Johannisson, Disambiguating implicit constructions in OCL, in Workshop on OCL and Model Driven Engineering at UML2004, Lisbon (2004).

[24] A. Kundu and E. Bertino Structural signatures for tree data structures. Proc. VLDB Endow. 1 (2008) 138–150. | DOI

[25] I. Lamrani, A. Banerjee and S. K. Gupta, Hymn: Mining linear hybrid automata from input output traces of cyber-physical systems, in 2018 IEEE Industrial Cyber-Physical Systems (ICPS), IEEE (2018) 264–269. | DOI

[26] X. Li and A. Gar-On Yeh, Data mining of cellular automata’s transition rules. Int. J. Geogr. Inf. Sci. 18 (2004) 723–744. | DOI

[27] Y. Li Approximation and robustness of fuzzy finite automata. Int. J. Approx. Reas. 47 (2008) 247–257. | MR | Zbl | DOI

[28] D. L. Ly and H. Lipson Learning symbolic representations of hybrid dynamical systems. J. Mach. Learn. Res. 13 (2012) 3585–3618. | MR | Zbl

[29] R. Medhat, S. Ramesh, B. Bonakdarpour and S. Fischmeister, A framework for mining hybrid automata from input/output traces, in Proceedings of the 12th International Conference on Embedded Software. IEEE Press (2015) 177–186.

[30] S. Moghari and M. Ghorani, A symbiosis between cellular automata and dynamic weighted multigraph with application on virus spread modeling. Chaos Solitons Fract. 155 (2022) 111660. | DOI

[31] S. Moghari and M. Zahedi (1711-4091), Multidimensional fuzzy finite tree automata. Iran. J. Fuzzy Syst. 16 (2019) 155–167. | MR | Zbl

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

[33] S. Moghari, M. M. Zahedi and R. Ameri New direction in fuzzy tree automata. Iranian J. Fuzzy Syst. 8 (2011) 59–68. | MR | Zbl

[34] S. Mohammed, A. F. Barradah and E.-S. M. El-Alfy, Selectivity estimation of extended XML query tree patterns based on prime number labeling and synopsis modeling. Simul. Model. Practice Theory 64 (2016) 30–42. | DOI

[35] S. Mohammed, E.-S. M. El-Alfy and A. F. Barradah, Improved selectivity estimator for XML queries based on structural synopsis. World Wide Web 18 (2015) 1123–1144. | DOI

[36] J. Mordeson and D. S. Malik, Fuzzy automata and languages: theory and applications. Chapman & Hall, London (2002). | MR | Zbl

[37] L. D. Nguyen and D. Q. Tran Measurement of fuzzy membership functions in construction risk assessment. J. Constr. Eng. Manag. 147 (2021) 04021005. | DOI

[38] B. E. Reddy, R. O. Reddy and E. K. Reddy Pattern analysis and texture classification using finite state automata scheme. Int. J. Adv. Intell. Parad. 14 (2019) 30–45.

[39] M. S. Roodposhti, J. Aryal and B. A. Bryan, A novel algorithm for calculating transition potential in cellular automata models of land-use/cover change. Environ. Model. Softw. 112 (2019) 70–81. | DOI

[40] M. G. Soto, T. A. Henzinger, C. Schilling and L. Zeleznik, Membership-based synthesis of linear hybrid automata, in International Conference on Computer Aided Verification. Springer (2019) 297–314. | MR

[41] J. L. Verdegay, Vol. 377 of Uncertainty Management with Fuzzy and Rough Sets. Springer (2019).

[42] L. Wang, Y. Wang, D. Cai, D. Zhang and X. Liu, Translating a math word problem to an expression tree. Preprint 2018). | arXiv

[43] L.-G. Wang, T. T.-Y. Lam, S. Xu, Z. Dai, L. Zhou, T. Feng, P. Guo, C. W. Dunn, B. R. Jones, T. Bradley et al., Treeio: an R package for phylogenetic tree input and output with richly annotated and associated data. Mol. Biol. Evol. 37 (2020) 599–603. | DOI

[44] X. Wu and D. Theodoratos Template-based bitmap view selection for optimizing queries over tree data. Int. J. Cooperative Inf. Syst. 25 (2016) 1650005. | DOI

[45] C. Yang and Y. Li Approximate bisimulations and state reduction of fuzzy automata under fuzzy similarity measures. Fuzzy Sets Syst. 391 (2020) 72–95. | MR | Zbl | DOI

[46] H. Ying and F. Lin Online self-learning fuzzy discrete event systems. IEEE Trans. Fuzzy Syst. 28 (2020) 2185–2194. | DOI

[47] M. Yulduz Lexico-grammatical parts of speech expressing the indefiniteness of the subject. JournalNX 7 (2021) 323–327.

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

[49] L. A. Zadeh The concept of a linguistic variable and its application to approximate reasoning-I. Inf. Sci. 8 (1975) 199–249. | MR | Zbl | DOI

[50] L. A. Zadeh The concept of a linguistic variable and its application to approximate reasoning-II. Inf. Sci. 8 (1975) 301–357. | MR | Zbl | DOI

[51] H. J. Zimmermann, Fuzzy set theory and its applications, 3rd edn. Springer Science & Business Media (2011). | Zbl | MR

Cité par Sources :