Learning Realtime One-Counter Automata
- Open Access
- 2022
- OriginalPaper
- Buchkapitel
Erschienen in:
- Verfasst von
- Véronique Bruyère
- Guillermo A. Pérez
- Gaëtan Staquet
- Verlag
- Springer International Publishing
Zusammenfassung
We present a new learning algorithm for realtime one-counter automata. Our algorithm uses membership and equivalence queries as in Angluin’s $${L}^*$$ L ∗ algorithm, as well as counter value queries and partial equivalence queries. In a partial equivalence query, we ask the teacher whether the language of a given finite-state automaton coincides with a counter-bounded subset of the target language. We evaluate an implementation of our algorithm on a number of random benchmarks and on a use case regarding efficient JSON-stream validation.
- Titel
- Learning Realtime One-Counter Automata
- Verfasst von
-
Véronique Bruyère
Guillermo A. Pérez
Gaëtan Staquet
- Copyright-Jahr
- 2022
- Buch
-
Tools and Algorithms for the Construction and Analysis of Systems
Print ISBN: 978-3-030-99523-2
Electronic ISBN: 978-3-030-99524-9
Copyright-Jahr: 2022
- DOI
- https://doi.org/10.1007/978-3-030-99524-9_13
