Decidable and undecidable problems about quantum automata. - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2003

Decidable and undecidable problems about quantum automata.

(1) , (1) , (1) , (1)
1

Résumé

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.
Nous étudions le problème suivant : est-ce que le langage reconnu par un certain automate quantique est vide ? Nous savons que ce problème est indécidable dans le cas des automates probabilistes, que le seuil de reconnaissance soit strict ou ne le soit pas. nous montrons que pour les automates quantiques, en revanche, la réponse n'est pas la même dans les deux cas.
Fichier principal
Vignette du fichier
RR2003-24.pdf (214.44 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101900 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101900 , version 1

Citer

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⟩
10 Consultations
101 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More