The code problem for directed figures

Michał Kolarz

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2010)

  • Volume: 44, Issue: 4, page 489-506
  • ISSN: 0988-3754

Abstract

top
We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.

How to cite

top

Kolarz, Michał. "The code problem for directed figures." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 44.4 (2010): 489-506. <http://eudml.org/doc/244964>.

@article{Kolarz2010,
abstract = {We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.},
author = {Kolarz, Michał},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {directed figures; variable-length codes; codicity verification; Sardinas-Patterson algorithm},
language = {eng},
number = {4},
pages = {489-506},
publisher = {EDP-Sciences},
title = {The code problem for directed figures},
url = {http://eudml.org/doc/244964},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Kolarz, Michał
TI - The code problem for directed figures
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2010
PB - EDP-Sciences
VL - 44
IS - 4
SP - 489
EP - 506
AB - We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.
LA - eng
KW - directed figures; variable-length codes; codicity verification; Sardinas-Patterson algorithm
UR - http://eudml.org/doc/244964
ER -

References

top
  1. [1] P. Aigrain and D. Beauquier, Polyomino tilings, cellular automata and codicity. Theoret. Comput. Sci. 147 (1995) 165–180. Zbl0873.68139
  2. [2] D. Beauquier and M. Nivat, A codicity undecidable problem in the plane. Theoret. Comput. Sci. 303 (2003) 417–430. Zbl1053.68067
  3. [3] J. Berstel and D. Perrin, Theory of Codes. Academic Press (1985). Zbl0587.68066
  4. [4] G. Costagliola, F. Ferrucci and C. Gravino, Adding symbolic information to picture models: definitions and properties. Theoret. Comput. Sci. 337 (2005) 51–104. Zbl1077.68041
  5. [5] M. Kolarz and W. Moczurad, Directed figure codes are decidable. Discrete Mathematics and Theoretical Computer Science 11 (2009) 1–14. Zbl1193.68155
  6. [6] S. Mantaci and A. Restivo, Codes and equations on trees. Theoret. Comput. Sci. 255 (2001) 483–509. Zbl0974.68095
  7. [7] W. Moczurad, Defect theorem in the plane. RAIRO-Theor. Inf. Appl. 41 (2007) 403–409. Zbl1144.68048
  8. [8] M. Moczurad and W. Moczurad, Decidability of simple brick codes, in Mathematics and Computer Science, Vol. III (Algorithms, Trees, Combinatorics and Probabilities). Trends in Mathematics, Birkhäuser (2004), 541–542. Zbl1094.68051
  9. [9] M. Moczurad and W. Moczurad, Some open problems in decidability of brick (labelled polyomino) codes, in Cocoon 2004 Proceedings. Lect. Notes Comput. Sci. 3106 (2004) 72–81. Zbl1091.05016

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.