Decidability of simple brick codes. (English) Zbl 1094.68051

Drmota, Michael (ed.) et al., Mathematics and computer science III. Algorithms, trees, combinatorics and probabilities. Proceedings of the international colloquium of mathematics and computer sciences, Vienna, September 13–17, 2004. Basel: Birkhäuser (ISBN 3-7643-7128-5/hbk). Trends in Mathematics, 541-542 (2004).
Summary: Bricks are polyominoes with labelled cells. The problem 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 show that the undecidability frontier could be improved to 13 if the Post Correspondence Problem with three pairs should prove undecidable.
For the entire collection see [Zbl 1047.68003].


68Q45 Formal languages and automata
94A45 Prefix, length-variable, comma-free codes
05B50 Polyominoes
03B25 Decidability of theories and sets of sentences