6533b861fe1ef96bd12c42c6

RESEARCH PRODUCT

Unary Probabilistic and Quantum Automata on Promise Problems

Aida GainutdinovaAbuzer Yakaryilmaz

subject

State-transition matrixDiscrete mathematicsDeterministic finite automatonUnary operationMarkov chainUnary languageProbabilistic logicQuantum finite automataBinary numberComputer Science::Computational ComplexityComputer Science::Formal Languages and Automata TheoryMathematics

description

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. But, in contrary to the binary problems, the computational powers of Las-Vegas QFAs and bounded-error PFAs are equivalent to deterministic finite automata (DFAs). Lastly, we present a new family of unary promise problems with two parameters such that when fixing one parameter QFAs can be exponentially more succinct than PFAs and when fixing the other parameter PFAs can be exponentially more succinct than DFAs.

yearjournalcountryeditionlanguage
2015-01-01
https://doi.org/10.1007/978-3-319-21500-6_20