Back to Search
Start Over
Counting Subwords and Regular Languages
- 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.
- Subjects :
- Computer Science - Formal Languages and Automata Theory
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1804.11175
- Document Type :
- Working Paper