{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:57:50Z","timestamp":1762325870964,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Angluin's L$^*$ algorithm learns the minimal deterministic finite automaton\n(DFA) of a regular language using membership and equivalence queries. Its\nprobabilistic approximatively correct (PAC) version substitutes an equivalence\nquery by numerous random membership queries to get a high level confidence to\nthe answer. Thus it can be applied to any kind of device and may be viewed as\nan algorithm for synthesizing an automaton abstracting the behavior of the\ndevice based on observations. Here we are interested on how Angluin's PAC\nlearning algorithm behaves for devices which are obtained from a DFA by\nintroducing some noise. More precisely we study whether Angluin's algorithm\nreduces the noise and produces a DFA closer to the original one than the noisy\ndevice. We propose several ways to introduce the noise: (1) the noisy device\ninverts the classification of words w.r.t. the DFA with a small probability,\n(2) the noisy device modifies with a small probability the letters of the word\nbefore asking its classification w.r.t. the DFA, (3) the noisy device combines\nthe classification of a word w.r.t. the DFA and its classification w.r.t. a\ncounter automaton, and (4) the noisy DFA is obtained by a random process from\ntwo DFA such that the language of the first one is included in the second one.\nThen when a word is accepted (resp. rejected) by the first (resp. second) one,\nit is also accepted (resp. rejected) and in the remaining cases, it is accepted\nwith probability 0.5. Our main experimental contributions consist in showing\nthat: (1) Angluin's algorithm behaves well whenever the noisy device is\nproduced by a random process, (2) but poorly with a structured noise, and, that\n(3) is able to eliminate pathological behaviours specified in a regular way.\nTheoretically, we show that randomness almost surely yields systems with\nnon-recursively enumerable languages.<\/jats:p>","DOI":"10.46298\/lmcs-20(1:22)2024","type":"journal-article","created":{"date-parts":[[2024,3,20]],"date-time":"2024-03-20T13:15:07Z","timestamp":1710940507000},"source":"Crossref","is-referenced-by-count":1,"title":["Analyzing Robustness of Angluin's L$^*$ Algorithm in Presence of Noise"],"prefix":"10.46298","volume":"Volume 20, Issue 1","author":[{"given":"Lina","family":"Ye","sequence":"first","affiliation":[]},{"given":"Igor","family":"Khmelnitsky","sequence":"additional","affiliation":[]},{"given":"Serge","family":"Haddad","sequence":"additional","affiliation":[]},{"given":"Beno\u00eet","family":"Barbot","sequence":"additional","affiliation":[]},{"given":"Benedikt","family":"Bollig","sequence":"additional","affiliation":[]},{"given":"Martin","family":"Leucker","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Neider","sequence":"additional","affiliation":[]},{"given":"Rajarshi","family":"Roy","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2024,3,20]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/13257\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/13257\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,20]],"date-time":"2024-03-20T13:15:07Z","timestamp":1710940507000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/11472"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,20]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(1:22)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2306.08266v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2306.08266v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2306.08266","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2306.08266","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2024,3,20]]},"article-number":"11472"}}