Colóquio de Matemática – 20/03/2026 às 14h:00m
Colóquio de Matemática
Título: Fantastic Shift Spaces and Where to Find Them
Palestrante: Prof. Dr. Marcelo Sobottka (UFSC)
Resumo: The aim of this talk is to present and describe 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.
Data: Quarta-Feira, 20 de Março de 2026, 14h:00m
Local: Auditório Airton Silva, Departamento de Matemática – MTM /CFM