Filtrations of Formal Languages by Arithmetic Progressions
From MaRDI portal
Publication:5300608
DOI10.3233/FI-2013-804zbMATH Open1294.68104arXiv1112.3758MaRDI QIDQ5300608
Author name not available (Why is that?)
Publication date: 27 June 2013
Published in: (Search for Journal in Brave)
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. 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.
Full work available at URL: https://arxiv.org/abs/1112.3758
No records found.
No records found.
This page was built for publication: Filtrations of Formal Languages by Arithmetic Progressions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300608)
