Algorithms for Testing of Codes and Lozenge-Codes

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 ⊆ M, X = φ^-1 (B), decides in time complexity O(n²) whether X is a code, where n is the finite index of the syntactic congruence of X. A test of Sardinas-Patterson type for ◇-codes is given when they are ◇-regular languages. As a consequence, we obtain an O(n²) time complexity algorithm for ◇-codes.