Affiliations: Hung Yen University of Technology and Education, Dan Tien, Khoai Chau, Hung Yen, Viet Nam. hannguyen@utehy.edu.vn | Vinh University of Technology and Education, Hung Dung, Vinh, Viet Nam. hnvinh.skv@moet.edu.vn | Nam Dinh University of Technology and Education, Phu Nghia, Nam Dinh, Viet Nam. thangdgqt@gmail.com | Ha Noi University of Science and Technology, No. 1 Dai Co Viet, Ha Noi, Viet Nam. huyfr2002@yahoo.com
Note: [] Address for correspondence: Hung Yen University of Technology and Education, Dan Tien, Khoai Chau, Hung Yen, Viet Nam This work is partially supported by Vietnamese National Foundation for Science and Technology Development (NAFOSTED)
Abstract: The Sardinas-Patterson's test for codes has contributed many effective testing algorithms to the development of theory of codes, formal languages, etc. However, we will show that a modification of this test proposed in this paper can deduce more effective testing algorithms for codes. As a consequence, we establish a quadratic algorithm that, given as input a regular language X defined by a tuple (�, M, B), where � : A* → M is a monoid morphism saturating X, M is a finite monoid, $B \subseteq M$, X = �−1(B), decides in time complexity $\mathcal{O}(n^2)$ whether X is a code, where n = Card(M). Specially, n can be chosen as the finite index of X. A quadratic algorithm for testing of ◊-codes is also established.
