Abstract
We consider the problem of recognizability of some classes of polyominoes in the theory of picture languages. In particular we focus our attention on the problem posed by Matz of finding a non-recognizable picture language for which his technique for proving the non-recognizability of picture languages fails. We face the problem by studying the family of L-convex polyominoes and some closed families that are similar to the recognizable family of all polyominoes but result to be non-recognizable. Furthermore we prove that the family of L-convex polyominoes satisfies the necessary condition given by Matz for the recognizability and we conjecture that the family of L-convex polyominoes is non-recognizable.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barcucci, E., Del Lungo, A., Nivat, M., Pinzani, R.: Reconstructing convex polyominoes from horizontal and vertical projections. Theoret. Comput. Sci. 155, 321–347 (1996)
Bousquet-Mèlou, M.: A method for the enumeration of various classes of column-convex polygons. Dis. Math. 154, 1–25 (1996)
Castiglione, G., Restivo, A.: Reconstruction of L-convex Polyominoes. Electronic Notes in Discrete Mathematics 12 (2003)
Castiglione, G., Restivo, A.: Ordering and Convex Polyominoes. In: Margenstern, M. (ed.) MCU 2004. LNCS, vol. 3354, pp. 128–139. Springer, Heidelberg (2005)
Castiglione, G., Frosini, A., Restivo, A., Rinaldi, S.: Enumeration of L-convex Polyominoes. Theoret. Comput. Sci. 347, 336–352 (2005)
Castiglione, G., Frosini, A., Munarini, E., Restivo, A., Rinaldi, S.: Enumeration of L-convex Polyominoes, II. Bijection and area. In: FPSAC 2005, June 20–25, 2005, Taormina (2005)
Castiglione, G., Frosini, A., Restivo, A., Rinaldi, S.: A Tomographical Characterization of L-convex Polyominoes. In: Andrès, É., Damiand, G., Lienhardt, P. (eds.) DGCI 2005. LNCS, vol. 3429, pp. 115–125. Springer, Heidelberg (2005)
Castiglione, G., Frosini, A., Munarini, E., Restivo, A., Rinaldi, S.: Combinatorial aspects of L-convex polyominoes. European Journal of Combinatorics (in Press)
De Carli, F., Frosini, A., Rinaldi, S., Vuillon, L.: On the Tiling System Recognizability of Various Classes of Convex Polyominoes. Annals of combinatorics (to appear)
Del Lungo, A., Nivat, M., Pinzani, R.: The number of convex polyominoes reconstructible from their orthogonal projections. Discrete Math. 157, 65–78 (1996)
Dhar, D.: Equivalence of two-dimensional directed animal problem to a onedimensional path problem. Adv. in Appl. Math. 9, 959–962 (1988)
Gardner, M.: Mathematical Games. Scientific American 196, 126–134 (1957)
Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Salomaa, A., Rozemberg, G. (eds.) Handbook of Formal Languages, vol. 3, pp. 215–267. Springer, Heidelberg (1997)
Girault-Beauquier, D., Nivat, M.: Tiling the plane with one tile. In: Proceedings of the sixth annual symposium on Computational geometry, June 07-09, 1990, Berkley, California, United States (1990)
Golomb, S.W.: Checker boards and polyominoes. Amer. Math. Monthly 61, 675–682 (1954)
Golomb, S.W.: Polyominoes. Scribner, New York (1965)
Golomb, S.W.: Polyominoes: Puzzles, Patterns, Problems and Packing. Princeton Academic Press, London (1996)
Hakim, V., Nadal, J.P.: Exact result for 2D directed lattice animals on a strip of finite width. J. Phys. A: Math. 16, L213–L218 (1983)
Herman, G.T., Kuba, A.: Discrete Tomography: Foundations, Algorithms and Applications, Birkhauser Boston, Cambridge, MA on of convex 2D discrete sets in polynomial time. Theoret. Comput. Sci. 283, 223–242 (2002)
Kuba, A., Balogh, E.: Reconstruction of convex 2D discrete sets in polynomial time. Theoret. Comput. Sci. 283, 223–242 (2002)
Matz, O.: On piecewise testable, starfree, and recognizable picture languages. In: Nivat, M. (ed.) ETAPS 1998 and FOSSACS 1998. LNCS, vol. 1378, pp. 203–210. Springer, Heidelberg (1998)
Reinhardt, K.: On some recognizable picture-languages. In: Brim, L., Gruska, J., Zlatuška, J. (eds.) MFCS 1998. LNCS, vol. 1450, pp. 760–770. Springer, Heidelberg (1998)
Reinhardt, K.: The #a = #b Pictures are Recognizable. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 527–538. Springer, Heidelberg (2001)
Salomaa, A., Soittola, M.: Automata-theoretic aspects of formal power series. Springer, New York (1978)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Castiglione, G., Vaglica, R. (2007). Recognizable Picture Languages and Polyominoes. In: Bozapalidis, S., Rahonis, G. (eds) Algebraic Informatics. CAI 2007. Lecture Notes in Computer Science, vol 4728. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75414-5_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-75414-5_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75413-8
Online ISBN: 978-3-540-75414-5
eBook Packages: Computer ScienceComputer Science (R0)