# Tag Info

6

The answer by @YuvalFilmus is perfectly fine, and points you to the import notion of star height. But let me add a little bit more. We will show that languages of your form give a proper subset of the languages of star height one. But first, some musings what might come close to your form. General Regular Languages First, probably the closest form to yours ...

3

Interesting question. The right intuition should probably be along the guideline that two random subsets of cardinality $n$ drawn from some $cn$ elements for some constant $c$ differ from each other significantly with a probability very close to 1 and, hence, the weight of the minimum spanning tree of the graph $G$ should be $\mathcal\Theta(n^2)$ on average. ...

2

You can't. Consider the following sets for some $k$, with $m=k^2$ (they both are powers of $2$): $\{1..k\}$, $\{k+1..2k\}$, $\ldots$, $\{m-k+1..m\}$ $\{1, 3, 5, \ldots, 2k-1\}$, $\{2, 4, 6, \ldots, 2k\}$, $\{2k+1, 2k+3, \ldots, 4k - 1\}$, $\{2k+2, 2k+4, \ldots, 4k\}$, $\ldots$ $\{1, 5, 9, \ldots, 4k - 3\}$, $\{2, 6, 10, \ldots, 4k-2\}$ $\ldots$. Each ...

2

Every language of this form can be represented as a regular expression without nested Kleene star. That is, its star height is $1$. The star height hierarchy is strict, and in particular, it is known that the language $(a^*b^*c)^*$ cannot be represented in that form. An example over a binary alphabet would be $(aa(ab)^*bb(ab)^*)^*$.

2

You can reduce 1-IN-3 SAT to your problem (an instance is a 3CNF, and we want to find a satisfying assignment having exactly one satisfied literal per clause), assuming $p \geq 3$. A clause $x \lor y \lor z$ is encoded as the constraint $x+y+z=1$. A clause $\bar x \lor y \lor z$ is encoded as the constraint $1-x+y+z = 1$; and so on. When $p = 2$, your ...

1

A set "multiplied" with another set is called the cartesian product and is formed of tuples of elements, one from each set you are multiplying. If you have $S = \{a, b\}$ and $T = \{x, y\}$, then $$S \times T = \{ (a,x), (a,y), (b, x), (b, y)\},$$ and its cardinality is actually $|S\times T| = |S| \cdot |T|$.

1

This is how you should solve it. Let $\Sigma_1=\Sigma$ We are asked to find: $|\Sigma^ 4|$ Now $$\Sigma^4 = \Sigma . \Sigma . \Sigma . \Sigma = \{a,b\} . \{a,b\}. \{a,b\} . \{a,b\}$$ $$\text{ Here . means the concatenation operator}$$ So this is equivalent to number of ways of forming strings of length $4$ with symbols from $\Sigma$. We have $4$ places, ...

1

You don't define $H_0$. Presumably it's an undecidable set. First, $f : \mathbb{N} \to H_0$ only means that all the values of $f(x)$ are in $H_0$, i.e. the image of $f$ is a subset of $H_0$: $f(\mathbb{N}) \subseteq H_0$. The proof of the counterexample involves a stronger property: it constructs a function $f$ whose image is exactly $H_0$, that is, \$f(\...

Only top voted, non community-wiki answers of a minimum length are eligible