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

Document Type: Research Paper

Author

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.

Keywords

References

[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. Ignjatovic and T. Petkovic, 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. Stamenkovic, J. Ignjatovic and T. Petkovic, 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-unifi cation 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. Stuber and H. Vogler, Weighted fi nite 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 fi nite 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 fi nite
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. Ignjatovic, M. Ciric and S. Bogdanovic, 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 Veri cation, 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 in finite 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 fi nite 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 fi nite 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.