Undecidability and nonperiodicity for tilings of the plane
From MaRDI portal
Publication:2540183
DOI10.1007/BF01418780zbMath0197.46801WikidataQ55880602 ScholiaQ55880602MaRDI QIDQ2540183
Publication date: 1971
Published in: Inventiones Mathematicae (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/142073
Polyhedra and polytopes; regular figures, division of spaces (51M20) Undecidability and degrees of sets of sentences (03D35) Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)
Related Items
On the solvability of domino snake problems, Entropy dimension of shifts of finite type on free groups, Tilings: recursivity and regularity, Inversion of 2D cellular automata: Some complexity results, The surjectivity problem for 2D cellular automata, Efficient 3-SAT algorithms in the tile assembly model, Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model, Aperiodic SFTs on Baumslag-Solitar groups, Scale-free effect of substitution networks, Topologically mixing properties of multiplicative integer systems, Taylor-Socolar hexagonal tilings as model sets, Dominoes and the complexity of subclasses of logical theories, Topological entropy for shifts of finite type over \(\mathbb{Z}\) and trees, Simulation of effective subshifts by two-dimensional subshifts of finite type, Lots of aperiodic sets of tiles, Nonemptiness problems of Wang cubes with two colors, Substitutive structure of Jeandel-Rao aperiodic tilings, Subshifts as models for MSO logic, Arithmetic computation in the tile assembly model: addition and multiplication, A family of non-periodic tilings of the plane by right golden triangles, Turing degrees of multidimensional SFTs, The complexity of generalized domino tilings, A counterexample to Thiagarajan's conjecture on regular event structures, Seas of squares with sizes from a \(\Pi_{1}^{0}\) set, Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness, Full sets of pictures to encode pictures, The periodic domino problem revisited, Mixing properties for hom-shifts and the distance between walks on associated graphs, Tile invariants: New horizons., Countable sofic shifts with a periodic direction, Complexity of graph self-assembly in accretive systems and self-destructible systems, Aperiodic tilings with one prototile and low complexity atlas matching rules, Fixed-point tile sets and their applications, The Thue-Morse-Pascal double sequence and similar structures, Groups, graphs, languages, automata, games and second-order monadic logic, Combinatorics and topology of the Robinson tiling, Tilings and quasiperiodicity., Polyominoes simulating arbitrary-neighborhood zippers and tilings, Nondeterministic polynomial time factoring in the tile assembly model, Solving NP-complete problems in the tile assembly model, The computation of overlap coincidence in Taylor-Socolar substitution tiling, Packing, covering and tiling in two-dimensional spaces, A uniquely ergodic cellular automaton, Tilings of the plane and Thurston semi-norm, On translating one polyomino to tile the plane, Characterization and topological behavior of homomorphism tree-shifts, Computational aspects of M. C. Escher's ribbon patterns, Hardness of conjugacy, embedding and factorization of multidimensional subshifts, A Random NP-complete problem for inversion of 2D cellular automata, A notion of effectiveness for subshifts on finitely generated groups, On the entropy of \(\mathbb{Z}^d\) subshifts of finite type, The large scale geometry of strongly aperiodic subshifts of finite type, Aperiodic tiles, Aperiodic tilings and entropy, On the entropies of subshifts of finite type on countable amenable groups, The domino problem of the hyperbolic plane is undecidable, On periodicity of two-dimensional words, Translation invariant extensions of finite volume measures, Nonemptiness problems of Wang tiles with three colors, A characterization of the entropies of multidimensional shifts of finite type, A hierarchical strongly aperiodic set of tiles in the hyperbolic plane, Affability of Euclidean tilings, Local rules and global order, or aperiodic tilings, Theory of cellular automata: a survey, The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics, Permutations with restricted movement, Decidability of irreducible tree shifts of finite type, The complexity of small universal Turing machines: A survey, Nilpotency and periodic points in non-uniform cellular automata, Rectangular tileability and complementary tileability are undecidable, Path finding in the tile assembly model, Fusion: a general framework for hierarchical tilings of \(\mathbb{R }^d\), Compact packings of the plane with three sizes of discs, Pictures worth a thousand tiles, a geometrical programming language for self-assembly, The 4-way deterministic tiling problem is undecidable, Regular production systems and triangle tilings, Slopes of multidimensional subshifts, Sturmian ground states in classical lattice-gas models, Tilings, substitution systems and dynamical systems generated by them, Tiling with polyominoes and combinatorial group theory, The price of universality, A self-similar aperiodic set of 19 Wang tiles, Translationally invariant universal classical Hamiltonians, Mass problems associated with effectively closed sets, Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type, Quantified block gluing for multidimensional subshifts of finite type: aperiodicity and entropy, A strongly aperiodic shift of finite type on the discrete Heisenberg group using Robinson tilings, On the complexity of deadlock detection in families of planar nets, Markov partitions for toral \(\mathbb{Z}^2\)-rotations featuring Jeandel-Rao Wang shift and model sets, Frontier between decidability and undecidability: A survey, Tiling allowing rotations only, Sandpile toppling on Penrose tilings: identity and isotropic dynamics, Domino problem for pretty low complexity subshifts, Global fixed point attractors of circular cellular automata and periodic tilings of the plane: Undecidability results, Automorphisms of \(\mathbb Z^ d\)-subshifts of finite type, Undecidability of PDL with \(L=\{a^{2^ i}| i\geq 0\}\), Computation theoretic aspects of cellular automata, Reversibility of 2D cellular automata is undecidable, Reversibility and surjectivity problems of cellular automata, Entropies realizable by block gluing \(\mathbb{Z}^{d}\) shifts of finite type, Rohlin properties for $\mathbb{Z}^{d}$ actions on the Cantor set, Finitely presented nilsemigroups: complexes with the property of uniform ellipticity, The Complexity of Small Universal Turing Machines: A Survey, AVERAGE FERMAT DISTANCES OF TWO-COLORED SUBSTITUTION NETWORKS, Undecidable relativizations of algebras of relations, Global order from local sources, The topological strong spatial mixing property and new conditions for pressure approximation, Matrix Characterization of Multidimensional Subshifts of Finite Type, Self-stabilisation of Cellular Automata on Tilings, Effective S-adic Symbolic Dynamical Systems, Computability in Symbolic Dynamics, The Domino Problem for Self-similar Structures, Degrees of Unsolvability: A Tutorial, Unnamed Item, Tilings and quasiperiodicity, Undecidability of the Spectral Gap, Automorphisms of compact groups, Strongly aperiodic subshifts of finite type on hyperbolic groups, Quasiperiodicity and Non-computability in Tilings, The topological entropy of cellular automata is uncomputable, Cellular automata and bootstrap percolation, Parametrization by horizontal constraints in the study of algorithmic properties of \(\mathbb{Z}^2\)-subshifts of finite type, Complex tilings, Decidability of CPC-irreducibility of subshifts of finite type over free groups, Aperiodic subshifts of finite type on groups which are not finitely generated, AN APERIODIC TILE WITH EDGE-TO-EDGE ORIENTATIONAL MATCHING RULES, In Memoriam: Raphael Mitchel Robinson, Undecidable translational tilings with only two tiles, or one nonabelian tile, On mixing properties of Markov tree-shifts, Mixing properties of tree-shifts, On the Besicovitch-stability of noisy random tilings, A review of SHACL: from data validation to schema reasoning for RDF graphs, The structure of translational tilings in $\mathbb{Z}^d$, Deterministic coloring of a family of complexes, Arithmetical hierarchy of the Besicovitch-stability of noisy tilings, About the domino problem in the hyperbolic plane from an algorithmic point of view, A Study on Complexity Measure of Diamond Tile Self-assembly System, Simulations and the lamplighter group, Inseparability and Conservative Extensions of Description Logic Ontologies: A Survey, Nonrecursive tilings of the plane. I, Nonrecursive tilings of the plane. II, On intrinsic ergodicity of factors of subshifts, Decidability and periodicity of low complexity tilings, THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE, About the Domino Problem for Subshifts on Groups, Finite entropy for multidimensional cellular automata, Unnamed Item, Unnamed Item, An aperiodic monotile that forces nonperiodicity through dendrites, Building a Stationary Stochastic Process From a Finite-Dimensional Marginal, Four-cycle free graphs, height functions, the pivot property and entropy minimality, Subshifts with sparse traces, Introduction to Hierarchical Tiling Dynamical Systems, The Undecidability of the Domino Problem, The Boolean algebra of logic, Undecidability of representability as binary relations, Periodicity of one-dimensional tilings, $\it \Pi^0_1$ Sets and Tilings, Multidimensional paperfolding systems, On the finite-dimensional marginals of shift-invariant measures, An aperiodic set of 11 Wang tiles, On the automorphism groups of multidimensional shifts of finite type, Medvedev degrees of two-dimensional subshifts of finite type, Constructing New Aperiodic Self-simulating Tile Sets, Multidimensional sofic shifts without separation and their factors, shifts of finite type without equal entropy full shift factors, Framed Versus Unframed Two-Dimensional Languages, Unnamed Item, Tilings: simulation and universality, Strong cocycle triviality for \(Z^{2}\) subshifts, Spatial chaos of Wang tiles with two symbols, Hierarchy and Expansiveness in 2D Subshifts of Finite Type, Triangular Tile Self-assembly Systems, Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems, A Self-assembly Model of Time-Dependent Glue Strength, Extended symmetry groups of multidimensional subshifts with hierarchical structure, The expressiveness of quasiperiodic and minimal shifts of finite type, Heesch Numbers of Edge-Marked Polyforms, Nonemptiness problems of plane square tiling with two colors, Asymptotic Cellular Complexity, Subshifts, Languages and Logic, Branching-Time Temporal Logics with Minimal Model Quantifiers, Algorithms for translational tiling, Average-Case Completeness in Tag Systems, Multidimensional Shifts And Finite Matrices, The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane, Compact Packings of the Plane with Three Sizes of Discs, Two-dimensional partial orderings: Undecidability, ACTIVE TILE SELF-ASSEMBLY, PART 1: UNIVERSALITY AT TEMPERATURE 1, ACTIVE TILE SELF-ASSEMBLY, PART 2: SELF-SIMILAR STRUCTURES AND STRUCTURAL RECURSION, A generalization of the simulation theorem for semidirect products, Weak colored local rules for planar tilings, Characterizations of periods of multi-dimensional shifts, Classification of sofic projective subdynamics of multidimensional shifts of finite type, Verification of mixing properties in two-dimensional shifts of finite type, A new mathematical model for tiling finite regions of the plane with polyominoes, Support stability of maximizing measures for shifts of finite type, Decidability and undecidability in cellular automata
Cites Work
