## IAM-PIMS-MITACS Distinguished Colloquium: Prof. Brian Marcus

- Date: 01/24/2011
- Time: 15:00

University of British Columbia

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.