DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
Rechercher
(titres de publication, de périodique et noms de colloque inclus)
2022-04-07 - Colloque/Article dans les actes avec comité de lecture - Anglais - 20 page(s) (A publier)

Bruyère Véronique , Pérez Guillermo, Staquet Gaëtan , "Learning Realtime One-Counter Automata" in International Conference on Tools and Algorithms for Construction and Analysis of Systems, Munich, Allemagne, 2022

  • Codes CREF : Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Informatique théorique (S829)
  • Instituts UMONS : Institut de Recherche en Technologies de l’Information et Sciences de l’Informatique (InforTech), Institut de Recherche sur les Systèmes Complexes (Complexys)
  • Centres UMONS : Modélisation mathématique et informatique (CREMMI)
Texte intégral :

Abstract(s) :

(Anglais) We present a new learning algorithm for realtime one-counter automata. Our algorithm uses membership and equivalence queries as in Angluin’s 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.


Mots-clés :
  • (Anglais) Active learning
  • (Anglais) Realtime one-counter automata