| Title: | revisiting the power and equivalence of one-way quantum finite automata |
| Author: | Li Lvzhou
; Qiu Daowen
|
| Source: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|
| Conference Name: | 6th International Conference on Intelligent Computing, ICIC 2010
|
| Conference Date: | August 18,
|
| Issued Date: | 2010
|
| Conference Place: | Changsha, China
|
| Keyword: | Automata theory
; Equivalence classes
; Formal languages
; Linguistics
; Quantum computers
|
| Publish Place: | Germany
|
| Indexed Type: | ei
|
| ISSN: | 3029743
|
| ISBN: | 3642149316
|
| Department: | (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
|
| Sponsorship: | IEEE Computational Intelligence Society; International Neural Network Society; National Science Foundation of China
|
| English Abstract: | 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. |
| Language: | 英语
|
| Content Type: | 会议论文
|
| URI: | http://ir.iscas.ac.cn/handle/311060/8892
|
| Appears in Collections: | 中科院软件所图书馆_2010软件所会议论文
|
| File Name/ File Size |
Content Type |
Version |
Access |
License |
|
|---|
| revisiting the power and equivalence of one-way quantum finite automata.pdf（189KB） | -- | -- | 限制开放 | -- | 联系获取全文 |
|
| Recommended Citation: | |
Li Lvzhou,Qiu Daowen. revisiting the power and equivalence of one-way quantum finite automata[C]. 见:6th International Conference on Intelligent Computing, ICIC 2010. Changsha, China. August 18,.
|
|
|
