Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 8 / Issue 2

available in:   PDF (196 kB) PS (149 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-008-02-0141


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