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
Publisher :
arXiv, 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 :
OpenAIRE
Accession number :
edsair.doi.dedup.....f4a20e5b903960cafbb14292c47b8970
Full Text :
https://doi.org/10.48550/arxiv.1804.11175