automata theory based on complete residuated lattice-valued logic: turing machines

ISCAS OpenIR

	automata theory based on complete residuated lattice-valued logic: turing machines
	Wu Lihua; Qiu Daowen; Xing Hongyan
	2012
发表期刊	Fuzzy Sets and Systems
ISSN	1650114
卷号	208 页码:43-66
摘要	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
部门归属	(1) Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, China; (2) SQIG - Instituto de Telecomunicações, Departamento de Matemática, Universidade Técnica de Lisboa, Avenida Rovisco Pais 1049-001, Lisbon, Portugal; (3) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China; (4) College of Informatics, South China Agricultural University, Guangzhou 510642, China
语种	英语
WOS记录号	WOS:000309803300003
引用统计	被引频次：16[WOS] [WOS记录] [WOS相关记录]
内容类型	期刊论文
URI标识	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.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
1-s2.0-S016501141200（334KB）			开放获取	使用许可	请求全文