Hardness of conjugacy, embedding and factorization of multidimensional subshifts

DOI10.1016/J.JCSS.2015.05.003MaRDI QIDQ494068zbMATH OpenOpenAlexFDO

Authors Emmanuel Jeandel, Pascal Vanier

Publication date 31 August 2015

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2015.05.003

zbMATH Keywords

embeddingfactorizationtilingscomputabilityconjugacysubshift of finite typearithmetical hierarchysubshiftsSFTs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Hardness of conjugacy, embedding and factorization of multidimensional subshifts of finite type
• Computational complexity of \(k\)-block conjugacy
• Complexity of conjugacy, factoring and embedding for countable sofic shifts of rank 2
• On the conjugacy problem of cellular automata
• Multidimensional shifts of finite type and sofic shifts

Cites work

• scientific article; zbMATH DE number 5380239 (Why is no real title available?)
• scientific article; zbMATH DE number 2158945 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• $\it \Pi^0_1$ Sets and Tilings
• A note on universality in multidimensional symbolic dynamics
• An Introduction to Symbolic Dynamics and Coding
• Classification of subshifts of finite type
• Endomorphisms and automorphisms of the shift dynamical system
• Hardness of conjugacy, embedding and factorization of multidimensional subshifts of finite type
• Lower entropy factors of sofic systems
• On factor universality in symbolic spaces
• On the dynamics and recursive properties of multidimensional symbolic systems
• On the subsystems of topological Markov chains
• Simulation of effective subshifts by two-dimensional subshifts of finite type
• Theory of computation.
• Undecidability and nonperiodicity for tilings of the plane

Cited in

(8)

• Hardness of conjugacy, embedding and factorization of multidimensional subshifts of finite type
• Parametrization by horizontal constraints in the study of algorithmic properties of \(\mathbb{Z}^2\)-subshifts of finite type
• Arithmetical hierarchy of the Besicovitch-stability of noisy tilings
• Computational complexity of \(k\)-block conjugacy
• Optimal state amalgamation is NP-hard
• Decidability of irreducible tree shifts of finite type
• Complexity of conjugacy, factoring and embedding for countable sofic shifts of rank 2
• Algorithmic complexity for the realization of an effective subshift by a sofic

This page was built for publication: Hardness of conjugacy, embedding and factorization of multidimensional subshifts

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