Top

Soft Computing

Published in:

14-09-2017 | Methodologies and Application

On characterization of fuzzy tree pushdown automata

Author: M. Ghorani

Published in: Soft Computing | Issue 4/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper introduces the concepts of fuzzy tree pushdown automata and fuzzy context-free tree grammars. At first, we show that any fuzzy context-free tree grammar can be converted into a corresponding definition of fuzzy Chomsky normal form for trees. Then, the relation between a fuzzy context-free tree grammar and a fuzzy tree pushdown automaton is investigated. In fact, we show that the class of languages accepted by fuzzy tree pushdown automata is identical to the one generated by fuzzy context-free tree grammars. Some examples are given to clarify the results.

previous article Sorting of decision-making methods based on their outcomes using dominance-vector hesitant fuzzy-based distance

next article BIAM: a new bio-inspired analysis methodology for digital ecosystems based on a scale-free architecture

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Abolpour KH, Zahedi MM (2012) Isomorphism between two BL-general fuzzy automata. Soft Comput 16(4):729–736CrossRefMATH

Bozapalidis S, Bozapalidoy OL (2010) Fuzzy tree language recognizability. Fuzzy Sets Syst 161:716–734MathSciNetCrossRefMATH

Brainerd WS (1969) Tree generating regular systems. Inf Control 14:217–231MathSciNetCrossRefMATH

Chaudhari SR, Joshi MN (2012) A note on fuzzy tree automata. Int J Comput Appl 56(17):1–5

Chomsky N (1959) On certain formal properties of grammars. Inf control 2:137–167MathSciNetCrossRefMATH

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

Doner JE (1970) Tree acceptors and some of their applications. J Comput Syst Sci 4:406–451MathSciNetCrossRefMATH

Doostfatemeh M, Kremer SC (2005) New directions in fuzzy automata. Int J Approx Reason 38:175–214MathSciNetCrossRefMATH

Drewes F (2006) Grammatical picture generation. A tree-based approach, texts in theoretical computer science, an EATCS series. Springer, Berlin

Ésik Z, Liu G (2007) Fuzzy tree automata. Fuzzy Sets Syst 158:1450–1460MathSciNetCrossRefMATH

Ghorani M, Zahedi MM (2012) Characterizations of complete residuated lattice-valued finite tree automata. Fuzzy Sets Syst 199:28–46MathSciNetCrossRefMATH

Ghorani M, Zahedi MM (2016) Alternating regular tree grammars in the framework of lattice-valued logic. Iran J Fuzzy Syst 13(2):71–94MathSciNetMATH

Ghorani M, Zahedi MM (2017) Coding tree languages based on lattice valued logic. Soft Comput 21(14):3815–3825

Ghorani M, Zahedi MM, Ameri R (2012) Algebraic properties of complete residuated lattice valued tree automata. Soft Comput 16(10):1723–1732CrossRefMATH

Gilleron R, Tison S, Tommasi M (1993) Solving systems of set constraints using tree automata. Lect Notes Comput Sci 665:505–514MathSciNetCrossRefMATH

Ignjatovic J, Ćirić M, Bogdanovic S (2008) Determinization of fuzzy automata with membership values in complete residuated lattices. Inf Sci 178:164–180MathSciNetCrossRefMATH

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, Proceedings of U.S. Japan Seminar, University of California, Berkeley, CA, 1974, Academic Press, New York, pp. 301–328

Lan S (1992) A machine accepted fuzzy context-free languages-fuzzy pushdown automata. BUSEFAL 49:67–72

Lee ET, Zadeh LA (1969) Note on fuzzy languages. Inf Sci 1:421–434MathSciNetCrossRef

Li Y (2011) Finite automata theory with membership values in lattices. Inf Sci 181(5):1003–1017MathSciNetCrossRefMATH

Li YM, Ma ZY (2015) Quantitative computational tree logic model checking based on generalized possibility measures. IEEE Trans Fuzzy Syst 23(6):2034–2047CrossRef

Li L, Qiu D (2015) On the state minimization of fuzzy automata. IEEE Trans Fuzzy Syst 23(2):434–443CrossRef

Li YM, Li YL, Ma ZY (2015) Computation tree logic model checking based on possibility measures. Fuzzy Sets Syst 262:44–59MathSciNetCrossRefMATH

Mezei J, Wright JB (1967) Algebraic automata and context-free sets. Inf Control 11:3–29MathSciNetCrossRefMATH

Moghari S, Zahedi MM, Ameri R (2011) New direction in fuzzy tree automata. Iran J Fuzzy Syst 8(5):59–68MathSciNetMATH

Mordeson JN, Malik DS (2002) Fuzzy automata and languages: theory and applications. Chapman & Hall CRC, LondonCrossRefMATH

Nidhi K, Ajay K (2016) Fuzzy state grammar and fuzzy deep pushdown automaton. J Intell Fuzzy Syst 31(1):249–258CrossRefMATH

Pan PY, Li YM, Cao YZ, Ma ZY (2015) Model checking fuzzy computation tree logic. Fuzzy Sets Syst 262:60–77

Pan HY, Li YM, Cao YZ, Ma ZY (2016) Model checking computation tree logic over finite lattices. Theor Comput Sci 612:45–62MathSciNetCrossRefMATH

Qiu DW (2004) Characterizations of fuzzy finite automata. Fuzzy Sets Syst 141:391–414MathSciNetCrossRefMATH

Salomaa K (1988) Deterministic tree pushdown automata and monadic tree rewriting systems. J Comput Syst Sci 37(3):367–394MathSciNetCrossRefMATH

Santos ES (1968) Maximin automata. Inf Control 12:367–377MathSciNetCrossRefMATH

Santos ES (1972) On reduction of maxmin machines. J Math Anal Appl 37:677–686MathSciNetCrossRef

Schimpf KM (1982) A parsing method for context-free tree languages. Ph.D. dissertation, University of Pennsylvania, Philadelphia, PA

Schimpf KM, Gallier JH (1985) Tree pushdown automata. J Comput Syst Sci 30(1):25–40MathSciNetCrossRefMATH

Schwentick T (2007) Automata for XMLA survey. J Comput Syst Sci 73(3):289–315MathSciNetCrossRefMATH

Shamsizadeh M, Zahedi MM (2016) Intuitionistic general fuzzy automata. Soft Comput 20(9):3505–3519CrossRefMATH

Thatcher JW, Wright JB (1968) Generalized finite automata theory with an application to a decision-problem of second order logic. Math Syst Theory 2:57–81MathSciNetCrossRefMATH

Thomason MG, Marinos PN (1974) Deterministic acceptors of regular fuzzy languages. IEEE Trans Syst Man Cybern 4:228–230MathSciNetCrossRefMATH

Wang J, Yin M, Gu W (2013) Fuzzy multiset finite automata and their languages. Soft Comput 17(3):381–390CrossRefMATH

Wee WG, Fu KS (1969) A formulation of fuzzy automata and its application as a model of learning systems. IEEE Trans Syst Man Cybern 5:215–223MATH

Xing HY (2007) Fuzzy pushdown automata. Fuzzy Sets Syst 158(13):1437–1449MathSciNetCrossRefMATH

Xing HY, Qiu DW (2009) Pumping lemma in context-free grammar theory based on complete residuated lattice-valued logic. Fuzzy Sets Syst 160(8):1141–1151MathSciNetCrossRefMATH

Xing HY, Qiu DW, Liu FC (2009) Automata theory based on complete residuated lattice-valued logic: pushdown automata. Fuzzy Sets Syst 160(8):1125–1140MathSciNetCrossRefMATH

Zhang X, Li Y (2009) Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata. Soft Comput 13(6):611–616CrossRefMATH

Title: On characterization of fuzzy tree pushdown automata
Author: M. Ghorani
Publication date: 14-09-2017
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 4/2019
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-017-2829-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2019

A bi-objective fleet size and mix green inventory routing problem, model and solution method

Mining stock category association on Tehran stock market

A genetic algorithm approach to the smart grid tariff design problem

A Gould-type integral of fuzzy functions II

CCODM: conditional co-occurrence degree matrix document representation method

Sorting of decision-making methods based on their outcomes using dominance-vector hesitant fuzzy-based distance

Premium Partner