SOFSEM 2001 28th Annual Conference on Current Trends in Theory and Practice of Informatics November 24 - December 1, 2001 Piestany, Slovak Republic, Europe

---

Abstract of Paper

Quantum Finite State Transducers
by Rusins Freivalds and Andreas Winter

Abstract:

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 trans­
ducers, 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 incom­
parable to that of their probabilistic counterpart. This we show by discussing a number of
characteristic examples.