Open Access 2022 | OriginalPaper | Chapter
Learning Realtime One-Counter Automata
Authors : Véronique Bruyère, Guillermo A. Pérez, Gaëtan Staquet
Published in: Tools and Algorithms for the Construction and Analysis of Systems
Publisher: Springer International Publishing
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.