排序方式: 共有2条查询结果,搜索用时 15 毫秒
1
1.
We analyze the properties of probabilistic reversible decide-and-halt automata (DH-PRA) and show that there is a strong relationship between DH-PRA and 1-way quantum automata. We show that a general class of regular languages is not recognizable by DH-PRA by proving that two “forbidden” constructions in minimal deterministic automata correspond to languages not recognizable by DH-PRA. The shown class is identical to a class known to be not recognizable by 1-way quantum automata. We also prove that the class of languages recognizable by DH-PRA is not closed under union and other non-trivial Boolean operations. 相似文献
2.
Andris Ambainis Martin Beaudry Marats Golovkins Arnolds Kikusts Mark Mercer Denis Therien 《Theory of Computing Systems》2006,39(1):165-188
We use tools from the algebraic theory of automata to investigate the
class of languages recognized by two models of Quantum Finite Automata (QFA):
Brodsky and Pippenger's end-decisive model (which we call BPQFA)
and a new QFA model (which we call LQFA) whose definition is motivated by
implementations of quantum computers using nucleo-magnetic resonance (NMR).
In particular, we are interested in LQFA since NMR was used to construct the most powerful physical quantum machine to date.
We give a complete characterization of the languages recognized by LQFA and by Boolean combinations of BPQFA. It is a surprising
consequence of our results that LQFA and Boolean combinations of
BPQFA are equivalent in language recognition power. 相似文献
1