Computing degree and class degree

DOI10.1016/J.TCS.2014.04.008MaRDI QIDQ2447767zbMATH OpenOpenAlexFDO

Authors Mahsa Allahbakhshi

Publication date 29 April 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.2530

zbMATH Keywords

class degreesofic shiftsfactor codesmeasures of relative maximal entropytransition classes

Mathematics Subject Classification ID

Entropy and other invariants (28D20) Symbolic dynamics (37B10)

Abstract: Let $pi$ be a factor code from a one dimensional shift of finite type $X$ onto an irreducible sofic shift $Y$. If $pi$ is finite-to-one then the number of preimages of a typical point in $Y$ is an invariant called the degree of $pi$. In this paper we present an algorithm to compute this invariant. The generalized notion of the degree when $pi$ is not limited to finite-to-one factor codes, is called the class degree of $pi$. 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.

Recommendations

• Class degree and relative maximal entropy
• The multiplicative inequality for class degrees via relative transition classes
• Structure of transition classes for factor codes on shifts of finite type
• Degrees of Constant-to-One Factor Maps

Cites work

• scientific article; zbMATH DE number 3139241 (Why is no real title available?)
• scientific article; zbMATH DE number 1984015 (Why is no real title available?)
• A Markovian Function of a Markov Chain
• An Introduction to Symbolic Dynamics and Coding
• An algorithm for sofic shift equivalence
• Class degree and relative maximal entropy
• Finite procedures for sofic systems
• Infinite-to-One Codes and Markov Measures
• Invariant measures of full dimension for some expanding maps

Cited in

(4)

• Degrees of Constant-to-One Factor Maps
• Class degree and relative maximal entropy
• The multiplicative inequality for class degrees via relative transition classes
• Structure of transition classes for factor codes on shifts of finite type

This page was built for publication: Computing degree and class degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2447767)