On the complexity of Turing machine accepting fuzzy language

Author

Pan Yingjun ; Zou Tie

Author_Institution

Key Lab. of Opto-Electron. Technol. & Syst., ChongQing Univ., Chongqing, China

fYear

2012

fDate

29-31 May 2012

Firstpage

112

Lastpage

116

Abstract

Based on the definition of single-tape Fuzzy Non-deterministic Turing Machine (FNTM), this article discussed in details the process of FNTM accepting language and researched the computational complexity of fuzzy Turing Machine (TM) accepting λ-cut language by using the Deterministic Turing Machine (DTM) to simulate its process, thus drawing the conclusion that the judgment of FNTM accepting λ-cut language is a matter of the NP-completeness, and that it is not essentially helpful to adjust the membership degree in facing the time complexity problem when simulating the process of FNTM accepting the language.

Keywords

Turing machines; computational complexity; computational linguistics; fuzzy systems; λ-cut language; NP-completeness; Turing machine complexity; deterministic Turing machine; fuzzy language; single-tape fuzzy nondeterministic Turing machine; Computational complexity; Computational modeling; Computers; Magnetic heads; Polynomials; Turing machines; λ-cut language; Fuzzy Turing Machine; Fuzzy language; Fuzzy relations; Fuzzy system models; NP-completeness;

fLanguage

English

Publisher

ieee

Conference_Titel

Fuzzy Systems and Knowledge Discovery (FSKD), 2012 9th International Conference on

Conference_Location

Sichuan

Print_ISBN

978-1-4673-0025-4

Type

conf

DOI

10.1109/FSKD.2012.6233747

Filename

6233747