Pacific Institute for the Mathematical Sciences - PIMS

Computing the Entropy of Two-Dimensional Shifts of Finite Type

A one-dimensional shift of finite type (SFT) is the set of infinite
sequences that do not contain, as a sub-word, any finite word in a given
finite list. These systems are ubiquitous as models of dynamical
systems and also as constraints imposed on sequences to improve the
performance of data recording systems. Perhaps the most fundamental
quantity associated to an SFT is its entropy, which defined as the
asymptotic growth rate of the number of allowed finite words in the
system. The entropy is easily computable as the log of the largest
eigenvalue of a nonnegative integer matrix. A two-dimensional SFT (2-D
SFT) is defined as the set of tilings of the integer lattice that do not
contain as a sub-array any finite array in a given finite list. These
are much less understood than their one-dimensional counterparts. In
particular, there is no known closed-form expression for the entropy,
which is defined as the asymptotic growth rate of the number of allowed
arrays in the system. In this talk, we present results in joint work
with Erez Louidor and Ronnie Pavlov. These include improved numerical
approximations to entropy of specific 2-D SFT's and a numerical
approximation scheme which is provably exponentially accurate for a
class of 2-D SFT's.

Location: LSK 301

For more information please visit Institute of Applied Mathematics