Computer Science
Algorithms and Complexity Group

Wednesday, 20 September 2017 at 2:30PM

DC 1304

Distances Between Languages: Algorithms and Descriptional Complexity

Timothy Ng

Postdoctoral fellow, David R. Cheriton School of Computer Science

Distance measures are defined on words to describe their similarity. These measures can be extended to languages. We first consider the descriptional complexity of neighbourhoods of regular languages. The neighbourhood of a language L is the set of words within some fixed distance of a word in L. We consider the deterministic and nondeterministic state complexity of prefix, suffix, and subword distance neighbourhoods.

We then consider the relative distance between two languages. The relative distance from a language L_1 to a language L_2, if finite, is the smallest integer k such that for every word in L_1, there is a word in L_2 with distance at most k. We study the relative prefix distance between regular, visibly pushdown, deterministic context-free, and context-free languages. We show how to compute the distance between regular languages and determine whether the distance is bounded. For deterministic context-free languages and visibly pushdown languages, we show that the relative prefix distance to and from regular languages is decidable.