A Similarity Measure for Cyclic Unary Regular Languages

• Autorzy: Dassow, J. , Martin, G.M. , Vico, F.J.
• Języki publikacji: EN

Abstrakty

EN

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 Sorensen 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 Sorensen 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.

Słowa kluczowe

EN

similarity measure; cyclic unary regular language; Jaccard coefficient; Sorensen coefficient

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 96, nr 1/2
• Strony: 71-88
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Dassow, J.

autor

Martin, G.M.

autor

Vico, F.J.

• Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, PSF 4120, D-39016 Magdeburg, Germany,

Bibliografia

• [1] Bennett, C. M., Gács, P., Li, M., Vitanyi, P. M. B., Zurek, W. H.: Information distance, IEEE Transactions on Information Theory (1998) 1407-1423.
• [2] Carrasco, R.: Accurate Computation of the Relative Entropy between Stochastic Regular Grammars, RAIRO, Theoretical Informatics and Applications 31 (5) (1997) 437-444.
• [3] Carrasco, R., Rico, J.: A Similarity between Probabilistic Tree Languages: Application to XML Document Families, Pattern Recognition 36 (2003) 2197-2199.
• [4] Chrobak, M.: Finite automata and unary languages, Theor. Comp. Sci. 47 (1986) 149-158; Errata in Theor. Comp. Sci. 302 (2003) 497-498.
• [5] Dassow, J., Martın, G. M., Vico, F. J.: Dynamical systems based on regular sets, Submitted.
• [6] Domaratzki,M., Ellul, K., Shallit, J., Wang, M.: Non-Uniqueness and Radius of Cyclic Unary NFAs, Intl. J. Found. Comp. Sci. 16 (2005) 883-896.
• [7] Gecseg, F., Peak, I.: Algebraic Theory of Automata. Academiai Kiado, Budapest, 1972.
• [8] Gramlich, G.: Probabilistic and Nondeterministic Unary Automata, in: Proceedings of Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 2747, Springer-Verlag, (2003) 460-469.
• [9] Jiang, T., McDowell, E., Ravikumar, B.: The Structure and Complexity of Minimal NFA's over a Unary Alphabet. Intl. J. Found. Comp. Sci. 2 (1991) 163-182.
• [10] Levi, A.: Basic Set Theory. Dover, 1979.
• [11] Mera, F., Pighizzini, G.: Complementing Unary Nondeterministic Automata, Theor. Comput. Sci. 330 (2005) 349-360.
• [12] Mereghetti, C., Pighizzini, G.: Optimal simulations between unary automata. SIAM J. Comput 30 (2001) 1976-1992.
• [13] Pighizzini, G.: Unary Language Concatenation and Its State Complexity, in: Proceedings 5th International Conference on Implementation and Application of Automata, Lecture Notes in Computer Science 2088 (2001) 252-262.
• [14] Pighizzini, G., Shallit, J.: Unary Language Operations, State Complexity and Jacobsthal's Function, Intl. J. Found. Comp. Sci. 13 (2002) 145-159.
• [15] Rijsbergen, C. J. van: Information Retrieval. London, 1979.
• [16] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages. Springer, 1997.
• [17] Tan, P.-N., Steinbach, M. Kumar, V.: Introduction to Data Mining. Addison-Wesley, 2006.
• [18] Wikipedia articles on Jaccard coefficient and Sørensen coefficient.