Colóquio de Matemática
20/03/2026, 14h – Auditório Airton Silva
Universidade Federal de Santa Catarina
Título: Fantastic Shift Spaces and Where to Find Them
Resumo: The aim of this talk is to present and describe several classes of shift spaces in the spirit of medieval bestiaries. While traditional bestiaries describe fantastic creatures, this bestiary is devoted to creatures that, although symbolic, are no less real than a lion or an elephant (and no less amazing or enchanting than a siren).
Given a nonempty countable set (an alphabet), the full shift over it is the set of all sequences over the alphabet indexed either by the nonnegative integers (the one-sided shift) or by the integers (the two-sided shift). A shift space (or subshift) is a subset of the full shift consisting of all sequences that avoid a given set of forbidden finite words. In other words, a shift space is a space of sequences in which only certain words and sentences are allowed to appear, that is, the sequences must follow a grammar. For this reason, shift spaces provide excellent models for studying subjects such as coding theory, formal language theory, complexity (entropy), ergodic theory, and related areas.
In this talk, I begin by discussing the definitions of shifts of finite type (SFTs) and sofic shifts. Based on these definitions, I introduce two new classes of shift spaces that arise naturally in the infinite-alphabet setting: weakly sofic shifts and shifts of variable length (SVL).
When the alphabet is finite, only sofic shifts can be presented by finite directed labeled graphs (indeed, admitting such a presentation is an alternative definition of sofic shifts in the finite-alphabet case). In contrast, it is easy to see that every one-sided shift space over a countable alphabet can be presented by a countable directed labeled graph. However, there exist two-sided shift spaces over countable alphabets that cannot be presented by countable graphs. I will present results characterizing graphs that present one- or two-sided shifts of finite type and (weakly) sofic shifts.
, seguindo as instruções do edital abaixo e respeitando os critérios do Edital FAPESC 25/2025.
