2018/07/13 by Maksims Dimitrijevs, Dimitrijevs, Maksims, Abuzer Yakaryılmaz +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic, Reasoning, and Knowledge #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1807.05169
openalex publication_date 2018/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.