0
$\begingroup$

Let $L=\{0,1\}^*$ (the set of binary words on $0$ and $1$), Given an integer $k$, and $S$ a finite subset of $L$ define recursively the following sequence of subsets of $L$: $$\begin{align} A_1 &=S\cup \{\epsilon\} \\ A_{n+1} &=\left\{\prod_{i=1}^ka_i^{n_i}\Big/a_i\in A_n, n_i\in \Bbb{N}\right\}\end{align}$$

My question:

For each integer $n$ there exists a polynomial $P$ such that the number of words of length $h$ in $A_n$ is less or equal to $P(h)$.

Example if $S=\left\{\epsilon,0,1\right\}$ and $k=2$ then $$A_2=\left\{\prod_{i=1}^2a_i^{n_i}\Big/a_i\in S \right\}=\left\{0^n1^m,1^n0^m/n,m\in\Bbb N\right\}$$ and the number of words of length $h$ is $2h+2$.

If $S$ is finite then I can prove that $A_2$ contains no more than $|S|\dbinom{|S|+k-1}{k-1}$, but how can I prove a similar result for $A_n$.

Thanks for your help.

$\endgroup$
2
  • $\begingroup$ Are you shure of your $k$ in the definition of $A_{n+1}$ (in the term $\prod_{i=1}^k\, a_i^{n_i}$) ? $\endgroup$
    – Duchamp Gérard H. E.
    Apr 3, 2015 at 17:43
  • $\begingroup$ Yes, every time we only use the product of $k$ elements and $k$ is fixed in the beginning so the sequence of subsets depends on $S$ and $k$ $\endgroup$
    – Elaqqad
    Apr 3, 2015 at 17:45

1 Answer 1

Reset to default
1
$\begingroup$

HINT: A word of length $h$ in $A_{n+1}$ is a composition of words of $A_n$, each of which must obviously have length at most $h$. There is a polynomial $P_n$ such that $A_n$ has at most $\sum_{i=0}^nP_n(i)$ words of length at most $h$, so you’re essentially working with an alphabet of size at most $\sum_{i=0}^nP_n(i)$.

$\endgroup$
6
  • $\begingroup$ The problem is a word has lenght $h$ in $A_{n+1}$ if ond only if there exists $h_1n_1+\cdots+h_kn_k=n$ for some integers $n_i$ and words $w_i$ of lenght $h_i$ in $A_n$ and so : $$P_{n+1}=\sum_{(h_1,\cdots,h_k)}P_n(h_1)P_n(h_2)\cdots P_n(h_k) Numsol(h_1n_1+\cdots+h_kn_k=h) $$ $\endgroup$
    – Elaqqad
    Apr 3, 2015 at 18:12
  • $\begingroup$ @Elaqqad: But you need only an upper bound, so there’s no harm in overcounting. $\endgroup$
    – Brian M. Scott
    Apr 3, 2015 at 18:20
  • $\begingroup$ Do you mean that we can take $P_{n+1}=(\sum_{i=1}^nP_n(i))^k$ $\endgroup$
    – Elaqqad
    Apr 3, 2015 at 18:28
  • $\begingroup$ @Elaqqad: No, it would be $P_{n+1}(h)=\left(\sum_{i=0}^hP_n(i)\right)^k$. $\endgroup$
    – Brian M. Scott
    Apr 3, 2015 at 18:35
  • $\begingroup$ Ok thanks you very much! $\endgroup$
    – Elaqqad
    Apr 3, 2015 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.