In the paper [13] Păun, Polkowski and Skowron introduce several indiscernibility relations among strings that are infinite index equivalence or tolerance relations, and study lower and upper rough approximations of languages defined by them. In this paper we develop a further study of some of these indiscernibility relations among strings. We characterize the classes defined by them, and the rough approximations of general and context free languages under them. We also compare some of the rough approximations these relations produce to the ones given by the congruences defining testable, reverse testable, locally testable, piecewise testable and commutative languages. Those yield languages belonging to that families. Next, we modify some of the relations to obtain congruences, and study the families of languages the rough approximations under them give rise to. One of these modificated relations turns out to be the k-abelian congruence, that was defined by J. Karhumäki in [7], in the context of combinatorics on words. We show that it defines a pseudo-principal +-variety, a term defined in [9]. Our results in that work are then applied to determine when a given language has a best upper approximation in that family. Finally, we make some comments on the accuracy of the rough approximations obtained in each case.

In this paper we attempt to measure the accuracy of approximations of regular languages by languages in +−varieties (as defined by Eilenberg). These approximations are upper approximations in the sense of Pawlak’s rough set theory with respect to congruences belonging to the variety of congruences corresponding to the given +−variety. In our approach, the accuracy of an approximation is measured by the relative density of the object language in the approximation language and the asymptotic behavior of this quotient. In particular, we apply our measures of accuracy to k-definite, reverse k-definite, i, j-definite and k-testable approximations.