Wyniki wyszukiwania - Biblioteka Nauki

Ten serwis zostanie wyłączony 2025-02-11.

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

1 Fundamenta Informaticae

1 2013

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: regularity-preserving transformation

Sortuj według:

Ogranicz wyniki do:

Filtrations of Formal Languages by Arithmetic Progressions

100%

Mousavi H. , Shallit J.

Fundamenta Informaticae

2013

tom Vol. 123, nr 2

135--142

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.