Hardness of conjugacy, embedding and factorization of multidimensional subshifts
From MaRDI portal
Publication:494068
DOI10.1016/J.JCSS.2015.05.003zbMATH Open1328.68074OpenAlexW567294561MaRDI QIDQ494068FDOQ494068
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
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
embeddingfactorizationtilingscomputabilityconjugacysubshift of finite typearithmetical hierarchysubshiftsSFTs
Cites Work
- Theory of computation.
- Title not available (Why is that?)
- An Introduction to Symbolic Dynamics and Coding
- Endomorphisms and automorphisms of the shift dynamical system
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the dynamics and recursive properties of multidimensional symbolic systems
- Lower entropy factors of sofic systems
- On the subsystems of topological Markov chains
- Undecidability and nonperiodicity for tilings of the plane
- Classification of subshifts of finite type
- Simulation of effective subshifts by two-dimensional subshifts of finite type
- On factor universality in symbolic spaces
- Hardness of conjugacy, embedding and factorization of multidimensional subshifts of finite type
- $\it \Pi^0_1$ Sets and Tilings
- A note on universality in multidimensional symbolic dynamics
Cited In (8)
- Arithmetical hierarchy of the Besicovitch-stability of noisy tilings
- 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
- Optimal state amalgamation is NP-hard
- Algorithmic complexity for the realization of an effective subshift by a sofic
- Decidability of irreducible tree shifts of finite type
- Computational complexity of \(k\)-block conjugacy
- Complexity of conjugacy, factoring and embedding for countable sofic shifts of rank 2
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)
