23.04.2009

Kody etykietowanych poliomin

Na rozmaite struktury dwuwymiarowe -- zwane figurami, obrazami, klockami itp. -- można patrzeć jako na uogólnienia słów. W takim kontekście rozpatrywane są w szczególności własność defektu oraz rozstrzygalność sprawdzania, czy dany zbiór jest kodem -- dwie ważne własności dotyczące kodów na słowach.
(Przy ustalonym alfabecie $A$, zbiór $X \subseteq A^*$ jest kodem, jeżeli dowolny iloczyn z $X^*$ ma jednoznaczny rozkład nad $X$. Twierdzenie o defekcie mówi, że dla dowolnego niekodu $Y$ istnieje kod $X$ taki, że $|X|<|Y|$ oraz $Y^+ \subseteq X^+$).
Niestety, przejście od zwykłych słów do np. etykietowanych poliomin powoduje utratę obydwu tych własności. Rozważamy zatem figury zaczepione, zdefiniowane jako etykietowane poliomina z wyróżnionym punktem początkowym i końcowym, wyposażone w operację katenacji z funkcją łączącą, która służy do rozstrzygania ewentualnych kolizji etykiet. Pokazujemy, że sprawdzenie, czy dany zbiór figur zaczepionych jest kodem, jest rozstrzygalne, oraz podajemy konstruktywny algorytm. Rozstrzygamy również, tym razem negatywnie, kwestię twierdzenia o defekcie.