| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 438115 | Theoretical Computer Science | 2009 | 9 Pages |
Abstract
Let the words of a language L be arranged in increasing radix order: L={w0,w1,w2,…}. We consider transformations that extract terms from L in an arithmetic progression. For example, two such transformations are and . Lecomte and Rigo observed that if L is regular, then so are , , and analogous transformations of L. We find good upper and lower bounds on the state complexity of this transformation. We also give an example of a context-free language L such that is not context-free.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
