Some Properties of Fuzzy Finite Tree Automata

Abstract

This paper examines fuzzy tree automata\'s deterministic, reduced, and homomorphic properties. It is demonstrated through an example that there is a deterministic fuzzy tree automaton for the nondeterministic one. For every given fuzzy tree automaton, an equivalent reduced fuzzy tree automaton is displayed. A theorem that fuzzy tree languages are preserved by tree homomorphism is derived.

Introduction

The text explores extensions of finite state automata, particularly focusing on fuzzy finite tree automata (FFTA) and their deterministic counterparts (DFFTA). It discusses foundational definitions and formalizes fuzzy finite tree automata, including states, input alphabets, transition rules, and fuzzy final states.

Key results include:

• Equivalence of Deterministic and Non-Deterministic Fuzzy Tree Automata: For any fuzzy tree automaton AAA, there exists a deterministic fuzzy tree automaton AdA_dAd? such that both recognize the same fuzzy tree language L(A)=L(Ad)L(A) = L(A_d)L(A)=L(Ad?), although membership values for specific trees may differ.

• Reduced Fuzzy Finite Tree Automata: Every fuzzy tree automaton has an equivalent reduced version where all states are accessible, ensuring minimal representation without loss of recognized language.

• Tree Homomorphisms: If LLL is recognized by a fuzzy tree automaton and hhh is a linear tree homomorphism, then h(L)h(L)h(L) is also recognized by a fuzzy tree automaton. The text provides a construction method for such automata under tree homomorphisms.

Examples illustrate these constructions and proofs, showing how membership values are computed and how automata transition rules are derived.

Conclusion

Automata on infinite words, weighted automata, fuzzy automata on finite and infinite words, tree automata, and weighted tree automata are some of the ways that finite state automata have been expanded. We refer to [8] for a general treatment of fuzzy automata and languages.

References

[1] Alexandru Mateescu, A., Salomaa, A., Salomaa, K. and Sheng Yi, “Lexical Analysis with a simple finite-fuzzy-automaton model, Journal of Uni-Comp.Sci. 1, No.5(1995), 292-311. [2] Bozapalidis, S. and Bozapalidou, O.L, Fuzzy tree language recognizability, Fuzzy Sets and Systems 161(2010)716734. [3] Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S. and Tommasi, M. Tree Automata Techniques and Applications. Draft Book, http://13ux02.univ-lille3.fr/tata/ (2008). [4] Dubois, D. Prade, H. Fuzzy Sets and Systems : Theory and Applications, Academic Press, New York, 1980. [5] Esik, Z, Lin, G, Fuzzy Tree Automata, Fuzzy Sets and Systems, 158(2007) 14501460. [6] Chitra, K. and Rajaretnam, T., A Study on Recognizability of Max Weighted Finite State Automaton, Journal of Computer and Mathematical Sciences, e-ISSN: 2319-8133, p-ISSN: 0976-5727, Vol.8, Issue 11, November 2017, 658-673. [7] Chitra, K. and Rajaretnam, T., Some Products on Max Weighted Finite State Automaton, International Journal of Applied Engineering Research, e-ISSN: 0973-9769, p-ISSN: 0973-4562, Vol.13, Number 22, 2018, 15806-15823. [8] Eilenberg, S. Automata, Languages and Machines, Vol.A, Academic Press, New York, 1974. [9] Malik, D.S. and Mordeson, J.N., Fuzzy Automata and Languages Theory and applications, CRC, 2002 [10] Saridha. S , An Introduction to Plus Weighted Dendro language and its Properties, Aryabhatta Journal of Mathematics and Informatics, Volume 5, Issue 1, Jan -June 2023. Pg. No. 93-100, ISSN No: 0975-7139(P) 2394-9309. [11] Saridha. S, “ An Innovative ideas on Plus Weighted Linear Grammar”, Aryabhatta Journal of Mathematics & Informatics, Volume 15, No.2, Page no: 173-178, ISSN 2321-9653, Jan -Dec 2023. [12] Saridha. S, “Construction of Derivation Trees of Plus Weighted Context Free Grammars”, International Journal for Research in Applied Science and Engineering Technology (IJRASET), Volume 11, Issue III, March 2023, Page No:1821-1827, ISSN: 2321-9653. [13] Saridha. S, “An Introduction to Plus Weighted Dendrolanguage and its properties”, Volume 15, Issue I, Aryabhatta journal of mathematics & Informatics(AJMI), Jan-June 2023, Page No: 93-100, ISSN: 2394-9309. [14] Saridha. S, “Application of Fuzzy Hyper graph in Medical Diagnosis”,International Journal of Research in Applied Science and Engineering Technology,Volume 12, Issue I, Page no: 872-875, ISSN 2321-9653, Jan 2024. [15] Saridha. S, “An overview on Intuitionistic Fuzzy Multi-Hypergroup”, International Journal of Research in Applied Science and Engineering Technology,Volume 12, Issue II, Page no: 1316-1318, ISSN 2321-9653, Feb 2024. [16] Saridha. S, “An application of Fuzzy Graph Structure in Human Trafficking”, Research Updates in Mathematics and Computer Science, Volume 5, Chapter 6, Issue II, Page no: 70-80, ISBN: 978-81-972756-4-7, May 2024.

Copyright

Copyright © 2025 Chitra K.. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.