Directed figure codes are decidable - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2009

Directed figure codes are decidable

Résumé

Two-dimensional structures of various kinds can be viewed as generalizations of words. Codicity verification and the defect effect, important properties related to word codes, are studied also in this context. Unfortunately, both are lost in the case of two common structures, polyominoes and figures. 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. We prove that in this setting verification whether a given finite set of directed figures is a code is decidable and we give a constructive algorithm. We also clarify the status of the defect effect for directed figures.
Fichier principal
Vignette du fichier
1106-4263-1-PB.pdf (142.46 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00988215 , version 1 (07-05-2014)

Identifiants

Citer

Michal Kolarz, Wlodzimierz Moczurad. Directed figure codes are decidable. Discrete Mathematics and Theoretical Computer Science, 2009, Vol. 11 no. 2 (2), pp.1--14. ⟨10.46298/dmtcs.455⟩. ⟨hal-00988215⟩

Collections

TDS-MACS
66 Consultations
999 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More