Computing degree and class degree

详细信息    查看全文

• 作者：Mahsa Allahbakhshi¹ ; ^{mallahbakhshi@dim.uchile.cl" class="auth_mail}
• 关键词：Factor codes ; Sofic shifts ; Measures of relative maximal entropy ; Transition classes ; Degree ; Class degree
• 刊名：Theoretical Computer Science
• 出版年：22 May 2014
• 年：2014
• 卷：535
• 期：Complete
• 页码：59-64
• 全文大小：207 K

文摘

Let 蟺 be a factor code from a one dimensional shift of finite type X onto an irreducible sofic shift Y. If 蟺 is finite-to-one then the number of preimages of a typical point in Y is an invariant called the degree of 蟺. In this paper we present an algorithm to compute this invariant. The generalized notion of the degree when 蟺 is not limited to finite-to-one factor codes, is called the class degree of 蟺. The class degree of a code is defined to be the number of transition classes over a typical point of Y and is invariant under topological conjugacy. We show that the class degree is computable.