×

Algebraic properties of complete residuated lattice valued tree automata. (English) Zbl 1290.68074

Summary: This paper investigates tree automata based on complete residuated lattice valued (referred to as \(L\)-valued) logic. First, we define the notions of \(L\)-valued set of pure subsystems and \(L\)-valued set of strong pure subsystems, as well as, their relation is considered. Also, \(L\)-valued \(n\)-tuple operator consist of \(n\) successors is defined, some of its properties are examined and its relation with pure subsystem is analyzed. Furthermore, we investigate some concepts such as \(L\)-valued set of (strong) homomorphisms, \(L\)-valued set of (strong) isomorphisms, and \(L\)-valued set of admissible relations. Moreover, we discuss bifuzzy topological characterization of \(L\)-valued tree automata. Finally, the relations of homomorphisms between the \(L\)-valued tree automata to continuous mappings and open mappings is examined.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abolpour KH, Zahedi MM (2012) Isomorphism between two BL-general fuzzy automata. Soft Comput 16:729–736 · Zbl 1259.68136 · doi:10.1007/s00500-011-0782-4
[2] Bozapalidis S, Bozapalidoy OL (2010) Fuzzy tree language recognizability. Fuzzy Sets Syst 161:716–734 · Zbl 1184.68308 · doi:10.1016/j.fss.2009.08.008
[3] Comon H, Dauchet M, Gilleron R, Jacquemard F, Lugiez D, Loding C, Tison S, Tommasi M (2007) Tree automata: techniques and applications. http://tata.gforge.inria.fr
[4] Degtyarev A, Gurevich YU, Narendran P, Veanes M, Voronkov A (2000) Decidability and complexity of simultaneous rigid E-unification with one variable and related results. Theor Comput Sci 243:167–184 · Zbl 0944.68103 · doi:10.1016/S0304-3975(98)00185-6
[5] Doner JE (1965) Decidability of the weak second-order theory of two successors. Not Am Math Soc 12:365–468
[6] Doner JE (1970) Tree acceptors and some of their applications. J Comput Syst Sci 4:406–451 · Zbl 0212.02901 · doi:10.1016/S0022-0000(70)80041-1
[7] Esik Z, Liu G (2007) Fuzzy tree automata. Fuzzy Sets Syst 158:1450–1460 · Zbl 1123.68057 · doi:10.1016/j.fss.2007.02.016
[8] Inagaki Y, Fukumura T (1975) On the description of fuzzy meaning of context-free language. In: Fuzzy sets and their applications to cognitive and decision processes. Proc. U.S. Japan Seminar, University of California, Berkeley, CA, 1974, Academic Press, New York, pp 301–328
[9] Gallagher JP, Puebla G (2002) Abstract interpretation over non-deterministic finite tree automata for set-based analysis of logic programs. In: PADL 2002, pp 243–261
[10] Gecseg F, Steinby M (1984) Tree automata. Akademiai Kiado, Budapest
[11] Ghorani M, Zahedi MM (2011) Characterizations of complete residuated lattice-valued finite tree automata. Fuzzy Sets Syst 199:28–46 · Zbl 1253.68203 · doi:10.1016/j.fss.2011.11.010
[12] Gilleron R, Tison S, Tommasi M (1993) Solving systems of set constraints using tree automata. Lect Notes Comput Sci 665:505–514 · Zbl 0797.68115 · doi:10.1007/3-540-56503-5_50
[13] Gori M, Petrosino A (2004) Encoding nondeterministic fuzzy tree automata into recursive neural networks. IEEE Trans Neural Netw 156(6):1435–1449 · doi:10.1109/TNN.2004.837585
[14] Hopcroft JE, Motwani R, Ullman JD (1979) Introduction to automata theory, languages and computation. Addison-Wesley, New york
[15] Lee ET (1982) Fuzzy tree automata and syntactic pattern recognition. IEEE Transactions On Pattern Analysis And Machine Intelligence PAMI-4:445–449 · Zbl 0483.68076
[16] Lei HX, Li Y (2007) Minimization of states in automata theory based on finite lattice-ordered monoids. Inf Sci 177:1413–1421 · Zbl 1109.68058 · doi:10.1016/j.ins.2006.07.015
[17] Li YM, Pedrycz W (2007) Minimization of lattice finite automata and its application to the decomposition of lattice languages. Fuzzy Sets Syst 158(13):1423–1436 · Zbl 1123.68063 · doi:10.1016/j.fss.2007.03.003
[18] Lu X, Shang Y, Lu R (2011) Automata theory based on lattice-ordered semirings. Soft Comput 15:269–280 · Zbl 1237.68116 · doi:10.1007/s00500-010-0565-3
[19] Malik DS, Mordeson JN (2000) Fuzzy discrete structures. Physica-Verlag, New York
[20] Mockor J (2002) Semigroup homomorphisms and fuzzy automata. Soft Comput 6:422–427 · Zbl 1039.68080 · doi:10.1007/s005000100156
[21] Moghari S, Zahedi MM, Ameri R (2011) New direction in fuzzy tree automata. Iran J Fuzzy Syst 8(5):59–68 · Zbl 1260.68210
[22] Mordeson JN, Malik DS (2002) Fuzzy automata and languages: theory and applications. Chapman & Hall CRC, London, BocaRaton
[23] Pavelka J (1979) On fuzzy logic I: many-valued rules of inferences. Z Math Logik Grundlagen Math 25:45–52 · Zbl 0435.03020 · doi:10.1002/malq.19790250304
[24] Pavelka J (1979) On fuzzy logic II: enriched residuated lattices and semantics of propositional calculi. Z Math Logik Grundlagen Math 25:119–134 · Zbl 0446.03015 · doi:10.1002/malq.19790250706
[25] Pavelka J (1979) On fuzzy logic III: semantical completeness of some many-valued propositional calculi. Z Math Logik Grundlagen Math 25:447–464 · Zbl 0446.03016 · doi:10.1002/malq.19790252510
[26] Qiu DW (2001) Automata theory based on completed residuated lattice-valued logic (I). Sci China Ser F 44(6):419–429
[27] Qiu DW (2002) Automata theory based on completed residuated lattice-valued logic (II). Sci China Ser F 45(6):442–452 · Zbl 1161.68549
[28] Qiu DW (2004) Characterizations of fuzzy finite automata. Fuzzy Sets Syst 141:391–414 · Zbl 1059.68069 · doi:10.1016/S0165-0114(03)00202-1
[29] Qiu DW (2006) Pumping lemma in automata theory based on complete residuated lattice- valued logic: a note. Fuzzy Sets Syst 157:2128–2138 · Zbl 1121.03048 · doi:10.1016/j.fss.2006.03.014
[30] Qiu DW (2007) A note on Trillas CHC models. Artif Intell 171:239–254 · Zbl 1168.06302 · doi:10.1016/j.artint.2006.12.002
[31] Thatcher JW, Wright JB (1968) Generalized finite automata with an application to a decision problem of second-order logic. Math Syst Theory 2:57–82 · Zbl 0196.01901 · doi:10.1007/BF01691346
[32] Shang Y, Lu R (2007) Semirings and pseudo MV algebras. Soft Comput 11:847–853 · Zbl 1124.06006 · doi:10.1007/s00500-006-0136-9
[33] Wu L, Qiu DW (2010) Automata theory based on completed residuated lattice-valued logic: reduction and minimization. Fuzzy Sets Syst 161:1635–1656 · Zbl 1192.68426 · doi:10.1016/j.fss.2009.12.011
[34] Xing HY, Qiu DW, Liu FC (2009) Automata theory based on complete residuated lattice-valued logic: pushdown automata. Fuzzy Sets Syst 160:1125–1140 · Zbl 1182.68108 · doi:10.1016/j.fss.2008.07.010
[35] Xing HY, Qiu DW, Liu FC, Fan ZJ (2007) Equivalence in automata theory based on complete residuated lattice-valued logic. Fuzzy Sets Syst 158:1407–1422 · Zbl 1152.68463 · doi:10.1016/j.fss.2007.01.008
[36] Xing HY, Qiu DW (2009) Pumping lemma in context-free grammar theory based on complete residuated lattice-valued logic. Fuzzy Sets Syst 160:1141–1151 · Zbl 1187.68305 · doi:10.1016/j.fss.2008.06.016
[37] Ying MS (1991) A new approach for fuzzy topology (I). Fuzzy Sets Syst 39:303–321 · Zbl 0718.54017 · doi:10.1016/0165-0114(91)90100-5
[38] Ying MS (1992) A new approach for fuzzy topology (II). Fuzzy Sets Syst 47:221–232 · Zbl 0752.54002 · doi:10.1016/0165-0114(92)90181-3
[39] Ying MS (1993) A new approach for fuzzy topology (III). Fuzzy Sets Syst 55:193–207 · Zbl 0785.54013 · doi:10.1016/0165-0114(93)90132-2
[40] Ying MS (1993) Fuzzifying topology based on complete residuated lattice valued logic (I). Fuzzy Sets Syst 56:337–373 · Zbl 0787.54010 · doi:10.1016/0165-0114(93)90215-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.