title: How to show that L = L(G)?

text:
# Question
Title: How to show that L = L(G)?
Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is important that the grammar at hand is *correct*, that is generates exactly the desired words.

We can often argue on a high-level why the grammar is an adequate representation of the desired language, omitting a formal proof. But what if we are in doubt or need a formal proof for some reason? What are techniques we can apply?

This is supposed to become a reference question. Therefore, please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

# Answer
Grammars are inherently recursive objects, so the answer seems obvious: by induction. That said, the specifics are often tricky to get right. In the sequel I will describe a technique that allows to reduce many a grammar-correctness proof to mechanical steps, provided some creative preprocessing is done. $\newcommand{\lang}\[1\]{\mathcal{L}(#1)} \newcommand{\sent}\[1\]{\vartheta(#1)} \newcommand{\derive}{\mathbin{\Rightarrow}} \newcommand{\derivestar}{\mathbin{\Rightarrow^\*}} \newcommand{\nats}{\mathbb{N}}$

The basic idea is to not restrict oneself to *words* of grammar and language; it is hard to grasp the structure of the grammar in this way. Instead, we will argue about the set of *sentences* the grammar can create. Furthermore, we will split one daunting proof goal into many small goals that are more tractable.

Let $G=(N,T,\delta,S)$ a formal grammar with non-terminals $N$, terminals $T$, rules $\delta$ and starting symbol $S \in N$. We denote by $\sent{G}$ the set of sentences that can be derived from $S$ given $\delta$, that is $\alpha \in \sent{G} \iff S \derivestar \alpha$. The language generated by $G$ is $\lang{G} = \sent{G} \cap T^\*$. Suppose we want to show that $L = \lang{G}$ for some $L \subseteq T^\*$.

## The ansatz

Here is how we go about that. We define $M\_1, \dots, M\_k \subseteq (N \cup T)^\*$ so that

1. $\displaystyle \sent{G} = \bigcup\_{i=1}^k M\_i$ and
2. $\displaystyle T^\* \cap \bigcup\_{i=1}^k M\_i = L$.

While 2. is usually clear by definition of the $M\_i$, 1. requires some serious work. The two items together clearly imply $\lang{G} = L$ as desired.

For ease of notation, let's denote $M = \bigcup\_{i=1}^k M\_i$.

## The rocky road

There are two major steps to performing such a proof.

* **How to find (good) $M\_i$?**
One strategy is to investigate *phases* the grammar works through. Not every grammar is amenable to this idea; in general, this is a creative step. It helps if we can define the grammar ourselves; with some experience, we will be able to define grammars more tractable with this approach.
* **How to prove 1.?**
As with any set equality, there are two directions.

+ $\sent{G} \subseteq M$: (structural) induction over the productions of $G$.
    + $M \subseteq \sent{G}$: Usually one induction by $M\_i$, starting from the one that contains $S$.

This is as specific as it gets; the details depend on the grammar and language at hand.

## Example

Consider the language

$\qquad \displaystyle L = \\{ a^n b^n c^m \mid n,m \in \nats \\}$

and the grammar $G = (\\{S,A\\}, \\{a,b,c\\}, \delta, S)$ with $\delta$ given by

$\qquad \begin{align} S &\to Sc \mid A \\ A &\to aAb \mid \varepsilon \end{align}$

for which we want to show that $L = \lang{G}$. What are the phases this grammar works through? Well, first it generates $c^m$ and then $a^n b^n$. This immediately informs our choice of $M\_i$, namely

$\qquad \begin{align} M\_0 &= \\{Sc^m \mid m \in \nats \\} \\;, \\ M\_1 &= \\{ a^n A b^n c^m \mid m,n \in \nats \\} \\;, \\ M\_2 &= \\{ a^n b^n c^m \mid m,n \in \nats \\} \\;. \\ \end{align}$

As $M\_2 = L$ and $M\_0 \cap T^\* = M\_1 \cap T^\* = \emptyset$, item 2. is already taken care of. Towards 1., we split the proof in two parts as announced.

$\mathbf{\sent{G} \subseteq M}$

We perform structural induction along the rules of $G$.

**I.A.:** Since $S = Sc^0 \in M\_0$ we anchor successfully.

**I.H.:** Assume for some set of sentences $X \subseteq \sent{G}$ that we also know $X \subseteq M$.

**I.S.:** Let $w \in X \subseteq \sent{G} \cap M$ arbitrary. We have to show that whatever form $w$ has and whatever rule is applied next, we don't leave $M$. We do this by complete case distinction. By induction hypothesis, we know that (exactly) one of the following cases applies:

* $w \in M\_0$, that is $w = Sc^m$ for some $m \in \nats$.
Two rules can be applied, both of which derive a sentence in $M$:
    + $Sc^m \derive Sc^{m+1} \in M\_0$ and
    + $Sc^m \derive Ac^m = a^0Ab^0c^m \in M\_1$.
* $w \in M\_1$, i.e. $w = a^nAb^nc^m$ for some $m,n \in \nats$:
    + $w \derive a^{n+1}Ab^{n+1}c^m \in M\_1$ and
    + $w \derive a^nb^nc^m \in M\_2$.
* $w \in M\_2$: since $w \in T^\*$, no further derivations are possible.

Since we have successfully covered all cases, the induction is complete.

$\mathbf{\sent{G} \supseteq M}$

We perform one (simple) proof per $M\_i$. Note how we chain the proofs so "later" $M\_i$ can anchor using the "earlier" $M\_i$.

* $M\_1$: We perform an induction over $m$, anchoring in $Sc^0 = S$ and using $S \to Sc$ in the step.
* $M\_2$: We fix $m$ to an arbitrary value and induce over $n$. We anchor in $Ac^m$, using that $S \derivestar Sc^m \derive Ac^m$ by the former proof. The step progresses via $A \to aAb$.
* $M\_3$: For arbitrary $m,n \in \nats$ we use the former proof for $S \derivestar a^nAb^nc^m \derive a^nb^nc^m$.

This concludes the second direction of the proof of 1., and we are done.

We can see that we heavily exploit that the grammar is *linear*. For non-linear grammars, we need $M\_i$ with more than one variable parameter (in the proof(s)), which can become ugly. If we have control over the grammar, this teaches us to keep it simple. Consider as deterring example this grammar which is equivalent to $G$:

$\qquad \begin{align} S &\to aAbC \mid \varepsilon \\ A &\to aAb \mid \varepsilon \\ C &\to cC \mid \varepsilon \end{align}$

## Exercise

Give a grammar for

$\qquad L = \\{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \nats, k \neq o, 2l = n, m \geq 2 \\}$

and prove its correctness.

If you have trouble, a grammar:

> Consider $G = (\\{S,B\_r,B\_l,A,C\\}, \\{a,b,c\\}, \delta, S)$ with productions
> $\quad \begin{align} S &\to bSb \mid B\_l \mid B\_r \\ B\_l &\to bB\_l \mid bA \\ B\_r &\to B\_r b \mid Ab \\ A &\to aAaa \mid C \\ C &\to bcC \mid bcbc \end{align}$

and $M\_i$:

> $\quad\begin{align} M\_0 &= \\{ b^i S b^i \mid i \in \nats \\} \\ M\_1 &= \\{ b^i B\_l b^o \mid o \in \nats, i \geq o \\} \\ M\_2 &= \\{ b^k B\_r b^i \mid k \in \nats, i \geq k \\} \\ M\_3 &= \\{ b^k a^i A a^{2i} b^o \mid k,o,i \in \nats, k \neq o \\} \\ M\_4 &= \\{ b^k a^l (bc)^i C a^{2l} b^o \mid k,o,l,i \in \nats, k \neq o \\} \\ M\_5 &= L \end{align}$

## What about non-linear grammars?

The characterising feature of the class of context-free languages is the Dyck language: essentially, every context-free language can be expressed as the intersection of a Dyck language and a regular language. Unfortunately, the Dyck language is not linear, that is we can give no grammar that is inherently suited to this approach.

We can, of course, still define $M\_i$ and do the proof, but it's bound to be more arduous with nested inductions and what not. There is one general way I know of that can help to some extent. We change the ansatz to showing that we generate *at least* all required words, and that we generate the right amount of words (per length). Formally, we show that

1. $\displaystyle \sent{G} \supseteq L$ and
2. $\displaystyle |\lang{G} \cap T^n| = |L \cap T^n|$ for all $n \in \nats$.

This way, we can restrict ourselves to the "easy" direction from the original ansatz and exploit structure in the language, ignoring overcomplicated features the grammar may have. Of course, there is no free lunch: we get the all new task of counting the words $G$ generates for *each* $n \in \nats$. Lucky for us, this is often tractable; see here and here for details¹. You can find some examples in my bachelor thesis.

For ambiguous and non-context-free grammars, I'm afraid we are back to ansatz one and thinking caps.

---

1. When using that particular method for counting, we get as a bonus that the grammar is unambiguous. In turn, this also means that the technique has to fail for ambiguous grammars as we can never prove 2.
> 26 votes

---
Tags: formal-languages, formal-grammars, proof-techniques, reference-question
---


# Question
Title: Did I correctly prune this min-max search tree using alpha-beta pruning?
I am studying some old past test questions. Is this search tree correctly pruned?

# Answer
> 0 votes
I was close. Here's an answer from my tutor which makes sense:

> There should be some pruning on the last branch.
>
> When descending into the third branch from the main node, the top criteria is \>=12. The first sub-tree of that node sets its value to 13 (\>12), so the next sub-tree is expanded. When the value of the node changes to 12 after the second sub-tree is completed, the condition triggers.
>
> It doesn't matter what the value of the last sub-tree is. If the value is \> 12 then min will choose it and max will choose the previous top-level sub-tree (value 12). if the value is \<= 12 then min will choose 12 and the overall value doesn't change. For this reason the last two nodes (both value 10) are pruned before being examined.

I think he may have slightly messed up his wording in the last paragraph, but basically we are not going to improve on the 12, as min will select 12 and less, so there's no point in checking anymore.

# Answer
> 1 votes
I once implemented this in common lisp and running my program on your tree tells me that the pruned nodes are the one you marked and also the rightmost leaf and its parent. The output of the program gives $\alpha$ and $\beta$ values for each node (if you mark from A through X in a BFS manner, left-to-right. Then O and J are pruned).

```
MIN: K     -INFTY    11        [v:11]
MIN: L     11        INFTY     [v:9]
MAX: E     11        INFTY     [v:11]
MIN: M     -INFTY    4         [v:4]
MIN: N     4         11        [v:13]
MAX: F     4         11        [v:13]
MIN: B     -INFTY    11        [v:11]
MIN: P     11        12        [v:12]
MIN: Q     12        INFTY     [v:8]
MIN: R     12        INFTY     [v:4]
MAX: G     12        INFTY     [v:12]
MIN: C     11        12        [v:12]
MIN: S     12        INFTY     [v:9]
MIN: T     12        13        [v:13]
MIN: U     13        INFTY     [v:1]
MAX: H     13        INFTY     [v:13]
MIN: V     12        13        [v:12]
MIN: W     12        13        [v:9]
MAX: I     12        13        [v:12]
MIN: D     12        13        [v:12]
MAX: A     12        INFTY     [v:12]
12
21
T

```

---
Tags: search-trees, check-my-answer
---


# Question
Title: Behavior of iterative application of LZ77
I have been experimenting with LZ77 (naively $O(n^2)$ runtime, infinite window). Applying it to the 7th Fibonacci word $abaababaabaab$ yields the correct LZ factorization:

$\qquad a,b,a,aba,baaba,ab$.

My question is about the behavior of LZ77 if we iterate it. My experiments suggest that reapplication of LZ77 to the input will yield no further patterns that were not found the first time.

By reapplication I mean, where in the first instance we treat the factors of the string as the sequence of unit symbols 'a' and 'b', in the second application the factors are the LZ factors. I was hoping to discover (over larger various texts, like the Complete Sonnets of Shakespeare) increasing gains, and possibly, "multilevel" patterns found by LZ over the sequence of factors of the previous iterate. But none of this occurred. The sequence of factors after the second iteration is exactly the same as the first.

So where is the bug in my thinking? Is there a simple proof of this given the definition of an LZ factor being the longest prefix from the current position occurring in the concatenation of the preceding LZ factors?

# Answer
> 8 votes
Lempel and Ziv proved that under some reasonable assumptions, the limiting rate of their algorithm is equal to the entropy of the text. That means that in the limit, the output should be completely random. Random text cannot be compressed (on average), so you should expect that if you take a long text and apply Lempel-Ziv twice, then the second time wouldn't compress the text at all.

# Answer
> 1 votes
You have to be careful about what you mean by iterative. Did you apply this to a sequence of concatenations of the source string? Because that will certainly increase the dictionary. There might also be some interesting optimal intersections (from the coding perspective of the optimal prefix-free size of the pattern encoding vs the individual optimal prefix symbol encodings) of pattern sizes discovered by applying it forwards and backwards instead of iteratively.

---
Tags: strings, data-compression, lempel-ziv
---


# Question
Title: Approximate time for selection operation using index when equality is on nonkey
In database query processing, the approximate time for selection operation using primary index when equality is on key is $2(b\_s + b\_t)$ where $b\_s$ is disk seek time and $b\_t$ is disk transfer time (assuming one level of indexing), because one seek and transfer time will be needed for finding the index and another one will be for the actual data.

But what will happen if the equality is on a no- key value? Since now we cannot search in the index, don't we have to do a linear search?

# Answer
In this case full table scan will be executed.

The cost is $N$ I/O operations (where $N$ is a number of pages/blocks in your table)
> 1 votes

---
Tags: runtime-analysis, search-algorithms, databases
---


# Question
Title: Number of words in the regular language $(00)^*$
According to Wikipedia, for any regular language $L$ there exist constants $\lambda\_1,\ldots,\lambda\_k$ and polynomials $p\_1(x),\ldots,p\_k(x)$ such that for every $n$ the number $s\_L(n)$ of words of length $n$ in $L$ satisfies the equation

$\qquad \displaystyle s\_L(n)=p\_1(n)\lambda\_1^n+\dots+p\_k(n)\lambda\_k^n$.

The language $L =\\{ 0^{2n} \mid n \in\mathbb{N} \\}$ is regular ($(00)^\*$ matches it). $s\_L(n) = 1$ iff n is even, and $s\_L(n) = 0$ otherwise.

However, I can not find the $\lambda\_i$ and $p\_i$ (that have to exist by the above). As $s\_L(n)$ has to be differentiable and is not constant, it must somehow behave like a wave, and I can't see how you can possibly do that with polynomials and exponential functions without ending up with an infinite number of summands like in a Taylor expansion. Can anyone enlighten me?

# Answer
> 14 votes
For your language, can you take $p\_0(x) = 1/2$, $\lambda\_0 = 1$, $p\_1(x) = 1/2$, $\lambda\_1 = -1$, and $p\_i(x) = \lambda\_i = 0$ for $i \> 1$? The Wikipedia article doesn't say anything about the coefficients being either positive or integral. The sum for my choices is

$\qquad \displaystyle 1/2 + 1/2(-1)^n = 1/2 (1 + (-1)^n)$

which seems to be 1 for even $n$, and 0 for odd $n$. Indeed, a proof by induction seems straightforward.

# Answer
> 11 votes
@Patrick87 gives a great answer for your specific case, I thought I would give a tip of how to find $s\_L(n)$ in the more general case of any language $L$ that can be represented by an irreducible DFA (i.e. if it is possible to get to any state from any state). Note that your language is of this type.

---

### Proof of theorem for irreducible DFAs

Let $D$ be the transition matrix of your $m$-state DFA, since it is irreducible, the matrix is normal and has a full eigenbasis $|\lambda\_1\rangle ... |\lambda\_m\rangle$. Let $|A\rangle$ be the accept vector: i.e. $\langle i | A \rangle$ is 1 if $i$ is an accept state, and 0 otherwise. WLOG assume that $|1\rangle$ is the initial state, and since we have a complete eigenbasis, we know that $|1\rangle = c\_1|\lambda\_1\rangle + ... + c\_m|\lambda\_m\rangle$ for some coefficients $c\_1 ... c\_m$ (note that $c\_i = \langle \lambda\_i | i \rangle$).

Now we can prove a restricted case of the theorem in the question (restricted to irreducible DFAs; as an exercise generalize this proof to the whole theorem). Since $D$ is the transition matrix $D|1\rangle$ is the vector of states reachable after reading any one character, $D^2|1\rangle$ is the same for two characters, etc. Given a vector $|x\rangle$, $\langle A|x\rangle$ is simply the sum of the components of $|x\rangle$ that are accept states. Thus:

$$ \begin{align} s\_L(n) & = \langle A |D^n| 1 \rangle \\ & =\langle A | D^n (c\_1 |\lambda\_1\rangle ... c\_m |\lambda\_m\rangle) \\ & = c\_1 \lambda\_1^n \langle A | \lambda\_1 \rangle + ... + c\_m \lambda\_m^n \langle A | \lambda\_m \rangle \\ & = \langle A | \lambda\_1 \rangle\langle\lambda\_1|1\rangle \lambda\_1^n + ... + \langle A | \lambda\_m \rangle\langle \lambda\_m | 1 \rangle \lambda\_m^n \\ & = p\_1\lambda\_1^n + ... + p\_m \lambda\_m^m \end{align} $$

Now we know that for an irreducible m-state DFA, $p\_1 ... p\_m$ will be zero order polynomials (i.e. constants) that depends on the DFA and $\lambda\_1 ... \lambda\_m$ will be eigenvalues of the transition matrix.

### Generality note

If you want to prove this theorem for arbitrary DFA, then you will need to look at the Schur decomposition of $D$ and then polynomials of non-zero degree will pop up because of the nilpotent terms. It is still enlightening to do this, since it will let you bound the max degree of the polynomials. You will also find a relationship between how complicated the polynomials are and how many $\lambda$s you will have.

---

### Application to specific question

For your language $L$ we can select the DFA with transition matrix:

$$ D = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} $$

and accept vector:

$$ A = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$$

Find the eigenvectors and their eigenvalues $\lambda\_1 = 1$ with $| \lambda\_1 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ and $\lambda\_2 = -1$ with $| \lambda\_2 \rangle = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ -1 \end{pmatrix}$. We can use this to find $p\_1 = 1/2$ and $p\_2 = 1/2$. To give us:

$$s\_L(n) = \frac{1}{2} + \frac{1}{2}(-1)^n$$

# Answer
> 6 votes
Continuing Artem's answer, here is a proof of the general representation. As Artem shows, there is an integer matrix $A$ and two vectors $x,y$ such that $$ s\_L(n) = x^T A^n y. $$ (The vector $x$ is the characteristic vector of the start state, the vector $y$ is the characteristic vector of all accepting state, and $A\_{ij}$ is equal to the number of transitions from state $i$ to state $j$ in a DFA for the language.)

Jordan's theorem states that over the complex numbers, $A$ is similar to a matrix with blocks of one of the forms $$ \begin{pmatrix} \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 & 0 \\ 0 & \lambda & 1 & 0 \\ 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & \lambda \end{pmatrix}, \ldots $$ If $\lambda \neq 0$, then the $n$th powers of these blocks are $$ \begin{pmatrix} \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} \\ 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2} \lambda^{n-2} \\ 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} & \binom{n}{3}\lambda^{n-3} \\ 0 & \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} \\ 0 & 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & 0 & \lambda^n \end{pmatrix}, \ldots $$ Here's how we got to these formulas: write the block as $B = \lambda + N$. Successive powers of $N$ are successive secondary diagonals of the matrix. Using the binomial theorem (using the fact that $\lambda$ commutes with $N$), $$ B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots. $$ When $\lambda = 0$, the block is nilpotent, and we get the following matrices (the notation $\[n = k\]$ is $1$ if $n=k$ and $0$ otherwise): $$ \begin{pmatrix} \[n=0\] \end{pmatrix}, \begin{pmatrix} \[n=0\] & \[n=1\] \\ 0 & \[n=0\] \end{pmatrix}, \begin{pmatrix} \[n=0\] & \[n=1\] & \[n=2\] \\ 0 & \[n=0\] & \[n=1\] \\ 0 & 0 & \[n=0\] \end{pmatrix}, \begin{pmatrix} \[n=0\] & \[n=1\] & \[n=2\] & \[n=3\] \\ 0 & \[n=0\] & \[n=1\] & \[n=2\] \\ 0 & 0 & \[n=0\] & \[n=1\] \\ 0 & 0 & 0 & \[n=0\] \end{pmatrix} $$

Summarizing, every entry in $A^n$ is either of the form $\binom{n}{k} \lambda^{n-k}$ or of the form $\[n=k\]$, and we deduce that $$ s\_L(n) = \sum\_i p\_i(n) \lambda\_i(n) + \sum\_j c\_j \[n=j\], $$ for some complex $\lambda\_i,c\_j$ and complex polynomials $p\_i$. In particular, for large enough $n$, $$ s\_L(n) = \sum\_i p\_i(n) \lambda\_i(n). $$

---
Tags: formal-languages, regular-languages, combinatorics, word-combinatorics
---


# Question
Title: Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state
I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question. The question states that the PDA has at most 2 states. Clearly 1 will be the start state while the other will be the final state (they cannot be the same since otherwise the empty string will be accepted). My initial idea was to take a grammar for $L$ in GNF (Greibach Normal Form) (refer to Ran's answer below for details on how a CFG in GNF can be converted to a PDA having 1 state and no $\epsilon$-transitions that accepts by empty store) and then give a PDA for this that meets the specification. But the problem is that I cannot find a way to do this without having an $\epsilon$-move at the final step when I have to move to the final state after the stack is empty. Any help would be greatly appreciated.

The PDA can be specified as $M = (K, \Sigma,\delta, q\_0, Z\_0, \\{q\_f\\} )$ where $q\_0$ is the initial state, $Z\_0$ is the initial stack symbol and $q\_f$ is the final state. The exact question is

> Show that if $L$ is a CFL and $\epsilon$ does not belong to $L$, then there is a PDA $M$ accepting $L$ by final state such that $M$ has at most 2 states and makes no $\epsilon$-moves.

Thus, the PDA should

1. accept by final state
2. have at most 2 states
3. make no $\epsilon$-moves

# Answer
Indeed, as you say, a PDA can accept by final state or by empty stack. The two acceptance criteria can be effectively translated into one another. Main ingredient of that translation is to clearly mark the bottom symbol of the stack, so the PDA knows when the stack will be empty. In that way it will not accidently block or accept when not planned.

True, given a CF grammar you can construct a single state PDA, accepting by empty stack. In that simulation the contents of the stack correspond to the part of the string not rewritten in a leftmost derivation. If the CFG you start with is in Greibach Normal form, then the PDA can be constructed to be "real-time" i.e., it has no $\epsilon$-moves.

The point is to combine both ideas. Thus mark the last nonterminal. When it is removed (not replaced by another nonterminal), then move to the second state, the final accepting state (at the same time emptying the stack).

For the CFG from your example $S\to aSB, S\to aB, B\to b$ this can be obtained by changing the grammar a little and making a "marked" copy $\bar X$ of each nonterminal $X$ to indicate bottom of stack: $\bar S\to aS\bar B, \bar S\to a\bar B, \bar B\to b, S\to aSB, S\to aB, B\to b$. Production $\bar B\to b$ is the final one. $\bar S$ is the new start symbol.
> 3 votes

# Answer
Converting a CFG to PDA can be done with a PDA that has only 2 states, but indeed you will need to use epsilon moves, at least in the second state that performs the derivation of the word and compares it to the input (avoiding $\epsilon$-moves in the first state is trivial).

The reason you need $\epsilon$-moves, is to perform the derivation of the word over the stack without reading the input. for instance, if the grammar is something like $S\to A$, $A\to a$, then you need an $\epsilon$-move to perform the first transition on the stack, but for the second rule you don't need an $\epsilon$-move, as you can do this production only when the input is $a$.

In other words, if all your productions were of the form $$ A \to \alpha B\_1 B\_2 B\_3$$ where $\alpha$ is a terminal and $B\_i$ is a variable – you will be able to avoid $\epsilon$-moves.

But this is exactly Greibach's Normal Form. Since any CFG can be converted into Greibach's normal-form, you are done.
> 2 votes

---
Tags: formal-languages, context-free, automata, pushdown-automata
---


# Question
Title: Space complexity for finding the minimum number outside the list of numbers
We are given an (unsorted) list $L=(a\_1,\dots,a\_n)$ of numbers of size $n$, where $a\_i\in \\{ 1,\dots,B\\}$.

We want to find the minimum number $x$ from $\\{ 1,\dots,B\\} \backslash L$.

> What is the space complexity of this problem ? (The space to store the input, $L$, does not count.) What if the input $L$ is in a stream which you can only read from left to right for at most constant number of passes ?

The obvious way to solve this is just to copy $L$ into the working memory and then (in-place) sort $L$, and find $x$ in the obvious way. This algorithm uses space of size $n$.

Can we do better ?

# Answer
> 4 votes
You can solve this in time $O(n\log B)$ and constant space (assuming a machine word can store numbers up to $\max(n,B)$) using binary search.

Edit: Here are some more details. I am making the assumption that no number appears twice - perhaps that's an unfounded assumption. Given $K$, we can check whether $K\<L$, $K=L$ or $K\>L$ by counting how many numbers smaller than $K$ appear in the input, and whether $K$ itself appears in the input. This takes $O(n)$.

Edit 2: Following eig's suggestion, since we know that the missing number is smaller than $n+2$, this actually takes time $O(n\log n)$.

# Answer
> 3 votes
For your second question, one can obtain some space bounds for deterministic streaming. (See Sasho Nikolov's answer for the randomized single-pass case.)

If $n$ is constant, you can find the minimum using $\lceil \log\_2 B \rceil$ bits, by storing the smallest element not seen so far, and streaming the list $n$ times. Each pass is guaranteed to either result in the minimum, or to disqualify one (or more, if there are repeats) of the $n$ elements of the list.

I presume you actually meant that $n$ should not be fixed.

Then with single-pass deterministic streaming, one has to use at least $B$ bits of space. This is required to distinguish the different choices of the list $L$, by an application of the single-pass streaming Comparison Lemma (see ECCC TR12-183 for details about the technique). The intuition is that if fewer bits are kept, then there are two input streams that represent two different subsets of $B$ which end up with the same internal state; an adversary can then add numbers to the end of the stream to ensure that the algorithm gives the wrong answer. For an upper bound, $B + 2\lceil \log B \rceil$ bits is enough. Keep an array of $B$ bits, a variable to index to the array, and a temporary variable. Initially the array entries are set to 0. Change the bit for $i$ to 1 if $i$ is read. The first 0 entry in the array gives the right answer. So the lower bound of $B$ bits is nearly tight for single-pass deterministic streaming.

I have not seen this problem before, and I do not know what the bounds would be for more than 1 but less than $n$ passes. See also a similar question of mine at CSTheory.

*Edit:* expanded and corrected the single-pass bounds.

# Answer
> 2 votes
An easy reduction from the Index problem shows a lower bound of $\Omega(B)$ for single pass randomized algorithms. Recall that in the Index problem Alice is given a subset $S$ of $U$ and Bob is given an element $e$ of $U$. The goal is to compute whether $e \in S$. The (randomized) one-way communication complexity of Index is $\Omega(|U|)$.

For the reduction, let us identify $U$ with $\\{1, \ldots, B\\}$, i.e. fix some bijection $f$ between $U$ and $\\{1, \ldots, B\\}$. For an instance $(S, e)$ of the Index problem, let $L\_0 = \\{1, \ldots, B\\} \setminus f(S)$, where $f(S) = \\{f(a): a \in S\\}$; let $L\_1 = \\{i: i \< f(e)\\}$. The stream consists of $L\_0$ followed by $L\_1$. Clearly the minimum number not in $L = L\_0 \cup L\_1$ is at least $f(e)$, because $L\_1$ includes all numbers smaller than $f(e)$. If $e \in S$, then $L\_0$ does not include $f(e)$ and the minimum number outside $L$ is at least $f(e) + 1$; otherwise the minimum is $f(e)$.

As usual, Alice can process $L\_0$ using the streaming algorithm, send the contents of memory to Bob, who then uses the memory to process $L\_1$ and compute the final answer and decide whether $f \in S$. This gives a one-way communication protocol for Index with communication complexity at most the space complexity of the streaming protocol, and, because the communication complexity is at least $\Omega(|U|) = \Omega(B)$, the space complexity is at least as many bits as well. Obviously this is tight up to constants for single-pass streaming.

# Answer
> 1 votes
Suppose instead that you're interested in the *parity* of $x$. Consider the two-player communication scenario where one player gets the even half of $L$ and the other player gets the odd half of $L$. It seems plausible that the deterministic communication complexity of this game is $\Omega(n)$, and so the usual argument would give an $\Omega(n)$ bits space lower bound.

---
Tags: algorithms, space-complexity, streaming-algorithm
---


title: calculate lower bound of busy beaver

text:
# Question
Title: calculate lower bound of busy beaver
Let $m$ be the number of states (without the halting-state) of a deterministic turing-machine with $\Sigma$ = {} and $\Gamma$ = {$\square$, 0, 1}. Let $G(m)$ be the maximum number of ones, which can be generated by a deterministic turing-machine, before going into the halting-state. Prove that $G(m)$ $\in$ $\Omega(2^m)$. (This is about the so called "busy beaver" problem, with the mathematical rado-function $\Sigma(N)$ or $bb(N)$.) Who can me help with that?

# Answer
All you need to do is show that a machine with $m$ states can halt with $\Omega(2^m)$ 1's on the tape.

There are many ways to prove this. This is just one suggestion, and it may be sub-optimal.

Let $T$ be a machine that on a word of the form $0^i1^j$, when the head is in the leftmost $0$, halts with $0^i1^{2j}$ on the tape and the head at the leftmost $0$.

$T$ is a fixed machine, and thus has $t$ states, for a constant $t$.

We now construct the machine $M\_i$ as follows: first, $M\_i$ writes $0^i1$ on the tape, using $i+1$ states. It then moves the head to the left most cell, using another single state. Then, if the leftmost cell is $0$, it erases it and passes control to $T$ (this requires $t+1$ states). If the leftmost cell is $1$, it halts.

$M\_i$ has $i+2+t$ states, and after it halts the tape contains exactly $2^i$ 1's (since in every call to $T$ we double the number of 1's, and we call $T$ $i$-times).

Thus, if $M\_i$ has $m$ states, it halts with $\frac{2^m}{t+2}\in\Omega(2^m)$ 1's, and we are done.
> 2 votes

---
Tags: turing-machines
---


# Question
Title: Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time?
Given a positively weighted DAG (directed acyclic graph) $D = (V,E)$, can you create a new non-weighted DAG $D'$ by converting each edge with weight $w(e) = x$ into x non-weighted edges and vertices? I believe this would take $O(|E|+W)$ time where $|E|$ is the number of edges and $W$ is the total weight of all edges. My concern is whether I can include this weight variable and still consider this algorithm to be in polynomial time.

(NOTE: This algorithm may apply to all positively weighted graphs, not just DAGs.)

# Answer
> 3 votes
I believe that this would qualify as pseudo-polynomial time. See http://en.wikipedia.org/wiki/Pseudo-polynomial\_time.

The idea is that, usually we represent the time complexity as a function of the length of the string (bit) representation of the input. So your algorithm runs in polynomial time, given a fixed (or at least bounded) value for $W$.

To follow your algorithm, if you perform $O(|w|) $ operations for each edge, you perform $O(2^{b})$ operations where $b$ is the length of the binary-representation of the weight. This means that overall, the algorithm runs in $O(|E|2^{b\_{max}})$, where $b\_{max}$ is the length of the largest edge weight.

In summary, if you fix an upper bound on the edge weights, $b\_{max}$ becomes a constant and the algorithm runs in linear time, but if you allow edge weights to be unbounded, the algorithm is exponential.

This is a common pattern we see when dealing with numerical inputs. The Knapsack problem, as well as factoring the product of two primes, face the same issue.

---
Tags: algorithms, graphs, algorithm-analysis, polynomial-time
---


title: Is Hidoku NP complete?

text:
# Question
Title: Is Hidoku NP complete?
A Hidoku is a $n \times n$ grid with some pre-filled integers from 1 to $n^2$. The goal is to find a path of successive integers (from 1 to $n^2$) in the grid. More concrete, each cell of the grid must contain a different integer from 1 to $n^2$ and each cell with value $z ≠ n^{2}$ must have a neighbor cell with value $z + 1$ (can also be diagonally).

Is it NP hard to decide whether a given Hidoku is solvable? What reduction could be used?

Edit: according to the comments, I give a little clarification. Given is a grid of cells, some of them already contain values (integers from 1 to n²). We must fill all remaining cells with integers from 1 to $n^2$, such that no two cells have the same value and that every cell with value $z ≠ n²$ has a neighbor with value $z + 1$. That is, after filling out the cells, we must find the path $1, 2, 3,\cdots, n^2$. In the grid, which logically visits each cell.

An example of a Hidoku woud be http://www.janko.at/Raetsel/Hidoku/018.c.gif. An already solved Hidoku is http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel\_7august\_hidoku\_schwer\_loesung20100810172340.gif, where you can see the path I was refering to.

# Answer
> 7 votes
I think it is $\sf{NP}$-complete: as noticed by Raphael, Hamiltonian cycle on grid graphs *with holes* problem is NP-complete (Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton Paths in Grid Graphs. SIAM J. Comput. 11(4): 676-686 (1982)).

So given a grid graph $G$ with holes, you can easily build an equivalent Hidoku game where the initial fixed cells fill all the even diagonals; the empty odd diagonals form an undirected graph that is equivalent to the original grid graph $G$ and the Hidoku has a solution if and only if the original grid graph has an Hamiltonian path.

Figure 1: a grid graph with holes and the equivalent $12 \times 12$ Hidoku puzzle (blue cells represent the initial fixed numbered cells ($1$ is the first, $144$ is the last), white cells are the cells that the player must fill, purple line indicates the sequence of the initial fixed numbered cells).

Auxiliary (filled) lines can be added to the bottom or right side to make it a square.

Another example of reduction from a grid graph to an Hidoku puzzle: the 6x4 grid graph is embedded in a larger 13x13 grid; the even diagonals are filled with fixed numbers, and the remaining free cells are equivalent to the original grid graph.

The full picture with transformation can be downloaded here.

Some additional notes to complete the answer:

* the problem is also known as Hidato; the board can have an arbitrary shape (but as a generalization of the square case, it remains NP-hard);
* as correctly evidenced by Steven Stadnicki in his answer it is not obvious that the problem is in NP if the initial partially filled grid is not given as an $n \times n$ array of integers but is given in some *succinct* representation; however it is clearly in NP if the initial board is given using the *reasonable* list of integers representation;
* I think that the original rules of the game say that the *solution should be unique*; so the problem is in US (US-hard), and unlikely to be in NP.

In summary, if we drop the unique solution constraint and specify the initial board with a list of $n^2$ integers the game is $\sf{NP}$-complete.

# Answer
> 2 votes
One subtle catch: while I think that Vor's answer does a pretty good job of explaining why it would be NP-hard, it's not immediately clear that the problem is *in* NP, depending on what you define as the input size! Note that the problem specification for an $n\times n$ grid doesn't actually have to be of size $\Omega(n)$; it consists of the integer $n$ (of size $\lg n$) and some number of triplets of integers $(x\_i, y\_i, w\_i): x\_i, y\_i\leq n, w\_i\leq n^2$ saying that the cell with coordinates $(x\_i, y\_i)$ has value $w\_i$; each of these triplets is of size $\lg n + \lg n + \lg n^2 = 4\lg n\in O(\lg n)$, so unless you have at least $\Omega(n)$ triplets of initial values specified then your total input size might actually be $o(n)$.

It's very possible that you need at least $\Omega(n)$ given cells to have a unique solution, and so any specification with less than that many givens can be rejected out of hand, but (a) that presumes you're asking about the 'unique solution' variant of the problem rather than the 'exists a solution' variant, and (b) it's not immediately obvious that even that restriction is true; I'm not sure how I would go about trying to prove it.

(For a discussion of similar issues, see my question of a while back on the complexity of succinct Nurikabe over on the cstheory.SE site.)

---
Tags: complexity-theory, reductions, np-hard
---


# Question
Title: What is a compact way to represent a partition of a set?
There exist efficient data structures for representing set partitions. These data structures have good time complexities for operations like Union and Find, but they are not particularly space-efficient.

**What is a space-efficient way to represent a partition of a set?**

Here is one possible starting point:

I know that the number of partitions of a set with $N$ elements is $B\_N$, the $N$-th Bell number. So the optimal space complexity for representing a partition of a set with $N$ elements is $\log\_2(B\_N)$ bits. To find such a representation, we could look for a one-to-one mapping between (the set of partitions of a set of $N$ elements) and (the set of integers from $1$ to $B\_N$).

Is there such a mapping that is efficient to compute? What I mean by "efficient" is that I want to convert this compact representation to / from an easy-to-manipulate representation (such as a list of lists) in time polynomial in $N$ or $\log\_2(B\_N)$.

# Answer
> 7 votes
You can use the way that the recurrence formula below is derived to find your encoding: $$ B\_{n+1} = \sum\_{k=0}^n \binom{n}{k} B\_k. $$ This is proved by considering how many other elements are in the part containing the element $n+1$. If there are $n-k$ of these, then we have $\binom{n}{n-k} = \binom{n}{k}$ choices for them, and $B\_k$ choices for partitioning the rest.

Using this, we can give a recursive algorithm to convert any partition of $n+1$ to a number in the range $0,\ldots,B\_{n+1}-1$. I assume you already have a way of converting a subset of size $k$ of $\\{1,\ldots,n\\}$ to a number in the range $0,\ldots,\binom{n}{k}-1$ (such an algorithm can be devised in the same way using Pascal's recurrence $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$).

Suppose that the part containing $n+1$ contains $k$ other elements. Find their code $C\_1$. Compute a partition of $\\{1,\ldots,n-k\\}$ by "compressing" all the remaining elements to that range. Recursively compute its code $C\_2$. The new code is $$C = \sum\_{l=0}^{n-k-1} \binom{n}{l} B\_l + C\_1 B\_{n-k} + C\_2. $$

In the other direction, given a code $C$, find the unique $k$ such that $$ \sum\_{l=0}^{n-k-1} \binom{n}{l} B\_l \leq C \< \sum\_{l=0}^{n-k} \binom{n}{l} B\_l, $$ and define $$ C' = C - \sum\_{l=0}^{n-k-1} \binom{n}{l} B\_l. $$ Since $0 \leq C' \< \binom{n}{k} B\_{n-k}$, it can be written as $C\_1 B\_{n-k} + C\_2$, where $0 \leq C\_2 \< B\_{n-k}$. Now $C\_1$ codes the elements in the part containing $n+1$, and $C\_2$ codes a partition of $\\{1,\ldots,n-k\\}$, which can be decoded recursively. To complete the decoding, you have to "uncompress" the latter partition so that it contains all the element not appearing in the part containing $n+1$.

---

Here is how to use the same technique to encode a subset $S$ of $\\{1,\ldots,n\\}$ of size $k$, recursively. If $k=0$ then the code is $0$, so suppose $k\>0$. If $n \in S$ then let $C\_1$ be a code of $S \setminus \\{n\\}$, as a subset of size $k-1$ of $\\{1,\ldots,n-1\\}$; the code of $S$ is $C\_1$. If $n \notin S$ then let $C\_1$ be a code of $S$, as a subset of size $k$ of $\\{1,\ldots,n-1\\}$; the code of $S$ is $C\_1 + \binom{n-1}{k-1}$.

To decode a code $C$, there are two cases. If $C \< \binom{n-1}{k-1}$ then decode a subset $S'$ of $\\{1,\ldots,n-1\\}$ of size $k-1$ whose code is $C$, and output $S' \cup \\{n\\}$. Otherwise, decode a subset $S'$ of $\\{1,\ldots,n-1\\}$ of size $k$ whose code is $C - \binom{n-1}{k-1}$, and output $S'$.

---
Tags: data-structures, combinatorics, space-complexity, sets, partitions
---


# Question
Title: Have I got the right understanding of the mu operator?
I have a homework problem that says:

***For $g(x,y)=xy-5$ compute $h(x) = \mu y(g(x,y))$ and determine its domain.***

I was under the impression that this means the least y such that $g(x,y)=0$, so then $y = \frac{5}{x}, D=\\{x \in \mathbb{N}, x \neq 0\\}$

So $h(x)=\frac{5}{x}$?

# Answer
> 2 votes
Hint: $h(x)$ is always a non-negative integer (whenever it's defined).

As a side note, usually primitive recursive functions are assumed to be non-negative, and so $\max(xy-5,0)$ is more usual than what you wrote.

---
Tags: terminology, computability, mu-calculus
---


# Question
Title: How to evaluate the clock cycle for MIPS single cycle CPU
**The Situation**

I'm trying to read the book 'Digital Design Computer Architecture'.
In the part of Performance Analysis(7.3.4 in the book), Author refers to clock cycle for MIPS single cycle processor. But I think there's something wrong with author's evaluating clock cycle.

Author says,

```
T(Clock cycle) = T(pcq_pc) + T(mem) + Max[tRfread, t(sext)] + t(Mux)
                 + T(ALU) + T(mem) + t(mux) + T(RFsetup)

```

But I think clock cycle 'T' would be ( if T(RFread) \> T(mux) + T(sext) )

```
T(Clock cycle) = T(pcq_pc) + T(mem) + T(RFread) + T(ALU) + T(mem) + T(mux) + T(Rfsetup)

```

Since I think the MUX followed by ALU **already selects** known sign-extend immediate before register value(the pin `RD1` in below diagram) is known.

and if T(RFread) is less than T(mux) plus T(sext).

```
T(Clock cycle) = T(pcq_pc) + T(mem) + T(sext) + T(Mux)
                 + T(ALU) + T(mem) + T(mux) + T(RFsetup)

```

**Some referenced information by the book.**

* T(pcq\_pc) is propagation delay for PC.
* T(mem) is read-propagation delay for instruction memory and data memory.
* T(sext) is propagation delay for Sign Extend logic.
* T(RFread) is read-progagation delay for register file.
* T(mux) is propagation delay for MUX.
* T(ALU) is propagation delay for ALU.
* T(RFsetup) is setup time for Register file.(Register value is written on positive clock edge)

Here is Diagram for MIPS single cycle CPU.

Is my thought correct? If you think author is right, Could you tell my why?
Any help would be awesome!

# Answer
Now that you have (dramatically) modified your question:

The author of the book is correct. RD1 can not be on the critical path because the time to read RD1 is the same as the time to read RD2, but then RD2 needs to go through the mux in front of the ALU. If the time to read RD2 \> T(Sext) then RD2 is on the critical path, if T(Sext) \> T(RFread) then Sext is on the critical path. That's what the Max() operator does. Either way T(mux) needs to be in the expression.

Your last expression with T(Sext) +T(mux) is the same as what the author's expression gives in the case that T(Sext) \> T(RFread). But your middle expression is wrong: if T(RFread (the read of RD1)) \> T(Sext) + T(mux) then T(RFread (the read of RD2)) + T(mux) \> T(Sext) + T(mux) + T(mux) \> T(Sext) + T(mux). So you need to have T(mux) in the expression no matter which T(RFread) or T(Sext) is larger.

The basic rule (which you are mostly correctly following) is: use Max() for things that proceed in parallel, + for things that follow in sequence. The mux comes after both the Sign extend *and* after the read of RD2.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: What is the name of the optimization that removes self eliminating multiplication-division statements?
I have a compiler optimization which should be quite common, but I can not find a name for it, nor a reference that describes it.

Given an integer x, not known at optimization time, a known constant c and the following program

```
x_1 = x * c
x_2 = x_1 / c
print(x_2)

```

It's pretty clear that the code can be optimized to

```
print(x)

```

What is the name of this optimization? Is there a paper/book describing it?

Thanks!

# Answer
It's probably most easily described as a two-step process. First a step of Copy Propagation to get

```
x_2=x*c/c
print(x_2)

```

followed by a step of Constant folding to remove the unecessary operations.
> 3 votes

---
Tags: optimization, compilers
---


# Question
Title: Questions about an answer to a pumping lemma question for CFLs
In the answer to this question, I'm not understanding how the string is derived for a given $l$.

For example,

> Case 1: $vx = a^i$ where $i \> 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} d^n \notin L$.

Why is $l = 2$ chosen and how is $a^{n+i}b^{n+1}c^{n+1}d^n$ derived from $l = 2$?

Also, how can $vx$ be chosen instead of $vwx$ as the OP chose? What do we do about $w$? Is it the empty string?

# Answer
The essential idea is that pumping lemma tells you about string $uv^lwx^ly$ with $l \geq 0$. That is, you can "pump" to $uwy$, if $l = 0$, that way shortening the initial string.

The answer considers the string $a^n b^{n+1} c^{n+1} d^n$. Removing a single $b$ or inserting a single $a$ would move the string out of the language. Removal and insertion correspond to $l = 0$ and $l = 2$.

The answer only considers $vx$, because $w$ does not matter - it will not be pumped.

If $v$ or $x$ contains any $a$s, double them to get more $a$s then $c$s. If $v$ or $x$ contains any $b$s, remove them to get fewer $b$s than $d$s. $v$ and $x$ will never contain both $a$s and $c$s, because $|vwx| \leq n$. Same is true about the other pair of symbols.
> 2 votes

---
Tags: context-free, pumping-lemma
---


# Question
Title: Size of maximum clique given a fixed amount of edges?
Given an undirected graph $G = (V,E)$, what is the clique number $\omega(G)$ given $|E|$, *i.e.*, the size of the largest clique in a graph with $|E|$ edges.

I think this is doable after realizing that the number of edges in a clique is equal to the *triangular number*: $$|E(K\_k)| = \frac{1}{2}k(k-1).$$

I am looking for a closed formula.

# Answer
> 3 votes
The graph can have clique number 1 (if we allow the graph to be disconnected), or 2 (consider a long path). The graph can have a clique of size at most $$\frac{1}{2} (\sqrt{8m + 1} + 1),$$ where $m = |E|$, provided of course that $|V|$ is large enough.

---
Tags: algorithms, graphs
---


title: The notion of density of distribution

text:
# Question
Title: The notion of density of distribution
I have difficulties in understanding the notion of density for distribution.

**Notion of density for distribution**. A distribution $H$ over $\\{0,1\\}^n$ has density $\sigma$ if for every $x \in \\{0,1\\}^{n}$, $Pr\[H=x\] \leq \frac{1}{2^n\sigma}$.

The following is my desperate tries to understand the notion. if $H$ is uniform distribution over $\\{0,1\\}^n$ then for every $x \in \\{0,1\\}^n$, $Pr\[H=x\]=\frac{1}{2^n}$.

if a distribution $H$ has density $\sigma = 1$ then $P\[H=x\]\leq\frac{1}{2^n}$, so distribution $H$ is upper bounded by the uniform distribution.

if a distribution $H$ has density $\sigma = \frac{1}{2}$ then $P\[H=x\]\leq\frac{1}{2^{n-1}}$, so distribution $H$ is upper bounded by the uniform distribution over $\\{0,1\\}^{n-1}$.

if a a distribution $H$ has density $\sigma = \frac{1}{2^n}$ then $P\[H=x\]\leq 1$.

So density $\sigma$ might determine the part of distribution over $2^n$ where the actual "probabilistic weight" should be placed? However it's always upper bounded, therefore we can always say something about the upper bound?

As you see I don't have intuition behind this notion and I would appreciate any help.

# Answer
> 2 votes
This notion seems to be a measure of uniformity. If $\sigma=1$ you get a uniform distribution on $\\{0,1\\}^n$ (since the sum over all strings of length $n$ is $1$), but for other $\sigma$s (e.g. $\sigma = 2^{-k}$) it's still distribution on $\\{0,1\\}^n$, not on $\\{0,1\\}^{n-k}$ or similar. Thus saying that a distribution on another (disjoint) set is an upper bound is absolutely wrong (but they are related, s.b.).

If for some $x$ the probability is greater than $\frac{1}{2^n}$ it has to be smaller for others. On the other hand for $\sigma=\frac{1}{2}$ at least half of the strings have nonzero probability since the sum of any number of elements $\< 2^{n-1}$ is smaller than $1$. This holds for any $\sigma \> 0$, i.e. $\sigma 2^n$ elements have nonzero probability.

Using this you can *compare* the distribution for $\sigma=2^{-k}$ to the distribution for $\sigma=1$ (i.e. uniform) on $\\{0,1\\}^{n-k}$. It's easy to see that the entropy of the distribution with $\sigma=2^{-k}$ on $\\{0,1\\}^n$ (let $H$ be a random variable with this distribution) is at least the entropy of the uniform distribution on $\\{0,1\\}^{n-k}$ (RV denoted by $U$) since for every injection $f: \\{0,1\\}^{n-k}\rightarrow \\{0,1\\}^n:$ $$\mathbb{P}(U=x)\geq \mathbb{P}(H=f(x)) \quad .$$

---
Tags: complexity-theory, probability-theory
---


# Question
Title: How to sample uniformly from a stream of elements, some of which are unsuited?
I get values $x\_t$ in an online fashion and want to buy "good" ones, where "good" means that some measure $P(x\_t) \>T$. Consider the following simple algorithm.

```
T = 0.7
N = 100 // or any value N > B
B = 20 // or any value 1 < B < N

l = 0

for t from 1 to N:
    input a new observation x_t
    let P(x_t) the probability associated to x_t

    if P(x_t) > T:
        l = l + 1
        pay 1 dollar to buy y_t the label of x_t
        output immediately the label y_t

```

If the condition $P(x\_t) \> T$ is used then we get about $l = 100-70 = 30$, this is ok since the value of $T$ is set to $0.7$.

Now if I want to add a constraint which is: additionally to the fact that elements $x\_t$ for which the label $y\_t$ is purchased are those for which $P(x\_t) \> T$, I want also that we do not buy more than $B=20$ labels (for example because we only have 20 dollars as budget).

But the problem is that, if I replace the the condition ($P(x\_t) \> T$) by ($P(x\_t) \> T \wedge l \< B$), then the elements $x\_t$ for which we buy a label are more likely to be among the first elements $t$ that we browse (that is, for an element $x\_{95}$ for $t = 95$ for example we will never have a chance to buy its label even if its probability was $P(x\_{95}) \gg T$). But I want that all the elements from $t = 1$ to $N$ will have equal chance to buy their label (not advantaging only the first elements).

Note: the condition that $P(x\_t) \> T$ for buying the label of a new observation $x\_t$, should not be removed from my code. This is important for me: only labels of observations for which $P(x\_t)$ was higher than $T$ at time $t$, are possibly purchased; and we should not purchase more than our budget $B$. Note also that a purchased label should immediately be output after we buy it, we should not wait until the end to decide if we buy it or not.

Also, note that we do not have the N elements beforehand; at each time $t$ we see just one new observation $x\_t$. And note that you pay 1 dollar when you select a given $x\_t$ to ask for its label and that you should output answer (label of selected $x\_t$) immediately; so you can not select some $B$ elements then replace them with new selected other elements, because your budget $B$ will already be finished.

# Answer
> 2 votes
The easiest way to solve this problem might be to randomly permute the input. For example, you could compute a random permutation pi on N elements, and replace the main loop with

```
for s from 1 to N:
   t = pi[s]
   ...

```

Edit: If you want to solve this in an online fashion, here is a different suggestion. Consider first the case $B=1$ and a threshold $T$ that always holds. So given a sequence of elements, we want to select a uniformly random one in an online fashion. This is done by the following algorithm:

```
for t from 1 to N:
  x = input()
  with probability 1/t:
    selected = x
return selected

```

Now let's still assume that $B=1$, but let the threshold be arbitrary:

```
 count = 0
 for t from 1 to N:
   x = input()
   if P(x) > T:
     count = count + 1
     with probability 1/count:
       selected = x
 return selected

```

Now assume we have arbitrary $B \geq 1$, but all the elements cross the threshold:

```
for t from 1 to N:
  x = input()
  if t <= B:
    selected[t] = x
  else:
    with probability B/t:
      i = random({1,...,B})
      selected[i] = x
return selected

```

Finally, putting everything together:

```
count = 0
for t from 1 to N:
  x = input()
  if P(x) > T:
    count = count + 1
    if count <= B:
      selected[count] = x
    else:
      with probability B/count:
        i = random({1,...,B})
        selected[i] = x
return selected

```

Edit 2: Here is yet another suggestion, assuming that you know both $N$ and the number of elements crossing the threshold, let's say $M$. You choose a random subset $S$ of size $M$ of $\\{1,\ldots,N\\}$. You select the $k$th element crossing the threshold for each $k \in S$.

If you only have an estimate for $M$, you can try a similar algorithm in which you guess $M$ and hope for the best.

Here is pseudocode for the algorithm:

```
S = random subset of {1,...,N} of size M
count = 0
for t from 1 to N:
  x = input()
  if P(x) > T:
    count = count + 1
    if count in S:
      select x

```

---
Tags: probabilistic-algorithms, online-algorithms, sampling
---


# Question
Title: Does converting algorithms into elementary recursive form preserve runtime bounds?
There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class?

For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity?

By converting into elementary recursive form, I mean:

Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form.

By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else".

Modification to the question: Let us say that for all decision problems we consider, there exist function problems that have same time complexity as their decision problem counterparts. For example, for 3-SAT problem with some input $x$, one satisfying assignment to the variables is treated as output. The reason why some people think this question is not valuable may be because for all decision problems, output is always either zero or one. So let us consider the function version of decision problems (that keeps time complexity).

# Answer
> 1 votes
This depends highly on the encoding. If you consider bounded summation, the number of summations done is the *value* of the first argument of the function.

If the "encoding" (whatever that means) of the input is unary, this takes linear time, otherwise it takes exponential time in the size of the input. It is not obvious that it makes sense to assume input to be unary.

Elementary recursive functions are over natural numbers and do not speak of their encoding: is $s(0)$ encoded as $1$ or as $s0$?

---
Tags: complexity-theory, time-complexity, arithmetic
---


# Question
Title: FFT implementation using Danielson-Lanczos Lemma
I am trying to understand FFT algorithm explained here

```
FFT(x) {   n=length(x);
if (n==1) return x;
m = n/2;
X = (x_{2j})_{j=0}^{m-1};
Y = (x_{2j+1})_{j=0}^{m-1};
X = FFT(X);
Y = FFT(Y);
U = (X_{k mod m})_{k=0}^{n-1};
V = (g^{-k}Y_{k mod m})_{k=0}^{n-1};
return U+V;
}

```

The author says that the above comes from Danielson-Lanczos Lemma.

I am unable to understand what is the meaning of the lines:

X = (x\_{2j})\_{j=0}^{m-1};

Y = (x\_{2j+1})\_{j=0}^{m-1};

# Answer
The meaning of the first line is "Let $X$ be an array of length $m$ (with indices running from $0$ to $m-1$) such that $X\_j = x\_{2j}$ for $j \in \\{0,\ldots,m-1\\}$." The second line has a similar meaning, with $Y\_j = x\_{2j+1}$ instead.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Is a language with only a stack of fixed-size integers Turing-complete?
I encountered the brainfuck programming language which I know is turing complete. However I then decided to create a high level language that gets compiled to brainfuck code.

There is only one data type in it (integer, since that's the only data type brainfuck supports). It supports functions and subroutines (to which you can pass integers by value, but not arrays, though you can access an array in the global scope from within a function/subroutine) but it does not support recursion (all function and subroutine calls are inlined). It supports statically allocated arrays (size known at compile time) and has just one unbounded stack. You can store as many items as you like in the stack, unlike with arrays, but you only have one stack for your entire program.

I have these limitations to achieve a balance between ease of use, and fast generated code.

However, I never studied any of this stuff and I actually started this project to learn about compilers (by making one), therefore my question is:

From the above description, is this language turing complete?

# Answer
If your language supports an arbitrarily large array of integers (even of numbers in $\\{0,1\\}$), then you can simulate the tape of a TM. Then, clearly your language is Turing complete.

EDIT: based on your comment, you don't have an arbitrary array.

In this case, you can do the following: If you can keep two counters (integers), and increase or decrease them, and check whether they are 0, then you can simulate a *two counter machine* (Minsky Machine), which is Turing complete (with a caveat).

If you also bound the maximal value that an integer can take, then I believe that your machine is no more powerful than a PDA.
> 4 votes

# Answer
If you want to build a compiler, brainfuck is near the worst language to start with... it was *designed* to be a total mess.

A practical way to understand a compiler is Fraser and Hanson's "A Retargetable C Compiler: Design and Implementation", the book contains the full source code for a simple (but complete) ANSI C compiler. From the link you can get the source code for the (much improved) last version. But note that real compilers are *much* more complex, LCC has carefully selected schemas for conditionals and loops, does careful instruction selection, and a bit of on-the-fly expression simplification; but little else in terms of "code optimization". If you'd like to mess with a real compiler, take a peek at LLVM, the official compiler for MacOS. It is nicely structured from the ground up, thus much more understandable than the organically grown GCC. Perhaps tcc, the Tiny C Compiler (outgrowth of an International Obfuscated C Code Contest entry for 2002, where they asked for the smallest C compiler able to compile itself) might be of amusement value...
> 1 votes

---
Tags: programming-languages, turing-completeness
---


# Question
Title: Is the intersection of two context free languages recursively enumerable?
I read a quotation attributed to Sheila Greibach that says that the intersection of two context free grammars is recursively enumerable.

I could not, however, find a citation for this quotation (and searching has failed to turn up a restatement of this result somewhere else).

Can anyone provide a proof or a citation to the original proof for this result? Can anyone state that it is false?

# Answer
> 5 votes
This result more easily follows from the fact that every context-free grammar is recursively enumerable, by enumerating all parse trees. The intersection of any two r.e. languages is r.e. - just enumerate them both and output every word that appears on both lists. The other direction (given by the quotation you found) is more interesting.

Edit: As Huck correctly comments, there are actually efficient algorithms for deciding membership in context-free languages. But the argument above holds for the most general grammars possible, in which case we prove that the language corresponding to any grammar is recursively enumerable. (Replace parse trees with the a sequence of rule applications.)

---
Tags: formal-languages, computability, context-free
---


title: Prove that the Language is Recognizable

text:
# Question
Title: Prove that the Language is Recognizable
I got stuck on this question while studying for final exam.

I thought about reducing L' to L to prove that L' is recognizable since L is recognizable. I am not 100% sure if that is correct.

# Answer
sPaz, your answer in the comment is on the right track.

I'll give you some more hints.

1. Since $L$ is RE, as you said, we have a TM that accepts it. Let's call it $R$.
2. Now, we can run $M\_i$ on $x$ for any $M\_i$ that is being accepted by $R$.
3. The question is, what happens if $M\_i$ is not accepted by $R$ (and in fact, $R$ goes into a loop)? Also, what happens if $M\_1$ is accepted by $R$, but $M\_1$ goes on an infinite loop on input $x$?

The standard technique of "running in parallel" (dovetailing) should help you to complete your proof. In more details:

> We have a counter $i$. We run $i$ steps of $R$ on any machine $M\_j$ such that $\langle M\_j \rangle \< i$. We keep a list of all the machines that were accepted by $R$. For each such machine, we run $i$ steps of that machine on $x$. If any of them accepts, we accept. Otherwise, we set $i\leftarrow i+1$ and continue.
> 3 votes

---
Tags: computability, turing-machines, reductions
---


# Question
Title: Why isn't set $\{ \langle i, j \rangle \mid W_i = \overline{W_j}\}$ a recursively enumerated set?
Why isn't the set $\\{ \langle i, j \rangle \mid W\_i = \overline W\_j\\}$ a r.e. set?

Note: $W\_x = L(M\_x)$

# Answer
> 1 votes
**Hint:** Use a reduction for the proof. If your language $L=\\{ \langle i, j \rangle \mid W\_i = \overline W\_j\\}$ is r.e. then of course every language where the second machine $M\_j$ is fixed is also r.e.. Say, you pick for $M\_j$ the Turing machine that always accepts, then you are left with showing that the language $L\_0=\\{ i \mid W\_i = \emptyset \\}$ is not r.e.. This again can be shown with a reduction (i.e., show that $\overline{\text{HALT}}\le\_p L\_0$). Alternatively, show that $L\_0$ is not decidable (Rice's Theorem), but $\overline{L\_0}$ is Turing-recognizable.

---
Tags: computability, reductions
---


# Question
Title: Set cover problem and the existence of such cover
In the set cover problem we want to find in the $\mathbb{S} \subset 2^\mathbb{U}$ the subset $\\{s\_i\\}\_{1..k}$, such that $\cup s\_i = \mathbb{U}$ for given $K$, where $k \le K$. But how to reduce the set cover problem to the set covering decision problem (determining whether is there such cover or not)? The same with problems like a TSP is always easy enough: we exclude some elements, check if the needed condition is still met and know already, are these elements needed or not. But it doesn't work here and I am stuck. I would be appreciated if you could give me some hints for this problem.

# Answer
There are two approaches for this:

The "hands on" way: first, find the minimal $k$ for which there is a set cover, by repeatedly calling an oracle for the decision problem (you can even do a binary search, but it isn't necessary). Once you have the minimal $k$, choose a set $s\_1\in S$, and check if there is a set cover of size $k$ in $S\setminus\\{s\_1\\}$. If there is, you don't need $s\_1$, so throw it away. If there isn't, remove $s\_1$ from $U$, and repeat the process with $k-1$, until you have the set cover, which will be minimal.

The more theoretical approach is as follows. Since SET-COVER is NP-complete, there is a reduction from it to SAT, and a reduction from SAT to SET-COVER. If you examine the standard reductions (i.e. the Cook-Levin theorem, and a textbook reduction for $SAT\le\_p SET-COVER$), you will see that both reductions are *Levin* reductions, which means that not only they are reductions, but they also preserve witnesses. That is, given a solution to the output of the reduction, you can generate from it a solution to the input.

Now you can proceed as follows. Given an instance for SET-COVER, find the minimal $k$ as before, and then reduce the problem with this $k$ to SAT. Now, if you have an oracle for the decision problem, you can reduce SAT to the SET-COVER, so you can also solve SAT using this oracle. For SAT we know how to find a solution using an oracle (just try bit-by-bit), so you can find a witness, and from this generate a witness for SET-COVER.

The latter works with any NP-complete problem.
> 2 votes

---
Tags: np-complete, reductions
---


# Question
Title: Proving ALLTM complement not recognizable
A few definitions..

$$ \begin{align\*} \mathrm{ALL}\_{\mathrm{TM}} &= \Bigl\\{\langle M \rangle \\,\Big|\\, \text{$M$ a Turing Machine over $\\{0,1\\}^{\*}$},\\;\\; L(M) = \\{0,1\\}^{\*} \Bigr\\} \\\\[2ex\] \overline{\mathrm{ALL}}\_{\mathrm{TM}} &= \Bigl\\{\langle M \rangle \\,\Big|\\, \text{$M$ a Turing Machine over $\\{0,1\\}^{\*}$},\\;\\; L(M) \ne \\{0,1\\}^{\*} \Bigr\\} \\\\[2ex\] B\_{\mathrm{TM}} &= \Bigl\\{\langle M \rangle \\,\Big|\\, \text{$M$ is a Turing Machine over $\\{0,1\\}^{\*}$},\\;\\; \varepsilon \in L(M) \Bigr\\} \end{align\*} $$

We are showing a reduction from $B\_{\mathrm{TM}}$ to $\overline{\mathrm{ALL}}\_{\mathrm{TM}}$. In my notes I have the following solution to this problem which I'm trying to understand.

1. Let $\alpha \in \\{0,1\\}^\*$. Check that $\alpha$ is of form $\langle M \rangle$, where $M$ is a TM over $\\{0,1\\}$. Else, let $f(\alpha)$ be anything not in $\overline{\mathrm{ALL}}\_{\mathrm{TM}}$.
2. Let $f(\alpha)$ be $\langle M' \rangle$, where $M'$ on $x$ runs $M$ on $\varepsilon$ (blank string) for up to $|x|$ steps. If $M$ accepts (in that time), then $M'$ rejects. Otherwise, $M'$ accepts.

What I'm trying to understand is why must we run the TM $M'$ for $|x|$ steps for this to work? If we change the part #2 of the transformation to the following, why wouldn't this work?

* Let $f(\alpha)$ be $\langle M' \rangle$, where $M'$ on $x$ runs $M$ on $\varepsilon$ (blank string). If $M$ accepts, reject. Otherwise accept.

Which then it follows that $\varepsilon \in L(M) \\!\iff\\! L(M) = \varnothing$, that is $L(M) \neq \\{0,1\\}^\*$.

# Answer
> 2 votes
First, there is a small typo in (1) - if $\alpha$ is not a legal encoding, then you should return something that is in $ALL\_{TM}$ (since you are reducing to the complement).

For your question: the key point here is that a TM does not always halt on its input. Thus, the phrase "otherwise accept" in your suggestion for (2) is not computable. If you run $M$ on $\epsilon$, and $M$ does not halt, then the lanugage of $M'$ will be $\emptyset$, which makes the reduction fail.

In general, when you perform reductions that output a machine that simulates another machine, you must always consider the possibility that the latter will not halt. If this poses a problem (as it does here), a good trick to circumvent it is to limit the step number, and since often you want this limit to exist, but to be \`\`unbounded'', then using the input for the machine as a limit is a good idea.

---
Tags: computability, turing-machines, undecidability
---


# Question
Title: Transforming an arbitrary cover into a vertex cover
Given is a planar graph $G=(V,E)$ and let $\mathcal{G}$ denote its embedding in the plane s.t. each edge has length $1$. I have furthermore a set $C$ of points where each point $c \in C$ is contained in $\mathcal{G}$. Furthermore, it holds for any point $p$ in $\mathcal{G}$ that there exists a $c \in C$ with geodesic distance to $p$ at most one. (The distance is measured as the shortest distance within $\mathcal{G}$.)

I want to argue that given a $C$ for which the above condition holds, I can easily transform it into a vertex cover, or put differently, transform it into a $C'$ of same cardinality s.t any $c \in C'$ is placed in $\mathcal{G}$ at a vertex of $G$, and $C'$ still covers $G$.

My approach was to orient the edges and move the points in $C$ at the end vertex of the arc. But so far I did not find a correct orientation which yields $C'$ from $C$.

Does anybody have an idea?

# Answer
> 5 votes
If no points in $C$ lie exactly on the mid-point of an edge in $\mathcal{G}$, then it suffices to associate each point in $C$ to the nearest vertex in $\mathcal{G}$. I will leave it as an exercise to the reader to prove this (hint: prove by contradiction).

On the other hand, if points in $C$ are allowed to lie on the mid-point of edges, then we can provide a counter-example:

The blue lines and circles are $\mathcal{G}$ and the red crosses are $C$.

EDITED TO ADD: An example with a biconnected graph

---
Tags: algorithms, graphs, set-cover
---


# Question
Title: Are there a lambda-mu expression equivalent to the yin yang puzzle?
The yin yang puzzle was written in Scheme. Since it uses call/cc, it is not possible to express it in a pure lambda expression, unless we do a CPS transform.

However, given the fact that $\lambda \mu$-calculus have the power to model call/cc, is it possible to write an equivalent $\lambda \mu$-expression? I am still learning $\lambda \mu$-deductions, so this would be a good example to show how the deduction works.

There is no need to model the "display" command in a pure expression. Ideally only showing how the calculus keep looping and evaluates diffident terms again and again.

**UPDATE** My translation in $\lambda$-expression with CPS:

```
(λcallcc.callcc (λyin.callcc (λyang.yin yang))(λcc.cc cc)

```

In CPS, `(λcc.cc cc)` is what "call with current continuation" means. So the expression takes it as a parameter. This will result in assign the sub-expression starts `λyin` assign its continuation into parameter `yin`. And then in the body, the second callcc assigns the `yang` of sub-expression starts `λyang` into itself. Finally, apply `yin yang`.

Note the above translate is not full CPS, only the concept of call/cc has been translated. But it provides the same behavior and it is not hard to do a full CPS translate.

# Answer
You can get an important hint to solution by thinking how to make the yin-yang puzzle work in a typed language, see this question. OCaml computes the type of `yin` and `yang` to be `('a -> 'a) as 'a`, which is a recursive type equal to its own function space. Such a type is precisely what it takes to implement the untyped $\lambda$-calculus in a typed language.

What does this have to do with your question? In the untyped $\lambda$-calculus (or typed calculus with general recursive types) we can *define* $\mu$ and other fixed-point combinators. So, since `yin` and `yang` cannot be given types, we must use the untyped $\lambda$-calculus, but then $\mu$ is not needed as a primitive. In fact, the CPS transform of the puzzle will be just pure $\lambda$-calculus.

You can compute the CPS transform in the privacy of your mind. Here is my version, written in Ocaml. To run it, you need to pass `-rectypes` to Ocaml:

```
let callcc f k = f k ;;
let yin c = callcc (fun x -> x x) (fun k -> print_char '@'; c k) ;;
let yang c = callcc (fun x -> x x) (fun k -> print_char '*'; c k) ;;
let _  = yin yang (fun x -> x) ;;

```

Clearly, the `let` statements are just a convenience. Without them, and with `callcc` expanded out, we get:

```
(fun c -> (fun x -> x x) (fun k -> print_char '@'; c k))
(fun c -> (fun x -> x x) (fun k -> print_char '*'; c k))
(fun x -> x)

```

We could remove the `print_char` statement and $\eta$-reduce:

1. Start with:

```
(fun c -> (fun x -> x x) (fun k -> c k))
(fun c -> (fun x -> x x) (fun k -> c k))
(fun x -> x)

```
2. Reduce `fun k -> c k` to `c`:

```
(fun c -> (fun x -> x x) c) (fun c -> (fun x -> x x) c) (fun x -> x)

```
3. Reduce `fun c -> (fun x -> x x) c` to `fun x -> x x`:

```
(fun x -> x x) (fun x -> x x) (fun x -> x)

```

So the essence of the yin-yang puzzle is just self-application of self-application. How appropriate! As a last step, we can put in the `print_char` statements again, to get a one-liner:

```
(fun x -> x (fun k -> print_char '@'; x k)) (fun x -> x (fun k -> print_char '*'; x k)) (fun x -> x)

```
> 3 votes

---
Tags: lambda-calculus, continuations
---


# Question
Title: What is the difference between the semantic and syntactic views of function types?
**Edit:** My original question referred to *nonconstructive* and *constructive* definitions of function types. I changed the terminology in the question and the title to *semantic* and *syntactic*, which the answer indicates is the correct terminology for this distinction.

I can recall two ways of defining functions in set theory and programming languages with set-theoretic foundations. The function type $\tau \to \sigma$ can be defined *semantically* as the set of all maps from $\tau$ to $\sigma \cup \\{\bot\\}$, i.e., all objects $f$ such that if $x \in \tau$ then $f(x) \in \sigma \cup \\{\bot\\}$. Alternatively, the function type $\tau \to \sigma$ can be defined *syntactically* as the set of all terms in a given language whose type is $\tau \to \sigma$ (possibly modulo some equivalence relationship). As a programmer, I work with the latter definition, but I often pretend that I'm working with the former definition.

What are the differences between the inhabitants of $\tau \to \sigma$ according to the two definitions above? For instance, are uncomputable functions included in the first but not the second definition?

To be precise, I'm interested in the situation where terms are strongly typed, functions are side effect free and may be nonterminating, and functions are equal iff, for all inputs, they both diverge or both return the same value.

# Answer
These are not called constructive and nonconstructive! The one you call "nonconstructive" works just as well in constructive mathematics (you have to be a bit careful about how you define the $\bot$ value, but that is a technical detail).

Rather, you are asking about **semantic** and **syntactic** distinctions. We imagine that the expressions we write in a program correspond to abstract mathematical objects. For example, the syntactic expression `(fun n => 2 + n) 2` denotes the number $4$. (Under this view "evaluating a program" is about finding out which abstract mathematical object it denotes.)

We can then ask what mathematical objects corresponding to expressions of type `a -> b`. Presumably they are actual mathematical functions (although that is not so clear in the presence of computational effects). But they are not *all* functions, because those functions that can be expressed in a programming language have special properties, such as:

1. they are *Turing computable* (because programming langauges can be interprted by Turing machiens).
2. they are *continuous* (because in finite time we can only get finite information about input, and continuity essentially says that only finite amount of input is required to produce a finite amount of output).

So, it may make sense to restrict to special kinds of mathematical functions (only computable ones, only continuous ones). This way our mathematical objects will correspond more closely to our programs, and so presumably we will have a better setup. (In fact, as soon as we have a language with recursion, we cannot think of expressions of type `a -> b` as just ordinary functions, but rather somehting like the continuous ones--but let me not go there just now.)

As you say, most programers take a **syntactic** view, in which functions *are* syntactic expressions. This is certainly a possibility that can go a long way. But the **semantic** view in which we think of programs as denoting mathematical objects has its benefits too. Mathematicians know an awful lot about computability and continuity, and you can bring the knowledge in when you take the semantic view.

A trivial application of the semantic method is this: suppose we want to implement comparison of functions `eq : (nat -> nat) -> (nat -> nat) -> bool` which tells us whether two functions `f, g : nat -> nat` are equal. How do we do it? The answer is that we cannot implement it because that would give us a discontinuous function. But proving this fact using only syntactic methods is much harder. In fact, I do not know how to do it without using some computability theory, which again is a semantic method. You may think it is obvious that `eq` cannot be implemented, in which case you should wonder why `eq : (nat -> bool) -> (nat -> bool) -> bool` *can* be implemented (and the implementation was first found using semantic methods).

Another area where the semantic view is needed is numerical computation. It is absurd to claim that a program (syntactic entity) for solving a differential equation has nothing to do with differential equations (semantic entity).

Let me also say what the **constructive-nonconstructive** distinction is. This is about the *logic* you use to do math. If we use nonconstructive logic, which is the traditional way to do it, then we will be able to prove that there exist non-computable functions. Consequently, there will be functions we cannot implement. But if we use constructive logic, then it is impossible to prove existence of a non-computable function. (In fact, we may add an axiom to constructive logic which says "all maps are computable", although I would advise against this: how do you know that all external input that is coming into your computer from the universe is computable?) This is not the traditional way, but it is one that programers can sympathize with.

Lastly, I want to nitpick about something your write in your title. *Definitions* are not constructive or non-constructive. They just are. Constructivity is important when we *prove* and *construct* things. Function types in a programming language are defined a la type theory in terms of:

* a type constructor, such as `->`
* rules for *forming* terms, such as $\lambda$-abstraction
* rules for *using* terms, such as application
* *equations* which are supposed to hold, such as $\beta$-reduction.

This works equally well in constructive and non-constructive logic, because it is just syntax. There are meta-theorems which say that for finite discrete objects (syntax, natural numbers, finite graphs, lists, ...) there is no difference between constructive and non-constructive logic (I am skipping over a lot of details). But when you ask for the *semantics* of your type, i.e., what mathematical object it corresponds to, then it makes a difference.
> 9 votes

---
Tags: terminology, programming-languages, type-theory
---


# Question
Title: How to perform bottom-up construction of heaps?
What are the steps to perform bottom-up heap construction on a short sequence, like `1, 6, 7, 2, 4`?

At this link there are instructions on how to do for a list of size 15, but I can't \[necessarily\] apply the same process to a list of 5 items (my trouble is that 5 is not enough to provide a complete tree).

# Answer
Five nodes is plenty to make a tree. See for example here. His first example has 6 nodes, not 5, but it should get you started.

A heap is a binary tree with all levels filled except, perhaps, the last. The last level is filled in left-to-right until you run out of elements.

So yours would start out like this:

The heap invariant is that each parent is smaller than both its children. In the heap construction algorithm you work bottom up, restoring the heap invariant. One way to do this is a recursive post-order tree traversal:

```
Heapify (x):
    if (x->is_leaf) return x
    l = Heapify (x->left_child)
    if (exists(x->right_child)):
        r = Heapify (x->right_child)
        if ((r->value < x->value) && (r->value < l->value)):
            swap(r->value, x->value)                    # r->value was smallest
    if (l->value < x->value):
        swap(l->value, x->value)                        # l->value was smallest
    return x

```

In actual code for heaps the heap is often represented as an array with the elements stored top-to-bottom and left-to-right in each level. The first element is the root, the second and third elements are the children of the root, and so on. In this case you can do the initial heap creation by working backwards through the array to get a post-order tree traversal for cheap (i.e., as an iterative algorithm that doesn't need to recurse).
> 4 votes

---
Tags: data-structures, heaps
---


# Question
Title: Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves
This problem is about finding a route on a square grid. The starting point is $(1,1)$ and the target point $(n,m)$. I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$. Now I need to determine if there is a path from $(1,1)$ to $(n,m)$, and if so to return the shortest one.

Now I believe that if I trace back my steps from the input point $(n,m)$ I can always know which move I made out of the two possible ones since if $n=m$ then there is no route, this means I'm always take the smaller coordinate and subtract it from the bigger one. But that means I have at most only one possible route to $(n,m)$ so why was I asked to return the shortest one?

Am I missing anything ?

# Answer
> 6 votes
No, your reasoning seems right. Sometimes problem setters just throw in such things in order to make the problem sound harder than it is.

---
Tags: algorithms, graphs, shortest-path, square-grid
---


title: Time Complexity of a selection problem

text:
# Question
Title: Time Complexity of a selection problem
I wonder what's the time complexity of the following selection problem I found while thinking of a string-matching problem.

\[Assuming operations on integers take $O(1)$ time\]

We are Given $m$ sets, with $n$ integer numbers each. We want to select exactly one integer from each set, to make a set S, such that $~ l = \max(S) - \min(S)~$ is minimized.

For example, n = 4, m = 3:

$S\_1 = \\{1, 43, 71, 101\\}$

$S\_2 = \\{18, 53, 80, 107\\}$

$S\_3 = \\{3, 16, 51, 208\\}$

Now

$~S = \\{43, 53, 51\\}$

has one number from each set and

$~l = \max(S) - \min(S) = 53 - 43 = 10 ~$

wich is the minimum possible value of $l$ (I think).

First thing I tried was a reduction to the set cover problem, but I wasn't able to find one.

# Answer
If you are trying to prove $NP$-Hardness of that problem, you need a reduction *from* (not *to*).

Anyway, I don't think this is $NP$-hard (unless $P = NP$, of course)

Suppose the $S\_i$ are sorted.

Suppose you decide that element $x \in S\_j$ will be minimum. Now in each other set, you can find the smallest element greater (or equal to) $x$ using binary search, and take the maximum among those.

Do this for each of the $mn$ numbers, assuming it is the minimum. Pick the best set you get. This gives you a polynomial time algorithm: $m \log n$ time for each of the $mn$ elements, giving an $O(m^2n \log n)$ time algorithm.
> 3 votes

---
Tags: complexity-theory, time-complexity, set-cover
---


# Question
Title: Colour a binary tree to be a red-black tree
A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition).

I was wondering if we can do something similar with Red-Black trees.

> Given an arbitrary uncoloured binary tree (with NULL nodes), is there a "fast" algorithm which can determine if we can colour (and find a colouring) the nodes Red/Black so that they satisfy all the properties of a Red-Black tree (definition as in this question)?

An initial thought was that we can just remove the NULL nodes and try to recursively verify if the resulting tree can be a red-black tree, but that didn't seem to go anywhere.

I did (a brief) web search for papers, but could not seem to find any which seem to deal with this problem.

It is possible that I am missing something simple.

# Answer
> 12 votes
If for each node of a tree, the longest path from it to a leaf node is no more than twice longer than the shortest one, the tree has a red-black coloring.

Here's an algorithm to figure out the color of any node `n`

```
if n is root,
    n.color = black
    n.black-quota = height n / 2, rounded up.

else if n.parent is red,
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    if n.min-height < n.parent.black-quota, then
        error "shortest path was too short"
    else if n.min-height = n.parent.black-quota then
        n.color = black
    else (n.min-height > n.parent.black-quota)
        n.color = red
    either way,
        n.black-quota = n.parent.black-quota - 1

```

Here `n.black-quota` is the number of black nodes you expect to see going to a leaf, from node `n` and `n.min-height` is the distance to the nearest leaf.

For brevity of notation, let $b(n) = $ `n.black-quota`, $h(n) = $ `n.height` and $m(n) = $ `n.min-height`.

**Theorem:** Fix a binary tree $T$. If for every node $n \in T$, $h(n) \leq 2m(n)$ and for node $r = \text{root}(T)$, $b(r) \in \[\frac{1}{2}h(r), m(r)\]$ then $T$ has a red-black coloring with exactly $b(r)$ black nodes on every path from root to leaf.

**Proof:** Induction over $b(n)$.

Verify that all four trees of height one or two satisfy the theorem with $b(n) = 1$.

By definition of red-black tree, root is black. Let $n$ be a node with a black parent $p$ such that $b(p) \in \[\frac{1}{2}h(p), m(p)\]$. Then $b(n) = b(p) -1$, $h(n) = h(p)-1$ and $h(n) \geq m(n) \geq m(p)-1$.

Assume the theorem holds for all trees with root $r$, $b(r) \< b(q)$.

If $b(n) = m(n)$, then $n$ can be red-black colored by the inductive assumption.

If $b(p) = \frac{1}{2}h(p)$ then $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$. $n$ does not satisfy the inductive assumption and thus must be red. Let $c$ be a child of $n$. $h(c) = h(p)-2$ and $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$. Then $c$ can be red-black colored by the inductive assumption.

Note that, by the same reasoning, if $b(n) \in (\frac{1}{2}h(r), m(r))$, then both $n$ and a child of $n$ satisfy the inductive assumption. Therefore $n$ could have any color.

# Answer
> 2 votes
I believe Karolis' answer is correct (and a pretty nice characterization of red-black trees, giving an $O(n)$ time algorithm), just wanted to add another possible answer.

One approach is to use dynamic programming.

Given a tree, for each node $n$, you construct two sets: $S\_R(n)$ and $S\_B(n)$ which contains the possible black-heights for the subtree rooted at $n$. $S\_R(n)$ contains the black-heights assuming $n$ is coloured Red, and $S\_B(n)$ assuming $n$ is coloured black.

Now given the sets for $n.Left$ and $n.Right$ (i.e direct children of $n$), we can compute the corresponding sets for $n$, by taking appropriate intersections and unions (and incrementing as needed).

I believe this comes out be an $O(n \log n)$ time algorithm.

---
Tags: algorithms, data-structures, binary-trees, search-trees
---


title: Parallel Computing: Past Vs Present

text:
# Question
Title: Parallel Computing: Past Vs Present
Parallel computing is not new but it is becoming common now a days. This is essentially driven by the need of the users (they need to process more data now) and also because of physical limitations on chip designing e.g power dissipation limits forcing to manufacturers to move to multicore CPUs.

My question is how is the parallel computing different now from what they used to do 30 years back?

# Answer
> 3 votes
30 years ago research into cache-coherent shared memory was just beginning. There were machines where you could send messages between processors. By 1983 there were a few (room sized) machines where processors could communicate through a shared memory interface (for example, the Cray X-MP), but they didn't have cache coherence. Most communication between processors in the early to mid '80s was done using message passing APIs. Today almost everyone uses the MPI standard for message passing APIs. The MPI standardization process started in 1992.

Cache-coherent shared memory multiprocessors and shared memory programming (for performance (as opposed to multi-threaded programming, which can be a convenient way to organize programs that need to interact asynchronously with the outside world)) started becoming somewhat common in the 1990s for systems with 10s of processors. The OpenMP standard for specifying parallel computation in Fortran or C was first published in 1997. Today (2013) you can buy a shared-memory machine with 8 hardware contexts for a few hundred dollars, and you can buy a shared-memory machine with 10s of hardware contexts for a few thousand dollars.

Hardware offload (to GPUs) started becoming popular when NVidia released the CUDA SDK for their GeForce GPUs in 2007. The computing model with hardware offload is heterogeneous and in flux (currently some computing is done on the main processor, which tends to be shared-memory, then data gets copied back and forth between the processor and the GPU, some computing is done in the many vector lanes on the GPU, which can share some memory, but also have some private memories, and then the results are copied back to the main processor.) It appears as if most vendors are trying to come up with approaches to make the movement between cpu and gpu more streamlined.

Meanwhile in the last 30 years the advent of techniques to dramatically improve single-thread performance have also internally leveraged a great deal of parallelism. Deep pipelining, superscalar and branch speculation techniques allow tens of instructions from a single thread to be in flight simultaneously. Each CPU in the Cray X-MP in 1983 could complete a theoretical peak of 200MFLOPS with a 105MHz clock, whereas a single core today might be able to do 12 GFLOPS with a 3GHz clock. So, many computations that would have needed to be hand-parallelized 30 years ago do not need to be explicitly parallelized today.

# Answer
> 0 votes
a main difference is that the hardware itself is highly parallelized whereas decades ago parallelism was more "simulated" at the OS level with multitasking on hardware that was not inherently parallel. so there were many processes for different users on a multiuser system, but the parallelism happened through context switching. for many years there was significant research into optimizing context switching techniques etc, optimizing single core CPUs to minimize context switching overhead, etc.

now a CPU generally inherently consists of multicore technology whereas pre mid 2000s most CPUs were single core. now there is a new Moores-law like scaling increase in CPU cores. a useful scientific ref that is helpful in conceptualizing and understanding the historical "paradigm shift" in parallel processing wrt CPUs & other hardware is The landscape of parallel computing, the view from Berkeley, 2006

---
Tags: parallel-computing, history
---


# Question
Title: Introduction to complexity and computability
I'm looking for a good book that explains these subjects in a readable way. Any suggestions ?

I currently pursuing my BSC in computer science, and I just failed to pass the course introduction to thr theory of computation and complexity. I would like to have more reference and sources of knowledge so I can understand the subject better. Examples and solutions for various problems like proving undecidability, many to one reductions, etc can help me alot.

# Answer
> 11 votes
For an introduction to the theory of computation I recommend you these great books (in order of increasing "complexity"):

1) Introduction to the Theory of Computation by Michael Sipser

It is very readable, theorems are very well explained and there are plenty of exercises (some with solutions and/or hints) and references.

2) Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences) by Michael R. Garey

The "bible" of NP-completeness. Although the second part is a mere list of NP-complete problems (with hints on the reductions), the first part is a good introduction to computational complexity and is focused on the theory of NP-completeness (but there are no exercises).

3) Computational Complexity: A Modern Approach by Sanjeev Arora

... This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory, including interactive proofs, PCP, derandomization, and quantum computation.... It has plenty of examples/exercises (unfortunately some nice (advanced) topics like Kolmogorov complexity or Descriptive complexity are missing).

Finally, if you need more intermediate/advanced books on computational complexity, then take a look to
Lance Fortnow's Favorite Computational Complexity books list on Amazon ...
without any doubt a bunch of "gems" :-)

# Answer
> 3 votes
you mention you want *readable* but then you state you want to have examples of problem & problem solving which are generally two different categories of references. here are some suggestions on *readable* background for general understanding and for "motivation" but not with problem sets.

a useful strategy is to look for "key/interesting/outstanding problems" in the area of study in this case complexity/computability theory. in this area the key open problem is P$\stackrel{?}{=}$NP for over 4 decades. Fortnow has released a brand new book on the subject which conveys the general significance of the problem, its deep/wideranging connections/implications, general aspects and applications of complexity theory, etc. you mention you'd like a "readable" survey and this book is very much targeted at a mass/not-overly-technical audience but also CS students should likely find it highly readable.

The golden ticket: P, NP, and the search for the impossible by Lance Fortnow. see also publisher page (Princeton university press) with TOC. see also this review by Schaefer, New York Journal of Books

Computability theory is another area that is covered in this readable ref by researcher Martin Davis: Engines of Logic: Mathematicians and the Origin of the Computer

---
Tags: complexity-theory, computability, reference-request, books
---


title: Cross Compiler's T diagram

text:
# Question
Title: Cross Compiler's T diagram
I'm studying Bootstrapping from Red Dragon Book Compilers and found the T diagram for cross compiler pretty confusing. I can't understand what is meant by "Run compiler1 through compiler2". Can anyone provide some better explanation, analogy or an example to relate with some real world compiler?

Some notation first. By $LSN=$ I mean a compiler for language $L$ written in language $S$ that produces output language/machine code $N$. This is a *tombstone* or *T-diagrams*.

> **Compiling a Compiler**
>
> 1. Suppose we have cross-compiler for a new language L in implementation language S generating code for machine N.
>
> $LSN=$
> 2. Suppose we also have an existing S compiler running on machine M implementing code for machine M:
>
> $SMM=$
> 3. Run LSN through SMM to produce LMN
>
> **Compiler Construction**
>
> $LMN = LSN + SMM$

# Answer
> 12 votes
The T-diagrams (which you had omitted from the original version of your question) are crucial for understanding this sort of question. Let's look at the last T-diagram.

The first T describes a compiler from L to N written in S.

The second T describes a compiler from S to M written in M (or running on M). This will be your *compiler compiler*.

Applying the second T to the first T compiles the first T so that it runs on machine M. The result is thus a compiler from L to N running on machine M.

The fact that the second T also runs on machine M is captures that you are running the compiler compiler on the machine which you will run the compiler, rather than having to use a cross compiler (which would be the case if the bottom M were different).

# Answer
> 5 votes
It means that we compile LSN with SMM, that is, run source code of LSN through SMM.

When SMM compiles some source code, it produces an executable for machine M, so when we compile LSN with SMM we get LMN - an executable, which compiles L source files on machine M in order to produce executables for machine N.

Perhaps it would be easier to understand this with an analogy. Supppse we have a C compiler `cc` which is written in Fortran, which generates ARM code. Suppose we also have a Fortran compiler `fc` on our x64 computer. If we compile `cc` source code with `fc` we get a program which runs on x64, compiles C programs, but produces executables for ARM.

# Answer
> 0 votes
To make it simple....

Note: Remember Compiler can run only on a low level language.

In 1st Diagram,compiler is written in HLL(High Level Langg) so inorder to run that on a machine the implementation langg of compiler should be in LLL.

So,in 2nd Diagram,the Implementation langg of compiler is ran on a self Resident compiler such that the target code can run on its own machine.

Finally ,combining both of them the compiler runs on a machine with langg--M

input langg--L

output Langg--N

---
Tags: compilers, terminology
---