1. Filtrations of Formal Languages by Arithmetic Progressions.
- Author
-
Mousavi, Hamoon and Shallit, Jeffrey
- Subjects
- *
FORMAL languages , *ARITHMETIC series , *MATHEMATICAL bounds , *COMPUTATIONAL complexity , *DATA mining , *MATHEMATICAL sequences , *MACHINE theory - Abstract
A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF