Hans Zantema: Computation of complexity of automatic sequences

Event Details

In an earlier talk the complexity of an automatic sequence was presented as the minimal size of an automaton describing the sequence. More precisely, the n-th element of the binary sequence is 1 if and only if the binary representation of n is accepted by the automaton. On this notion some main properties were investigated. In the meantime a paper on this work has been accepted for the LATA 2020 conference, and was honored by the best paper award. After a recap of the main notions and properties, in this talk the focus will be on how to compute the corresponding minimal automaton automatically from a prefix of the sequence, by means of SMT solving, and on criteria on how long this prefix should be.