Abstract
A polyomino contour can be represented as a word over a four letter alphabet A. Each letter induces a unit line pointing one of the four directions (right, left, up and down). According to[b], checking whether a rational language R⊂A* contains a polyomino contour word is undecidable. We restrict the problem to convex polyominoes and we prove that, in this case, the problem turns out to be decidable.
This work was partially supported by the Esprit Basic Research Action Working Group N∘3166 ASMICS and the PRC Mathématiques et Informatiques.
The authors thank the referees for their useful comments.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
D. Beauquier, A Undecidable Problem about Rational Sets and Contour Words of Polyominoes, Information Processing Letters 37 (1991), 257–263.
R. Berger, The undecidability of the domino problem, Memoirs Amer. Math. Soc. 66 (1966), 72.
D. Beauquier, M. Latteux, K. Slowinski, A decidability result about convex polyominoes, Technical Report I.T. 214 (1991), University of Lille, France.
D. Beauquier, M. Nivat, On translating one polyomino to tile the plane, Discrete and Computational Geometry, to appear.
J. Dassow, Convexity and Simplicity of Chain Code Picture Languages, Rostock. Math. Kolloq. 34 (1988), 53–60.
J. Dassow, Graph-theoretical Properties and Chain Code Picture Languages, J. Inf. Process. Cybern. EIK25 (1989), 423–433.
J. Dassow, F. Hinz, Decision Problems and Regular Chain Code Picture Languages, to appear in Discrete Applied Mathematics.
M.P. Delest and G. Viennot, Algebraic Languages and Polyominoes enumeration, Theoretical Computer Science 34 (1984), 169–206.
D. Ellard, Poyominoes and Enumeration, Math. Gazette 66 (1982), 130–314.
S.W. Golomb, Polyominoes, Georges Allen and Unwin Ltd (London, 1966).
S.W. Golomb, Tiling with sets of Polyominoes, S. Combinatorial Theory 9 (1970), 60–71.
B. Grünbaum, G.C. Shephard, Tilings and Patterns, Freeman & Company (New York, 1986).
J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley (Reading MA, 1979).
M. Jantzen, Confluent string rewriting, EATCS Monog. on T.C.S. 14 (Springer-Verlag, 1988).
J.E. Pin, Variétés de langages formels, Masson (1984).
R.M. Robinson, Undecidability and non Periodicity of Tilings of the Plane, Inventione Math. 12 (1971), 177–209.
H.D. Shapiro, Theorical limitations on the efficient user of parallel memories, I.E.E. Trans. Computing (1978).
K. Slowinski, Systèmes de réécriture et langages de mots de figure, Ph. D. Thesis (1992), University of Lille, France.
H. Wang, Notes on a class of tiling problems, Fundam. Mathematics 82 (1975), 295–305.
H.A.G. Wiljshoff, J. Van Leeuwen, Periodic versus arbitrary tessellations of the plane using polyominoes of a single type, Inf. Control 62 (1984), 1–25.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beauquier, D., Latteux, M., Slowinski, K. (1992). A decidability result about convex polyominoes. In: Simon, I. (eds) LATIN '92. LATIN 1992. Lecture Notes in Computer Science, vol 583. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0023815
Download citation
DOI: https://doi.org/10.1007/BFb0023815
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55284-0
Online ISBN: 978-3-540-47012-0
eBook Packages: Springer Book Archive