NEW DIRECTION IN FUZZY TREE AUTOMATA

Document Type: Research Paper

Authors

1 Department of Mathematics, Science Faculty, Alzahra University, Vanak, Tehran, Iran

2 Department of Mathematics, Shahid Bahonar University of Kerman, Kerman, Iran

3 College of Sciences, Tehran University, P.O. Box 14155-6455, Tehran, Iran

Abstract

In this paper, our focus of attention is the proper propagation
of fuzzy degrees in determinization of $Nondeterministic$ $Fuzzy$
$Finite$ $Tree$ $Automata$ (NFFTA). Initially, two determinization
methods are introduced which have some limitations (one in
behavior preserving and other in type of fuzzy operations). In
order to eliminate these limitations and increasing the
efficiency of FFTA, we define the notion of fuzzy complex state
and $Complex$ $FFTA$ (CFFTA). Also, we define
$\nabla$-normalization operation in algebra of fuzzy complex
state to solve the multi membership state problem in fuzzy
automata. Furthermore, we discuss the relationship between FFTA
and CFFTA. Finally, determinization of CFFTA is presented.

Keywords


bibitem{Arbib:a}
M. A. Arbib, {it From automata theory to brain theory}, Int. J.
Man-Machine Studies, {bf 7}textbf{(3)} (1975), 279-295.

bibitem{Bozapalidis:a}
S. Bozapalidis and O. L. Bozapalidoy, {it Fuzzy tree language
recognizability}, Fuzzy Sets and Systems, {bf
161}textbf{(5)} (2010), 716-734.

bibitem{Comon:a}
H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, C.
Loding, S. Tison and M. Tommasi, {it Tree automata: techniques
and applications}, Available: http://tata.gforge.inria.fr, 2007.

bibitem{Doner:a}
J. E. Doner, {it Decidability of the weak second-order theory of
two successors}, Notices American Mathematic Society, {bf
12} (1965), 365-486.

bibitem{Doner:b}
J. E. Doner, {it Tree acceptors and some of their applications},
Journal of Computer and System Science, {bf 4} (1970), 406-451.

bibitem{Doostfatemeh:a}
M. Doostfatemeh and S. C. Kremer, {it New directions in fuzzy
automata}, Int. J. Approximate Reasoning, {bf 38} (2005),
175-214.

bibitem{Esik:a}
Z. Esik and L. Guangwu, {it Fuzzy tree automata}, Fuzzy Sets and
Systems, {bf 158} (2007), 1450-1460.

bibitem{Gaines:a}
B. Gaines and L. J. Kohout, {it The logic of automata}, Int. J.
General Systems, {bf 2} (1976), 191-208.

bibitem{Horry:a}
M. Horry and M. M. Zahedi, {it Hypergroups and general fuzzy
automata}, Iranian Journal of Fuzzy Systems, {bf
6}textbf{(2)} (2009), 61-74.

bibitem{Mateescu:a}
A. Mateescu, A. Salomaa, K. Salomaa and S. Yu, {it Lexical
analysis with a simple finite fuzzy automata model}, Journal of
Universal Computing, {bf 1}textbf{(5)} (1995), 288-307.

bibitem{Mordeson:a}
J. Mordeson and D. Malik, {it Fuzzy automata and languages:
theory and applications}, Chapman & Hall, London, 2002.

bibitem{Rabin:a}
M. O. Rabin, {it FHandbook of mathematical logic}, North
Holland, 1977.

bibitem{Thatcher:a}
J. W. Thatcher and J. B. Wright, {it Generalized finite automata
with an application to a decision problem of second-order logic},
Mathematical System Theory, {bf 2} (1968), 57-82.

bibitem{Thatcher:b}
J. W. Thatcher and J. B. Wright, {it Generalized finite
automata}, Notices American Mathematic Society, {bf 820} (1965).

bibitem{Thomas:a}
W. Thomas, {it Handbook of theoretical computer science},
Elsevier, {bf B} (1990).

bibitem{Wee:a}
W. G. Wee, {it On generalization of adaptive algorithm and
application of the fuzzy sets concept to pattern classification},
Ph.D. Dissertation, Purdue University, Lafayette, 1967.

bibitem{Ying:a}
M. Ying, {it A formal model of computing with words}, IEEE
Transactions on Fuzzy Systems, {bf 10}textbf{(5)} (2002),
640-652.

bibitem{Zadeh:a}
L. A. Zadeh, {it Fuzzy sets}, Information and Control, {bf
8} (1965), 338-353.