On the Accuracy of Rough Approximations of Regular Languages

Article type: Research Article

Authors: Torres, Gabriela Martín

Affiliations: Research Group on Mathematical Linguistics, Rovira i Virgili University, Spain. [email protected]

Note: [] Address for correspondence: Research Group on Mathematical Linguistics, Rovira i Virgili University, Spain.

Abstract: 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.

DOI: 10.3233/FI-2014-1058

Journal: Fundamenta Informaticae, vol. 132, no. 4, pp. 533-545, 2014