|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 3 van 5 gevonden artikelen
| Titel: |
Filtrations of Formal Languages by Arithmetic Progressions |
| Auteur: |
Mousavi, Hamoon Shallit, Jeffrey |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 123 (2013) nr. 2 pagina's 135-142 |
| Jaar: |
2013-05-29 |
| Inhoud: |
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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 3 van 5 gevonden artikelen
| << vorige | volgende >> |