Fuzzy and Intuitionistic Fuzzy Turing Machines

• Autorzy: Moniri M.
• Języki publikacji: EN

Abstrakty

EN

First we define a new class of fuzzy Turing machines that we call Generalized Fuzzy Turing Machines. Our machines are equipped with rejecting states as well as accepting states. While we use a t-norm for computing degrees of accepting or rejecting paths, we use its dual t-conorm for computing the accepting or rejecting degrees of inputs. We naturally define when a generalized fuzzy Turing machine accepts or decides a fuzzy language. We prove that a fuzzy language L is decidable if and only if L and its complement are acceptable. Moreover, to each r.e. or co-r.e language L, we naturally correspond a fuzzy language which is acceptable by a generalized fuzzy Turing machine. A converse to this result is also proved. We also consider Atanasov’s intuitionistic fuzzy languages and introduce a version of fuzzy Turing machine for studying their computability theoretic properties.

Słowa kluczowe

EN

Theory of Computing; fuzzy language; fuzzy Turing machine; generalized fuzzy; Turing machine; intuitionistic fuzzy Turing machine

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 3
• Strony: 305--315
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Moniri M.

• Department of Mathematics, Shahid Beheshti University G. C., Evin, Tehran, Iran

Bibliografia

• [1] K. Atanassov, Intuitionistic fuzzy sets, Fuzzy Sets and Systems, Vol. 20, (1986) 87-96.
• [2] B. C. Bedregal and S. Figueira, On the computing power of fuzzy Turing machines, Fuzzy Sets and Systems, Vol. 159, (2008) 1072-1083.
• [3] D. van Dalen, Logic and Structure, fourth edition, Springer, 2004.
• [4] J. E. Hopcroft, R. Motwani and J. D. Ullman, 2nd edition, Introduction to Automata Theory, Languages and Computation, Addison Wesley, Reading, MA, 2001.
• [5] P. Hájek, Metamathematics of Fuzzy Logic, Kluwer, 1998.
• [6] Yongming Li, Fuzzy Turing machines: variants and universality, IEEE Transactions on Fuzzy Systems, Vol. 16, No. 6, (2008) 1491-1502.
• [7] Yongming Li, Lattice-valued fuzzy Turing machines: Computing power, universality and efficiency, Fuzzy Sets and Systems, Vol. 160, 2009, 3453-3474.
• [8] Xiaowei Zhang and Yongming Li, Intuitionistic fuzzy recognizers and intuitionistic fuzzy automata, Soft Computing, Vol. 13, 2009, 611-616.
• [9] M. Moniri and A. Sadeghian, Intuitionistic fuzzy Turing machines, Unpublished.
• [10] E. T. Lee and L. A. Zadeh, Note on fuzzy languages, Information Sciences, Vol. 4, (1969) 421-434.
• [11] H. T. Nguyen and E. A. Walker, A First Course in Fuzzy Logic, Third Edition, Chapman and Hall/CRC, 2006.
• [12] E. Santos, Fuzzy algorithms, Information and Control, Vol. 17, (1970) 326-339.
• [13] E. Santos, Fuzzy and probablistic programs, Information Sciences, Vol. 10, (1976) 331-335.
• [14] J. Wiedermann, Charactrizing the super-Turing power and efficiency of classical fuzzy Turing machines, Theoretical Computer Science, Vol. 317, (2004) 61-69.
• [15] L. A. Zadeh, Fuzzy algorithms, Information and Control, Vol. 2, (1968) 94-102.