License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2023.21
URN: urn:nbn:de:0030-drops-182145
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18214/
Moeller, Mark ;
Wiener, Thomas ;
Solko-Breslin, Alaia ;
Koch, Caleb ;
Foster, Nate ;
Silva, Alexandra
Automata Learning with an Incomplete Teacher
Abstract
The preceding decade has seen significant interest in use of active learning to build models of programs and protocols. But existing algorithms assume the existence of an idealized oracle - a so-called Minimally Adequate Teacher (MAT) - that cannot be fully realized in practice and so is usually approximated with testing. This work proposes a new framework for active learning based on an incomplete teacher. This new formulation, called iMAT, neatly handles scenarios in which the teacher has access to only a finite number of tests or otherwise has gaps in its knowledge. We adapt Angluin’s L^⋆ algorithm for learning finite automata to incomplete teachers and we build a prototype implementation in OCaml that uses an SMT solver to help fill in information not supplied by the teacher. We demonstrate the behavior of our iMAT prototype on a variety of learning problems from a standard benchmark suite.
BibTeX - Entry
@InProceedings{moeller_et_al:LIPIcs.ECOOP.2023.21,
author = {Moeller, Mark and Wiener, Thomas and Solko-Breslin, Alaia and Koch, Caleb and Foster, Nate and Silva, Alexandra},
title = {{Automata Learning with an Incomplete Teacher}},
booktitle = {37th European Conference on Object-Oriented Programming (ECOOP 2023)},
pages = {21:1--21:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-281-5},
ISSN = {1868-8969},
year = {2023},
volume = {263},
editor = {Ali, Karim and Salvaneschi, Guido},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18214},
URN = {urn:nbn:de:0030-drops-182145},
doi = {10.4230/LIPIcs.ECOOP.2023.21},
annote = {Keywords: Finite Automata, Active Learning, SMT Solvers}
}
