Two-dimensional comma-free and cylindric codes. (English) Zbl 1355.68145
Summary: A two-dimensional code of pictures is defined as a set \(X \subseteq \operatorname{\Sigma}^{\ast \ast}\) such that any picture over \(\Sigma\) is tilable in at most one way with pictures in \(X\). It has been proved that it is undecidable whether a finite set of pictures is a code. Here we introduce two classes of picture codes: the comma-free codes and the cylindric codes, with the aim of generalizing the definitions of comma-free (or self-synchronizing) code and circular code of strings. The properties of these classes are studied and compared, in particular in relation to maximality and completeness. As a byproduct, we introduce self-covering pictures and study their periodicity issues.
References:
| [1] | Aigrain, P.; Beauquier, D., Polyomino tilings, cellular automata and codicity, Theoret. Comput. Sci., 147, 165-180 (1995) · Zbl 0873.68139 |
| [2] | Amir, A.; Benson, G., Two-dimensional periodicity in rectangular arrays, SIAM J. Comput., 27, 1, 90-106 (1998) · Zbl 0907.68108 |
| [3] | Anselmo, M.; Giammarresi, D.; Madonia, M., Picture codes and deciphering delay, Inform. and Comput. (2016), in press · Zbl 1368.68229 |
| [4] | Anselmo, M.; Giammarresi, D.; Madonia, M., Prefix picture codes: a decidable class of two-dimensional codes, Int. J. Found. Comput., 25, 8, 1017-1031 (2014), World Scientific Publishing Company · Zbl 1309.68113 |
| [5] | Anselmo, M.; Giammarresi, D.; Madonia, M., Unbordered pictures: properties and construction, (Maletti, A., Procs. CAI 2015. Procs. CAI 2015, LNCS, vol. 9270 (2015), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 45-57 · Zbl 1401.94009 |
| [7] | Anselmo, M.; Giammarresi, D.; Madonia, M.; Restivo, A., Unambiguous recognizable two-dimensional languages, RAIRO Theor. Inform. Appl., 40, 2, 227-293 (2006), EDP Sciences · Zbl 1112.68085 |
| [8] | Anselmo, M.; Jonoska, N.; Madonia, M., Framed versus unframed two-dimensional languages, (Nielsen, M.; etal., Procs. SOFSEM 09. Procs. SOFSEM 09, LNCS, vol. 5404 (2009), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 79-92 · Zbl 1206.68166 |
| [9] | Beauquier, D.; Nivat, M., A codicity undecidable problem in the plane, Theoret. Comput. Sci., 303, 417-430 (2003) · Zbl 1053.68067 |
| [10] | Berstel, J.; Perrin, D.; Reutenauer, C., Codes and Automata (2009), Cambridge University Press |
| [11] | Blum, M.; Hewitt, C., Automata on a two-dimensional tape, IEEE Symposium on Switching and Automata Theory, 155-160 (1967) |
| [12] | Book, R. V.; Otto, F., String-Rewriting Systems (1993), Springer-Verlag · Zbl 0832.68061 |
| [13] | Bozapalidis, S.; Grammatikopoulou, A., Picture codes, RAIRO Theor. Inform. Appl., 40, 4, 537-550 (2006) · Zbl 1117.94015 |
| [14] | Churchill, A. L., Restrictions and generalizations on comma-free codes, Electron. J. Combin., 16, 1 (2009) · Zbl 1160.94017 |
| [15] | Galil, Z.; Park, K., Truly alphabet independent two-dimensional pattern matching, (Proc. 33rd IEEE Symposium on Foundations of Computer Science (1992), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA), 247-256 · Zbl 0942.68707 |
| [16] | Gamard, G.; Richomme, G., Coverability in two dimensions, (Dediu, A.-H.; etal., Procs. LATA 2015. Procs. LATA 2015, LNCS, vol. 8977 (2015), Springer), 402-413 · Zbl 1423.68370 |
| [17] | Giammarresi, D.; Restivo, A., Recognizable picture languages, Int. J. Pattern Recognit., 6, 2-3, 241-256 (1992) |
| [18] | Giammarresi, D.; Restivo, A., Two-dimensional languages, (Rozenberg, G.; etal., Handbook of Formal Languages, vol. III (1997), Springer Verlag), 215-268 |
| [19] | Golomb, S. W.; Gordon, B.; Welch, L. R., Comma-free codes, Canad. J. Math., 10, 202-209 (1958) · Zbl 0081.14601 |
| [20] | Kari, J.; Szabados, M., An algebraic geometric approach to Nivat’s conjecture, ICALP, 2, 273-285 (2015) · Zbl 1434.68265 |
| [21] | Kolarz, M.; Moczurad, W., Multiset, set and numerically decipherable codes over directed figures, (Combinatorial Algorithms, 23rd International Workshop IWOCA. Combinatorial Algorithms, 23rd International Workshop IWOCA, LNCS, vol. 7643 (2012), Springer), 224-235 · Zbl 1293.94048 |
| [22] | Lam, N. H., Completing comma-free codes, Theoret. Comput. Sci., 301, 1-3, 399-415 (2003) · Zbl 1022.68059 |
| [23] | Lam, N. H., Finite completion of comma-free codes. Part 1, RAIRO Theor. Inform. Appl., 38, 2, 91-115 (2004) · Zbl 1058.94009 |
| [24] | Lam, N. H., Finite completion of comma-free codes. Part 2, RAIRO Theor. Inform. Appl., 38, 2, 117-136 (2004) · Zbl 1058.94010 |
| [25] | Mignosi, F.; Restivo, A.; Silva, P. V., On Fine and Wilf’s theorem for bidimensional words, Theoret. Comput. Sci., 292, 1, 245-262 (2003) · Zbl 1064.68075 |
| [26] | Moczurad, M.; Moczurad, W., Some open problems in decidability of brick (labeled polyomino) codes, (Chwa, K.-Y.; Munro, J. I., COCOON 2004. COCOON 2004, LNCS, vol. 3106 (2004), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 72-81 · Zbl 1091.05016 |
| [27] | Regnier, M.; Rostami, L., A unifying look at d-dimensional periodicities and space coverings, CPM, 1993, 215-227 (1993) |
| [28] | Scholtz, R. A., Maximal and variable word-length comma-free codes, IEEE Trans. Inform. Theory, IT-15, 555-559 (1969) · Zbl 0172.43104 |
| [29] | Simplot, D., A characterization of recognizable picture languages by tilings by finite sets, Theoret. Comput. Sci., 218, 2, 297-323 (1991) · Zbl 0916.68186 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
