Finite state and finite stop quantum languages

doi:10.1007/s10773-005-4781-z

	Finite state and finite stop quantum languages
	Lu, RQ ; Zheng, H
	2005-09-01
发表期刊	INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS
ISSN	0020-7748
卷号	44 期号:9 页码:1495-1530
摘要	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).
关键词	finite state quantum automata finite stop quantum automata complex valued quantum automata quantum languages
DOI	10.1007/s10773-005-4781-z
收录类别	SCI
语种	英语
WOS研究方向	Physics
WOS类目	Physics, Multidisciplinary
WOS记录号	WOS:000234299000013
出版者	SPRINGER/PLENUM PUBLISHERS
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/9973
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Lu, RQ
作者单位	1.Acad Sinica, Acad Math & Syst Sci, Inst Math, AMSS, Beijing 100080, Peoples R China 2.Fudan Univ, Shanghai Key Lab Intelligent Informat Proc, Shanghai 200433, Peoples R China 3.Beijing Univ Technol, Beijing Key Lab Multimedia & Intelligent Software, Beijing 100022, Peoples R China 4.Acad Sinica, Inst Comp Technol, Key Lab IIP, Beijing 100080, Peoples R China 5.Acad Sinica, Key Lab MADIS, Beijing 100080, Peoples R China 6.Patent Examinat Cooperat Ctr, State Intellectual Property Off Peoples Republ Ch, Beijing 100080, 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.