Relation Between Deterministic Fuzzy Tree Automata and Normal Recognizable Step Mappings

Document Type : Original Article

Author

Department of Applied Mathematics and Computer Science, Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran

Abstract

In this paper we investigate fuzzy tree automata. Fuzzy tree automata extend fuzzy automata. In fuzzy automata we deal with strings and in fuzzy tree automata we utilize trees instead of strings. We define a recognizable step fuzzy tree language and by a theorem we show that recognizable fuzzy tree language is recognizable step fuzzy tree language. Then, we define a deterministic fuzzy tree automaton and support of a fuzzy tree language and show that support of a fuzzy tree language can be recognized by a fuzzy tree automaton. We explain these concepts by examples. We also show that for a recognizable step mapping, there exists a deterministic fuzzy tree automaton that can recognize it, and vice versa. In fact we prove that the class of recognizable fuzzy tree languages is equal to the class of normal recognizable step mappings.The obtained theorems generalize the results of weighted automata to tree automata.

Keywords

References

[1] 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, Available: http://tata.gforge.inria.fr.
 
[4] J.E. Doner, (1965), Decidability of the weak second-order theory of two successors, 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 Systems, 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 Mathematics 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 contextfree 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 Transaction 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 application 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.
 
[25] L.A. Zadeh, (1965), Fuzzy sets. Inf. Control, 8(3), 338-353.
Fuzzy Systems and its Applications
Volume 4, Issue 2 - Serial Number 9
March 2022
Pages 113-132

Files

History

  • Receive Date: 15 November 2021
  • Revise Date: 09 December 2021
  • Accept Date: 03 March 2022

Share

How to cite

Statistics