Succinctness of two-way probabilistic and quantum finite automata

Abstract : We introduce a new model of two-way finite automaton, which is endowed with the capability of resetting the position of the tape head to the left end of the tape in a single move during the computation. Several variants of this model are examined, with the following results: The weakest known model of computation where quantum computers recognize more languages with bounded error than their classical counterparts is identified. We prove that two-way probabilistic and quantum finite automata (2PFAs and 2QFAs) can be considerably more concise than both their one-way versions (1PFAs and 1QFAs), and two-way nondeterministic finite automata (2NFAs). For this purpose, we demonstrate several infinite families of regular languages which can be recognized with some fixed probability greater than 1 2 by just tuning the transition amplitudes of a 2QFA (and, in one case, a 2PFA) with a constant number of states, whereas the sizes of the corresponding 1PFAs, 1QFAs and 2NFAs grow without bound. We also show that 2QFAs with mixed states can support highly efficient probability amplification.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (4), pp.19-40
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990436
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:36:54
Dernière modification le : lundi 9 avril 2018 - 10:11:19
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:12:39

Fichier

1457-5718-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990436, version 1

Collections

Citation

Abuzer Yakaryilmaz, A. C. Cem Say. Succinctness of two-way probabilistic and quantum finite automata. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (4), pp.19-40. 〈hal-00990436〉

Partager

Métriques

Consultations de la notice

60

Téléchargements de fichiers

147