Quadratic Algorithms for Testing of Codes and ⋄-Codes.

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. [ABSTRACT FROM AUTHOR]