Alternating Regular Tree Grammars in the Framework of Lattice-Valued Logic

[1] A. Bouhoula, J. P. Jouannaud and J. Meseguer, Specication 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 Innite 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 verication, 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.