Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2

DOI10.1007/978-3-319-18812-6_10zbMath1432.68166arXiv1408.6695OpenAlexW1840762010MaRDI QIDQ5501618

Ilkka Törmä, Jarkko Peltomäki

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

topological conjugacysofic shiftgraph isomorphismcomplexity classSFT

Mathematics Subject Classification ID

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

Related Items (2)

Decidability and universality of quasiminimal subshifts ⋮ Computational complexity of \(k\)-block conjugacy

Cites Work

• On the complexity of H-coloring
• Computational Aspects of Cellular Automata on Countable Sofic Shifts
• An Introduction to Symbolic Dynamics and Coding
• Classification of sofic projective subdynamics of multidimensional shifts of finite type
• Constructions with Countable Subshifts of Finite Type
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2