Title | Quantum automata and algebraic groups |
Author(s) | Harm Derksen, Emmanuel Jeandel, Pascal Koiran |
Type | Article in Journal |
Abstract | 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. |
Keywords | Quantum automata, Probabilistic automata, Undecidability, Algebraic groups, Algebraic geometry |
ISSN | 0747-7171 |
URL |
http://www.sciencedirect.com/science/article/pii/S0747717105000088 |
Language | English |
Journal | Journal of Symbolic Computation |
Volume | 39 |
Number | 3–4 |
Pages | 357 - 371 |
Year | 2005 |
Note | Special issue on the occasion of MEGA 2003 MEGA 2003 |
Edition | 0 |
Translation |
No |
Refereed |
No |