Back to Search Start Over

Counting Subwords and Regular Languages

Authors :
Colbourn, Charles J.
Dougherty, Ryan E.
Lidbetter, Thomas F.
Shallit, Jeffrey
Publication Year :
2018

Abstract

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). We 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.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1804.11175
Document Type :
Working Paper