Various kinds of decipherability of codes, weaker than unique decipherability, have been studied since mid-1980s. We consider decipherability
of directed gure codes, where directed gures are de ned as labelled polyomi-
noes with designated start and end points, equipped with catenation operation
that may use a merging function to resolve possible con
icts. This setting ex-
tends decipherability questions from words to 2D structures. In the present
paper we develop a (variant of) domino graph that will allow us to decide some
of the decipherability kinds by searching the graph for speci c paths. Thus the
main result characterizes directed gure decipherability by graph properties.
wydział: instytut / zakład / katedra:
Wydział Matematyki i Informatyki : Instytut Informatyki i Matematyki Komputerowej