Quantum automata and algebraic groups.

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.
Document type :
Reports
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101965
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:54 AM
Last modification on : Wednesday, May 15, 2019 - 6:13:31 AM

File

RR2003-39.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101965, version 1

Collections

Citation

Harm Derksen, Emmanuel Jeandel, Pascal Koiran. Quantum automata and algebraic groups.. [Research Report] LIP RR-2003-39, Laboratoire de l'informatique du parallélisme. 2003, 2+15p. ⟨hal-02101965⟩

Share

Metrics

Record views

8

Files downloads

31