Complexity of Shift Spaces on Semigroups

Abstract

Let $G=⟨S|R_A⟩$ be a semigroup with generating set $S$ and equivalences $R_A$ among $S$ determined by a matrix $A$. This paper investigates the complexity of $G$-shift spaces by yielding the topological entropies. After revealing the existence of topological entropy of $G$-shift of finite type ($G$-SFT), the calculation of topological entropy of $G$-SFT is equivalent to solving a system of nonlinear recurrence equations. The complete characterization of topological entropies of $G$-SFTs on two symbols is addressed, which extends [Ban and Chang, arXiv:1803.03082] in which $G$ is a free semigroup.