DIRECTED FIGURE CODES: DECIDABILITY FRONTIER
Michał Kolarz · Discrete Mathematics Algorithms and Applications · 2010
We consider directed figures defined as labelled polyominoes with designated start and end points, with a partial catenation. As we are interested in codicity verification for sets of figures, we show that it is decidable for sets of figures with parallel translation vectors, which is one of the decidability border cases in this setting. We give a constructive proof which leads to a straightforward algorithm.