TAILIEUCHUNG - Characterizations for several classes of alternative codes
Alternative codes, an extension of the notion of ordinary codes, have been first introduced and considered by P. T. Huy et al. in 2004. In this paper, we consider some new subclasses of alternative codes. In particular, characteristic properties and a hierarchy of such codes are established. Also, algorithms to test for these classes of codes are proposed. | Journal of Computer Science and Cybernetics, , (2016), 273-283 DOI CHARACTERIZATIONS FOR SEVERAL CLASSES OF ALTERNATIVE CODES NGO THI HIEN Hanoi University of Science and Technology; Abstract. Alternative codes, an extension of the notion of ordinary codes, have been first introduced and considered by P. T. Huy et al. in 2004. In this paper, we consider some new subclasses of alternative codes. In particular, characteristic properties and a hierarchy of such codes are established. Also, algorithms to test for these classes of codes are proposed. Keywords. Alternative code, norm alternative code, left norm alternative code, two-sided alternative code, left alternative code, strict alternative code. Mathematics Subject Classification (2010): 94A45, 68Q45. 1. INTRODUCTION The theory of length-variable codes has been initiated by M. P. Sch¨ utzenberger in the 1950s and then developed by many others. This theory has now become a part of theoretical computer science and of formal languages, in particular. 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 coded message admits only one factorization into code-words. Codes are useful in many areas of application such as information processing, data compression, cryptography, information transmission and so on. For background of the theory of codes we refer to [1, 7, 9]. As mentioned above, the definition of codes is essentially based on unambiguity of the (catenation) product of words. Different modifications of such a product may lead to different extensions of the notion of codes. Such an approach has been proposed by P. T. Huy et al. which deals with the so-called even alternative codes and their several subclasses [6, 12]. They demonstrated the importance characterizations (Lemmas 3-5) as well as algorithms to test for these classes (Lemma 6). For simplicity, even alternative
đang nạp các trang xem trước
