|
Additive Distances and Quasi_Distances Between Words
Cristian S. Calude (Computer Science Department, The University of Auckland, New Zealand)
Kai Salomaa (Department of Computing and Information Science, Queen's University Kingston, Canada)
Sheng Yu (Department of Computer Science, The University of Western Ontario, Canada)
Abstract: We study additive distances and quasi-distances between words. We show that every additive distance is finite. We then prove that every additive quasi-distance is regularity-preserving, that is, the neighborhood of any radius of a regular language with respect to an additive quasi-distance is regular. Finally, similar results will be proven for context-free, computable and computably enumerable languages.
1.) C. S. Calude, K. Salomaa, S. Yu (eds.). Advances and Trends in Automata and Formal Languages. A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen.
Keywords: some words
Categories: F.1.1, F.4.3
|
