  In this article, we study countable sofic shifts of Cantor-Bendixson rank at
most 2. We prove that their conjugacy problem is complete for GI, the
complexity class of graph isomorphism, and that the existence problems of block
maps, factor maps and embeddings are NP-complete.
