Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2
classification
🧮 math.DS
cs.CCcs.FL
keywords
complexityconjugacycountablemapsrankshiftssoficarticle
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.