ارتباط بین اتوماتای درختی فازی قطعی و نگاشت های مرحله ای تشخیص پذیر نرمال

نوع مقاله : مقاله پژوهشی

نویسنده

داﻧﺸﮑﺪه ﻋﻠﻮم رﯾﺎﺿﯽ، داﻧﺸﮕﺎه ﺻﻨﻌﺘﯽ ﺷﺎﻫﺮود، ﺷﺎﻫﺮود، اﯾﺮان

10.22034/jfsa.2022.315340.1100

چکیده

در اﯾﻦ ﻣﻘﺎﻟﻪ، ﺑﻪ ﺑﺮرﺳﯽ اﺗﻮﻣﺎﺗﺎی درﺧﺘﯽ ﻓﺎزی ﻣﯽﭘﺮدازﯾﻢ. ﯾﮏ زﺑﺎن درﺧﺖ ﻓﺎزی ﻣﺮﺣﻠﻪای ﺗﺸﺨﯿﺺﭘﺬﯾﺮ را ﺗﻌﺮﯾﻒ ﮐﺮده و ﻧﺸﺎن ﻣﯽدﻫﯿﻢ ﻫﺮ زﺑﺎن درﺧﺖ ﻓﺎزی ﺗﺸﺨﯿﺺﭘﺬﯾﺮ ﯾﮏ زﺑﺎن درﺧﺖ ﻓﺎزی ﻣﺮﺣﻠﻪای ﺗﺸﺨﯿﺺﭘﺬﯾﺮ اﺳﺖ. در اداﻣ ﻪ، ﯾ ﮏ اﺗ ﻮﻣ ﺎﺗ ﻮن درﺧﺘ ﯽ ﻓ ﺎزی ﻗ ﻄ ﻌ ﯽ را ﻣ ﻌ ﺮﻓ ﯽ ﮐ ﺮده و ﻧﺸ ﺎن ﻣ ﯽدﻫﯿ ﻢ ﺗﮑﯿ ﻪﮔ ﺎه ﯾﮏ زﺑﺎن درﺧﺖ ﻓ ﺎزی ﻗﺎﺑﻞ ﺗﺸﺨﯿﺺ ﺗ ﻮﺳﻂ ﯾﮏ اﺗ ﻮﻣ ﺎﺗﻮن درﺧﺘﯽ ﻓﺎزی، ﺗﺸﺨﯿﺺﭘﺬﯾﺮ اﺳﺖ. اﯾﻦ ﻣﻔﺎﻫﯿﻢ را روی ﺑﺮﺧﯽ اﺗﻮﻣﺎﺗﺎی درﺧﺘﯽ ﻓﺎزی ﻧﻤﺎﯾﺶ ﻣﯽدﻫﯿﻢ. ﻫﻤﭽﻨﯿﻦ، ﺛﺎﺑﺖ ﻣﯽﮐﻨﯿﻢ ﮐﻪ ﮐﻼس زﺑﺎنﻫﺎی درﺧﺖ ﻓﺎزی ﻗﺎﺑﻞ ﺗﺸﺨﯿﺺ ﺗﻮﺳﻂ اﺗﻮﻣﺎﺗﺎی درﺧﺘﯽ ﻓﺎزی ﻗﻄﻌﯽ، ﺑﺎ ﮐﻼس ﻧﮕﺎﺷﺖﻫﺎی ﻣﺮﺣﻠﻪای ﺗﺸﺨﯿﺺﭘﺬﯾﺮ ﺑﺮاﺑﺮ اﺳﺖ. در ﻧﻬﺎﯾﺖ، ﻧﺸﺎن ﻣﯽدﻫﯿﻢ ﮐﻪ ﯾﮏ زﺑﺎن درﺧﺖ ﻓﺎزی ﺗﻮﺳﻂ ﯾﮏ اﺗﻮﻣﺎﺗﻮن درﺧﺘﯽ ﻓﺎزی ﻗﻄﻌﯽ ﻗﺎﺑﻞ ﺗﺸﺨﯿﺺ اﺳﺖ اﮔﺮ و ﻓﻘﻂ اﮔﺮ آن زﺑﺎن، ﯾﮏ ﻧﮕﺎﺷﺖ ﻣﺮﺣﻠﻪای ﺗﺸﺨﯿﺺﭘﺬﯾﺮ ﻧﺮﻣﺎل ﺑﺎﺷﺪ.

کلیدواژه‌ها


[I] K. Abolpour, M.M. Zahedi, (2021), LB-valued general fuzzy automata, Fuzzy Sets and Systems, in press, https://doi.org/10.1016/j.fss.2021.08.017.
[2]    K. Abolpour, M.M. Zahedi, M. Golmohamadian, (2011), Some hyper K-algebraic structures induced by max-min general fuzzy automata, Iranian Journal of Fuzzy Systems, 8(1), 113-134.
[3]    H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, C. Loding, S. Tison, M. Tommasi, (2007), Tree Automata: Technigues and Applications, Avail- able: http://tata.gforge.inria.fr.
[4]    J.E. Doner, (1965), Decidability of the weak second-order theory of two succes- sors, Not. Am. Math. Soc. 12(1), 365–368.
[5]    M. Droste, T. Stuber, H. Vogler, (2010). Weighted finite automata over strong bimonoids, Information Sciences, 180(1), 156-166.
[6]    Z. Esik, G. Liu, (2007), Fuzzy tree automata, Fuzzy Sets and Systems, 158, 1450- 1460.
[7]    M. Ghorani, (2019), On characterization of fuzzy tree pushdown automata, Soft Computing 23(4), 1123-1131.
[8]    M. Ghorani, (2018), State hyperstructures of tree automata based on lattice-valued logic, RAIRO-Theoretical Informatics and Applications, 52(1), 23-42.
[9]    M. Ghorani, (2018), Tree automata based on complete residuated lattice-valued logic: reduction algorithm and decision problem, Iranian Journal of Fuzzy Sys- tems, 15(7), 103-119.
[10]        M. Ghorani, S. Garhwal, (2021), A minimization algorithm for fuzzy top-down tree automata over lattices, Journal of Intelligent & Fuzzy Systems, 40(3), 4471- 4480.
[11]        M. Ghorani, S. Moghari, (2021), Decidability of the minimization of fuzzy tree automata with membership values in complete lattices, Journal of Applied Math- ematics and Computing, in press, https://doi.org/10.1007/s12190-021-01529-6
[12]        M. Ghorani, M.M. Zahedi, (2012), Characterizations of complete residuated lattice-valued finite tree automata, Fuzzy Sets and Systems, 199, 28-46.
[13]        M. Ghorani, M.M. Zahedi, (2017), Coding tree languages based on lattice valued logic, Soft Computing, 21(14), 3815-3825.
[14]        M. Ghorani, M.M. Zahedi, R. Ameri, (2012), Algebraic properties of complete residuated lattice valued tree automata, Soft Computing, 16(10), 1723-1732.
[15]        Y. Inagaki, T. Fukumura, (1975), On the description of fuzzy meaning of context- free language, in: Fuzzy Sets and Their Applications to Cognitive and Decision Processes, Proc. Japan Seminar, University of California, Berkeley, CA, 1974, Academic Press, New York, pp. 301-328.
[16]        E. Jurvanen, M. Steinby, (2019), Fuzzy deterministic top-down tree automata, arXiv:1911.11529v1.
[17]        L. Li, D. Qiu, (2015), On the state minimization of fuzzy automata, IEEE Trans- action on Fuzzy Systems, 23(2), 434-443.
[18]        Y. Li, Z. Ma, (2015), Quantitative computational tree logic model checking based on generalized possibility measures, IEEE Transactions on Fuzzy Systems, 23(6), 2034- 2047.
[19]        S. Moghari, M.M. Zahedi, (2016), Similarity-based minimization of fuzzy tree automata, J. Appl. Math. Comput., 50(1), 417-436.
[20]        S. Moghari, M.M. Zahedi, (2019), Multidimensional fuzzy finite tree automata, Iranian Journal of Fuzzy Systems, 16(5), 155-167.
[21]        H.Y. Pan, Y. Li, Y.Z. Cao, Z. Ma, (2016), Model checking computation tree logic over finite lattices, Theoretical Computer Science, 612, 45-62.
[22]        M. Shamsizadeh, M.M. Zahedi, (2019), Bisimulation of type 2 for BL-general fuzzy automata, Soft Computing 23 (20), 9843-9852.
[23]        J.W. Thatcher, J.B. Wright, (1968), Generalized finite automata with an applica- tion to a decision problem of second-order logic, Math. Syst. Theory, 2(1), 57–82.
[24]        W.G. Wee, (1967), On generalization of adaptive algorithm and application of the fuzzy sets concept to pattern classification. Ph.D. thesis, Purdue University, Lafayette, IN.
[25]    L.A. Zadeh, (1965), Fuzzy sets. Inf. Control, 8(3), 338–353.