Analyzing Robustness of Angluin's L${}^{\ast }$ Algorithm in Presence of Noise

Lina Ye, Igor Khmelnitsky, Serge Haddad +5

Angluin's L${}^{\ast }$ algorithm learns the minimal deterministic finite automaton (DFA) of a regular language using membership and equivalence queries. Its probabilistic approximatively…