Cover Image

Undecidability of the block gluing classes of homshifts

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chandgotia, Nishant, Gangloff, Silvère, de Menibus, Benjamin Hellouin, Oprocha, Piotr
Format:	Preprint
Published:	2025
Subjects:	Dynamical Systems Computational Complexity Discrete Mathematics 37B51 05C60 68Q17
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the cohomology of homshifts
by: Chandgotia, Nishant, et al.
Published: (2025)

Minimality and computability of languages of G-shifts
by: Amir, Djamel Eddine, et al.
Published: (2025)

Short-range and long-range order: a transition in block-gluing behavior in Hom shifts
by: Gangloff, Silvere, et al.
Published: (2022)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

Computational Complexity of Minimal Trap Spaces in Boolean Networks
by: Moon, Kyungduk, et al.
Published: (2022)

Finitely Dependent Processes on Subshifts
by: Chandgotia, Nishant, et al.
Published: (2026)

Homomorphically Full Oriented Graphs
by: Bellitto, Thomas, et al.
Published: (2022)

Characterisation of the Set of Ground States of Uniformly Chaotic Finite-Range Lattice Models
by: Gayral, Léo, et al.
Published: (2023)

Subshifts defined by nondeterministic and alternating plane-walking automata
by: de Menibus, Benjamin Hellouin, et al.
Published: (2024)

Trifferent codes with small lengths
by: Kurz, Sascha
Published: (2023)

Structure and computability of preimages in the Game of Life
by: Salo, Ville, et al.
Published: (2023)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

Parametrized complexity of relations between multidimensional subshifts
by: Carrasco-Vargas, Nicanor, et al.
Published: (2025)

Two-player Domino games
by: de Menibus, Benjamin Hellouin, et al.
Published: (2023)

Results on three problems on isolation of graphs
by: Borg, Peter, et al.
Published: (2026)

WalkSAT is linear on random 2-SAT
by: Berenbrink, Petra, et al.
Published: (2024)

Non-Robustness of the Zero-Temperature-Limit Gibbs Measures to Perturbations of the Potential
by: Gayral, Léo, et al.
Published: (2025)

Ulam meets Turing: constructing quadratic maps with non-computable SRB measures
by: Rojas, Cristóbal, et al.
Published: (2024)

Complexity of learning matchings and half graphs via edge queries
by: Mande, Nikhil S., et al.
Published: (2025)

On the algorithmic descriptive complexity of attractors in topological dynamics
by: Rojas, Cristobal, et al.
Published: (2023)

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

String attractors and bi-infinite words
by: Béaur, Pierre, et al.
Published: (2024)

Edge open packing: complexity, algorithmic aspects, and bounds
by: Brešar, Boštjan, et al.
Published: (2024)

Linear extensions of finite posets
by: Chan, Swee Hong, et al.
Published: (2023)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

Graph polynomials: some questions on the edge
by: Farr, Graham, et al.
Published: (2024)

The random $k$-SAT Gibbs uniqueness threshold revisited
by: Chatterjee, Arnab, et al.
Published: (2025)

Regenerative Ulam-von Neumann Algorithm: An Innovative Markov chain Monte Carlo Method for Matrix Inversion
by: Ghosh, Soumyadip, et al.
Published: (2024)

Folding One Polyhedral Metric Graph into Another
by: Chung, Lily, et al.
Published: (2024)

Density of group languages in shift spaces
by: Berthé, Valérie, et al.
Published: (2024)

Trail Trap: a variant of Partizan Edge Geography
by: Buchanan, Calum, et al.
Published: (2024)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2024)

Boltzmann Distribution on "Short" Integer Partitions with Power Parts: Limit Laws and Sampling
by: Peyen, Jean C., et al.
Published: (2023)

Fault-tolerant mutual-visibility: complexity and solutions for grid-like networks
by: Cicerone, Serafino, et al.
Published: (2025)

Complexity of chess domination problems
by: Langlois-Rémillard, Alexis, et al.
Published: (2022)

Symbol Frequencies in Surjective Cellular Automata
by: de Menibus, Benjamin Hellouin, et al.
Published: (2025)

On balanceable and simply balanceable regular graphs
by: Ahanjideh, Milad, et al.
Published: (2024)

Vanishing of Schubert coefficients is in ${\sf AM}\cap {\sf coAM}$ assuming the GRH
by: Pak, Igor, et al.
Published: (2025)

Vanishing of Schubert coefficients in probabilistic polynomial time
by: Pak, Igor, et al.
Published: (2025)

Two block gluing constructions
by: Salo, Ville, et al.
Published: (2026)