English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Analyzing Robustness of Angluin's L* Algorithm in Presence of Noise

Khmelnitsky, I., Haddad, S., Ye, L., Barbot, B., Bollig, B., Leucker, M., et al. (2022). Analyzing Robustness of Angluin's L* Algorithm in Presence of Noise. Electronic Proceedings in Theoretical Computer Science, 370, 81-96. doi:10.4204/EPTCS.370.6.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/21.11116/0000-000B-5E54-E Version Permalink: https://hdl.handle.net/21.11116/0000-000B-5E5A-8
Genre: Journal Article

Files

show Files
hide Files
:
arXiv:2209.10315.pdf (Preprint), 672KB
View   Save
File Permalink:
https://hdl.handle.net/21.11116/0000-000B-5E56-C
Name:
arXiv:2209.10315.pdf
Description:
File downloaded from arXiv at 2022-11-03 13:55
OA-Status:
Not specified
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
http://creativecommons.org/licenses/by/4.0/

Locators

show

Creators

show
hide
 Creators:
Khmelnitsky, Igor1, Author
Haddad, Serge1, Author
Ye, Lina1, Author
Barbot, Benoît1, Author
Bollig, Benedikt1, Author
Leucker, Martin1, Author
Neider, Daniel1, Author           
Roy, Rajarshi2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Group R. Majumdar, Max Planck Institute for Software Systems, Max Planck Society, ou_2105292              

Content

show
hide
Free keywords: Computer Science, Formal Languages and Automata Theory, cs.FL,Computer Science, Artificial Intelligence, cs.AI
 Abstract: Angluin's L* algorithm learns the minimal (complete) deterministic finite
automaton (DFA) of a regular language using membership and equivalence queries.
Its probabilistic approximatively correct (PAC) version substitutes an
equivalence query by a large enough set of random membership queries to get a
high level confidence to the answer. Thus it can be applied to any kind of
(also non-regular) device and may be viewed as an algorithm for synthesizing an
automaton abstracting the behavior of the device based on observations. Here we
are interested on how Angluin's PAC learning algorithm behaves for devices
which are obtained from a DFA by introducing some noise. More precisely we
study whether Angluin's algorithm reduces the noise and produces a DFA closer
to the original one than the noisy device. We propose several ways to introduce
the noise: (1) the noisy device inverts 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 word before asking its classification w.r.t. the
DFA, and (3) the noisy device combines the classification of a word w.r.t. the
DFA and its classification w.r.t. a counter automaton. Our experiments were
performed on several hundred DFAs.
Our main contributions, bluntly stated, consist in showing that: (1)
Angluin's algorithm behaves well whenever the noisy device is produced by a
random process, (2) but poorly with a structured noise, and, that (3) almost
surely randomness yields systems with non-recursively enumerable languages.

Details

show
hide
Language(s): eng - English
 Dates: 2022-09-212022
 Publication Status: Published online
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 2209.10315
DOI: 10.4204/EPTCS.370.6
BibTex Citekey: KhmelnitskyGandALF22
URI: https://arxiv.org/abs/2209.10315v1
URI: https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?GandALF2022.6
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Electronic Proceedings in Theoretical Computer Science
  Abbreviation : EPTCS
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 370 Sequence Number: - Start / End Page: 81 - 96 Identifier: ISSN: 2075-2180

Source 2

show
hide
Title: Proceedings of the 13th International Symposium on Games, Automata, Logics and Formal Verification
  Abbreviation : GandALF 2022
  Subtitle : Madrid, Spain, September 21-23, 2022
Source Genre: Proceedings
 Creator(s):
Ganty, Pierre1, Editor
Della Monica, Dario1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -