Testing decipherability of directed figure codes with domino graphs

• Autorzy: Moczurad M. , Moczurad W.

Identyfikatory

DOI

10.4467/20838476SI.13.003.2088

• Języki publikacji: EN

Abstrakty

EN

Various kinds of decipherability of codes, weaker than unique decipherability, have been studied since mid-1980s. We consider decipherability of directed figure codes, where directed figures are defined as labelled polyominoes with designated start and end points, equipped with catenation operation that may use a merging function to resolve possible con icts. This setting extends decipherability questions from words to 2D structures. In the present paper we develop a (variant of) domino graph that will allow us to decide some of the decipherability kinds by searching the graph for specific paths. Thus the main result characterizes directed figure decipherability by graph properties.

Słowa kluczowe

EN

domino graph; directed figure; decipherability

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2013
• Tom: Vol. 22
• Strony: 27--40
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Moczurad M.

• Institute of Computer Science, Jagiellonian University, Prof. Stanisława Łojasiewicza 6, 30-348 Kraków, Poland

autor

Moczurad W.

• Institute of Computer Science, Jagiellonian University, Prof. Stanisława Łojasiewicza 6, 30-348 Kraków, Poland

Bibliografia

• [1] Lempel A.; On multiset decipherable codes, IEEE Transactions on Information Theory 32(5), 1986, pp. 714-716.
• [2] Head T., Weber A.; The finest homophonic partition and related code concepts. In: Mathematical Foundations of Computer Science MFCS 1994, vol. 841 of Lecture Notes in Computer Science, Springer, New York 1994, pp. 618-628.
• [3] Head T., Weber A.; Deciding multiset decipherability, IEEE Transactions on Information Theory 41(1), 1995, pp. 291-297.
• [4] Guzmán F.; Decipherability of codes, Journal of Pure and Applied Algebra 141(1), 1999, pp. 13-35.
• [5] Restivo A.; A note on multiset decipherable code, IEEE Transactions on Information Theory 35(3), 1989, pp. 662-663.
• [6] Blanchet-Sadri F., Morgan, C.; Multiset and set decipherable codes, Computers and Mathematics with Applications 41(10-11), 2001, pp. 1257-1262.
• [7] Blanchet-Sadri F.; On unique, multiset, set decipherability of three-word codes, IEEE Transactions on Information Theory 47(5), 2001, pp. 1745-1757.
• [8] Burderi F., Restivo A.; Varieties of codes and kraft inequality, Theory of Computing Systems 40(4), 2007, pp. 507-520.
• [9] Burderi F., Restivo A.; Coding partitions, Discrete Mathematics and Theoretical Computer Science 9(2), 2007, pp. 227-240.
• [10] Salomaa A., Salomaa K., Yu S.; Variants of codes and indecomposable languages, Information and Computation 207(11), 2009, pp. 1340-1349.
• [11] Aigrain P., Beauquier D.; Polyomino tilings, cellular automata and codicity,Theoretical Computer Science 147(1-2), 1995, pp. 165-180.
• [12] Giammarresi D., Restivo A.; Two-dimensional finite state recognizability, Fundamenta Informaticae 25(3), 1996, pp. 399-422.
• [13] Mantaci S., Restivo A.; Codes and equations on trees, Theoretical Computer Science 255, 2001, pp. 483-509.
• [14] Beauquier D., Nivat M.; A codicity undecidable problem in the plane, Theoretical Computer Science 303(2-3), 2003, pp. 417-430.
• [15] Moczurad W.; Brick codes: families, properties, relations, International Journal of Computer Mathematics 74, 2000, pp. 133-150.
• [16] Kolarz M., Moczurad W.; Directed figure codes are decidable, Discrete Mathematics and Theoretical Computer Science 11(2), 2009, pp. 1-14.
• [17] Costagliola G., Ferrucci F., Gravino C.; Adding symbolic information to picture models: definitions and properties, Theoretical Computer Science 337, 2005, pp. 51-104.
• [18] Moczurad W.; Directed figure codes with weak equality. In: Intelligent Data Engineering and Automated Learning IDEAL 2010, vol. 6283 of Lecture Notes in Computer Science, Springer, New York 2010, pp. 242-250.
• [19] Kolarz M.; The code problem for directed figures, Theoretical Informatics and Applications RAIRO 44(4), 2010, pp. 489-506.
• [20] Kolarz M.; Directed figure codes: Decidability frontier. In: COCOON 2010, vol. 6196 of Lecture Notes in Computer Science, Springer, New York 2010, pp. 530-539.
• [21] Kolarz M., Moczurad W.; Multiset, set and numerically decipherable codes over directed figures. In: IWOCA 2012, vol. 7643 of Lecture Notes in Computer Science, Springer, New York 2012, pp. 224-235.