Unary probabilistic and quantum automata on promise problems

Conference object, Article, Preprint English OPEN
Gainutdinova, Aida; Yakaryilmaz, Abuzer;
  • Subject: Computer Science - Computational Complexity | Computer Science - Formal Languages and Automata Theory
    arxiv: Computer Science::Computational Complexity | Computer Science::Formal Languages and Automata Theory

© Springer International Publishing Switzerland 2015. We continue the systematic investigation of probabilistic and quantum finite automata (PFAs and QFAs) on promise problems by focusing on unary languages. We show that bounded-error QFAs are more powerful than PFAs. B... View more