Complexity of Shift Spaces on Semigroups

2018/08/14 by Jung‐Chao Ban, Ban, J. C., Chih-Hung Chang +3
Computer Science · Mathematics · #Cellular Automata and Applications #Computational Complexity (cs.CC) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Dynamics and Fractals #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1808.04925

openalex publication_date 2018/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Dynamics in a Discrete Nagumo Equation: Spatial Topological Chaos
• Coloring Fibonacci-Cayley tree: An application to neural networks
• On the topological entropy of subshifts of finite type on free semigroups

Related

• On the topological entropy of subshifts of finite type on free semigroups
• Chain recurrence rates and topological entropy for free semigroup actions
• Computation of Topological Entropy via ϕ-expansion, an Inverse Problem for the Dynamical Systems βx+α\mod 1
• Entropy on normed semigroups (Towards a unifying approach to entropy)
• The entropy of holomorphic correspondences: exact computations and\n rational semigroups