pith. sign in

arxiv: 1804.11175 · v2 · pith:N3BE5RWQnew · submitted 2018-04-30 · 💻 cs.FL

Counting Subwords and Regular Languages

classification 💻 cs.FL
keywords languagesconditionlessnumberregularrespsubwordswords
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.