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?

  • 1
    $|a \cdot b| \leq |a||b|$2012-03-05
  • 6
    About the most you can say in general, I think, is that $$\max\{|a|,|b|\}\le|a\cdot b|\le|a||b|\;.$$2012-03-05
  • 3
    It looks like the binary operation $\cdot$ is string concatenation, which we can extend to a binary operation on sets. So maybe there is also an appropriate tag from computer science for this question?2012-03-05
  • 0
    @Willie, I don't think there is any field of computer science in which concatenation of strings is a central object of study. [tag:string-theory] perhaps? :)2012-03-05
  • 0
    @RahulNarain not concatenation per se :) String algorithms are pervasive in bioinformatics (which is under algorithms research group in my university).2012-03-05
  • 1
    @Gigili: Hey, it's Cauchy-Schwarz!2012-03-05
  • 0
    @NateEldredge: Right, what do you mean? $\cdot$ is a binary operation here as mentioned in comments.2012-03-05
  • 0
    @Gigili: I know, it's just a joke.2012-03-05
  • 0
    @Rahul, formal language theory has quite a lot to say about string concatenation; including the extension to sets of strings (_i.e._, languages) under consideration here.2012-03-06
  • 0
    My jokes have really been falling flat today. I should stop.2012-03-06
  • 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