(2022) Inferring Symbolic Automata.
In: CSL.
Conference:
CSL Annual Conference on Computer Science Logic
|
Text
Inferring Symbolic Automata.pdf Download (1MB) | Preview |
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.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Bernd Finkbeiner (Reactive Systems Group, RSG) |
| Conference: | CSL Annual Conference on Computer Science Logic |
| Depositing User: | Hadar Frenkel |
| Date Deposited: | 06 May 2022 07:01 |
| Last Modified: | 06 May 2022 08:19 |
| Primary Research Area: | NRA2: Reliable Security Guarantees |
| URI: | https://publications.cispa.saarland/id/eprint/3562 |
Actions
Actions (login required)
 |
View Item |