Ghorani, M. (2018). TREE AUTOMATA BASED ON COMPLETE RESIDUATED LATTICE-VALUED LOGIC: REDUCTION ALGORITHM AND DECISION PROBLEMS. Iranian Journal of Fuzzy Systems, 15(7), 103-119. doi: 10.22111/ijfs.2018.4288

Maryam Ghorani. "TREE AUTOMATA BASED ON COMPLETE RESIDUATED LATTICE-VALUED LOGIC: REDUCTION ALGORITHM AND DECISION PROBLEMS". Iranian Journal of Fuzzy Systems, 15, 7, 2018, 103-119. doi: 10.22111/ijfs.2018.4288

Ghorani, M. (2018). 'TREE AUTOMATA BASED ON COMPLETE RESIDUATED LATTICE-VALUED LOGIC: REDUCTION ALGORITHM AND DECISION PROBLEMS', Iranian Journal of Fuzzy Systems, 15(7), pp. 103-119. doi: 10.22111/ijfs.2018.4288

Ghorani, M. TREE AUTOMATA BASED ON COMPLETE RESIDUATED LATTICE-VALUED LOGIC: REDUCTION ALGORITHM AND DECISION PROBLEMS. Iranian Journal of Fuzzy Systems, 2018; 15(7): 103-119. doi: 10.22111/ijfs.2018.4288

TREE AUTOMATA BASED ON COMPLETE RESIDUATED LATTICE-VALUED LOGIC: REDUCTION ALGORITHM AND DECISION PROBLEMS

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

Abstract

In this paper, at first we define the concepts of response function and accessible states of a complete residuated lattice-valued (for simplicity we write $\mathcal{L}$-valued) tree automaton with a threshold $c.$ Then, related to these concepts, we prove some lemmas and theorems that are applied in considering some decision problems such as finiteness-value and emptiness-value of recognizable tree languages. Moreover, we propose a reduction algorithm for $\mathcal{L}$-valued tree automata with a threshold $c.$ The goal of reducing an $ \mathcal{L}$-valued tree automaton is to obtain an $\mathcal{L}$-valued tree automaton with reduced number of states %that all of its states are accessible all of which are accessible, in addition it recognizes the same language as the first one given. We compare our algorithm with some other algorithms in the literature. Finally, utilizing the obtained results, we consider some fundamental decision problems for $\mathcal{L}$-valued tree automata including the membership-value, the emptiness-value, the finiteness-value, the intersection-value and the equivalence-value problems.

[1] P. A. Abdulla, L. Holik, L. Kaati and T. Vojnar, A uniform (bi-)simulation-based framework for reducing tree automata, Electronic Notes in Theoretical Computer Science, 251(3) (2009), 27-48. [2] K. H. Abolpour and M. M. Zahedi, Isomorphism between two BL-general fuzzy automata, Soft Computing, 16(4) (2012), 729-736. [3] R. Almeida, Reducing nondeterministic tree automata by adding transitions, In: J. Bouda, L. Holik, J. Kofro~n, J. Strej~cek and A. Rambousek (Eds.), 11th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2016), Telc, Czech Republic, Electronic Proceedings in Theoretical Computer Science, 233 (2016), 35-51. [4] R. Almeida, L. Holik and R. Mayr, Reduction of nondeterministic tree automata, In: M. Chechik and J. Raskin (Eds.), Tools and Algorithms for the Construction and Analysis of Systems, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 9636 (2016), 717-735. [5] G. Birkhoff, Lattice Theory, American Mathematical Society, Providence, 1984. [6] S. Bozapalidis and O. L. Bozapalidoy, Fuzzy term language recognizability, Fuzzy Sets and Systems, 161 (2010), 716-734. [7] I. Chajda and J. Krnavek, Skew residuated lattices, Fuzzy Sets and Systems, 222 (2013), 78-83. [8] W. Cheng and Z. Mo, Minimization algorithm of fuzzy finite automata, Fuzzy Sets and Systems, 141 (2004), 439-448. [9] M. Ciric, A. Stamenkovic, J. Ignjatovic and T. Petkovic, Factorization of fuzzy automata, In: E. Csuhaj-Varju and Z. Esik (eds.), FCT 2007, Lecture Notes in Computer Science, 4639 (2007), 213-225. [10] M. Ciric, A. Stamenkovic, J. Ignjatovic and T. Petkovic, Fuzzy relation equations and reduc- tion of fuzzy automata, Journal of Computer and System Sciences, 76(7) (2010), 609-633. [11] L. C. Ciungu, Classes of residuated lattices, Annals of University of Craiova, Math. Comp. Sci. Ser., 33 (2006), 189-207. [12] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, C. Loding, S. Tison and M. Tommasi, Tree Automata: Techniques and Applications, Available: http://tata.gforge.inria.fr., 2007. [13] A. Degtyarev, Y. U. Gurevich, P. Narendran, M. Veanes and A. Voronkov, Decidability and complexity of simultaneous rigid E-unification with one variable and related results, Theoretical Computer Science, 243 (2000), 167-184. [14] J. E. Doner, Decidability of the weak second-order theory of two successors, Notices Amer. Math. Soc., 12 (1965), 365-468. [15] J. E. Doner, Term acceptors and some of their applications, Journal of Comput. and Syst. Sci., 4 (1970), 406-451. [16] M. Droste, T. Stuber and H. Vogler, Weighted finite automata over strong bimonoids, Inform. Sci., 180(1) (2010), 156-166. [17] M. Droste and H. Vogler, Weighted automata and multi-valued logics over arbitrary bounded lattices, Theoretical Computer Science, 418 (2012), 14-36. [18] Z. Esik and G. Liu, Fuzzy tree automata, Fuzzy Sets and Systems, 158 (2007), 1450-1460.

[19] J. P. Gallagher and G. Puebla, Abstract interpretation over non-deterministic finite tree au- tomata for set-based analysis of logic programs, In: S. Krishnamurthi and C. R. Ramakrishnan (Eds.), Practical Aspects of Declarative Languages, Lecture Notes in Computer Science, 2257 (2002), 243-261. [20] F. Gecseg and M. Steinby, Tree Automata, Akademiai Kiado, Budapest, 1984. [21] M. Ghorani and M. M. Zahedi, Characterizations of complete residuated lattice-valued finite tree automata, Fuzzy Sets and Systems, 199 (2012), 28-46. [22] M. Ghorani and M. M. Zahedi, Alternating regular tree grammars in the framework of lattice- valued logic, Iranian Journal of Fuzzy Systems, 13(2) (2016), 71-94. [23] M. Ghorani and M. M. Zahedi, Coding tree languages based on lattice-valued logic, Soft Computing, 21(14) (2017), 3815-3825. [24] M. Ghorani, M. M. Zahedi and R. Ameri, Algebraic properties of complete residuated lattice- valued tree automata, Soft Computing, 16(10) (2012), 1723-1732. [25] R. Gilleron, S. Tison and M. Tommasi, Solving systems of set constraints using tree automata, Lecture Notes in Computer Science, 665 (1993), 505{514. [26] J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-wesley, New York, 1979. [27] J. Ignjatovic, M. Ciric and S. Bogdanovic, Determinization of fuzzy automata with member- ship values in complete residuated lattices, Information Sciences, 178(1) (2008), 164-180. [28] O. Kupferman and Y. Lustig, Lattice automata, In: B. Cook andA. Podelski (Eds.), Proceedings of the 8th International Conference on Verication, Model Checking, and Abstract Interpretation, VMCAI 2007, Lecture Notes in Comput. Sci., 4349, pp. 199-213, Springer, Berlin, Heidelberg, 2007. [29] K. Lehmann and R. Pe~naloza, The complexity of computing the behaviour of lattice automata on infinite trees, Theoretical Computer Science, 534 (2014), 53-68. [30] H. X. Lei and Y. Li, Minimization of states in automata theory based on finite lattice-ordered monoids, Information Sciences, 177 (2007), 1413-1421. [31] Y. M. Li, Y. L. Li and Z. Y. Ma, Computation tree logic model checking based on possibility measures, Fuzzy Sets and Systems, 262 (2015), 44-59. [32] Y. M. Li and Z. Y. Ma, Quantitative computational tree logic model checking based on gener- alized possibility measures, IEEE Transactions on Fuzzy Systems, 23(6) (2015), 2034-2047. [33] Y. M. Li and W. Pedrycz, Minimization of lattice finite automata and its application to the decomposition of lattice languages, Fuzzy Sets and Systems, 158(13) (2007), 1423-1436. [34] Y. Li and Q. Wang, The universal fuzzy automata, Fuzzy Sets and Systems, 249 (2014), 27-48. [35] S. Moghari and M. M. Zahedi, Minimization of deterministic fuzzy tree automata, Journal of Fuzzy Set Valued Analysis, 2014 (2014), 1-18. [36] S. Moghari and M. M. Zahedi, Similarity-based minimization of fuzzy tree automata, J. Appl. Math. Comput., 50(1) (2016), 417-436. [37] S. Moghari, M. M. Zahedi and R. Amer, New direction in fuzzy tree automata, Iranian Journal of Fuzzy Systems, 8(5) (2011), 59-68. [38] J. N. Mordeson and D. S. Malik, Fuzzy Automata and Languages: Theory and Applications, Chapman & Hall CRC, London, Boca Raton, 2002. [39] P. Y. Pan, Y. M. Li, Y. Z. Cao and Z. Y. Ma, Model checking fuzzy computation tree logic, Fuzzy Sets and Systems, 262 (2015), 60-77. [40] H. Y. Pan, Y. M. Li, Y. Z. Cao and Z. Y. Ma, Model checking computation tree logic over finite lattices, Theoretical Computer Science, 612 (2016), 45-62. [41] J. Pavelka, On fuzzy logic II: enriched residuated lattices and semantics of propositional calculi, Z. Math. Logik Grundlagen Math., 25 (1979), 119-134. [42] D. W. Qiu, Automata theory based on completed residuated lattice-valued logic (I), Science in China (Series F), 44 (2001), 419-429. [43] D. W. Qiu, Automata theory based on completed residuated lattice-valued logic (II), Science in China (Series F), 45 (2002), 442-452.

[44] 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. [45] E. S. Santos, On reduction of maxmin machines, J. Math. Anal. Appl., 37 (1972), 677-686. [46] A. Stamenkovic, M. Ciric and J. Ignjatovic, Reduction of fuzzy automata by means of fuzzy quasi-orders, Information Sciences, 275 (2014), 168-198. [47] J. W. Thatcher and J. B. Wright, Generalized finite automata with an application to a decision problem of second-order logic, Mathematical System Theory, 2 (1968), 57-82. [48] 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. [49] 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. [50] 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.