LIPIcs.MFCS.2022.74.pdf
- Filesize: 0.69 MB
- 16 pages
We study the problem of active learning deterministic visibly pushdown automata. We show that in the classical L^*-setting, efficient active learning algorithms are not possible. To overcome this difficulty, we propose the accessible stack setting, where the algorithm has the read and write access to the stack. In this setting, we show that active learning can be done in polynomial time in the size of the target automaton and the counterexamples provided by the teacher. As counterexamples of exponential size are inevitable, we consider an algorithm working with words in a compressed representation via (visibly) Straight-Line Programs. Employing compression allows us to obtain an algorithm where the teacher and the learner work in time polynomial in the size of the target automaton alone.
Feedback for Dagstuhl Publishing