Supervisors

Suitable for

Abstract

There are several projects available on the theme “Automata Cascades”. Please get in touch for the most up-to-date information.

Automata Cascades are a modular, structured way to represent automata. An automaton is seen as consisting of many simpler automata that interact with each other. Fundamental results establish that large classes of automata can be expressed as cascades of very simple components. Please see the reference below for an introduction to the formalism.

There are projects focusing on:

(i) expressivity of classes of automata cascades,

(ii) computational complexity of decision problems for automata cascades,

(iii) learning automata cascades—complexity results and learning algorithms.

The specific topic will be identified together with the candidate, based on the candidate’s interests and background.

Reference:

Alessandro Ronca, Nadezda Alexandrovna Knorozova, Giuseppe De Giacomo: Automata Cascades: Expressivity and Sample Complexity. AAAI 2023

Pre-requisites: Some familiarity with automata. Familiarity with Complexity theory and Computational Learning Theory might be needed depending on the focus of the project