Differences

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

--- start [2024/04/03 12:33] – 139.124.146.3
+++ start [2024/04/30 14:50] – 139.124.146.3
@@ Line 22: / Line 22: @@
 ==== Upcoming talks ====
-**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]]**
+**April 30 2024: [[https://www.math.uni-bielefeld.de/baake/|Michael Baake]]** //Hats, CAPs and Spectres//
-**May 14 2024: [[https://dblp.org/pid/10/10715.html|Josef Rukavicka]]**
+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: [[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$.
+https://arxiv.org/abs/2312.10061
 **May 28 2024: [[https://www.lirmm.fr/~ochem/|Pascal Ochem]]**
@@ Line 38: / Line 50: @@
 ==== Past talks 2024 ====
+**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.
 **April 2 2024: John Campbell** // On the evaluation of infinite products involving automatic sequences//