Gastvortrag: Dana Fisman: Learning languages of infinite words

Dienstag, 16.11.2021, 11.00 Uhr

Ort: Online Session

Vortragende: Dana Fisman

 

Abstract: 

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.

 

https://rwth.zoom.us/j/92047949381?pwd=LzIwUW96WEM0MkRjZ01FUmhwd1I3QT09

Meeting ID: 920 4794 9381
Password: unravel