Decidability of Irreducible Tree Shifts of Finite Type

Abstract

We reveal an algorithm for determining the complete prefix code irreducibility (CPC-irreducibility) of dyadic trees labeled by a finite alphabet. By introducing an extended directed graph representation of tree shift of finite type (TSFT), we show that the CPC-irreducibility of TSFTs is related to the connectivity of its graph representation, which is a similar result to one-dimensional shifts of finite type.