Affiliations: Hung Yen University of Technology and Education, Dan Tien, Khoai Chau, Hung Yen, Viet Nam. [email protected] | Vinh University of Technology and Education, Hung Dung, Vinh, Viet Nam. [email protected] | Nam Dinh University of Technology and Education, Phu Nghia, Nam Dinh, Viet Nam. [email protected] | Ha Noi University of Science and Technology, No. 1 Dai Co Viet, Ha Noi, Viet Nam. [email protected]
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.
