revisiting the power and equivalence of one-way quantum finite automata

ISCAS OpenIR > 2010软件所会议论文

	revisiting the power and equivalence of one-way quantum finite automata
	Li Lvzhou; Qiu Daowen
	2010
会议名称	6th International Conference on Intelligent Computing, ICIC 2010
会议录名称	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
页码	40551
会议日期	August 18,
会议地点	Changsha, China
收录类别	ei
出版地	Germany
ISSN	3029743
ISBN	3642149316
部门归属	(1) Department of Computer Science, Sun Yat-sen University, Guangzhou 510275, China; (2) SQIG-Instituto de Telecomunicações, IST, TULisbon, Av. Rovisco Pais, Lisbon 1049-001, Portugal; (3) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China
摘要	We give a new proof for the fact that measure-many one-way quantum finite automata (MM-1QFA) recognize only regular languages with bounded error. Our proof, different from the one in the literature, gives another insight to the recognition power of MM-1QFA. Moreover, we generalize the proof to a broader class of automata that include probabilistic automata and some kinds of quantum finite automata. In addition, we briefly discuss the equivalence problem of some quantum computing models in a uniform framework. © 2010 Springer-Verlag Berlin Heidelberg.
关键词	Automata Theory Equivalence Classes Formal Languages Linguistics Quantum Computers
主办者	IEEE Computational Intelligence Society; International Neural Network Society; National Science Foundation of China
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/8892
专题	2010软件所会议论文
推荐引用方式 GB/T 7714	Li Lvzhou,Qiu Daowen. revisiting the power and equivalence of one-way quantum finite automata[C]. Germany,2010:40551.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
revisiting the power（189KB）			限制开放	--	请求全文