Name
Abstract | ||
|---|---|---|
In this paper, we investigate the computational and verification power of bounded-error postselecting realtime probabilistic finite state automata (PostPFAs). We show that PostPFAs using rational-valued transitions can do different variants of equality checks and they can verify some nonregular unary languages. Then, we allow them to use real-valued transitions (magic-coins) and show that they can recognize uncountably many binary languages by help of a counter and verify uncountably many unary languages by help of a prover. We also present some corollaries on probabilistic counter automata. |
Year | Venue | DocType |
|---|---|---|
2018 | NCMA | Conference |
Volume | Citations | PageRank |
abs/1807.05169 | 0 | 0.34 |
References | Authors | |
8 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maksims Dimitrijevs | 1 | 3 | 3.14 |
| Abuzer Yakaryilmaz | 2 | 168 | 25.31 |