Multidimensional fuzzy finite tree automata

Document Type : Research Paper

Authors

1 Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran.

2 Faculty of Mathematics and Computer, Shahid Bahonar University of Kerman, Kerman, Iran.

Abstract

This paper introduces the notion of multidimensional fuzzy finite tree automata (MFFTA) and investigates its closure properties from the area of automata and language theory. MFFTA are a superclass of fuzzy tree automata whose behavior is generalized to adapt to multidimensional fuzzy sets. An MFFTA recognizes a multidimensional fuzzy tree language which is a regular tree language so that for each dimension, a fuzzy membership grade is assigned to each tree. We study MFFTA by extending some classical problems and properties of automata and regular languages such as determinization, reduction, duality and operations on languages. Furthermore, we provided the method of converting every complete fuzzy tree automata to an MFFTA as well as an example to show the efficiency of MFFTA in comparison to FFTA.
}

Keywords

References

[1] P. R. J. Asveld, Algebraic aspects of families of fuzzy languages, Theoretical Computer Science, 293(2) (2003),
417–445.
[2] S. Bozapalidis, O. L. Bozapalidoy, On the recognizability of fuzzy languages I, Fuzzy Sets and Systems, 157(17)
(2006), 2394–2402.
[3] S. Bozapalidis, O. L. Bozapalidoy, On the recognizability of fuzzy languages II, Fuzzy Sets and Systems, 159(1)
(2008), 107–113.
[4] S. Bozapalidis, O. L. Bozapalidoy, Fuzzy tree language recognizability, Fuzzy Sets and Systems, 161(5) (2010),
716–734.
[5] N. Chomsky, Three models for the description of language, IRE Transactions on Information Theory, 2(3) (1956),
113–124.
[6] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, C. Loding, S. Tison, M. Tommasi, Tree automata:
Techniques and applications, Online (2007), Available: http://tata.gforge.inria.fr, 2007.
[7] J. E. Doner, Decidability of the weak second-order theory of two successors, Notices American Mathematic Society,
12(1) (1965), 365–368.
[8] J. E. Doner, Tree acceptors and some of their applications, Journal of Computer and System Sciences, 4(5) (1970),
406–451.
[9] M. Doostfatemeh, S. C. Kremer, New directions in fuzzy automata, International Journal of Approximate Reasoning,
38(2) (2005), 175–214.
[10] Z. Esik, L. Guangwu, Fuzzy tree automata, Fuzzy Sets and Systems, 158(13) (2007), 1450–1460.
[11] M. K. Fallah, S. Moghari, E. Nazemi, 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.
[12] Z. Fülöp, S. Vágvölgyi, Minimization of deterministic top-down tree automata, Acta Cybernetica, 23(1) (2017),
379–401.
[13] Y. Guellouma, H. Cherroun, D. Ziadi, B. W. Watson, From tree automata to string automata minimization, Theory
of Computing Systems, 62(5) (2018), 1203-1222.
[14] J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to automata theory, Languages, and Computation, 3 edn,
Pearson Education, 2013.
[15] Y. Inagaki, T. Fukumura, On the description of fuzzy meaning of context-free language, In: Fuzzy Sets and their
Applications to Cognitive and Decision Processes, Proceedings of the U. S. Japan Seminar, University of California,
Berkeley, CA, (1975), 301–328.
[16] B. Kafle, J. P. Gallagher, Horn clause verification with convex polyhedral abstraction and tree automata-based
refinement, Computer Languages, Systems & Structures, 47(1) (2017), 2–18.
[17] S. Moghari, M. M. Zahedi, Similarity-based minimization of fuzzy tree automata, Journal of Applied Mathematics
and Computing, 50(1) (2016), 417–436.
[18] S. Moghari, M. M. Zahedi, R. Ameri, Efficient reduction of fuzzy finite tree automata, In: Proceedings of the
6th IMT-GT Conference on Mathematics, Statistics and its Applications (ICMSA2010) Universiti Tunku Abdul
Rahman, Kuala Lumpur, Malaysia, (2010), 1034–1042.
[19] S. Moghari, M. M. Zahedi, R. Ameri, 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.
[20] S. Moghari, M. M. Zahedi, R. Ameri, New direction in fuzzy tree automata, Iranian Journal of Fuzzy Systems, 8(5)
(2011), 59–68.
[21] J. Mordeson, D. S. Malik, Fuzzy automata and languages: Theory and applications, Chapman & Hall, London,
2002.
[22] H. Pan, Y. Li, Y. Cao, Z. Ma, Model checking fuzzy computation tree logic, Fuzzy Sets and Systems, 262 (2015),
60–77.
[23] Y. Shang, X. Yuan, E. S. Lee, The n-dimensional fuzzy sets and zadeh fuzzy sets based on the finite valued fuzzy
sets, Computers & Mathematics with Applications, 60(3) (2010), 442–463.
[24] J. W. Thatcher, J. B. Wright, Generalized finite automata, Notices American Mathematic Society, 12 (1965), 820.
[25] J. W. Thatcher, J. B. Wright, Generalized finite automata with an application to a decision problem of second-order
logic, Mathematical System Theory, 2(1) (1968), 57–82.
[26] L. A. Zadeh, Fuzzy sets, Information and Control, 8(3) (1965), 338–353.
[27] H. J. Zimmermann, Fuzzy set theory and its applications, 3 edn, Springer Science & Business Media, 2011.
Iranian Journal of Fuzzy Systems
Volume 16, Issue 5
September and October 2019
Pages 155-167

Files

Share

How to cite

Statistics