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

available in:   PDF (196 kB) PS (149 kB)
 
get:  
Similar Docs BibTeX   Write a comment
  
get:  
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