Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
start [2024/01/12 22:33] – 139.124.146.3 | start [2024/04/30 22:51] – 139.124.146.3 | ||
---|---|---|---|
Line 15: | Line 15: | ||
[[http:// | [[http:// | ||
[[https:// | [[https:// | ||
- | [[https://sites.google.com/ | + | [[https://www.manon-stipulanti.be/|Manon Stipulanti]], |
If you are interested in giving a talk, you are welcome to contact Narad Rampersad and Manon Stipulanti. | If you are interested in giving a talk, you are welcome to contact Narad Rampersad and Manon Stipulanti. | ||
Line 23: | Line 23: | ||
- | **January 23 2024: [[https://jakubmichalkonieczny.wordpress.com/|Jakub Konieczny]]** //Arithmetical subword complexity of automatic sequences// | + | **May 14 2024: [[https://dblp.org/pid/ |
- | **February 6 2024: Eric Rowland/ | + | In 2009, Shur published the following conjecture: Let $L$ be a power-free language and let $e(L)\subseteq L$ be the set of words of $L$ that can be extended to a bi-infinite word respecting the given power-freeness. If $u,v \in e(L)$ then $uwv \in e(L)$ for some word $w$. Let $L_{k, |
- | **February 20 2024: [[https://www.uliege.be/cms/c_9054334/ | + | https://arxiv.org/abs/2312.10061 |
- | **March 5 2024: [[https://finnlidbetter.com/|Finn Lidbetter]]** | + | **May 28 2024: [[https://www.lirmm.fr/ |
- | **March 19 2024: [[https://diamweb.ewi.tudelft.nl/ | + | **June 11 2024: [[https://mwhiteland.github.io/|Markus Whiteland]]** |
- | **April 2 2024: John Campbell** | + | **June 25 2024: [[http://iml.univ-mrs.fr/~cassaign/|Julien Cassaigne]]** |
- | We explore and discuss some recently introduced techniques concerning the evaluation of infinite products involving automatic sequences. | + | **July 9 2024: [[https:// |
- | **April 16 2024: [[https:// | ||
- | |||
- | **April 30 2024: [[https:// | ||
- | |||
- | **May 14 2024: [[https:// | ||
- | |||
- | **May 28 2024: [[https:// | ||
==== Past talks 2024 ==== | ==== Past talks 2024 ==== | ||
- | **January 9 2024: [[https:// | ||
- | {{ seminar2024:20240109muellner.pdf |slides}} | + | **April 30 2024: [[https:// |
- | {{ seminar2024: | + | {{ seminar2024: |
+ | {{ seminar2024: | ||
- | 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 | + | The recently discovered Hat is an aperiodic |
- | 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$. | + | monotile for the Euclidean plane, which needs a reflected |
+ | version for this property. The Spectre does not have this | ||
+ | (tiny) deficiency. We discuss | ||
+ | properties | ||
+ | what the long-range order of both tilings | ||
+ | briefly describe | ||
- | 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, | ||
- | This is joint work with Jean-Marc Deshouillers, | ||
- | ==== Past talks 2023 ==== | + | **April 16 2024: [[https:// |
- | **December 19 2023: [[https:// | + | {{ seminar2024:20240416piorkowski.mp4 |video of the talk}} |
- | {{ seminar2023: | + | 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. |
- | {{ seminar2023: | + | While existential quantifiers can be eliminated in linear time by application of a homomorphism, |
+ | We answer this question negatively. | ||
- | In the enchanting realm of CoWLand, where computer science wizards and mathematics enchanters gather via the magic of the Internet, a whimsical elf embarks us on a yuletide adventure. Our quest? To detect Sturmian words hidden in the snowy languages | + | In my talk, following |
- | I start from weak ω-automata, | ||
+ | Based on the paper: https:// | ||
- | **December 5 2023: [[https:// | + | Authors: Christoph Haase, R.P. |
- | {{ seminar2023:20231205rosenfeld.pdf |slides}} | + | Keywords: automatic structures, universal projection, tiling problems, state complexity. |
- | {{ seminar2023: | ||
+ | **April 2 2024: John Campbell** // On the evaluation of infinite products involving automatic sequences// | ||
- | I will present some results that we recently obtained about word | + | {{ seminar2024:20240402campbell.pdf |slides}} |
- | reconstruction problems. In this setting you can ask queries from a | + | |
- | fixed family of queries about an unknown word $W$ and your goal is to | + | |
- | reconstruct $W$ by asking the least possible number of queries. We study | + | |
- | the question for 3 different families of queries: | + | |
- | - "How many occurrences of $u$ in $W$ as a factor?", | + | |
- | - "How many occurrences of $u$ in $W$ as a subword?", | + | |
- | - "Does $u$ occur in $W$ as a subword?", | + | |
- | Each of these cases had already been studied, and we improve | + | {{ seminar2024: |
- | bounds for each of them. | + | |
- | In particular, in the second case, you can ask queries about the | + | |
- | number of occurrences of any given subword. Fleischmann, | + | |
- | Manea, Nowotka and Rigo gave an algorithm that reconstructs any | + | |
- | binary word $W$ of length $n$ in at most $n/2 +1$ queries. We prove that | + | |
- | $O((n log n)^{(1/2)})$ queries suffice. In this talk, I will provide a few | + | |
- | necessary definitions and present our results. | + | |
- | This is joint work with Gwenaël Richomme. | ||
+ | We explore and discuss some recently introduced techniques concerning the evaluation of infinite products involving automatic sequences. | ||
- | **November 21 2023: [[https:// | ||
- | sparse automatic sets// | ||
- | {{ seminar2023:20231121albayrak.pdf |slides}} | + | **March 19 2024: [[https:// |
- | {{ seminar2023:20231121albayrak.mp4 |video of the talk}} | + | {{ seminar2024:20240319kraaikamp.pdf |slides}} |
+ | {{ seminar2024: | ||
- | In 1979, Erdős conjectured that for $k \ge 9$, $2^k$ is | ||
- | not the sum of distinct powers of $3$. That is, the set of powers of | ||
- | two (which is $2$-automatic) and the $3$-automatic set consisting of | ||
- | numbers whose ternary expansions omit $2$ has finite intersection. A | ||
- | theorem of Cobham (1969) says that if $k$ and $\ell$ are two | ||
- | multiplicatively independent natural numbers then a subset of the | ||
- | natural numbers that is both $k$- and $\ell$-automatic is eventually | ||
- | periodic. | ||
- | given by Semenov (1977). | ||
- | light of Cobham’s theorem, we give a quantitative version of the | ||
- | Cobham-Semenov theorem for sparse automatic sets, showing that the | ||
- | intersection of a sparse $k$-automatic subset of $\mathbb{N}^d$ and a | ||
- | sparse $\ell$-automatic subset of $\mathbb{N}^d$ is finite. Moreover, | ||
- | we give effectively computable upper bounds on the size of the | ||
- | intersection in terms of data from the automata that accept these | ||
- | sets. | ||
+ | In this talk $N$-expansions, | ||
+ | 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. | ||
- | **November 7 2023: [[https:// | + | 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). | ||
- | {{ seminar2023:20231107-puzynina.pdf |slides}} | + | **March 5 2024: [[https:// |
- | {{ seminar2023:20231107-puzynina.mp4 |video of the talk}} | + | {{ seminar2024:20240305lidbetter.pdf |slides}} |
+ | {{ seminar2024: | ||
- | We say that an infinite word $u$ on a $d$-ary alphabet has the well distributed occurrences | ||
+ | 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, | ||
+ | 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. | ||
- | **October 24 2023: [[https:// | ||
- | {{ seminar2023:20231024goulet-ouellet.pdf |slides}} | + | **February 20 2024: [[https:// |
- | {{ seminar2023:20231024goulet-ouellet.mp4 |video of the talk}} | + | {{ seminar2024:20240220cabezas.pdf |slides}} |
+ | {{ seminar2024: | ||
- | The notion of density for languages was studied by Schützenberger in the 60s and by Hansel and Perrin in the 80s. In both cases, the authors focused on densities defined by Bernoulli measures. In this talk, I will present new results about densities of regular languages under invariant measures of minimal shift spaces. We introduce a compatibility condition which implies convergence of the density to a constant which depends only on the given rational language. This result can be seen as a form of equidistribution property. The compatibility condition can be stated either in terms of return words or of a skew product. The passage between the two forms is made more transparent using simple combinatorial tools inspired by ergodic theory and cohomology. This is joint work with Valérie Berthé, Carl-Fredrik Nyberg Brodda, Dominique Perrin and Karl Petersen. | ||
+ | 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). | ||
- | **October 10 2023: [[https:// | ||
- | {{ seminar2023: | ||
- | {{ seminar2023:20231010dvorakova.mp4 |video of the talk}} | + | **February 6 2024: [[https:// |
- | In this contribution we carry on a study of string attractors of important classes of sequences. | + | {{ seminar2024:20240206rowland.pdf |slides}} |
- | Attractors of minimum size of factors/ | + | |
- | Recently, string attractors in fixed points of k-bonacci-like morphisms have been described (Gheeraert, Romana, Stipulanti, 2023). | + | |
- | In our talk we aim to present the following results: | + | {{ seminar2024:20240206rowland.mp4 |video |
- | Using the fact that standard Sturmian sequences may be obtained when iterating palindromic closure, we were able to find attractors of minimum size of all factors of Sturmian sequences. These attractors were different from the ones found for prefixes by Mantaci et al. It was then straightforward to generalize the result to factors of episturmian sequences. | + | |
- | Observing usefullness of palindromic closures when dealing with attractors, we turned our attention to pseudopalindromic prefixes | + | |
+ | 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' | ||
- | **September 26 2023: | ||
- | for the Fibonacci morphism// | ||
- | {{ seminar2023: | ||
- | {{ seminar2023:20230926currie.mp4 |video of the talk}} | + | **January 23 2024: [[https:// |
- | The Thue-Morse morphism is the binary map $\mu: 0 \to 01, 1 \to 10$. A word $w$ is | + | {{ seminar2024:20240123konieczny.pdf |slides}} |
- | overlap-free if it has no factor of the form $xyxyx$, where $x$ is | + | |
- | non-empty. A deep connection between these two concepts is the engine | + | |
- | behind several results: | + | |
- | - The precise characterization | + | {{ seminar2024: |
- | overlap-free binary words (Fife’s Theorem); | + | |
- | - A precise enumeration of overlap-free binary words; | ||
- | - A characterization | + | It is well-known that the subword complexity |
- | Thue-Morse | + | |
- | - The determination | + | 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 " |
- | overlap-free word. | + | |
- | Given another morphism, is there an analog of overlap-freeness which | + | 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. |
- | facilitates | + | |
- | yes for the period doubling morphism $\delta :0 \to 01, 1\to 00$, and for the | + | |
- | Fibonacci morphism $\varphi :0\to 01, 1\to 0$. | + | |
+ | **January 9 2024: [[https:// | ||
- | ** September 12 2023:** **[[https:// | + | {{ seminar2024:20240109muellner.pdf |slides}} |
- | {{ seminar2023:20230912espinoza.pdf |slides}} | + | {{ seminar2024:20240109muellner.mp4 |video of the talk}} |
- | {{ seminar2023: | ||
- | In the context of symbolic dynamics, the class of " | + | 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 |
+ | They also showed that a special class of synchronizing automatic sequences have at most linear | ||
+ | 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, | ||
- | **May 15 2023: [[https:// | + | This is joint work with Jean-Marc Deshouillers, Michael Drmota, Andrei Shubin |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | + | ||
- | A set of shapes is called aperiodic if the shapes admit tilings of | + | |
- | the plane, but none that have translational symmetry. | + | |
- | open problem asks whether a set consisting of a single shape could | + | |
- | be aperiodic; such a shape is known as an aperiodic monotile or | + | |
- | | + | |
- | | + | |
- | | + | |
- | | + | |
- | | + | |
- | + | ||
- | Full disclosure: this is the same title and abstract that I just sent to Kevin Hare for the Numeration seminar the week before (May 9th). I expect that the talks will be largely the same, but if I have a chance to incorporate any connections to combinatorics on words into my talk for you, I will. | + | |
- | + | ||
- | + | ||
- | **May 8 2023: [[https:// | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | + | ||
- | + | ||
- | Perfectly clustering words are special factors in trajectories of discrete interval exchange transformation with symmetric permutation. If the discrete interval exchange transformation has two intervals, they are Christoffel words. Therefore, perfectly clustering words are a natural generalization of Christoffel words. In this talk, an induction on discrete interval exchange transformation with symmetric permutation will be presented. | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | ** April 3 2023: [[https:// | + | |
- | + | ||
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | + | ||
- | Additive number theory | + | |
- | Surprisingly, | + | |
- | results in this area. | + | |
- | In this talk I will discuss the number of representations of an integer N as | + | |
- | a sum of elements from some famous sets, such as the evil numbers, the | + | |
- | odious | + | |
- | numbers, the Rudin-Shapiro numbers, Wythoff sequences, etc. | + | |
- | + | ||
- | ** Mar 27 2023: [[https:// | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | + | ||
- | The set of morphisms mapping any Sturmian sequence to a Sturmian sequence forms together with composition the so-called monoid of Sturm. | + | |
- | alternative proofs of four known results on Sturmian sequences fixed by a primitive morphism and a new result concerning the square root of a Sturmian sequence. | + | |
- | + | ||
- | + | ||
- | + | ||
- | ** Mar 6 2023: Léo Poirier and [[https:// | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | {{ 20230306poirier_steiner.mp4 |video of the talk}} | + | |
- | + | ||
- | + | ||
- | + | ||
- | A set of words, also called a language, is letter-balanced if the number of occurrences of each letter only depends on the length of the word, up to a constant. Similarly, a language is factor-balanced if the difference of the number of occurrences of any given factor in words of the same length is bounded. The most prominent example of a letter-balanced but not factor-balanced language is given by the Thue-Morse sequence. We establish connections between the two notions, in particular for languages given by substitutions and, more generally, by sequences of substitutions. We show that the two notions essentially coincide when the sequence of substitutions is proper. For the example of Thue-Morse-Sturmian languages, we give a full characterisation of factor-balancedness. | + | |
- | + | ||
- | + | ||
- | + | ||
- | ** Feb 27 2023: [[https:// | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | + | ||
- | In this talk, we present some of the links between combinatorial games and language theory. A combinatorial game is a 2-player game with no chance and with perfect information. Amongst them, the family of heap games such as the game of Nim, subtraction or octal games belong to the the most studied ones. Generally, the analysis of such games consist in determining which player has a winning strategy. We will first see how this question is investigated in the case of heap games. | + | |
- | + | ||
- | In a second part of the talk, we will present a generalization of heap games as rewrite games on words. This model was introduced by Waldmann in 2002. Given a finite alphabet | + | |
- | + | ||
- | + | ||
- | + | ||
- | ** Feb 6 2023: Matthew Konefal** //Examining the Class of Formal Languages which are Expressible via Word Equations// | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | A word equation can be said to express a formal language via each variable occurring in it. The class $WE$ of formal languages which can be expressed in this way is not well understood. I will discuss | + | |
- | + | ||
- | + | ||
- | ** Jan 23 2023: [[https:// | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | {{ seminar2023: | + | |
- | + | ||
- | + | ||
- | + | ||
- | At first, we will summarize both the history and the state of the art of the critical exponent and the asymptotic critical exponent of balanced sequences. | + | |
- | Second, we will colour the Fibonacci sequence by suitable constant gap sequences to provide an upper bound on the asymptotic repetitive threshold of $d$-ary balanced sequences. The bound is attained for $d$ equal to $2$, $4$ and $8$ and we conjecture that it happens for infinitely many even $d$'s. | + | |
- | Finally, we will reveal an essential difference in behavior of the repetitive threshold and the asymptotic repetitive threshold of balanced sequences: The repetitive threshold of $d$-ary | + | |
- | + | ||
- | Joint work with Edita Pelantová. | + | |
- | + | ||
- | + | ||
- | ** Jan 9: [[https:// | + | |
- | Determining the index of the Simon congruence is a long outstanding open problem. Two words $u$ and $v$ are called Simon congruent if they have the same set of scattered factors, which are parts of the word in the correct order but not necessarily consecutive, | + | ==== Archives 2023 ==== |
- | {{ seminar2023: | + | The talks of 2023 are available [[2023|here]]. |
- | {{ seminar2023: | ||