Differences

This shows you the differences between two versions of the page.

--- start [2024/01/24 09:13] – 139.124.146.3
+++ start [2024/04/30 22:51] (current) – 139.124.146.3
@@ Line 15: / Line 15: @@
 [[http://ion.uwinnipeg.ca/~nrampers/|Narad Rampersad]], University of Winnipeg,
 [[https://cs.uwaterloo.ca/~shallit/|Jeffrey O. Shallit]], University of Waterloo,
-[[https://sites.google.com/view/manonstipulanti/|Manon Stipulanti]], Université de Liège.
+[[https://www.manon-stipulanti.be/|Manon Stipulanti]], Université de Liège.
 If you are interested in giving a talk, you are welcome to contact Narad Rampersad and Manon Stipulanti.
@@ Line 23: / Line 23: @@
+**May 14 2024: [[https://dblp.org/pid/10/10715.html|Josef Rukavicka]]** //Restivo Salemi property for $\alpha$-power free languages with $\alpha \geq 5$ and $k \geq 3$ letters//
-**February 6 2024: Eric Rowland/Reem Yassawi/Manon Stipulanti**
+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,\alpha}$ denote an $\alpha$-power free language over an alphabet with $k$ letters, where $\alpha$ is a positive rational number and $k$ is positive integer. We prove the conjecture for the languages $L_{k,\alpha}$, where $\alpha\geq 5$ and $k \geq 3$.
-**February 20 2024: [[https://www.uliege.be/cms/c_9054334/fr/repertoire?uid=u240328|Christopher Cabezas]]**
+https://arxiv.org/abs/2312.10061
-**March 5 2024: [[https://finnlidbetter.com/|Finn Lidbetter]]**
+**May 28 2024: [[https://www.lirmm.fr/~ochem/|Pascal Ochem]]**
+**June 11 2024: [[https://mwhiteland.github.io/|Markus Whiteland]]**
+**June 25 2024: [[http://iml.univ-mrs.fr/~cassaign/|Julien Cassaigne]]**
+**July 9 2024: [[https://scholar.google.com.au/citations?user=C_02gXUAAAAJ&hl=en|Jamie Simpson]]**
+==== Past talks 2024 ====
+**April 30 2024: [[https://www.math.uni-bielefeld.de/baake/|Michael Baake]]** //Hats, CAPs and Spectres//
+{{ seminar2024:20240430baake.pdf |slides}}
+{{ seminar2024:20240430baake.mp4 |video of the talk}}
+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.
+**April 16 2024: [[https://dblp.org/pid/215/5120.html|Radosław Piórkowski]]** //Universal quantification in automatic structures—an ExpSpace-hard nut to crack//
+{{ seminar2024:20240416piorkowski.mp4 |video of the talk}}
+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.
-**March 19 2024: [[https://diamweb.ewi.tudelft.nl/~cork/|Cor Kraaikamp]]**
 **April 2 2024: John Campbell** // On the evaluation of infinite products involving automatic sequences//
+{{ seminar2024:20240402campbell.pdf |slides}}
+{{ seminar2024:20240402campbell.mp4 |video of the talk}}
 We explore and discuss some recently introduced techniques concerning the evaluation of infinite products involving automatic sequences.
-**April 16 2024: [[https://dblp.org/pid/215/5120.html|Radosław Piórkowski]]**
-**April 30 2024: [[https://www.math.uni-bielefeld.de/baake/|Michael Baake]]**
+**March 19 2024: [[https://diamweb.ewi.tudelft.nl/~cork/|Cor Kraaikamp]]** //An introduction to $N$-expansions with a finite set of digits//
-**May 14 2024: [[https://dblp.org/pid/10/10715.html|Josef Rukavicka]]**
+{{ seminar2024:20240319kraaikamp.pdf |slides}}
-**May 28 2024: [[https://www.lirmm.fr/~ochem/|Pascal Ochem]]**
+{{ seminar2024:20240319kraaikamp.mp4 |video of the talk}}
+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: [[https://finnlidbetter.com/|Finn Lidbetter]]** //Improved bound for the Gerver-Ramsey collinearity problem//
+{{ seminar2024:20240305lidbetter.pdf |slides}}
+{{ seminar2024:20240305lidbetter.mp4 |video of the talk}}
+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: [[https://www.uliege.be/cms/c_9054334/fr/repertoire?uid=u240328|Christopher Cabezas]]** //Large normalizer of odometers and higher-dimensional automatic sequences//
+{{ seminar2024:20240220cabezas.pdf |slides}}
+{{ seminar2024:20240220cabezas.mp4 |video of the talk}}
+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: [[https://ericrowland.github.io/|Eric Rowland]]** //Algebraic power series and their automatic complexity//
+{{ seminar2024:20240206rowland.pdf |slides}}
+{{ seminar2024:20240206rowland.mp4 |video of the talk}}
+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.
-**June 11 2024: [[https://mwhiteland.github.io/|Markus Whiteland]]**
-==== Past talks 2024 ====
 **January 23 2024: [[https://jakubmichalkonieczny.wordpress.com/|Jakub Konieczny]]** //Arithmetical subword complexity of automatic sequences//