Computer Science Seminar
Speaker: Sayan Mukherjee, Université Libre de Bruxelles, Belgium
Date: Thursday, 1 August 2024
Time: 2:00 PM
Venue: Lecture Hall 4
Greybox Learning of Languages Recognizable by Event-Recording Automata
Sayan Mukherjee
Université Libre de Bruxelles, Belgium.
01-08-24

---

Abstract

Given a (timed/untimed) language over finite words, inferring an automaton that recognizes the target language, is an active area of research. Broadly, there are two frameworks for learning various classes of automata -- (i) active learning, where the learner makes queries to a teacher, and (ii) passive learning, where the learner is instead provided with a labelled (positive and negative) set of examples. In this talk, we revisit the active learning of timed languages recognizable by Event-Recording Automata (ERA) -- a determinizable subclass of Timed Automata. Our framework employs a method known as greybox learning, which enables the learning of ERA with a minimal number of control states. This approach avoids learning the region automaton associated with the language, contrasting with existing methods. We have implemented our greybox learning algorithm with some heuristics that maintain low computational complexity. We will demonstrate how our algorithm works through some examples. This is a joint work with Anirban Majumdar and Jean-François Raskin.