^{1}Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran

^{2}Department of Mathematics, Graduate University of Advanced Technology, Kerman, Iran

Abstract

In this paper, two different ways of introducing alternation for lattice-valued (referred to as {L}valued) regular tree grammars and {L}valued top-down tree automata are compared. One is the way which defines the alternating regular tree grammar, i.e., alternation is governed by the non-terminals of the grammar and the other is the way which combines state with alternation. The first way is taken over to prove a main theorem: the class of languages generated by an {L}valued alternating regular tree grammar {LAG}) is equal to the class of languages accepted by an {L}valued alternating top-down tree automaton {LAA}). The second way is taken over to define a new type of automaton by combining the {L}valued alternating top-down tree automaton with stack, called {L}-valued alternating stack tree automaton {LASA} and the generative power of it is compared to some well-known language classes, especially to {LAA} and to {LAG} Also, we have derived a characterization of the state alternating regular tree grammar {LSAG}) in terms of {LASA}.

[1] A. Bouhoula, J. P. Jouannaud and J. Meseguer, Specication and proof in membeship equa- tional logic, Theoretical Computer Science, 236 (2000), 35-132. [2] G. Birkho, Lattice theory, American Mathematical Society Colloquium Publications, New York, 1984. [3] S. Bozapalidis and O. L. Bozapalidoy, Fuzzy tree language recognizability, Fuzzy Sets and Systems, 161(5) (2010), 716-734. [4] J. R. Buchi, Weak second-order arithmetic and nite automata, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 6 (1960), 66-92. [5] Y. Cao, L. Xia and M. Ying, Probabilistic automata for computing with words, Journal of Computer and System Sciences, 79(1) (2013), 152-172. [6] A. K. Chandra, D. C. Kozen and L. J. Stockmeyer, Alternation, Journal of the ACM, 28(1) (1981), 114-133. [7] S. R. Chaudhari and M. N. Joshi, A note on fuzzy tree automata, International Journal of Computer Applications, 56(17) (2012), 1-5. [8] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, C. Loding, S. Ti- son and M. Tommasi, Tree automata: technigues and applications, 2007. Available: http://tata.gforge.inria.fr. [9] Z. Esik and G. Liu, Fuzzy tree automata, Fuzzy Sets and Systems, 158 (2007), 1450-1460. [10] B. Finkbeiner and H. Sipma, Checking nite traces using alternating automata, Formal Meth- ods in System Design, 24(2) (2004), 101-127. [11] F. Gecseg and M. Steinby, Tree automata, Akademiai Kiado, Budapest, 1984.

[12] M. Ghorani and M. M. Zahedi, Characterization of complete residuated lattice-valued nite tree automata, Fuzzy Sets and Systems, 199 (2012), 28-46. [13] M. Ghorani, M. M. Zahedi and R. Ameri, Algebraic properties of complete residuated lattice- valued tree automata, Soft Computing, 16 (2012), 1723-1732. [14] J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to automata theory, languages and computation, 3rd edition, Addison-Wesley, 2006. [15] H. Hosoya, J. Vouillon and B. C. Pierce, Regular expression types for XML, ACM Transac- tions on Programming Languages and Systems, 27(1) (2005), 46-90. [16] J. Ignjatovic, M. Ciric and S. Bogdanovic, Determinization of fuzzy automata with member- ship values in complete residuated lattices, Information Sciences, 178 (2008), 164-180. [17] J. Jin, Q. Li and Y. Li, Algebraic properties of L-fuzzy nite automata, Information Science, 234 (2013), 182-202. [18] D. Kirsten, Alternating tree automata and parity games, In: E. Gradel (Ed.), Automata, Logics, and Innite Games, Springer-Verlag, Berlin, 2002. [19] R. E. Ladner, R. J. Lipton and L. J. Stockmeyer, Alternating pushdown automata, Proceeding of 19th FOCS, IEEE Computer Society Press, Silver Spring, (1978), 92-106. [20] R. E. Ladner, R. J. Lipton and L. J. Stockmeyer, Alternating pushdown and stack automata, SIAM Journal on Computing, 13 (1984), 135-155. [21] E. T. Lee and L. A. Zadeh, Note on fuzzy languages, Information Sciences, 1 (1969), 421-434. [22] H. X. Lei and Y. Li, Minimization of states in automata theory based on nite lattice-ordered monoids, Information Sciences, 177 (2007), 1413-1421. [23] Y. M. Li and W. Pedrycz, Minimization of lattice nite automata and its application to the decomposition of lattice languages, Fuzzy Sets and Systems, 158(13) (2007), 1423-1436. [24] L. Li and D. Qiu, On the state minimization of fuzzy automata, IEEE Transaction on Fuzzy Systems, 23(3) (2015), 434 - 443. [25] Y. Li and Q. Wang, The universal fuzzy automata, Fuzzy Sets and Systems, 249 (2014), 27-48. [26] F. Lin and H. Ying, Modeling and control of fuzzy discrete event systems, IEEE Trans. Syst., Man, Cybern. B, Cybern., 32 (2002), 408- 415. [27] J. N. Mordeson and D. S. Malik, Fuzzy automata and languages: theory and applications, Chapman & Hall CRC, London, Boca Raton, 2002. [28] E. Moriya, A grammatical characterization of alternating pushdown automata, Theoretical Computer Science, 67 (1989), 75-85. [29] E. Moriya, D. Hofbauer, M. Huber and F. Otto, On state-alternating context-free grammars, Theoretical Computer Science, 337 (2005), 183-216. [30] E. Moriya and F. Otto, Two ways of introducing alternation into context-free grammars and pushdown automata, IEICE Transactions on Information and Systems, E90D(6) (2007), 889-894. [31] E. Moriya and F. Otto, On alternating phrase-structure grammars, In: C. Martin-Vide, F. Otto and H. Fernau (Eds.), Language and Automata Theory and Applications, Springer- Verlag Berlin, Heidelberg, 2008. [32] C. W. Omlin, K. K. Thornber and C. L. Giles, Fuzzy nite-state automata can be determin- istically encoded in recurrent neural networks, IEEE Trans. Fuzzy Syst., 5 (1998), 76-89. [33] W. Pedrycz and A. Gacek, Learning of fuzzy automata, International Journal of Computa- tional Intelligence and Applications, 1 (2001), 19-33. [34] D. W. Qiu, Automata theory based on completed residuated lattice-valued logic (I), Science in China (Series F), 44 (2001), 419{429. [35] D. W. Qiu, Automata theory based on completed residuated lattice-valued logic (II), Science in China (Series F), 45 (2002), 442{452. [36] D. W. Qiu, Characterizations of fuzzy nite automata, Fuzzy Sets and Systems, 141 (2004), 391-414. [37] D. W. Qiu, Supervisory control of fuzzy discrete event systems: a formal approach, IEEE Transactions on Systems, Man and Cybernetics-Part B, 35(1) (2005), 72-88.

[38] D. W. Qiu, Pumping lemma in automata theory based on complete residuated lattice-valued logic: a note, Fuzzy Sets and Systems, 157 (2006), 2128-2138. [39] E. S. Santos, Maximin automata, Inform. and Control, 12 (1968), 367-377. [40] G. Slutzki, Alternating tree automata, In: G. Goos and J. Hartmanis (Eds.), 8th colloquium Laquila Proceeding on Trees in Algebra and Programming, Springer-Verlag, Berlin, 1983. [41] G. Slutzki, Alternating tree automata, Theorical Computer Science, 41 (1985), 305-318. [42] J. Tang, Y. Fang and J. G. Tang, The lattice-valued Turing machines and the lattice-valued type 0 grammars, Mathematical Problems in Engineering, 2014 (2014), 1-6. [43] M. G. Thomason and P. N. Marinos, Deterministic acceptors of regular fuzzy languages, IEEE Trans. Syst., Man, Cybern., 4 (1974), 228-230. [44] M. Y. Vardi, Alternating automata and program verication, In: J. Van Leeuwen (Ed.), Computer Science Today, Recent Trends and Developments, Springer-Verlag, Berlin, 1995. [45] M. Y. Vardi, An automata-theoretic approach to linear temporal logic, In: F. Moller and G. Birtwistle (Eds.): Logics for Concurrency: Structure versus Automata, Springer-Verlag, Berlin, 1996. [46] M. Y. Vardi, Alternating automata: checking truth and validity for temporal logics, Proceding of the 14th Int. Conference on Automated Deduction, Springer-Verlag, Berlin, 1997. [47] K. N. Verma and J. Goubault-Larrecq, Alternating two-way AC-tree automata, Information and Computation, 205 (2007), 817-869. [48] W. G. Wee and K. S. Fu, A formulation of fuzzy automata and its application as a model of learning systems, IEEE Trans. Systems Man Cybern., 5 (1969), 215-223. [49] T. Wilke, Alternating tree automata, parity games, and modal -calculus, Bulletin of the Belgian Mathematical Society-Simon Stevin, 8(2) (2001), 359-391. [50] L. Wu and D. W. Qiu, Automata theory based on completed residuated lattice-valued logic: reduction and minimization, Fuzzy Sets and Systems, 161 (2010), 1635-1656. [51] H. Y. Xing and D. W. Qiu, Pumping lemma in context-free grammar theory based on complete residuated lattice-valued logic, Fuzzy Sets and Systems, 160 (2009), 1141-1151. [52] H. Y. Xing, D. W. Qiu and F. C. Liu, Automata theory based on complete residuated lattice- valued logic: pushdown automata, Fuzzy Sets and Systems, 160 (2009), 1125-1140. [53] H. Y. Xing, D. W. Qiu, F. C. Liu and Z. J. Fan, Equivalence in automata theory based on complete residuated lattice-valued logic, Fuzzy Sets and Systems, 158 (2007), 1407-1422.