2011/12/16 by Hamoon Mousavi, Jeffrey Shallit, Mousavi, Hamoon +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1112.3758
revision correcting some typos
openalex publication_date 2011/12/16 · arxiv created 2012/03/30 · arxiv updated 2012/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that the operation diag, which extracts the diagonal of words of square length arranged in a square array, preserves regularity but does not preserve context-freeness.