A codicity undecidable problem in the plane.

DOI10.1016/S0304-3975(03)00029-XzbMath1053.68067OpenAlexW2064947749MaRDI QIDQ1401375

Maurice Nivat, Danièle Beauquier

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00029-x

zbMATH Keywords

TilingUndecidabilityCodePolyominoDomino tiling

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Polyominoes (05B50)

Related Items

Unbordered Pictures: Properties and Construction ⋮ Full sets of pictures to encode pictures ⋮ Defect theorem in the plane ⋮ Characterization and measure of infinite two-dimensional strong prefix codes ⋮ Structure and properties of strong prefix codes of pictures ⋮ How Many Figure Sets Are Codes? ⋮ The code problem for directed figures ⋮ Picture codes and deciphering delay ⋮ Two-dimensional comma-free and cylindric codes ⋮ Sets of Pictures Avoiding Overlaps ⋮ Rectangular tileability and complementary tileability are undecidable ⋮ DIRECTED FIGURE CODES: DECIDABILITY FRONTIER ⋮ PREFIX PICTURE CODES: A DECIDABLE CLASS OF TWO-DIMENSIONAL CODES ⋮ Picture codes ⋮ Two-dimensional codes

Cites Work

• Unnamed Item
• Unnamed Item
• An undecidable problem about rational sets and contour words of polyominoes
• Recurring Dominoes: Making the Highly Undecidable Highly Understandable
• Notes on a class of tiling problems
• Tiling with sets of polyominoes
• The undecidability of the domino problem