automata theory based on complete residuated lattice-valued logic: turing machines
文献类型：期刊论文
| 作者 | Wu Lihua ; Qiu Daowen ; Xing Hongyan |
| 刊名 | Fuzzy Sets and Systems
 |
| 出版日期 | 2012 |
| 卷号 | 208页码:43-66 |
| ISSN号 | 1650114 |
| 英文摘要 | Automata theory based on complete residuated lattice-valued logic, called L-valued finite automata (L-VFAs), has been established by the second author in 2001. In view of the importance of Turing machines, in this paper, we establish a theory of Turing machines based on complete residuated lattice-valued logic, which is a continuation of L-VFAs. First, we give the definition of L-valued nondeterministic Turing machines (L-NTMs), and observe that the multitape L-NTMs have the same language-recognizing power as the single-tape L-NTMs. We give some related properties of L-valued Turing machines, and discuss computing with fuzzy letters via L-valued Turing machines. Second, we introduce the concepts of L-valued recursively enumerable languages and L-valued recursive languages, and obtain some equivalent relations. Some results concerning the characterization of n-recursively enumerable sets are given, and the super-computing power of L-valued Turing machines is investigated. We also prove that L-valued deterministic Turing machines and L-NTMs are not equivalent in the sense of recognizing or deciding languages. Finally, we show that there is no universal L-valued Turing machine. However, a universal L-valued Turing machine exists if the membership degrees of L-valued sets are restricted to a finite complete residuated lattice with universal bounds 0 and 1. © 2012 Elsevier B.V. |
| 收录类别 | EI |
| 语种 | 英语 |
| WOS记录号 | WOS:000309803300003 |
| 公开日期 | 2012-11-12 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/14732]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Wu Lihua,Qiu Daowen,Xing Hongyan. automata theory based on complete residuated lattice-valued logic: turing machines[J]. Fuzzy Sets and Systems,2012,208:43-66. |
| APA | Wu Lihua,Qiu Daowen,&Xing Hongyan.(2012).automata theory based on complete residuated lattice-valued logic: turing machines.Fuzzy Sets and Systems,208,43-66. |
| MLA | Wu Lihua,et al."automata theory based on complete residuated lattice-valued logic: turing machines".Fuzzy Sets and Systems 208(2012):43-66. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。