Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-24T12:02:52.907Z Has data issue: false hasContentIssue false
  • English
  • Français

The code problem for directed figures

Published online by Cambridge University Press:  28 February 2011

Michał Kolarz
Michał Kolarz*
Affiliation:
Institute of Computer Science, Jagiellonian University, Łojasiewicza 6, 30-348 Kraków, Poland; [email protected]
Get access

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.

Keywords

Directed figuresvariable-length codescodicity verificationSardinas-Patterson algorithm
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 44 , Issue 4 , October 2010 , pp. 489 - 506
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aigrain, P. and Beauquier, D., Polyomino tilings, cellular automata and codicity. Theoret. Comput. Sci. 147 (1995) 165–180. CrossRef
Beauquier, D. and Nivat, M., A codicity undecidable problem in the plane. Theoret. Comput. Sci. 303 (2003) 417–430. CrossRef
J. Berstel and D. Perrin, Theory of Codes. Academic Press (1985).
Costagliola, G., Ferrucci, F. and Gravino, C., Adding symbolic information to picture models: definitions and properties. Theoret. Comput. Sci. 337 (2005) 51–104. CrossRef
Kolarz, M. and Moczurad, W., Directed figure codes are decidable. Discrete Mathematics and Theoretical Computer Science 11 (2009) 1–14.
Mantaci, S. and Restivo, A., Codes and equations on trees. Theoret. Comput. Sci. 255 (2001) 483–509. CrossRef
Moczurad, W., Defect theorem in the plane. RAIRO-Theor. Inf. Appl. 41 (2007) 403–409. CrossRef
Moczurad, M. and Moczurad, W., 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.
Moczurad, M. and Moczurad, W., Some open problems in decidability of brick (labelled polyomino) codes, in Cocoon 2004 Proceedings. Lect. Notes Comput. Sci. 3106 (2004) 72–81. CrossRef