Complexity of conjugacy, factoring and embedding for countable sofic shifts of rank 2

DOI10.1007/978-3-319-18812-6_10MaRDI QIDQ5501618zbMATH OpenOpenAlexFDO

Authors Ville Salo, Ilkka A. Törmä

Publication date 4 August 2015

Published in Cellular Automata and Discrete Complex Systems (Search for Journal in Brave)

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

zbMATH Keywords

complexity classgraph isomorphismSFTsofic shifttopological conjugacy

Mathematics Subject Classification ID

Multidimensional shifts of finite type (37B51) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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.

Recommendations

• Hardness of conjugacy, embedding and factorization of multidimensional subshifts
• Computational complexity of k-block conjugacy
• Countable sofic shifts with a periodic direction
• Computability of countable subshifts
• Hardness of conjugacy, embedding and factorization of multidimensional subshifts of finite type

Cites work

• An Introduction to Symbolic Dynamics and Coding
• Classification of sofic projective subdynamics of multidimensional shifts of finite type
• Computational aspects of cellular automata on countable sofic shifts
• Constructions with countable subshifts of finite type
• Hardness of conjugacy, embedding and factorization of multidimensional subshifts of finite type
• scientific article; zbMATH DE number 3841910 (Why is no real title available?)
• scientific article; zbMATH DE number 5380239 (Why is no real title available?)
• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 910913 (Why is no real title available?)
• On the complexity of H-coloring
• Structural aspects of tilings

Cited in

(4)

• Computational complexity of problems for deterministic presentations of sofic shifts
• Computational complexity of k-block conjugacy
• Decidability and universality of quasiminimal subshifts
• Hardness of conjugacy, embedding and factorization of multidimensional subshifts

This page was built for publication: Complexity of conjugacy, factoring and embedding for countable sofic shifts of rank 2

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