An enumeration problem in symbolic dynamics

Speaker: Haritha Cheriyath
Center for Mathematical Modeling, U. de Chile
Date: Monday, May 06, 2024 at 2:30 p.m. Santiago time

Abstract:  Symbolic dynamics, initially used as a tool for analyzing general dynamical systems, has later caught more attention due to its independent applications in other areas including information theory and coding. From a given directed graph, we construct a symbolic space consisting of infinite paths on it. We are interested in studying its complexity by counting paths of fixed lengths. The topological entropy of this system is given by the growth rate of this complexity function.
When some of the edges are removed from the graph, the entropy of the new perturbed system drops. What if instead of edges, we make some paths to be forbidden? How much does the entropy drop when the lengths of these forbidden paths increase? These questions can be re-framed as enumeration of finite strings where a given collection of strings are forbidden. We explore more on this enumeration problem and if time permits, we discuss its applications in seemingly unrelated scenarios that include game theory and pattern matching algorithm.

 

Venue: Sala John Von Neumann, 7th floor, Beauchef 851