Decidable and undecidable problems about quantum automata.

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