Power of Randomization in Automata on Infinite Strings

Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan

Probabilistic Büchi Automata (PBA) are randomized, finite state automata that process input strings of infinite length. Based on the threshold chosen for the acceptance probability…