Jan Martens: Circular words, Fibonacci words and it’s implication on partition refinement algorithms for bisimilarity

Event Details

In this talk we will consider deterministic finite automata(DFAs) with a singleton as alphabet. These rather restrictive machines have a strong connection with a very specific field of word combinatorics. In particular we will show how the periodicity of the bouncing DVD logo[1](or a billiard ball) is related to these automata and generate so-called Fibonacci words. These words form an interesting class of automata[2] that indicates that there might be more efficient methods to compute bisimilarity than the method of partition refinement.

[1] https://bouncingdvdlogo.com/

[2] “Hopcroft’s algorithm and cyclic automata”  – Castiglione, Restivo & Sciortino (2008)