The seminar takes place biweekly on Tuesdays at 15:00 Paris time. In summer, it means 6:00 in California, 9:00 in New-York or Waterloo, 14:00 in London, 15:00 in Paris, 16:00 in Moscow and 22:00 in Tokyo. In winter, some of these numbers change. Please check in advance the time in your time zone.

The address of the Zoom meeting is https://zoom.us/j/92245493528 . The password is distributed in announcements. If you want to receive them, or receive them and want to unsubscribe, please write to Anna Frid.

All recorded talks are also available here.

Anna E. Frid, Aix-Marseille Université, Narad Rampersad, University of Winnipeg, Jeffrey O. Shallit, University of Waterloo, Manon Stipulanti, Université de Liège.

If you are interested in giving a talk, you are welcome to contact Narad Rampersad and Manon Stipulanti.

April 30 2024: Michael Baake Hats, CAPs and Spectres

The recently discovered Hat is an aperiodic monotile for the Euclidean plane, which needs a reflected version for this property. The Spectre does not have this (tiny) deficiency. We discuss the topological and dynamical properties of the Hat tiling, how the CAP relates to it, and what the long-range order of both tilings is. Finally, we briefly describe the analogous structure for the Spectre tiling.

May 14 2024: Josef Rukavicka

May 28 2024: Pascal Ochem

June 11 2024: Markus Whiteland

June 25 2024: Julien Cassaigne

July 9 2024: Jamie Simpson

April 16 2024: Radosław Piórkowski Universal quantification in automatic structures—an ExpSpace-hard nut to crack

Automatic structures are structures whose universe and relations can be represented as regular languages. It follows from the standard closure properties of regular languages that the first-order theory of an automatic structure is decidable.

While existential quantifiers can be eliminated in linear time by application of a homomorphism, universal quantifiers are commonly eliminated via the identity ∀x. Φ ≡ ¬(∃x. ¬Φ). If Φ is represented in the standard way as an NFA, a priori this approach results in a doubly exponential blow-up. However, the recent literature has shown that there are classes of automatic structures for which universal quantifiers can be eliminated without this blow-up when treated as first-class citizens and not resorting to double complementation. The existing lower bounds for some classes of automatic structures show that a singly exponential blow-up is unavoidable when eliminating a universal quantifier, but it is not known whether there may be better approaches that avoid the naïve doubly exponential blow-up. We answer this question negatively.

In my talk, following a short introduction to the field of automatic structures, I will present the construction of a family of NFA representing automatic relations for which the minimal NFA recognising the language after a universal projection step is doubly exponential, and deciding whether this language is empty is ExpSpace-complete.

Based on the paper: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.13

Authors: Christoph Haase, R.P.

Keywords: automatic structures, universal projection, tiling problems, state complexity.

April 2 2024: John Campbell On the evaluation of infinite products involving automatic sequences

slides

We explore and discuss some recently introduced techniques concerning the evaluation of infinite products involving automatic sequences.

March 19 2024: Cor Kraaikamp An introduction to $N$-expansions with a finite set of digits

slides

In this talk $N$-expansions, and in particular $N$-expansions with a finite set of digits, will be introduced. Although $N$-expansions were introduced as recent as 2008 by Ed Burger and some of his students, quite a number of papers have appeared on these variations of the regular continued fraction expansion. By choosing a domain for the underlying Gauss-map which does not contain the origin, a continued fraction with finitely many digits was introduced by Niels Langeveld in his MSc-thesis. It turns out that these continued fraction algorithms exhibit a very complicated and surprising rich dynamical behavior.

This talk is based on joint work with Yufei Chen (Shanghai, Delft), Jaap de Jonge (UvA, Amsterdam), Karma Dajani (Utrecht), Niels Langeveld (Montan U., Leoben), Hitoshi Nakada (Keio, Yokohama), and Niels van der Wekken (Netcompany).

March 5 2024: Finn Lidbetter Improved bound for the Gerver-Ramsey collinearity problem

slides

Let $S$ be a finite subset of $\mathbb{Z}^n$. A vector sequence $(z_i)$ is an $S$-walk if and only if $z_{i+1}-z_i$ is an element of $S$ for all $i$. Gerver and Ramsey showed in 1979 that for $S\subset\mathbb{Z}^3$ there exists an infinite $S$-walk in which no $5^{11}+1=48,828,126$ points are collinear. Using the same general approach, but with the aid of a computer search, we show how to improve the bound to $189$. We begin by restating the infinite $S$-walk as the fixed point of iterating a morphism defined for a $12$ letter alphabet.

February 20 2024: Christopher Cabezas Large normalizer of odometers and higher-dimensional automatic sequences

slides

For a $\mathbb Z^d$ topological dynamical system $(X, T, \mathbb Z^d)$, an isomorphism is a self-homeomorphism $\phi : X\to X$ such that for some matrix $M \in GL(d, \mathbb Z)$ and any $n \in \mathbb Z^d$, $\phi \circ T^n = T^{M_n} \circ \phi$, where $T^n$ denote the self-homeomorphism of $X$ given by the action of $n \in \mathbb Z^d$. The collection of all the isomorphisms forms a group that is the normalizer of the set of transformations $T^n$. In the one-dimensional case isomorphisms correspond to the notion of flip conjugacy of dynamical systems and by this fact are also called reversing symmetries.

These isomorphisms are not well understood even for classical systems. In this talk we will present a description of them for odometers and more precisely for $\mathbb Z^2$-constant base odometers, that is not simple. We deduce a complete description of the isomorphism of some $\mathbb Z^2$ minimal substitution subshifts. Thanks to this, we will give the first known example of a minimal zero-entropy subshift with the largest possible normalizer group. This is a joint work with Samuel Petite (Universitè de Picardie Jules Verne).

February 6 2024: Eric Rowland Algebraic power series and their automatic complexity

slides

A theorem of Christol gives a characterization of automatic sequences over a finite field: a sequence is automatic if and only if its generating series is algebraic. Since there are two representations for such a sequence – as an automaton and as a bivariate polynomial – a natural question is how the size of one representation relates to the size of the other. Bridy used tools from algebraic geometry to bound the size of the minimal automaton in terms of the size of the minimal polynomial. We have a new proof of Bridy's bound that works by converting algebraic sequences to diagonals of rational functions. Crucially for our interests, this approach can be adapted to work not just over a finite field but over the integers modulo a prime power. This is joint work with Manon Stipulanti and Reem Yassawi.

January 23 2024: Jakub Konieczny Arithmetical subword complexity of automatic sequences

slides

It is well-known that the subword complexity of an automatic sequence grows at most linearly, meaning that the number of length-$\ell$ subwords which appear in a given automatic sequence $a = (a(n))_n$ is at most $C \ell$ for a constant $C$ dependent only on $a$. In contrast, arithmetic subword complexity measures the number of subwords which appear along arithmetic progressions, and can grow exponentially even for very simple automatic sequences. Indeed, the classical Thue-Morse sequence has arithmetic subword complexity $2^{\ell}$, which is the maximal possible complexity for $\{0,1\}$-valued sequence.

Together with Jakub Byszewski and Clemens Müllner we obtained a decomposition result which allows us to express any (complex-valued) automatic sequence as the sum of a structured part, which is easy to work with, and a part which is pseudorandom or uniform from the point of view of higher order Fourier analysis. We now apply these techniques to the study of arithmetic subword complexity of automatic sequences. We show that for each automatic sequence $a$ there exists a parameter $r$ — which we dub “effective alphabet size” — such that the arithmetic subword complexity of $a$ is at least $r^{\ell}$ and at most $(r+o(1))^{\ell}$.

This talk is based on joint work with Jakub Byszewski and Clemens Müllner, and is closely related to the previous talk of Clemens Müllner at One World Combinatorics on Words Seminar.

January 9 2024: Clemens Müllner Synchronizing automatic sequences along Piatetski-Shapiro sequences

slides

Automatic sequences - that is, sequences computable by finite automata - have long been studied from the point of view of combinatorics on words. A notable property of these sequences is that their subword-complexity is at most linear. Avgustinovich, Fon-Der-Flaass and Frid introduced the notion of arithmetic subword-complexity - that is the number of different subwords of length $n$ that appear along some arithmetic progression. They also showed that a special class of synchronizing automatic sequences have at most linear arithmetic subword-complexity and some other class of automatic sequences on the alphabet $\Sigma$ have maximal possible subword-complexity $|\Sigma|^n$.

Synchronizing automatic sequences can be efficiently approximated using periodic functions and are usually more structured than general automatic sequences. We discuss a recent result showing that the arithmetic (and even polynomial) subword-complexity of synchronizing automatic sequences grows subexponentially. This was a key result to show that the subword-complexity of synchronizing automatic sequences along regularly growing sequences (such as Piatetski-Shapiro sequences) grows subexponentially, which is in stark contrast to other automatic sequences such as the Thue-Morse sequence. Moreover, this was a key ingredient to obtain rather precise estimates for the arithmetic (and polynomial) subword-complexity of general automatic sequences.

This is joint work with Jean-Marc Deshouillers, Michael Drmota, Andrei Shubin and Lukas Spiegelhofer.

The talks of 2023 are available here.

The talks of 2022 are available here.

The talks of 2021 are available here.

The talks of 2020 are available here.

Several starting lectures by Anna Frid are available here.