2
$\begingroup$

Please help me about this problem.

What's the relationship between $|a \cdot b|$ and $|a|$,$|b|$?

For Example:
$\begin{align}a&=\{11,0,1\} \\ b&=\{0,10\}\\ |a|&=3\\ |b|&=2\\ a\cdot b&=\{110, 1110,00,010,10,110\} = \{110,1110,00,010,10\}\end{align}$

So: $|a \cdot b| = 5$ but if $b=\{0,110\}$ then $a \cdot b=\{110,11110,00,0110,10,1110\}$ So: $|a \cdot b|=6$

How to make a formula for it?

  • 0
    Nice question, actually, as shown by dtldarek's comprehensive answer. In fact, you've touched on an active and rather deep area of research, namely the complexity of regular sets and their expressions and compositions under various operations, dot-depth and all that.2012-03-06

1 Answers 1

5

I assume that the $\cdot$ binary operation is the string concatenation extended to sets.

There are some special cases like $|a| = 0$ or $|a| = 1$ and similarly for $b$, but if $|a| \geq 2$ and $|b| \geq 2$, you can show a bit more: $|a|+|b| \leq |a\cdot b| \leq |a| |b|$. You can easily construct two extreme cases:

  • $|a\cdot b| = |a| |b|$ for any $a \subseteq \{ (01|10)^*111 \}$ and $b \subseteq \{ 000(01|10)^* \}$ where $^*$ is the Kleene star,
  • $|a|+|b| = |a\cdot b|$ for $a = \{ 0^k | k=1\ldots |a|\}$ and $b = \{ 0^k | k = 1\ldots |b|\}$.

Of course $|a\cdot b| \leq |a \times b| = |a||b|$. To prove that the second one is also an extreme case, let $c = a \cdot b$ and split all those sets by word length, i.e. let $a_k = \{ x \in a |\ \mathrm{length}(x) = k \}$, analogously for $b_k$ and $c_k$. We want to show that $ \sum_i |a_i| + \sum_j |b_j| \leq \sum_k |c_k| \,. \quad\quad\quad(1)$

First, consider the case where there is only one $k$ such that $a_k \neq 0$ (i.e. all the words from $a$ are the same length), then $|a\cdot b| = |a_k \cdot b| = |a_k||b| \geq |a|+|b|$ since $|a| \geq 2$ and $|b| \geq 2$. The similar case holds for $b$ if it contains words of the same length.

Now, let us assume (2) that there are words of different length in both $a$ and $b$. It is true that $ |c_k| = \left|\bigcup_i a_i \cdot b_{k-i}\right| \geq \max_{i} \{ |a_i \cdot b_{k-i}|\}\,. $ Let us say that $a_i$ participates in $c_k$ if $a_i \cdot b_{k-i}$ is not empty. From the equation above, if $a_i$ participates in $c_k$ then $|a_i| \leq |c_k| \,, \quad\quad\quad(3)$ same for $b_j$ (4). Thanks to the assumption (2) for every non-empty $a_i$ there are at least two sets $c_k$ it participates in. Also, there are similar two (or more) sets for every $b_j$, therefore there exists a perfect matching from non-empty $a$-s and $b$-s to non-empty $c$-s. Summing by this matching and applying one of (3),(4) we get (1) and that completes the proof.

  • 1
    I think there may be no closed formula for this.2012-03-05