| 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)
- In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata. The automata work by receiving a finite-length string of letters from a finite alphabet , and assigning to each such string a probability indicating the probability of the automaton being in an accept state; that is, indicating whether the automaton accepted or rejected the string. The languages accepted by QFAs are not the regular languages of deterministic finite automata, nor are they the stochastic languages of probabilistic finite automata. Study of these quantum languages remains an active area of research. (en)
- Un automa a stati finiti quantistico (QFA) è, in informatica quantistica e in informatica teorica, una generalizzazione degli automi a stati finiti che accettano una parola in base al risultato di una misura. Gli automi a stati finiti quantistici sono simili agli automi probabilistici, ma la classe dei linguaggi riconosciuta dagli automi quantistici è strettamente contenuta nella classe dei linguaggi riconosciuti dagli automi probabilistici. Gli automi a stati finiti quantistici possono anche essere visti come una versione quantistica di subshift di tipo finito o come una variante quantistica delle catene di Markov. Gli automi quantistici finiti sono, a loro volta, dei casi particolari dei cosiddetti automi finiti geometrici o degli automi finiti topologici. Un automa quantistico finito opera su parole finite , le cui lettere appartengono a un dato alfabeto . A ogni parola viene assegnata una probabilità; a seconda di questa probabilità, la parola viene accettata o rifiutata dall'automa. I linguaggi accettati dagli automi quantistici finiti non coincidono con i linguaggi regolari accettati dagli automi finiti, né con i linguaggi stocastici accettati dagli automi a stati finiti probabilistici. Lo studio degli automi finiti quantistici si divide in due aree principali che dipendono dalle transizioni autorizzate alla macchina di Turing corrispondente: gli one-way quantum finite automata (1QFA) per i quali ad ogni passo la testina di lettura si muove di una casella a destra e i two-way quantum finite automata (2QFA), per i quale la testina si può muovere sia a destra che a sinistra o rimanere ferma. Esistono diversi tipi di automi a stati finiti quantistici; il più restrittivo è quello detto measure-once e definito da Moore e Crutchfield nel 2000; un altro è quello degli automi measure-many, definiti da Kondacs e Watrous nel 1997. Nei measure-once, viene effettuata un'unica misura per ogni stringa d'ingresso dopo aver letto l'ultimo simbolo della parola, mentre per il measure-many, la misura viene effettuata dopo la lettura di ogni simbolo che compone l'input. Il measure-once è considerato il più vicino (anche per costruzione) alla teoria classica degli automi finiti. Altre definizioni più generali sono state proposte. Uno degli obiettivi dello studio degli automi a stati finiti quantistici è lo studio dei linguaggi formali che accettano; un altro è quello di studiare i problemi di decidibilità per queste classi di automi e linguaggi. (it)
- Kwantowy automat skończony (ang. Quantum Finite Automata, QFA) – abstrakcyjna maszyna o skończonej liczbie stanów, która – zaczynając w stanie początkowym – czyta kolejne symbole pewnego ciągu znaków ze skończonego zbioru i przydziela danemu ciągowi liczbę określającą prawdopodobieństwo znajdowania się maszyny w stanie akceptującym (końcowym). Czyli wskazuje na to, czy dany ciąg znaków należy do języka regularnego, do rozpoznawania którego jest zbudowana. Kwantowe automaty skończone są kwantowym analogiem bądź Łańcuchów Markowa i są związane z komputerami kwantowymi podobnie jak automaty skończone z maszynami Turinga. (pl)
- Na computação quântica, o autômato quântico finito ou QFA é uma analogia quântica do autômato probabilístico. Autômatos probabilísticos estão relacionados à computação quântica da mesma maneira que o autômato finito está relacionado à máquina de Turing. Muitos tipos de autômatos podem ser definidos, incluindo measure-once e measure-many autômatos. Autômatos quânticos de estados finitos podem ser entendidos como uma quantização do , ou uma quantização das cadeias de Markov. QFA é, de certa maneira, um caso especial de autômato geométrico finito ou autômato topológico finito. Os autômatos trabalham aceitando uma string de comprimento finito ou letras de um alfabeto finito e assinalando para cada uma dessas strings uma probabilidade indica a probabilidade do autômato estar em um estado aceitação, isto é,indicando se o autômato aceita ou rejeita a string. (pt)
|
| 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)
- In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata. (en)
- Un automa a stati finiti quantistico (QFA) è, in informatica quantistica e in informatica teorica, una generalizzazione degli automi a stati finiti che accettano una parola in base al risultato di una misura. (it)
- Kwantowy automat skończony (ang. Quantum Finite Automata, QFA) – abstrakcyjna maszyna o skończonej liczbie stanów, która – zaczynając w stanie początkowym – czyta kolejne symbole pewnego ciągu znaków ze skończonego zbioru i przydziela danemu ciągowi liczbę określającą prawdopodobieństwo znajdowania się maszyny w stanie akceptującym (końcowym). Czyli wskazuje na to, czy dany ciąg znaków należy do języka regularnego, do rozpoznawania którego jest zbudowana. (pl)
- Na computação quântica, o autômato quântico finito ou QFA é uma analogia quântica do autômato probabilístico. Autômatos probabilísticos estão relacionados à computação quântica da mesma maneira que o autômato finito está relacionado à máquina de Turing. Muitos tipos de autômatos podem ser definidos, incluindo measure-once e measure-many autômatos. Autômatos quânticos de estados finitos podem ser entendidos como uma quantização do , ou uma quantização das cadeias de Markov. QFA é, de certa maneira, um caso especial de autômato geométrico finito ou autômato topológico finito. (pt)
|
