Different models of automata with fuzzy states

Aleksandar Stamenković, Miroslav Ćirić, Jelena Ignjatović

DOI Number
-
First page
235
Last page
253

Abstract


In this paper we provide a general definition of automata with fuzzy stateswhich includes as its special cases automata used by Lin et al. [29], Liu and Qiu [30,31,42]and Xing et al. [56] in the study of fuzzy discrete event systems, as well as various typesof automata constructed in [14,15,18,32] for the purpose of the determinization of fuzzyautomata. We explain the relationships between these differentmodels of automata withfuzzy states and showthat every crisp-deterministic fuzzy automaton can be transformedinto a language-equivalent automaton with fuzzy states, and vice versa.

Keywords


fuzzy automaton, fuzzy language, crisp-deterministic fuzzy automaton, automaton with fuzzy states, Nerode automaton, derivative automaton, prefix-closure, fuzzy relation equation

Full Text:

PDF

References


R. Belohlavek, Fuzzy Relational Systems: Foundations and Principles. Kluwer, New York, 2002.

R. Belohlavek, Determinism and fuzzy automata. Information Sciences 143 (2002), 205–209.

R. Belohlavek and V. Vychodil, Fuzzy Equational Logic. Studies in Fuzziness and Soft Computing, Springer, Berlin-Heidelberg, 2005.

M. Ćirić, M. Droste, J. Ignjatović and H. Vogler, Determinization of weighted finite automata over strong bimonoids. Information Sciences 180 (2010), 3497–3520.

M. Ćirić, J. Ignjatović, N. Damljanović and M. Bašić, Bisimulations for fuzzy automata, Fuzzy Sets and Systems 186 (2012), 100–139.

M. Ćirić, J. Ignjatović, I. Jančić and N. Damljanović, Computation of the greatest simulations and bisimulations between fuzzy automata, Fuzzy Sets and Systems 208 (2012), 22–42.

M. Ćirić, A. Stamenković, J. Ignjatović and T. Petković, Factorization of fuzzy automata, In: Csuhaj-Varju, E., Esik, Z. (eds.), FCT 2007, Springer, Heidelberg, Lecture Notes in Computer Science 4639 (2007), 213–225.

M. Ćirić, A. Stamenković, J. Ignjatović and T. Petković, Fuzzy relation equations and reduction of fuzzy automata, Journal of Computer and SystemSciences 76 (2010), 609–633.

M. Droste, T. Stuber and H. Vogler, Weighted finite automata over strong bimonoids, Information Sciences 180 (2010), 156–166.

M. Droste and H. Vogler, Kleene and Buchi results for weighted automata and multi-valued logics over arbitrary bounded lattices, in: Y. Gao et al. (eds.), DLT 2010, Lecture Notes in Computer Science, 6224, 2010, pp. 160–172.

D. Dubois and H. Prade, Fuzzy Sets and Systems: Theory and Applications, Academic Press, New York, 1980.

M. M. Gupta, G. N. Saridis and B. R. Gaines, Fuzzy Automata and Decision Processes, North-Holland, New York, 1977.

J. Ignjatović and M. Ćirić, Formal power series and regular operations on fuzzy languages. Information Sciences 180 (2010), 1104–1120.

J. Ignjatović, M. Ćirić and S. Bogdanović, Determinization of fuzzy automata with membership values in complete residuated lattices. Information Sciences 178 (2008), 164–180.

J. Ignjatović, M. Ćirić, S. Bogdanović and T. Petković, Myhill-Nerode type theory for fuzzy languages and automata. Fuzzy Sets and Systems 161 (2010), 1288-1324.

Z. Jančić and M. Ćirić, Brzozowski type determinization for fuzzy automata. Fuzzy Sets and Systems 249 (2014), 73–82.

Z. Jančić, J. Ignjatović andM. Ćirić, An improved algorithm for determinization of weighted and fuzzy automata. Information Sciences 181 (2011), 1358–1368.

Z. Jančić, I. Micić, J. Ignjatović and M. Ćirić, Further improvements of determinization

methods for fuzzy finite automata. Fuzzy Sets and Systems, submitted for publication

(http://arxiv.org/pdf/1402.6510v3).

G. J. Klir and B. Yuan, Fuzzy Sets and Fuzzy Logic, Theory and Application, Prentice-Hall, Englevood Cliffs, NJ, 1995.

S. Konstantinidis, N. Santean and S. Yu, Fuzzification of rational and recognizable sets,

Fundamenta Informaticae 76 (2007), 413–447.

O. Kupferman and Y. Lustig, Lattice automata, in: Proceedings of VWCAI2007, Lecture

Notes in Computer Science 4349 (2007), pp. 199–213.

E. T. Lee and L.A. Zadeh,Note on fuzzy languages, Information Sciences 1 (1969), 421–434.

H. Lei and Y. M. Li, Minimization of states in automata theory based on finite lattice-ordered monoids, Information Sciences 177 (2007), 1413–1421.

P. Li and Y. M. Li, Algebraic properties of LA-languages, Information Sciences 176 (2006), 3232–3255.

Y.M. Li, Finite automata theory with membership values in lattices, Information Sciences 181 (2011), 1003–1017.

Y.M. Li and W. Pedrycz, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice ordered monoids. Fuzzy Sets and Systems 156 (2005), 68–92.

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 (2007), 1423–1436.

Z. Li, P. Li and Y.M. Li, The relationships among several types of fuzzy automata, Information Sciences 176 (2006), 2208–2226.

F. Lin, H. Ying, R.D.MacArthur, J. A. Cohn, D. Barth-Jones and L. R. Crane, Decision

making in fuzzy discrete event systems. Information Sciences 177 (2007), 3749–3763.

F. Liu and D.Qiu, Decentralized supervisory control of fuzzy discrete event systems. European Journal of Control 3 (2008), 234–243.

F. Liu and D. Qiu, Diagnosability of fuzzy discrete-event systems: A fuzzy approach. IEEE Transactions on Fuzzy Systems 17 (2) (2009), 372–384.

I.Micić, Z. Jančić, J. Ignjatović and M. Ćirić, Determinization of fuzzy automata by means of the degrees of language inclusion. IEEE Transactions on Fuzzy Systems, accepted for publication (http://arxiv.org/pdf/1410.6063).

J. N.Mordeson and D. S.Malik, Fuzzy Automata and Languages: Theory and Applications, Chapman & Hall/CRC, Boca Raton, London, 2002.

K. Peeva, Finite L-fuzzy acceptors, regular L-fuzzy grammars and syntactic pattern recognition, International Journal ofUncertainty, Fuzziness andKnowledge-BasedSystems 12 (2004), 89–104.

K. Peeva, Finite L-fuzzy machines, Fuzzy Sets and Systems 141 (2004), 415–437.

K. Peeva and Y. Kyosev, Fuzzy Relational Calculus: Theory, Applications, and Software (with CD-ROM), in Series “Advances in Fuzzy Systems – Applications and Theory”, Vol 22,

World Scientific, 2004.

K. Peeva and Z. Zahariev, Computing behavior of finite fuzzy machines – Algorithm and its application to reduction and minimization, Information Sciences 178 (2008), 4152–4165.

D. W. Qiu, Automata theory based on completed residuated lattice-valued logic (I), Science in China, Ser. F, 44 (6) (2001), 419–429.

D.W. Qiu, Automata theory based on completed residuated lattice-valued logic (II), Science in China, Ser. F, 45 (6) (2002), 442–452.

D. W. Qiu, Characterizations of fuzzy finite automata, Fuzzy Sets and Systems 141 (2004), 391–414.

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.

D. Qiu and F. Liu, Fuzzy discrete-event systems under fuzzy observability and a test algorithm. IEEE Transactions on Fuzzy Systems 17 (3) (2009) 578–589.

E. S. Santos, Maximin automata, Information and Control 12 (1968), 367–377.

E. S. Santos, On reduction of maxmin machines, Journal of Mathematical Analysis and

Applications 37 (1972), 677–686.

E. S. Santos, Fuzzy automata and languages, Information Sciences 10 (1976), 193–197.

A. Stamenković and M. Ćirić, Construction of fuzzy automata fromfuzzy regular expressions, Fuzzy Sets and Systems 199 (2012), 1–27.

A. Stamenković, M. Ćirić and J. Ignjatović, Reduction of fuzzy automata by means of fuzzy quasi-orders, Information Sciences 275 (2014), 168–198.

W.Wechler, The Concept of Fuzziness inAutomata and Language Theory, Akademie-Verlag, Berlin, 1978.

W. G. Wee, On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification, Ph.D. Thesis, Purdue University, 1967.

W. G. Wee and K. S. Fu, A formulation of fuzzy automata and its application as a model of learning systems, IEEE Transactions on Systems, Man and Cybernetics 5 (1969), 215–223.

L. H. Wu and D. W. Qiu, Automata theory based on complete residuated lattice-valued logic: Reduction and minimization, Fuzzy Sets and Systems 161 (2010), 1635–1656.

H. 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.

H. Xing and D.W. Qiu, Automata theory based on complete residuated lattice-valued logic: A categorical approach, Fuzzy Sets and Systems 160 (2009), 2416–2428.

H. 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.

H. 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.

H. Xing, Q. Zhang and K. Huang, Analysis and control of fuzzy discrete event systems using bisimulation equivalence, Theoretical Computer Science 456 (2012), 100–111.


Refbacks

  • There are currently no refbacks.




© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)