Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Metric Lexical Analysis
| |
|
Cristian S. Calude7  , Kai Salomaa8 and Sheng Yu9
| (7) |
Computer Science Department, The University of Auckland, Private Bag, 92109 Auckland, New Zealand |
| (8) |
Department of Computing and Information Science, Queen’s University, Kingston, Ontario, Canada, K7L 3N6 |
| (9) |
Department of Computer Science, The University of Western Ontario, London, Ontario, Canada, N6A 5B7 |
Abstract
We study automata-theoretic properties of distances and quasi-distances between words. We show that every additive distance
is finite. We also show that every additive quasi-distance is regularitypreserving, that is, the neighborhood of any radius
of a regular language with respect to an additive quasi-distance is regular. As an application we present a simple algorithm
that constructs a metric (fault-tolerant) lexical analyzer for any given lexical analyzer and desired radius (faulttolerance
index).
The work reported here has been supported by the Natural Sciences and Engineering Research Council of Canada Grants OGP0041630,
OGP0147224 and was done during the visit of the first author to the Department of Computer Science, The University of Western
Ontario, Canada.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|