Combinatorics and TCS seminar
Tuesday, 28th Nov 2023, 11 am
=======================
Venue: Ramanujan Hall
Host: S. Sivaramakrishnan
Speaker: Haritha Cheriyath, TIFR-CAM
Title: ENUMERATION OF SUBWORDS ON SEQUENCES AND ITS APPLICATIONS
Abstract: We start with an enumeration problem studied by Guibas and Odlyzko in 1979 and its applications in seemingly unrelated scenarios that include game theory, pattern matching algorithm, graph theory, and symbolic dynamics. One of the main objects of our study is a subshift of finite type, which is used as a tool to model a large class of dynamical systems. It consists of a collection of all one-sided sequences over a finite symbol set which contains none of a given finite collection of words. We discuss its correspondence with an edge labeled multigraph and hence with its associated adjacency matrix. We see how some (topological as well as measure-theoretic) properties of a subshift of finite type are studied using this correspondence and solve a generalized version of the enumeration problem.