Hardness of conjugacy and factorization of multidimensional subshifts of finite type

preprint2012arXivOpen access

Abstract

We investigate here the hardness of conjugacy and factorization of subshifts of finite type (SFTs) in dimension d>1d>1. In particular, we prove that the factorization problem is Σ30Σ^0_3-complete and the conjugacy problem Σ10Σ^0_1-complete in the arithmetical hierarchy.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.