DISTINGUISHABILITY AND COMPLETENESS OF CRISP DETERMINISTIC FUZZY AUTOMATA

Document Type: Research Paper

Authors

1 Indian School of Mines, Dhanbad, India

2 Department of Applied Mathematics, Indian Institute of Technology (ISM), Dhanbad-826004, India

Abstract

In this paper, we introduce and study notions like state-\\linebreak distinguishability, input-distinguishability and output completeness of states of a crisp deterministic fuzzy automaton. We show that for each crisp deterministic fuzzy automaton there corresponds a unique (up to isomorphism), equivalent distinguished crisp deterministic fuzzy automaton. Finally, we introduce two axioms related to output completeness of states and discuss the interrelationship between them.

Keywords


[1] Z. Bavel, Structure and transition preserving functions of nite automata, Journal of Asso-
ciation for Computing machinery, 15 (1968), 135{158.
[2] Y. Cao and Y. Ezawa, Nondeterministic fuzzy automata, Information Sciences, 191 (2012),
86{97.
[3] M.  Ciric and J. Ignjatovic, Fuzziness in automata theory: why? how?, Studies in Fuzziness
and Soft Computing, 298 (2013), 109{114.
[4] M. Doostfatemeh and S. C. Kremer, New directions in fuzzy automata, International Journal
of Approximate Reasoning, 38 (2005), 175{214.
[5] S. Ginsburg, Some remark on abstract automata, Transactions of the American Mathematical
Society, 96 (1960), 400{444.
[6] X. Guo, Grammar theory based on lattice-order monoid, Fuzzy Sets and Systems, 160 (2009),
1152{1161.
[7] W. M. L. Holcombe, Algebraic automata theory, Cambridge University Press, Cambridge,
1982.
[8] J. Ignjatovic, M. Ciric and S. Bogdanovic, Determinization of fuzzy automata with member-
ship values in complete residuated lattices, Information Sciences, 178 (2008), 164{180.
[9] J. Ignjatovic, M. Ciric, S. Bogdanovic and T. Petkovic, Myhill-Nerode type theory for fuzzy
languages and automata, Fuzzy Sets and Systems, 161 (2010), 1288{1324.
[10] M. Ito, Algebraic structures of automata, Theoretical Computer Science, 429 (2012), 164{
168.
[11] J. Jin, Q. Li and Y. Li, Algebraic properties of L-fuzzy nite automata, Information Sciences,
234 (2013), 182{202.
[12] Y. B. Jun, Intuitionistic fuzzy nite state automata, Journal of Applied Mathematics and
Computing, 17 (2005), 109{120.
[13] Y. B. Jun, Intuitionistic fuzzy nite switchboard state automata, Journal of Applied Mathe-
matics and Computing, 20 (2006), 315{325.
[14] Y. B. Jun, Quotient structures of intuitionistic fuzzy nite state automata, Information Sci-
ences, 177 (2007), 4977{4986.
[15] Y. H. Kim, J. G. Kim and S. J. Cho, Products of T-generalized state automata and T-
generalized transformation semigroups, Fuzzy Sets and Systems, 93 (1998), 87{97.
[16] H. V. Kumbhojkar and S. R. Chaudhari, On proper fuzzi cation of fuzzy nite state automata,
International Journal of Fuzzy Mathematics, 4 (2008), 1019{1027.
[17] Y. Li and W. Pedrycz, Fuzzy nite automata and fuzzy regular expressions with membership
values in lattice-ordered monoids, Fuzzy Sets and Systems, 156 (2005), 68{92.
[18] Y. Li and W. Pedrycz, The equivalence between fuzzy Mealy and fuzzy Moore automata, Soft
Computing, 10 (2006), 953{959.

[19] Y. Li and Q. Wang, The universal fuzzy automaton, Fuzzy Sets and Systems, 249 (2014),
27{48.
[20] D. S. Malik, J. N. Mordeson and M. K. Sen, Subautomata of fuzzy nite state automaton,
Journal of Fuzzy Mathematics, 2 (1994), 781{792.
[21] J. N. Mordeson and D. S. Malik, Fuzzy automata and languages: Theory and Applications,
Chapman and Hall/CRC. London/Boca Raton, 2002.
[22] K. Peeva and Zl. Zahariev, Computing behavior of nite fuzzy automata-algorithm and its
application to reduction and minimization, Information Sciences, 178 (2008), 4152{4165.
[23] D. Qiu, Automata theory based on complete residuated lattice-valued logic (I), Science in
China, 44 (2001), 419{429.
[24] D. Qiu, Automata theory based on complete residuated lattice-valued logic (II), Science in
China, 45 (2002), 442{452.
[25] E. S. Santos, General formulation of sequential automata, Information and control, 12 (1968),
5{10.
[26] W. Shukla and A. K. Srivastava, A topology for automata: A note, Information and Control,
32 (1976), 163{168.
[27] A. K. Srivastava and W. Shukla, A topology for automata II, International Journal of Math-
ematics and Mathematical Sciences, 9 (1986), 425{428.
[28] S. P. Tiwari and S. Sharan, Fuzzy automata based on lattice-ordered monoid with algebraic
and topological aspects, Fuzzy Information and Engineering, 4 (2012), 155{164.
[29] S. P. Tiwari and A. K. Singh, On minimal realization of fuzzy behavior and associated cate-
gories, Journal of Applied Mathematics and Computing, 45 (2014), 223{234.
[30] S. P. Tiwari, A. K. Singh and S. Sharan, Fuzzy subsystems of fuzzy automata based on lattice
ordered monoid, Annals of Fuzzy Mathematics and Informatics, 7 (2013), 437{445.
[31] S. P. Tiwari, A. K. Singh, S. Sharan and V. K. Yadav, Bifuzzy core of fuzzy automata, Iranian
Journal of Fuzzy Systems, 12 (2015), 63{73.
[32] D. Todinca and D. Butoianu, VHDL framework for modeling fuzzy automata, in: Proc. 14th
International Symposium on Symbolic and Numeric Algorithms for Scienti c Computing,
IEEE, (2012), 171{178.