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: |