Decidable and undecidable problems about quantum automata.

Abstract : We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101900
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:19 AM
Last modification on : Friday, May 17, 2019 - 1:39:22 AM

File

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

Identifiers

  • HAL Id : hal-02101900, version 1

Collections

Citation

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier. Decidable and undecidable problems about quantum automata.. [Research Report] LIP RR-2003-24, Laboratoire de l'informatique du parallélisme. 2003, 2+11p. ⟨hal-02101900⟩

Share

Metrics

Record views

5

Files downloads

19