×

Some open problems in decidability of brick (labelled polyomino) codes. (English) Zbl 1091.05016

Chwa, Kyung-Yong (ed.) et al., Computing and combinatorics. 10th annual international conference, COCOON 2004, Jeju Island, Korea, August 17–20, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22856-X/pbk). Lecture Notes in Computer Science 3106, 72-81 (2004).
Summary: Bricks are polyominoes with labelled cells. The problem of whether a given set of bricks is a code is undecidable in general. It is open for two-element sets. Here we consider sets consisting of square bricks only. We show that in this setting, the codicity of small sets (two bricks) is decidable, but 15 bricks are enough to make the problem undecidable. Thus the frontier between decidability and undecidability lies somewhere between these two numbers. Additionally we know that the codicity problem is decidable for sets with keys of size \(n\) when \(n=1\) and, under obvious constraints, for every \(n\). We prove that it is undecidable in the general case of sets with keys of size \(n\) when \(n \geq 6\).
For the entire collection see [Zbl 1053.68004].

MSC:

05B50 Polyominoes
03B25 Decidability of theories and sets of sentences
PDF BibTeX XML Cite
Full Text: DOI