I'm reading an article which defines something called a hash function.

Let $n\in\mathbb{N}$ and let $H:\{0,1\}^*\to\{0,1\}^n:m\to h=H(m)$...

I know that $\{0,1\}^n$ is the cartesian product of the set with itself $n$ times, but I am not familiar with the meaning of the asterisk in this context for $\{0,1\}^*$

Is anyone familiar with the notation?

  • 9
    $\begingroup$ I think this is Kleene star. $\endgroup$ – Wojowu Feb 26 '16 at 20:13
  • 1
    $\begingroup$ It should be emphasized that the answer given here (the Kleene star) applies to this particular case, as easily inferred from the context. There are dozens, if not hundreds, of different uses of a superscript asterisk in mathematics (and whatever text you're reading is not doing a very good job if the notation has not been clearly introduced and occasionally recalled). $\endgroup$ – Gro-Tsen Feb 26 '16 at 22:29

In your case $$\{0,1\}^*=\bigcup_{n=0}^\infty\{0,1\}^n$$

In context of hash-functions, $\{0,1\}^*$ would be the set of strings with "letters" 0,1; including the empty string but no single infinite string.


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.