Guest Talk: Dana Fisman: Learning languages of infinite words

Tuesday, November 16, 2021, 11:00am

Location: Online Session

Speaker: Dana Fisman



The problem of inferring an automaton model of a black box system has found many applications in formal methods of system design. If the black-box system implements (or can be abstracted as) a regular language of finite words, it can be inferred in polynomial time using query learning. In this talk we'll discuss the problem we face when the black-box system implements a regular language of infinite words (e.g.the black-box is a reactive system).

While there are automata processing infinite words e.g. (Buechiautomata) that have the same structure as automata on finite words (DFAs), learning them seems to be a much harder problem. During the talk we will get acquainted with the ideas behind learning algorithms for regular languages, the obstacles in devising learning algorithms for regular languages of infinite words, and state-of-the-art results on learnability of acceptors of regular languages of infinite words.

Meeting ID: 920 4794 9381
Password: unravel