6533b82cfe1ef96bd128fdde

RESEARCH PRODUCT

Quantum Finite State Transducers

Andreas WinterRusins Freivalds

subject

Discrete mathematicsPure mathematicsFinite-state machineDeterministic finite automatonComputer scienceComputer Science::Logic in Computer ScienceProbabilistic logicQuantum finite automataNondeterministic finite automatonState diagramQuantumComputer Science::Formal Languages and Automata TheoryQuantum computer

description

We introduce quantum finite state transducers (qfst), and study the class of relations which they compute. It turns out that they share many features with probabilistic finite state transducers, especially regarding undecidability of emptiness (at least for low probability of success). However, like their 'little brothers', the quantum finite automata, the power of qfst is incomparable to that of their probabilistic counterpart. This we show by discussing a number of characteristic examples.

yearjournalcountryeditionlanguage
2001-01-01
https://doi.org/10.1007/3-540-45627-9_20