English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Angluin's L$^*$ algorithm learns the minimal deterministic finite automaton(DFA) of a regular language using membership and equivalence queries. Itsprobabilistic approximatively correct (PAC) version substitutes an equivalencequery by numerous random membership queries to get a high level confidence tothe answer. Thus it can be applied to any kind of device and may be viewed asan algorithm for synthesizing an automaton abstracting the behavior of thedevice based on observations. Here we are interested on how Angluin's PAClearning algorithm behaves for devices which are obtained from a DFA byintroducing some noise. More precisely we study whether Angluin's algorithmreduces the noise and produces a DFA closer to the original one than the noisydevice. We propose several ways to introduce the noise: (1) the noisy deviceinverts the classification of words w.r.t. the DFA with a small probability,(2) the noisy device modifies with a small probability the letters of the wordbefore asking its classification w.r.t. the DFA, (3) the noisy device combinesthe classification of a word w.r.t. the DFA and its classification w.r.t. acounter automaton, and (4) the noisy DFA is obtained by a random process fromtwo DFA such that the language of the first one is included in the second one.Then when a word is accepted (resp. rejected) by the first (resp. second) one,it is also accepted (resp. rejected) and in the remaining cases, it is acceptedwith probability 0.5. Our main experimental contributions consist in showingthat: (1) Angluin's algorithm behaves well whenever the noisy device isproduced by a random process, (2) but poorly with a structured noise, and, that(3) is able to eliminate pathological behaviours specified in a regular way.Theoretically, we show that randomness almost surely yields systems withnon-recursively enumerable languages.

Analyzing Robustness of Angluin's L$^*$ Algorithm in Presence of Noise