Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Reports

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 metadata

https://hal-lara.archives-ouvertes.fr/hal-02101900
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:09:19 AM
Last modification on : Saturday, September 11, 2021 - 3:19:17 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

7

Files downloads

75