Geodesic
Decidability of multiset, set and numerically decipherable directed figure codes
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1.

Voir la notice de l'article provenant de la source Episciences

Codes with various kinds of decipherability, weaker than the usual unique decipherability, have been studied since multiset decipherability was introduced in mid-1980s. We consider decipherability of directed figure codes, where directed figures are defined as labelled polyominoes with designated start and end points, equipped with catenation operation that may use a merging function to resolve possible conflicts. This is one of possible extensions generalizing words and variable-length codes to planar structures. Here, verification whether a given set is a code is no longer decidable in general. We study the decidability status of figure codes depending on catenation type (with or without a merging function), decipherability kind (unique, multiset, set or numeric) and code geometry (several classes determined by relative positions of start and end points of figures). We give decidability or undecidability proofs in all but two cases that remain open. 
@article{DMTCS_2017_19_1_a10,
     author = {Moczurad, W{\l}odzimierz},
     title = {Decidability of multiset, set and numerically decipherable directed figure codes},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-1-11},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-11/}
}
TY  - JOUR
AU  - Moczurad, Włodzimierz
TI  - Decidability of multiset, set and numerically decipherable directed figure codes
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-11/
DO  - 10.23638/DMTCS-19-1-11
LA  - en
ID  - DMTCS_2017_19_1_a10
ER  - 
%0 Journal Article
%A Moczurad, Włodzimierz
%T Decidability of multiset, set and numerically decipherable directed figure codes
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-11/
%R 10.23638/DMTCS-19-1-11
%G en
%F DMTCS_2017_19_1_a10
Moczurad, Włodzimierz. Decidability of multiset, set and numerically decipherable directed figure codes. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1. doi : 10.23638/DMTCS-19-1-11. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-11/

Cité par Sources :