On the Generation of Aperiodic and Periodic Necklaces via T-augmentation

• Autorzy: Gulliver T.A. , Makwakwa I. , Speidel U.
• Języki publikacji: EN

Abstrakty

EN

In a recent report, Gulliver and Speidel showed that complete sets of aperiodic and - in some cases periodic - necklaces can be generated for arbitrary lengths as fixed-length subsets of variable-length T-codes. The T-codes to which they applied this observation were specifically T-codes constructed by systematic T-augmentation, that is by T-augmentation sequences in which each T-expansion parameter is 1 (simple T-augmentation) and where the T-codes A(p1,p2,1/4,pi) at each T-augmentation level i do not contain any codewords shorter than pi (strictly minimal T-augmentation). This present paper generalizes their result to arbitrary T-codes and formalizes their earlier result as a special case of the general result.

Słowa kluczowe

EN

necklaces; Lyndon words; cyclic equivalence; T-codes; synchronization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 1-2
• Strony: 91--107
• Opis fizyczny: bibliogr. 12 poz., tab., wykr.

Twórcy

autor

Gulliver T.A.

autor

Makwakwa I.

autor

Speidel U.

• Department of Computer Science, Tamaki Campus, The University of Auckland, Private Bag 92019, Auckland, New Zealand,

Bibliografia

• [1] D. Huffman: A Method for the Construction of Minimum Redundancy Codes. Proc. Inst. Radio Eng., 40:1098-1101, September 1952
• [2] W. L. Eastman: On the construction of comma-free codes, IEEE Trans. Inform. Theory, IT-11,1965,263-266
• [3] S. W. Golomb and B. Gordon: Codes with bounded synchronization delay, Inform, and Control, vol. 8,1965,355-376
• [4] R. A. Scholtz: Maximal and variable word-length comma-free codes, IEEE Trans. Inform. Theory, IT-15(2), March 1969, 300-306
• [5] M. R. Titchener: Generalized T-codes: an Extended Construction Algorithm for Self-Synchronizing Variable-Length Codes, IEE Proceedings - Computers and Digital Techniques, 143(3), June 1996, pp. 122-128.
• [6] U. Guenther: Data Compression and Serial Communication with Generalized T-Codes, Journal of Universal Computer Science, V. 2, N 11, 1996, pp. 769-795. http: //www. iicm. edu/jucs_2_ll
• [7] R. Nicolescu and M. R. Titchener, Uniqueness Theorems for T-Codes, Romanian Journal of Information Science and Technology, 1(3), March 1998, pp. 243-258.
• [8] U. Guenther: Robust Source Coding with Generalized T-Codes. PhD Thesis, The University of Auckland, 1998.http://www.tcs.auckland.ac.nz/~ulrich/phd.ps.gz
• [9] A. Gulliver and U. Speidel: On T-codes and neddaces, preprint under CDMTCS Research Report no. 290, Centre for Discrete Mathematics and Theoretical Computer Science, Auckland, October 2006, http://www.cs.auckland.ac.nz/CDMTCS/researchreports/290ulrich.pdf
• [10] A. Gulliver and U. Speidel: Synchronizing block codes with a decoder for variable-length codes, accepted for publication in the Proceedings of the 2007 IEEE International Symposium on Information Theory (ISIT2007), 24th - 29th June 2007, Nice, France
• [11] K. Cattell, F. Ruskey, J. Sawada, M. Serra and C.R. Miers, Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2), J. Algorithms, vol. 37, pp. 267-282,2000.
• [12] Ruskey, F., Savage, C. and Wang, M., Y., Generating Necklaces, January, 1991