FAQ
logo of Jagiellonian University in Krakow

Testing decipherability of directed figure codes with domino graphs

Publication date: 06.06.2014

Schedae Informaticae, 2013, Volume 22, pp. 27 - 40

https://doi.org/10.4467/20838476SI.13.003.2088

Authors

,
Małgorzata Moczurad
Institute of Computer Science, Jagiellonian University, Poland
All publications →
Włodzimierz Moczurad
Institute of Computer Science, Jagiellonian University, Poland
All publications →

Titles

Testing decipherability of directed figure codes with domino graphs

Abstract

Various kinds of decipherability of codes, weaker than unique de- cipherability, have been studied since mid-1980s. We consider decipherability of directed figure codes, where directed figures are defined as labelled polyomi- noes with designated start and end points, equipped with catenation operation that may use a merging function to resolve possible conflicts. This setting ex- tends 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.

References

Lempel A.; On multiset decipherable codes, IEEE Transactions on Information Theory 32(5), 1986, pp. 714{716.

Head T., Weber A.; The nest 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.

Head T., Weber A.; Deciding multiset decipherability, IEEE Transactions on Information Theory 41(1), 1995, pp. 291{297.

Guzman F.; Decipherability of codes, Journal of Pure and Applied Algebra 141(1), 1999, pp. 13{35.

Restivo A.; A note on multiset decipherable code, IEEE Transactions on Information Theory 35(3), 1989, pp. 662{663.

Blanchet-Sadri F., Morgan, C.; Multiset and set decipherable codes, Computers and Mathematics with Applications 41(10{11), 2001, pp. 1257{1262.

Blanchet-Sadri F.; On unique, multiset, set decipherability of three-word codes, IEEE Transactions on Information Theory 47(5), 2001, pp. 1745{1757.

Burderi F., Restivo A.; Varieties of codes and kraft inequality, Theory of Com- puting Systems 40(4), 2007, pp. 507{520.

Burderi F., Restivo A.; Coding partitions, Discrete Mathematics and Theoretical Computer Science 9(2), 2007, pp. 227{240.

Salomaa A., Salomaa K., Yu S.; Variants of codes and indecomposable languages, Information and Computation 207(11), 2009, pp. 1340{1349.

Aigrain P., Beauquier D.; Polyomino tilings, cellular automata and codicity, Theoretical Computer Science 147(1{2), 1995, pp. 165{180.

Giammarresi D., Restivo A.; Two-dimensional nite state recognizability, Fun- damenta Informaticae 25(3), 1996, pp. 399{422.

Mantaci S., Restivo A.; Codes and equations on trees, Theoretical Computer Science 255, 2001, pp. 483{509.

Beauquier D., Nivat M.; A codicity undecidable problem in the plane, Theoretical Computer Science 303(2{3), 2003, pp. 417{430.

Moczurad W.; Brick codes: families, properties, relations, International Journal of Computer Mathematics 74, 2000, pp. 133{150.

Kolarz M., Moczurad W.; Directed gure codes are decidable, Discrete Mathematics and Theoretical Computer Science 11(2), 2009, pp. 1{14.

Costagliola G., Ferrucci F., Gravino C.; Adding symbolic information to picture models: de nitions and properties, Theoretical Computer Science 337, 2005, pp. 51{104.

Moczurad W.; Directed gure 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.

Kolarz M.; The code problem for directed gures, Theoretical Informatics and Applications RAIRO 44(4), 2010, pp. 489{506.

Kolarz M.; Directed gure codes: Decidability frontier. In: COCOON 2010, vol. 6196 of Lecture Notes in Computer Science, Springer, New York 2010, pp. 530{539.

Kolarz M., Moczurad W.; Multiset, set and numerically decipherable codes over directed gures. In: IWOCA 2012, vol. 7643 of Lecture Notes in Computer Science, Springer, New York 2012, pp. 224{235.

Information

Information: Schedae Informaticae, 2013, Volume 22, pp. 27 - 40

Article type: Original article

Titles:

Polish:

Testing decipherability of directed figure codes with domino graphs

English:

Testing decipherability of directed figure codes with domino graphs

Authors

Institute of Computer Science, Jagiellonian University, Poland

Institute of Computer Science, Jagiellonian University, Poland

Published at: 06.06.2014

Article status: Open

Licence: None

Percentage share of authors:

Małgorzata Moczurad (Author) - 50%
Włodzimierz Moczurad (Author) - 50%

Article corrections:

-

Publication languages:

English