En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis. D'autres définitions, plus générales, ont été proposées, en généralisation des diverses variantes des automates, par exemple par . Un des objectifs de l’étude des automates fini quantiques est l’étude des langages formels qu'ils acceptent ; un autre est d'étudier les problèmes

Property Value
dbo:abstract
  • En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis. D'autres définitions, plus générales, ont été proposées, en généralisation des diverses variantes des automates, par exemple par . Un des objectifs de l’étude des automates fini quantiques est l’étude des langages formels qu'ils acceptent ; un autre est d'étudier les problèmes de décidabilité pour ces classes d'automates et de langages. Les automates finis quantiques sont similaires aux automates probabilistes, mais la classe des langages reconnus par automates quantiques est strictement contenue dans la classe des langages reconnus par automates probabilistes.Les automates finis quantiques peuvent aussi être vus comme une version quantique des sous-shifts de type fini, ou comme une variante quantique des chaînes de Markov. Les automates finis quantiques sont, à leur tour, des cas particuliers des automates finis dit géométriques ou des automates finis dit topologiques. Un automate fini quantique opère sur des mots finis , dont les lettres sont dans un alphabet donné . Il attribue à chaque mot une probabilité; en fonction de cette probabilité, le mot est accepté ou rejeté par l'automate. Les langages acceptés par les automates finis quantique ne coïncident pas avec les langages rationnels acceptés par les automates finis, ni avec les langages stochastiques acceptés par les automates finis probabilistes. (fr)
  • En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis. D'autres définitions, plus générales, ont été proposées, en généralisation des diverses variantes des automates, par exemple par . Un des objectifs de l’étude des automates fini quantiques est l’étude des langages formels qu'ils acceptent ; un autre est d'étudier les problèmes de décidabilité pour ces classes d'automates et de langages. Les automates finis quantiques sont similaires aux automates probabilistes, mais la classe des langages reconnus par automates quantiques est strictement contenue dans la classe des langages reconnus par automates probabilistes.Les automates finis quantiques peuvent aussi être vus comme une version quantique des sous-shifts de type fini, ou comme une variante quantique des chaînes de Markov. Les automates finis quantiques sont, à leur tour, des cas particuliers des automates finis dit géométriques ou des automates finis dit topologiques. Un automate fini quantique opère sur des mots finis , dont les lettres sont dans un alphabet donné . Il attribue à chaque mot une probabilité; en fonction de cette probabilité, le mot est accepté ou rejeté par l'automate. Les langages acceptés par les automates finis quantique ne coïncident pas avec les langages rationnels acceptés par les automates finis, ni avec les langages stochastiques acceptés par les automates finis probabilistes. (fr)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 9874390 (xsd:integer)
dbo:wikiPageLength
  • 27330 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 187297313 (xsd:integer)
dbo:wikiPageWikiLink
prop-fr:année
  • 1963 (xsd:integer)
  • 1997 (xsd:integer)
  • 2000 (xsd:integer)
  • 2002 (xsd:integer)
  • 2004 (xsd:integer)
  • 2005 (xsd:integer)
  • 2011 (xsd:integer)
  • 2014 (xsd:integer)
  • 2015 (xsd:integer)
prop-fr:arxiv
prop-fr:auteur
  • dbpedia-fr:Michael_Rabin
  • Alberto Bertoni (fr)
  • Alex Brodsky (fr)
  • Andris Ambainis et Abuzer Yakaryilmaz (fr)
  • Christian Choffrut (fr)
  • Emmanuel Jeandel (fr)
  • Flavio d’Alessandro (fr)
  • Harm Derksen (fr)
  • Mika Hirvensalo (fr)
  • Natacha Portier (fr)
  • Nicholas Pippenger (fr)
  • Pascal Koiran (fr)
  • Vincent D. Blondel (fr)
prop-fr:auteursOuvrage
  • Werner Kuich et George Rahonis (fr)
  • Werner Kuich et George Rahonis (fr)
prop-fr:collection
  • Lecture Notes in Computer Science 7020 (fr)
  • Lecture Notes in Computer Science 7020 (fr)
prop-fr:doi
  • 10.100700 (xsd:double)
  • 10.101600 (xsd:double)
  • 10.113700 (xsd:double)
  • 10.114200 (xsd:double)
prop-fr:eIsbn
  • 978 (xsd:integer)
prop-fr:fr
  • série rationnelle en variables non commutatives (fr)
  • série rationnelle en variables non commutatives (fr)
prop-fr:id
  • MC (fr)
  • KW (fr)
  • Quantum_stochastic_processes&oldid=17767 (fr)
  • YS (fr)
  • MC (fr)
  • KW (fr)
  • Quantum_stochastic_processes&oldid=17767 (fr)
  • YS (fr)
prop-fr:isbn
  • 978 (xsd:integer)
prop-fr:journal
  • Theoretical Computer Science (fr)
  • Information and Computation (fr)
  • Information and Control (fr)
  • SIAM Journal of Computing (fr)
  • FOCS’97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (fr)
  • Theoretical Computer Science (fr)
  • Information and Computation (fr)
  • Information and Control (fr)
  • SIAM Journal of Computing (fr)
  • FOCS’97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (fr)
prop-fr:mois
  • décembre (fr)
  • mars (fr)
  • janvier (fr)
  • juin (fr)
  • september (fr)
  • décembre (fr)
  • mars (fr)
  • janvier (fr)
  • juin (fr)
  • september (fr)
prop-fr:nom
  • Moore (fr)
  • Watrous (fr)
  • Say (fr)
  • Accardi (fr)
  • Crutchfield (fr)
  • Kondacs (fr)
  • Yakaryilmaz (fr)
  • Moore (fr)
  • Watrous (fr)
  • Say (fr)
  • Accardi (fr)
  • Crutchfield (fr)
  • Kondacs (fr)
  • Yakaryilmaz (fr)
prop-fr:numéro
  • 1 (xsd:integer)
  • 3 (xsd:integer)
  • 5 (xsd:integer)
  • 6 (xsd:integer)
  • 8 (xsd:integer)
prop-fr:numéroD'édition
  • 2 (xsd:integer)
prop-fr:pages
  • 66 (xsd:integer)
  • 230 (xsd:integer)
  • 275 (xsd:integer)
  • 357 (xsd:integer)
  • 873 (xsd:integer)
  • 1065 (xsd:integer)
  • 1456 (xsd:integer)
  • 1464 (xsd:integer)
prop-fr:passage
  • 146 (xsd:integer)
prop-fr:prénom
  • Luigi (fr)
  • A. (fr)
  • James P. (fr)
  • John (fr)
  • Cristopher (fr)
  • Attila (fr)
  • A.C.C. (fr)
  • Luigi (fr)
  • A. (fr)
  • James P. (fr)
  • John (fr)
  • Cristopher (fr)
  • Attila (fr)
  • A.C.C. (fr)
prop-fr:périodique
  • International Journal on Foundations of Computer Science (fr)
  • Journal of Symbolic Computation (fr)
  • SIAM Journal of Computing (fr)
  • International Journal on Foundations of Computer Science (fr)
  • Journal of Symbolic Computation (fr)
  • SIAM Journal of Computing (fr)
prop-fr:site
  • arxiv (fr)
  • arxiv (fr)
prop-fr:sousTitreOuvrage
  • Bozapalidis Festschrift (fr)
  • Bozapalidis Festschrift (fr)
prop-fr:texte
  • rationnelle (fr)
  • rationnelle (fr)
prop-fr:titre
  • Decidable and undecidable problems about quantum automata (fr)
  • Automata and Quantum Computing (fr)
  • Characterizations of 1-Way Quantum Finite Automata (fr)
  • On the decidability of the intersection problem for quantum automata and context-free languages (fr)
  • On the power of quantum finite state automata (fr)
  • Probabilistic Automata (fr)
  • Quantum Computing (fr)
  • Quantum automata and algebraic groups (fr)
  • Quantum automata and quantum grammars (fr)
  • Quantum stochastic processes (fr)
  • Unbounded-error quantum computation with small space bounds (fr)
  • Decidable and undecidable problems about quantum automata (fr)
  • Automata and Quantum Computing (fr)
  • Characterizations of 1-Way Quantum Finite Automata (fr)
  • On the decidability of the intersection problem for quantum automata and context-free languages (fr)
  • On the power of quantum finite state automata (fr)
  • Probabilistic Automata (fr)
  • Quantum Computing (fr)
  • Quantum automata and algebraic groups (fr)
  • Quantum automata and quantum grammars (fr)
  • Quantum stochastic processes (fr)
  • Unbounded-error quantum computation with small space bounds (fr)
prop-fr:titreChapitre
  • Quantum Automata Theory – A Review (fr)
  • Quantum Automata Theory – A Review (fr)
prop-fr:titreOuvrage
  • Algebraic Foundations in Computer Science (fr)
  • Algebraic Foundations in Computer Science (fr)
prop-fr:trad
  • rational series (fr)
  • rational series (fr)
prop-fr:url
prop-fr:volume
  • 6 (xsd:integer)
  • 25 (xsd:integer)
  • 31 (xsd:integer)
  • 34 (xsd:integer)
  • 39 (xsd:integer)
  • 209 (xsd:integer)
  • 237 (xsd:integer)
prop-fr:wikiPageUsesTemplate
prop-fr:éditeur
dct:subject
rdfs:comment
  • En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis. D'autres définitions, plus générales, ont été proposées, en généralisation des diverses variantes des automates, par exemple par . Un des objectifs de l’étude des automates fini quantiques est l’étude des langages formels qu'ils acceptent ; un autre est d'étudier les problèmes (fr)
  • En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis. D'autres définitions, plus générales, ont été proposées, en généralisation des diverses variantes des automates, par exemple par . Un des objectifs de l’étude des automates fini quantiques est l’étude des langages formels qu'ils acceptent ; un autre est d'étudier les problèmes (fr)
rdfs:label
  • Automate quantique (fr)
  • Autômato quântico (pt)
  • Automate quantique (fr)
  • Autômato quântico (pt)
rdfs:seeAlso
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is oa:hasTarget of
is foaf:primaryTopic of