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. 

This is a joint work with Charles Colbourn, Ryan Dougherty, and Jeffrey Shallit.

Note: This is a practice talk for DLT18 and so should be around 30 minutes.