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.CSL.2022.21
URN: urn:nbn:de:0030-drops-157412
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15741/
Fisman, Dana ;
Frenkel, Hadar ;
Zilles, Sandra
Inferring Symbolic Automata
Abstract
We study the learnability of symbolic finite state automata, a model shown useful in many applications in software verification. The state-of-the-art literature on this topic follows the query learning paradigm, and so far all obtained results are positive. We provide a necessary condition for efficient learnability of SFAs in this paradigm, from which we obtain the first negative result. The main focus of our work lies in the learnability of SFAs under the paradigm of identification in the limit using polynomial time and data. We provide a necessary condition and a sufficient condition for efficient learnability of SFAs in this paradigm, from which we derive a positive and a negative result.
BibTeX - Entry
@InProceedings{fisman_et_al:LIPIcs.CSL.2022.21,
author = {Fisman, Dana and Frenkel, Hadar and Zilles, Sandra},
title = {{Inferring Symbolic Automata}},
booktitle = {30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
pages = {21:1--21:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-218-1},
ISSN = {1868-8969},
year = {2022},
volume = {216},
editor = {Manea, Florin and Simpson, Alex},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15741},
URN = {urn:nbn:de:0030-drops-157412},
doi = {10.4230/LIPIcs.CSL.2022.21},
annote = {Keywords: Symbolic Finite State Automata, Query Learning, Characteristic Sets}
}
Keywords: |
|
Symbolic Finite State Automata, Query Learning, Characteristic Sets |
Collection: |
|
30th EACSL Annual Conference on Computer Science Logic (CSL 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
27.01.2022 |