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)
2021-10-18 - Travail sans promoteur/Travail de séminaire / Working Papers - Anglais - page(s)

Bruyère Véronique , Pérez Guillermo, Staquet Gaëtan , "Learning Realtime One-Counter Automata", 2021-10-18

  • 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)

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.

Identifiants :
  • arXiv : 2110.09434

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