A Similarity Measure for Cyclic Unary Regular Languages

Article type: Research Article

Authors: Dassow, Jürgen | Martín, Gema M. | Vico, Francisco J.

Affiliations: Otto-von-Guericke-UniversitätMagdeburg, Fakultät für Informatik, PSF 4120, D-39016 Magdeburg, Germany. E-mail: [email protected] | Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga Severo Ochoa, 4, Parque Tecnológico de Andalucíe;a, E-29590 Campanillas - Málaga, Spain. E-mail: gema,[email protected]

Abstract: A cyclic unary regular language is a regular language over a unary alphabet that is represented by a cyclic automaton. We propose a similarity measure for cyclic unary regular languages by modifying the Jaccard similarity coefficient and the Sørensen coefficient to measure the level of overlap between such languages. This measure computes the proportion of strings that are shared by two or more cyclic unary regular languages and is an upper bound of the Jaccard coefficient and the Sørensen coefficient. By using such similarity measure, we define a dissimilarity measure for cyclic unary regular languages that is a semimetric distance. Moreover, it can be used for the non-cyclic case.

Keywords: Similarity measure, cyclic unary regular language, Jaccard coefficient, Sørensen coef- ficient

DOI: 10.3233/FI-2009-168

Journal: Fundamenta Informaticae, vol. 96, no. 1-2, pp. 71-88, 2009