Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
start [2024/02/27 13:40] – 139.124.146.3start [2024/04/30 22:51] (current) – 139.124.146.3
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//
  
 +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$.
  
-**March 5 2024: [[https://finnlidbetter.com/|Finn Lidbetter]]** //Improved bound for the Gerver-Ramsey collinearity problem//+https://arxiv.org/abs/2312.10061
  
-Let $S$ be a finite subset of $\mathbb{Z}^n$. A vector +**May 28 2024: [[https://www.lirmm.fr/~ochem/|Pascal Ochem]]** 
-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 +**June 11 2024: [[https://mwhiteland.github.io/|Markus Whiteland]]** 
-$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 +**June 25 2024: [[http://iml.univ-mrs.fr/~cassaign/|Julien Cassaigne]]** 
-approach, but with the aid of a computer search, we show how to + 
-improve the bound to $189$. We begin by restating the infinite +**July 9 2024: [[https://scholar.google.com.au/citations?user=C_02gXUAAAAJ&hl=en|Jamie Simpson]]** 
-$S$-walk as the fixed point of iterating a morphism defined for a $12$ + 
-letter alphabet.+ 
 +==== 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// **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. 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}}
  
-**June 11 2024: [[https://mwhiteland.github.io/|Markus Whiteland]]** 
  
-**July 9 2024: [[https://scholar.google.com.au/citations?user=C_02gXUAAAAJ&hl=en|Jamie Simpson]]**+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).
  
-==== Past talks 2024 ====+**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.