Florian Bruse

Fabian Lehr, Florian Bruse

A formula of the modal mu-calculus enjoys finite convergence on a structure if there is some finite unfolding of the formula that defines the same set. A structure enjoys finite convergence if all formulas of the mu-calculus enjoy finite convergence on said structure. It is known that there are words that are not ultimately periodic, but have finite convergence. An almost-periodic word w is one in which each finite word v either appears only finitely often, or within each factor of some length that only depends only on w and v. It is immediate that words that have finite convergence must be almost periodic. In this paper we show the converse, namely that all almost-periodic words have finite convergence. This characterizes finite convergence on infinite words, and also re-proves a decidability result due to Semenov ('84).

Marco Sälzer, Eric Alsmann, Florian Bruse et al.

Verifying properties and interpreting the behaviour of deep neural networks (DNN) is an important task given their ubiquitous use in applications, including safety-critical ones, and their black-box nature. We propose an automata-theoric approach to tackling problems arising in DNN analysis. We show that the input-output behaviour of a DNN can be captured precisely by a (special) weak Büchi automaton and we show how these can be used to address common verification and interpretation tasks of DNN like adversarial robustness or minimum sufficient reasons.