Filtrations of Formal Languages by Arithmetic Progressions

• Autorzy: Mousavi H. , Shallit J.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

filtration; arithmetic progression; formal language; regular language; finite automaton; state complexity; context-free language; diagonal; regularity-preserving transformation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 2
• Strony: 135--142
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Mousavi H.

• School of Computer Science University of Waterloo Waterloo, ON N2L 3G1, Canada

autor

Shallit J.

• School of Computer Science University of Waterloo Waterloo, ON N2L 3G1, Canada

Bibliografia

• [1] Berstel, J., Boasson, L., Carton, O., Petazzoni, B., Pin, J.-E.: Operations preserving regular languages, Theoret. Comput. Sci., 354, 2006, 405–420.
• [2] Lepistö, A., Pappalardi, F., Saari, K.: Transposition invariant words, Theoret. Comput. Sci., 380, 2007, 377–387.
• [3] Markowsky, G.: Bounds on the index and period of a binary relation of a finite set, Semigroup Forum, 13, 1977, 253–259.
• [4] Miller, W.: The maximum order of an element of a finite symmetric group, Amer. Math. Monthly, 94, 1987, 497–506.
• [5] Zhang, G.-Q.: Automata, boolean matrices, and ultimate periodicity, Info. Computation, 152, 1999, 138–154.