multi-letter quantum finite automata: decidability of the equivalence and minimization of states
文献类型：期刊论文
| 作者 | Qiu Daowen ; Li Lvzhou ; Zou Xiangfu ; Mateus Paulo ; Gruska Jozef |
| 刊名 | ACTA INFORMATICA
 |
| 出版日期 | 2011 |
| 卷号 | 48期号:5-6页码:271-290 |
| ISSN号 | 0001-5903 |
| 中文摘要 | Multi-letter quantum finite automata (QFAs) can be thought of quantum variants of the one-way multi-head finite automata (Hromkovic, Acta Informatica 19:377-384, 1983). It has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages, for example (a + b)*b, that are not acceptable by QFAs of Moore and Crutchfield (Theor Comput Sci 237:275-306, 2000) as well as Kondacs and Watrous (66-75, 1997; Observe that 1-letter QFAs are exactly measure-once QFAs (MO-1QFAs) of Moore and Crutchfield (Theor Comput Sci 237: 275-306, 2000)). In this paper, we study the decidability of the equivalence and minimization problems of multi-letter QFAs. Three new results presented in this paper are the following ones: (1) Given a k(1)-letter QFA A(1) and a k(2)-letter QFA A(2) over the same input alphabet Sigma, they are equivalent if and only if they are (n(2)m(k-1) - m(k-1) + k)-equivalent, where m = vertical bar Sigma vertical bar is the cardinality of Sigma, k = max(k(1), k(2)), and n = n(1) + n(2), with n(1) and n(2) being numbers of states of A(1) and A(2), respectively. When k = 1, this result implies the decidability of equivalence of measure-once QFAs (Moore and Crutchfield in Theor Comput Sci 237:275-306, 2000). (It is worth mentioning that our technical method is essentially different from the previous ones used in the literature.) (2) A polynomial-time O(m(2k-1)n(8) + km(k)n(6)) algorithm is designed to determine the equivalence of any two multi-letter QFAs (see Theorems 2 and 3; Observe that if a brute force algorithm to determine equivalence would be used, as suggested by the decidability outcome of the point (1), the worst case time complexity would be exponential). Observe also that time complexity is expressed here in terms of the number of states of the multi-letter QFAs and k can be seen as a constant. (3) It is shown that the states minimization problem of multi-letter QFAs is solvable in EXPSPACE. This implies also that the state minimization problem of MO-1QFAs (see Moore and Crutchfield in Theor Comput Sci 237: 275-306, 2000, page 304, Problem 5), an open problem stated in that paper, is also solvable in EXPSPACE. |
| 英文摘要 | Multi-letter quantum finite automata (QFAs) can be thought of quantum variants of the one-way multi-head finite automata (Hromkovic, Acta Informatica 19:377-384, 1983). It has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages, for example (a + b)*b, that are not acceptable by QFAs of Moore and Crutchfield (Theor Comput Sci 237:275-306, 2000) as well as Kondacs and Watrous (66-75, 1997; Observe that 1-letter QFAs are exactly measure-once QFAs (MO-1QFAs) of Moore and Crutchfield (Theor Comput Sci 237: 275-306, 2000)). In this paper, we study the decidability of the equivalence and minimization problems of multi-letter QFAs. Three new results presented in this paper are the following ones: (1) Given a k(1)-letter QFA A(1) and a k(2)-letter QFA A(2) over the same input alphabet Sigma, they are equivalent if and only if they are (n(2)m(k-1) - m(k-1) + k)-equivalent, where m = vertical bar Sigma vertical bar is the cardinality of Sigma, k = max(k(1), k(2)), and n = n(1) + n(2), with n(1) and n(2) being numbers of states of A(1) and A(2), respectively. When k = 1, this result implies the decidability of equivalence of measure-once QFAs (Moore and Crutchfield in Theor Comput Sci 237:275-306, 2000). (It is worth mentioning that our technical method is essentially different from the previous ones used in the literature.) (2) A polynomial-time O(m(2k-1)n(8) + km(k)n(6)) algorithm is designed to determine the equivalence of any two multi-letter QFAs (see Theorems 2 and 3; Observe that if a brute force algorithm to determine equivalence would be used, as suggested by the decidability outcome of the point (1), the worst case time complexity would be exponential). Observe also that time complexity is expressed here in terms of the number of states of the multi-letter QFAs and k can be seen as a constant. (3) It is shown that the states minimization problem of multi-letter QFAs is solvable in EXPSPACE. This implies also that the state minimization problem of MO-1QFAs (see Moore and Crutchfield in Theor Comput Sci 237: 275-306, 2000, page 304, Problem 5), an open problem stated in that paper, is also solvable in EXPSPACE. |
| 学科主题 | Computer Science |
| 收录类别 | SCI |
| 资助信息 | National Natural Science Foundation60873055, 61073054; Natural Science Foundation of Guangdong Province of China10251027501000004; Fundamental Research Funds for the Central Universities10lgzd12, 11lgpy36; Ministry of Education of China20100171110042, 20100171120051; China Postdoctoral Science Foundation20090460808, 201003375; SQIG at IT; FCT; EUQSec PTDC/EIA/67661/2006, AMDSC UTAustin/MAT/0057/2008; MSM0021622419 |
| 语种 | 英语 |
| WOS记录号 | WOS:000297512700001 |
| 公开日期 | 2013-10-08 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/16144]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Qiu Daowen,Li Lvzhou,Zou Xiangfu,et al. multi-letter quantum finite automata: decidability of the equivalence and minimization of states[J]. ACTA INFORMATICA,2011,48(5-6):271-290. |
| APA | Qiu Daowen,Li Lvzhou,Zou Xiangfu,Mateus Paulo,&Gruska Jozef.(2011).multi-letter quantum finite automata: decidability of the equivalence and minimization of states.ACTA INFORMATICA,48(5-6),271-290. |
| MLA | Qiu Daowen,et al."multi-letter quantum finite automata: decidability of the equivalence and minimization of states".ACTA INFORMATICA 48.5-6(2011):271-290. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。