Testing decipherability of directed figure codes with domino graphs
cytuj
pobierz pliki
RIS BIB ENDNOTEChoose format
RIS BIB ENDNOTETesting 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.2088Authors
Testing decipherability of directed figure codes with domino graphs
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.
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: denitions 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: Schedae Informaticae, 2013, Volume 22, pp. 27 - 40
Article type: Original article
Titles:
Testing decipherability of directed figure codes with domino graphs
Testing decipherability of directed figure codes with domino graphs
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:
Article corrections:
-Publication languages:
EnglishView count: 2957
Number of downloads: 1375