Search

• < Previous
• 1
• Next >

Power of Randomization in Automata on Infinite Strings

Probabilistic B\"uchi Automata (PBA) are randomized, finite state automata that process input strings of infinite length. Based on the threshold chosen for the acceptance probability, different classes of languages can be defined. In this paper, we present a number of results that clarify the power&nbsp;[&hellip;]