Finite state and finite stop quantum languages

doi:10.1007/s10773-005-4781-z

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	Finite state and finite stop quantum languages
	Lu, RQ ; Zheng, H
刊名	INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS
	2005-09-01
卷号	44 期号:9 页码:1495-1530
关键词	finite state quantum automata finite stop quantum automata complex valued quantum automata quantum languages
ISSN号	0020-7748
DOI	10.1007/s10773-005-4781-z
英文摘要	We propose the concept of finite stop quantum automata (ftqa) based on Hilbert space and compare it with the finite state quantum automata (fsqa) proposed by Moore and Crutchfield (Theoretical Computer Science 237(1-2), 2000, 275-306). The languages accepted by fsqa form a proper subset of the languages accepted by ftqa. In addition, the fsqa form an infinite hierarchy of language inclusion with respect to the dimensionality of unitary matrices. We introduce complex-valued acceptance degrees and two types of finite stop quantum automata based on them: the invariant ftqa (icftq) and the variant ftqa (vcftq). The languages accepted by icftq form a proper subset of the languages accepted by vcftq. In addition, the icftq form an infinite hierarchy of language inclusion with respect to the dimensionality of unitary matrices. In this way, we establish two proper inclusion relations L (fsqa) subset of L (ftqa) and L (icftq) subset of L (vcftq), where the symbol L means languages, and two infinite language hierarchies L-n (fsqa) subset of Ln+1 (fsqa), L-n (icftq) subset of Ln+1 (icftq).
WOS研究方向	Physics
语种	英语
出版者	SPRINGER/PLENUM PUBLISHERS
WOS记录号	WOS:000234299000013
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/9972]
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Lu, RQ
作者单位	1.Fudan Univ, Shanghai Key Lab Intelligent Informat Proc, Shanghai 200433, Peoples R China 2.Acad Sinica, Acad Math & Syst Sci, Inst Math, AMSS, Beijing 100080, Peoples R China 3.Patent Examinat Cooperat Ctr, State Intellectual Property Off Peoples Republ Ch, Beijing 100080, Peoples R China 4.Acad Sinica, Key Lab MADIS, Beijing 100080, Peoples R China 5.Acad Sinica, Inst Comp Technol, Key Lab IIP, Beijing 100080, Peoples R China 6.Beijing Univ Technol, Beijing Key Lab Multimedia & Intelligent Software, Beijing 100022, Peoples R China
推荐引用方式 GB/T 7714	Lu, RQ,Zheng, H. Finite state and finite stop quantum languages[J]. INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS,2005,44(9):1495-1530.
APA	Lu, RQ,&Zheng, H.(2005).Finite state and finite stop quantum languages.INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS,44(9),1495-1530.
MLA	Lu, RQ,et al."Finite state and finite stop quantum languages".INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS 44.9(2005):1495-1530.