Quantum automata and algebraic groups

被引：33

作者：

Derksen, H

Jeandel, E

Koiran, P

机构：

[1] Ecole Normale Super Lyon, Lab Informat Parallelisme, F-69364 Lyon, France

[2] Univ Michigan, Dept Math, Ann Arbor, MI 48109 USA

来源：

JOURNAL OF SYMBOLIC COMPUTATION | 2005年 / 39卷 / 3-4期

基金：

美国国家科学基金会;

关键词：

quantum automata; probabilistic automata; undecidability; algebraic groups; algebraic geometry;

D O I：

10.1016/j.jsc.2004.11.008

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that several problems which are known to be undecidable for probabilistic automata become decidable for quantum finite automata. Our main tool is an algebraic result of independent interest: we give an algorithm which, given a finite number of invertible matrices, computes the Zariski closure of the group generated by these matrices. (c) 2005 Elsevier Ltd. All rights reserved.

引用

页码：357 / 371

页数：15

共 31 条

[1]

[Anonymous], 2002, ENCY MATH SCI

[2]

Babai L., 1993, Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation. ISSAC '93, P117, DOI 10.1145/164081.164104

[3] On the combinatorial and algebraic complexity of quantifier elimination [J].