Current students

Wednesday, August 29, 2018 1:30 pm - 1:30 pm EDT (GMT -04:00)

Seminar • Algorithms and Complexity — Counting Subwords and Regular Languages

Finn Lidbetter, Master’s candidate
David R. Cheriton School of Computer Science

Let x and y be words. We consider the languages whose words z are those for which the numbers of occurrences of x and y, as subwords of z, are the same (resp., the number of x's is less than the number of y's, resp., is less than or equal). In this talk we will give a necessary and sufficient condition on x and y for these languages to be regular, and we show how to check this condition efficiently.