Complexity of shift spaces on semigroups

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 Petersen–Salama entropies [defined in Petersen and Salama (Theoret Comput Sci 743:64–71, 2018)]. After revealing the...

Full description

Saved in:
Bibliographic Details
Published in:Journal of algebraic combinatorics 2021-03, Vol.53 (2), p.413-434
Main Authors: Ban, Jung-Chao, Chang, Chih-Hung, Huang, Yu-Hsiung
Format: Article
Language:English
Subjects:
Combinatorics
Complexity
Computer Science
Convex and Discrete Geometry
Entropy
Equivalence
Group Theory and Generalizations
Lattices
Mathematics
Mathematics and Statistics
Order
Ordered Algebraic Structures
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Petersen–Salama entropies [defined in Petersen and Salama (Theoret Comput Sci 743:64–71, 2018)]. After revealing the existence of Petersen–Salama entropy of G -shift of finite type ( G -SFT), the calculation of Petersen–Salama entropy of G -SFT is equivalent to solving a system of nonlinear recurrence equations. The complete characterization of Petersen–Salama entropies of G -SFTs on two symbols is addressed, which extends (Ban and Chang in On the topological entropy of subshifts of finite type on free semigroups, 2018. arXiv:1702.04394 ) in which G is a free semigroup.
ISSN:0925-9899
1572-9192
DOI:10.1007/s10801-019-00935-1