Directed Figure Codes with Weak Equality

摘要

We consider directed figures defined as labelled polyominoes with designated start and end points, equipped with catenation operation that uses a merging function to resolve possible conflicts. This is one of possible extensions generalizing words and variable-length codes to planar structures, creating a new tool for e.g. image analysis and retrieval. Within this model, we define four kinds of codes that differ in their treatment of start and end points. This is a generalization that weakens (one or both of) equality tests in the classical definition of a code. We show a strict hierarchy of those kinds and prove that testing whether a given set of figures is a code of a given kind is decidable. This is an extension of previous results, leading to a verification algorithm for codes of all four kinds.