Decimations of languages and state complexity
2009; Elsevier BV; Volume: 410; Issue: 24-25 Linguagem: Inglês
10.1016/j.tcs.2009.02.024
ISSN1879-2294
AutoresDalia Krieger, Avery Miller, Narad Rampersad, Bala Ravikumar, Jeffrey Shallit,
Tópico(s)DNA and Biological Computing
ResumoLet 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 even(L)={w0,w2,w4…} and odd(L)={w1,w3,w5,…}. Lecomte and Rigo observed that if L is regular, then so are even(L), odd(L), 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 even(L) is not context-free.
Referência(s)