tailieunhanh - A prime decomposition algorithm for supercodes

Trong bài báo này, một thuật toán phân tích nguyên tố đối với các siêu mã có độ phức tạp tuyến tính đã được đề xuất. Tính duy nhất của việc phân tích một siêu mã thành một tích ghép duy nhất các siêu mã nguyên tố cũng được chứng minh. . | Journal of Computer Science and Cybernetics, , (2013), 351–357 A PRIME DECOMPOSITION ALGORITHM FOR SUPERCODES KIEU VAN HUNG The Office of Government, 01 Hoang Hoa Tham, Hanoi, Vietnam kieuvanhung@ Tóm t t. Siêu mã, một loại mã độ dài thay đổi có nhiều tính chất đặc biệt, đã được giới thiệu và nghiên cứu bởi Đỗ Long Vân và tác giả trong một số bài báo gần đây. Một siêu mã được gọi là nguyên tố nếu nó không thể phân tích thành tích ghép của hai siêu mã khác. Phân tích nguyên tố đối với một siêu mã là phân tích nó thành tích ghép của các siêu mã nguyên tố. Trong bài báo này, một thuật toán phân tích nguyên tố đối với các siêu mã có độ phức tạp tuyến tính đã được đề xuất. Tính duy nhất của việc phân tích một siêu mã thành một tích ghép duy nhất các siêu mã nguyên tố cũng được chứng minh. T khóa. Mã, siêu mã, siêu mã nguyên tố, phân tích nguyên tố. Abstract. Supercode, a particular case of hypercodes, has been introduced and considered by D. L. Van and the author in previous papers. A supercode is called prime if it cannot be decomposed as a catenation of two supercodes. The prime decomposition of a supercode L is to decompose L into prime supercodes. In this paper, a linear-time prime decomposition algorithm for supercodes is proposed. The uniqueness of the prime decomposition for supercodes is presented. AMS Mathematics Subject Classification: 94A45, 68Q45. Key words. Code, supercode, prime supercode, prime decomposition. 1. INTRODUCTION Theory of length-variable codes has been initiated by M. P. Sch¨tzenberger and then u developed by many others. Codes are closely related to formal languages. A code is a language such that every text encoded by words of the language can be decoded in a unique way or, in other words, every encoded message admits only one factorization into code-words. Codes are useful in many application areas such as information processing, data compression, cryptography, information transmission and so on [9]. For .