Analogies and differences between quantum and stochastic automata
| Autor: | Marco Carpentieri, Alberto Bertoni |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Discrete mathematics
General Computer Science Stochastic modelling Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Quantum computing Automata Theoretical Computer Science Quantum probability Regular language Bounded function Probabilistic automaton Formal language Computer Science::Programming Languages Quantum finite automata Formal power series Computer Science::Formal Languages and Automata Theory Mathematics Quantum computer Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 262(1-2):69-81 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/s0304-3975(00)00154-7 |
| Popis: | We analyze some features of the behaviour of quantum automata, providing analogies and differences with the corresponding stochastic models. In particular, we prove: • there is a quantum automaton where the change of state depends on unitary transformations defined by matrices with nonnull amplitudes that accepts a non regular language with cut point zero and inverse error polynomially bounded, • stochastic automata with matrices having nonnull elements and with polynomial bounds on the inverse error recognize only regular languages, • the class of stochastic languages contains the class of quantum languages, • quantum languages are empty or contain an infinite number of words, • the class of quantum languages is not closed under complementation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect