Survey Lecture: Christof Löding: Learning Automata for Infinite Words

Thursday, May 06, 2021, 4:30pm

Speaker: Christof Löding


Learning Automata for Infinite Words

Learning techniques for deterministic finite automata (DFA) have been developed starting from the 1970ies. The two main settings are the construction of DFA from examples (finite sets of words that should be accepted or rejected by the DFA), and from queries to an oracle. These problems are already well understood for DFA, and various learning algorithms for these two settings exist.

Deterministic automata on infinite words define languages of infinite words, and are syntactically very similar to DFA. However, certain key properties of DFA that are used in learning algorithms do not hold for automata on infinite words. Therefore, only few results for learning automata over infinite words have been obtained up to now.

In this talk, I will illustrate these differences and report on ongoing joint work with Leon Bohn on algorithms for the construction of deterministic automata on infinite words from examples.


The talks of the UnRAVeL survey lecture 2021 will be given via Zoom every Thursday from 16:30 to 18:00:


Meeting ID: 960 4371 5437

Passcode: 039217