title: Counting binary trees

text:
# Question
Title: Counting binary trees
(I'm a student with some mathematical background and I'd like to know how to count the number of a specific kind of binary trees.)

Looking at Wikipedia page for Binary Trees, I've noticed this assertion that the number of rooted binary trees of size $n$ would be this Catalan Number: $$C\_n = \dfrac{1}{n+1}{2n \choose n}$$

But I don't understand how I could come up with such a result by myself? Is there a method to find this result?

Now, what if the order of sub-trees (which is left, which is right) is not considered? For example, from my point of view, I consider that these two trees are the same:

```
   /\   /\
  /\     /\

```

Would it be possible to apply a similar method to count how many of these objects have exactly $n$ nodes?

# Answer
For counting many types of combinatorial objects, like trees in this case, there are powerful mathematical tools (the symbolic method) that allow you to mechnically derive such counts from a description how the combinatorial objects are constructed. This involves generating functions.

An excellent reference is Analytic Combinatorics by the late Philipe Flajolet and Robert Sedgewick. It is available from the link above.

The late Herbert Wilf’s book generatingfunctionology is another free source.

And of course Concrete Mathematics by GKP is a treasure trove.

---

For binary trees it goes like this: First you need a clear definition of the tree.

*A binary tree is a rooted tree in which every non-leaf node has degree 2 exactly.*

Next we have to agree what we want to call *the size* of a tree.

On the left all nodes are equal. In the middle we distinguish the leaves and non-leaves. On the right we have a pruned binary tree where the leaves have been removed. Notice that it has unary branches of two types (left and right)!

Now we have to derive a description of how these combinatorial objects are built. In the case of binary trees a *recursive decomposition* is possible.

Let $\mathcal{A}$ be the set of all binary trees of the first type then symbolically we have:

It reads as: “An object of the class of binary trees is either a node or a node followed by two binary trees.” This can be written as equation of sets:

$$\mathcal{A}=\\{\bullet\\}\cup\bigl(\\{\bullet\\}\times\mathcal{A}\times\mathcal{A}\bigr)$$

By introducing the generating function $A(z)$ that enumerates this class of combinatorial objects we can translate the set equation into an equation involving the generating function.

$$A(z)=z+zA^2(z)$$

Our choice of treating all nodes equally and taking the number of nodes in the tree as notion of its size is expressed by “marking” the nodes with the variable $z$.

We can now solve the quadratic equation $zA^2(z)-A(z)+z=0$ for $A(z)$ and get, as usual, two solutions, the explicit closed form of the generating function:

$$A(z)=\frac{1\pm\sqrt{1-4z^2}}{2z}$$

Now we simply need Newton’s (generalized) Binomial Theorem:

$$(1+x)^a=\sum\_{k=0}^\infty\binom{a}{k}x^k$$

with $a=1/2$ and $x=-4z^2$ to expand the closed form of the generating function back into a power series. We do this because, the coefficient at $z^n$ is just the number of combinatorial objects of size $n$, typically written as $\[z^n\]A(z)$. But here our notion of “the size” of the tree forces us to look for the coefficient at $z^{2n+1}$. After a little bit of juggling with binomials and factorials we get:

$$\[z^{2n+1}\]A(z)=\frac{1}{n+1}\binom{2n}{n}.$$

If we start with the second notion of the size the recursive decomposition is:

We get a different class of combinatorial objects $\mathcal{B}$. It reads: “An object of the class of binary trees is either a leaf or a interal node followed by two binary trees.”

We can use the same approach and turn $\mathcal{B}=\\{\square\\}\cup\bigl(\\{\bullet\\}\times\mathcal{B}\times\mathcal{B}\bigr)$ into $\mathcal{B}=1+zB^2(z)$. Only this time the variable $z$ only marks the internal nodes, not the leaves, because the definition “the size“ is different here. We get a different generating function as well:

$$B(z)=\frac{1-\sqrt{1-4z}}{2z}$$

Extracting the coefficient yields

$$\[z^n\]B(z)=\frac{1}{n+1}\binom{2n}{n}.$$

Class $\mathcal{A}$ and $\mathcal{B}$ agree on the counts, because a binary tree with $n$ internal nodes has $n+1$ leaves, thus $2n+1$ nodes in total.

In the last case we have to work a little harder:

which is a description of non-empty pruned binary tries. We extend this to $$\begin{align}\mathcal{C}&=\\{\bullet\\}\cup\bigl(\\{\bullet\\}\times\mathcal{C}\bigr)\cup\bigl(\\{\bullet\\}\times\mathcal{C}\bigr)\cup\bigl(\\{\bullet\\}\times\mathcal{C}\times\mathcal{C}\bigr)\\\mathcal{D}&=\\{\epsilon\\}\cup\bigl(\\{\bullet\\}\times\mathcal{C}\times\mathcal{C}\bigr)\end{align}$$

and rewrite it with generating functions

$$\begin{align}C(z)&=z+2zC(z)+zC^2(z)\\D(z)&=1+zC^2(z)\end{align}$$

solve the quadratic equations

$$\begin{align}C(z)&=\frac{1-2z-\sqrt{1-4z}}{2z}\\D(z)&=\frac{1-\sqrt{1-4z}}{2z}\end{align}$$

and get yet again

$$\[z^n\]C(z)=\frac{1}{n+1}\binom{2n}{n}\quad n\ge1 \qquad \[z^n\]D(z)=\frac{1}{n+1}\binom{2n}{n} \quad n\ge0$$

Note that the *Catalan generating function* is

$$E(z)=\frac{1-\sqrt{1-4z}}{2}$$

it enumerates the class of *general trees*. That is the trees with no restriction on the node degree.

$$\mathcal{E}=\\{\bullet\\}\times\mathrm{SEQ}(\mathcal{E})$$

It reads as: “An object of the class of general trees is a node followed by a possible empty sequence of general trees.”

$$E(z)=\frac{z}{1-E(z)}$$

With the Lagrange-Bürmann Inversion Formula we get

$$\[z^n\]E(z)=\frac{1}{n+1}\binom{2n}{n}$$

So we proved that there are as many general trees as there are binary trees. No wonder there is a bijection between the general and binary trees. The bijection is known as the rotation correspondence (explained at the end of the linked article), that allows us two store every general tree as a binary tree.

Note that if we do not distinguish the left and right sibling in class $\mathcal{C}$ we get yet another class of trees $\mathcal{T}$:

the unary binary trees. $$\mathcal{T}=\\{\bullet\\}\times\mathrm{SEQ}\_{\le2}(\mathcal{T})$$ They have a generating function too $$T(z)=\frac{1-z-\sqrt{1-2z-3z^2}}{2z}$$ however their coefficient is different. You get the Motzkin numbers $$\[z^n\]T(z)=\frac{1}{n}\sum\_k\binom{n}{k}\binom{n-k}{k-1}.$$

Oh and if you don’t like generating functions there are plenty of other proofs too. See here, there is one where you could use the encoding of binary trees as Dyck words and and derive a recurrence from their recursive definition. Then solving that recurrence gives the answer too. However the symbolic method saves you from coming up with the recurrence in the first place, as it works directly with the blueprints of the combinatorial objects.
> 39 votes

# Answer
Generating functions are a very powerful and very useful magic wand. The following solution to the first question (why are there $C\_n$ trees) is somewhat less magical. Hence, cute.

**Example.** To produce a tree of $5$ nodes we start with a sequence in which $+1$ occurs $5+1$ times, and $-1$ occurs $5$ times. For example, $+-++-+--++-$. Among those prefixes with the smallest (and possibly negative) sum, pick the longest; in this case, $+-++-+--$. Take this prefix from the beginning and put it at the end; in this case, we get $++-+-++-+--$. Now change $+$ into $T$ and $-$ into $E$; in this case we get `TTETETTETEE`. Remove a $T$ from the beginning, add an $E$ at the end; in this case we get `TETETTETEEE`. This is a description of the tree `T(E,T(E,T(T(E,T(E,E)),E)))`. Below there's some explanation of why this is a bijection. Once you're convinced of that, counting is easy. There are $\binom{5+6}{5}$ sequences of $\pm1$, then we divided by $5+6$ because we chose one of the possible cyclic permutations.

**First bijection.** A typical definition for trees in ML is `type tree = T of tree * tree | E`; that is, a tree either has two (ordered) subtrees, or it is empty. Here is how trees are constructed: `T(T(E,E),T(T(E,E),T(E,E)))`. Dropping fluff, we can simply write `TTEETTEETEE`. All such descriptions will end with an `E`, so it is redundant: `TTEETTEETE`. (Note that the empty tree now corresponds to the empty string.) These strings have the property that each prefix has at least as many Ts as Es, and in total they have $n$ Ts and $n$ Es, where $n$ is the number of nodes of the tree.

**Second bijection.** We now replace T by +1 and E by -1. So, we are looking at sequences with $n$ values +1, with $n$ values -1, and with the sums of all prefixes $\ge0$.

**Third bijection.** We now change the requirement for prefixes a little: We ask that the sum of each non-empty prefix to be $\>0$. For this to be possible we let $n+1$ values +1 and $n$ values -1. (Otherwise the sum of the whole string would be 0 and would fail to meet the condition for prefixes.) These sequences must begin with +1. So, they really are the same as before, except they have a +1 stuck in the beginning.

**Raney property.** Now forget our sequences for a moment and consider some finite sequence of *integers* $x\_1$, $\ldots\\,$, $x\_m$ whose sum is 1. If all non-empty prefixes have positive sums, then no cyclic permutation of this sequence has the same property. Why? Well, suppose there is a $k\ne1$ such that $x\_k,\ldots,x\_m,x\_1,\ldots,x\_{k-1}$ also has all non-empty prefixes positive. Then $x\_1+\cdots+x\_{k-1}\ge1$ (property of sequence starting from $x\_1$) and $x\_k+\cdots+x\_m\ge1$ (property of sequence starting from $x\_k$); hence, $x\_1+\cdots+x\_m\ge2$, which contradicts the assumption that the sum for the whole sequence is 1.

Moreover, given some sequence with sum 1, there is always a cyclic permutation that makes all non-empty prefixes have positive sum. (This is true even for real numbers.)

**Conclusion.** Now let's count the sequences of +1 and -1 that are in a bijection with trees. Out of $2n+1$ numbers we must pick $n+1$ that equal +1, the others will be -1. There are ${2n+1\choose n+1}$ ways to do so. But, only $1$ in $2n+1$ sequences counted so far has positive prefixes. So, the number of rooted, ordered binary trees is:

$${1\over2n+1}{2n+1\choose n+1}={1\over2n+1}{2n+1\over n+1}{2n\choose n}={1\over n+1}{2n\choose n}$$
> 8 votes

---
Tags: combinatorics, binary-trees, discrete-mathematics
---


# Question
Title: Please explain this formal definition of computation
I am trying to attack TAOCP once again, given the sheer literal heaviness of the volumes I have trouble committing to it seriously. In TAOCP 1 Knuth writes, page 8, basic concepts::

> Let $A$ be a finite set of letters. Let $A^\*$ be the set of all strings in $A$ (the set of all ordered sequences $x\_1$ $x\_2$ ... $x\_n$ where $n \ge 0$ and $x\_j$ is in $A$ for $1 \le j \le n$). The idea is to encode the states of the computation so that they are represented by strings of $A^\*$ . Now let $N$ be a non-negative integer and Q (the state) be the set of all $(\sigma, j)$, where $\sigma$ is in $A^\*$ and j is an integer $0 \le j \le N$; let $I$ (the input) be the subset of Q with $j=0$ and let $\Omega$ (the output) be the subset with $j = N$. If $\theta$ and $\sigma$ are strings in $A^\*$, we say that $\theta$ occurs in $\sigma$ if $\sigma$ has the form $\alpha \theta \omega$ for strings $\alpha$ and $\omega$. To complete our definition, let $f$ be a function of the following type, defined by the strings $\theta\_j$, $\phi\_j$ and the integers $a\_j$, $b\_j$ for $0 \le j \le N$:
>
> * $f((\sigma, j)) = (\sigma, a\_j)$ if $\theta\_j$ does not occur in $\sigma$
> * $f((\sigma, j)) = (\alpha \psi\_j \omega, b\_j)$ if $\alpha$ is the shortest possible string for which $\sigma = \alpha \theta\_j \omega$
> * $f((\sigma,N)) = (\sigma, N)$

Not being a computer scientist, I have trouble grasping the whole passage. I kind of get the idea that is behind a system of opcodes, but I haven't progressed effectively in understanding. I think that the main problem is tat I don't know how to read it effectively.

Would it be possible to explain the passage above so that I can understand it, and give me a strategy in order to get in the logic in interpreting these statements?

# Answer
> 8 votes
We are missing some context so I have no idea what point Knuth is trying to make, but here's how to interpret a Turing machine this way. Perhaps it will help you understand what's going on. In general, a good way of getting a grip on a concept is playing with it. In the case of programming paradigms, that means writing a program. In this case, I will show how to write *any* program.

Suppose the tape of the Turing machine has symbols $\\{0,1,\epsilon\\}$ (where $\epsilon$ stands for "empty"), and add one more symbol which represents the location of the head $H$. Your states are going to be pairs of the form $(q,\alpha)$, where $q$ is a state of the Turing machine, and $\alpha \in \\{0,\ldots,14\\}$. We also identify $(F,0)$ with $N$ for any final state.

On (non-empty) input $x$, your starting point will be $(Hx,(s,0))$, where $s$ is the starting state. The difficult part is to encode states. Suppose that at state $q$, upon reading input $x$, you replace it with $a(q,x)$, move in direction $D(q,x) \in \\{L,R\\}$, and switch to state $\sigma(q,x)$. For the $\theta$s, we have $$ \begin{align\*} \theta\_{q,0} &= 0H0, & \theta\_{q,1} &= 0H1, & \theta\_{q,2} &= 0H\epsilon, \\ \theta\_{q,3} &= 1H0, & \theta\_{q,4} &= 1H1, & \theta\_{q,5} &= 1H\epsilon, \\ \theta\_{q,6} &= \epsilon H0 & \theta\_{q,7} &= \epsilon H1, & \theta\_{q,8} &= \epsilon H\epsilon, \\ \theta\_{q,9} &= H0, & \theta\_{q,10} &= H1, & \theta\_{q,11} &= H\epsilon, \\ \theta\_{q,12} &= 0H, & \theta\_{q,13} &= 1H, & \theta\_{q,14} &= \epsilon H. \end{align\*} $$ For the $a$s, we have $a\_{q,i} = (q,i+1)$ for $i \< 14$, and $a\_{q,14} = (q,14)$, though we should never really get that far. For the $b$s, we have $$ \begin{align\*} &b\_{q,0} = b\_{q,3} = b\_{q,6} = b\_{q,9} = (\sigma(q,0),0), \\ &b\_{q,1} = b\_{q,4} = b\_{q,7} = b\_{q,10} = (\sigma(q,1),0), \\ &b\_{q,2} = b\_{q,5} = b\_{q,8} = b\_{q,11} = b\_{q,12} = b\_{q,13} = b\_{q,14} = (\sigma(q,\epsilon),0). \end{align\*} $$ Now it remains to determine the $\psi$s. Let $a\_0 = a(q,0)$. If $D(q,0) = L$ then $$ \begin{align\*} \psi\_{q,0} &= H0a\_0, & \psi\_{q,3} &= H1a\_0, & \psi\_{q,6} &= \psi\_{q,9} = H\epsilon a\_0. \end{align\*} $$ If $D(q,0) = R$ then $$ \begin{align\*} \psi\_{q,0} &= 0a\_0H, & \psi\_{q,3} &= 1a\_0H, & \psi\_{q,6} &= \epsilon a\_0 H, & \psi\_{q,9} &= a\_0H\epsilon. \end{align\*} $$ Next, let $a\_1 = a(q,1)$. If $D(q,1) = L$ then $$ \begin{align\*} \psi\_{q,1} &= H0a\_1, & \psi\_{q,4} &= H1a\_1, & \psi\_{q,7} &= \psi\_{q,10} = H\epsilon a\_1. \end{align\*} $$ If $D(q,1) = R$ then $$ \begin{align\*} \psi\_{q,1} &= 0a\_1H, & \psi\_{q,4} &= 1a\_1H, & \psi\_{q,7} &= \epsilon a\_1 H, & \psi\_{q,10} &= a\_1 H\epsilon. \end{align\*} $$ Finally, let $a\_\epsilon = a(q,\epsilon)$. If $D(q,\epsilon) = L$ then $$ \begin{align\*} \psi\_{q,2} &= H0a\_\epsilon, & \psi\_{q,5} &= H1a\_\epsilon, & \psi\_{q,8} &= \psi\_{q,11} = H\epsilon a\_\epsilon, \\ \psi\_{q,12} &= H0a\_\epsilon, & \psi\_{q,13} &= H1a\_\epsilon, &\psi\_{q,14} &= H\epsilon a\_\epsilon. \end{align\*} $$ If $D(q,\epsilon) = R$ then $$ \begin{align\*} \psi\_{q,2} &= 0a\_\epsilon H, & \psi\_{q,5} &= 1a\_\epsilon H, & \psi\_{q,8} &= \epsilon a\_\epsilon H, & \psi\_{q,11} &= a\_\epsilon H\epsilon, \\ \psi\_{q,12} &= 0a\_\epsilon H, & \psi\_{q,13} &= 1a\_\epsilon H, & \psi\_{q,14} &= \epsilon a\_\epsilon H. \end{align\*} $$

Now apply $f$ repeatedly until you get stuck. If you follow the construction, you will see that we have simulated the running of the Turing machine.

# Answer
> 6 votes
Let us break it down bit by bit. First of all, remember what Knuth wrote on page 7:

> Let us formally define a *computational method* to be a quadruple $(Q,I,\Omega,f)$, in which $Q$ is a set containing subsets $I$ and $\Omega$, and $f$ is a function from $Q$ into itself. \[...\] The four quantities $Q$, $I$, $\Omega$, $f$ are intended to represent repectively the state of the computation, the input, the output, and the computational rule.

This is the outline. You have to read "represent" as "contain"; $Q$ is going to contain states (some of which are in $I$, some are in $\Omega$) and $f$ is going to be a transition function between states; think of it as a program.

> Let $A$ be a finite set of letters. Let $A^\*$ be the set of all strings in $A$ (the set of all ordered sequences $x\_1$ $x\_2$ ... $x\_n$ where $n \ge 0$ and $x\_j$ is in $A$ for $1 \le j \le n$).

This is just a reiteration of what $A^\*$ is. See also here.

> The idea is to encode the states of the computation so that they are represented by strings of $A^\*$.

This is probably the key sentence. We are talking about *computations*, that is execution sequences of some (programming language) statements which manipulate some *state*, which can be thought of as values in memory cells, or valuations of variables. Knuth says here that he wants to encode these states in an abstract way, namely as *word* over some alphabet.

**Example:** Consider a program that uses (at most) $k$ variables, each of which stores an integer. That is, a state is given by the tuple of values $(x\_1, \dots, x\_k)$ where $x\_k$ is the (current) value of the $k$-th variable. In order to encode states of this form in a formal language, we can choose $A = \\{0,1,\\#\\}$ with $\\#$ a separator. Now model such a state by $\\#\overline{x\_1}\\#\cdots\\#\overline{x\_k}\\#$ where $\overline{x\_i}$ is the binary encoding of $x\_i$.

Specifically, $(3,5,0)$ would be $\\#11\\#101\\#0\\#$.

> Now let $N$ be a non-negative integer and Q be the set of all $(\sigma, j)$, where $\sigma$ is in $A^\*$ and j is an integer $0 \le j \le N$; let $I$ be the subset of Q with $j=0$ and let $\Omega$ be the subset with $j = N$.

You misquoted there (bad Stefano!); the parentheses are not in the original text, and they were misleading (see above). Knuth defines $Q$ here as the set of *all possible states* ($\sigma \in A^\*$) at *all possible places in the computation* ($j$ can be understood as program counter). Therefore, $Q$ contains all statement-indexed states any computation of the algorithm given by $f$ can assume. By definition, we start with program counter $0$ and end in $N$, thus states indexed $0$ are input states and those indexed $N$ are output states.

> If $\theta$ and $\sigma$ are strings in $A^\*$, we say that $\theta$ occurs in $\sigma$ if $\sigma$ has the form $\alpha \theta \omega$ for strings $\alpha$ and $\omega$.

I hope that this is clear; it is just a (re)definition of substrings.

> To complete our definition, let $f$ be a function of the following type, defined by the strings $\theta\_j$, $\phi\_j$ and the integers $a\_j$, $b\_j$ for $0 \le j \le N$:
>
> * $f((\sigma, j)) = (\sigma, a\_j)$ if $\theta\_j$ does not occur in $\sigma$
> * $f((\sigma, j)) = (\alpha \psi\_j \omega, b\_j)$ if $\alpha$ is the shortest possible string for which $\sigma = \alpha \theta\_j \omega$
> * $f((\sigma,N)) = (\sigma, N)$

This is a a small programming language; if you fix $\theta\_j, \psi\_j, a\_j, b\_j$, you have a program. On program counter $j$, $f$ replaces the left-most occurrence $\theta\_j$ in the state with $\psi\_j$ and goes to statement $b\_j$. If there is no $\theta\_j$ in the current state, it goes to statement $a\_j$. The program loops if statement $N$ is reached, modelling termination.

On the upper half of page 8, there is a more concrete example of a "program" $f$. Keep in mind that Knuth is going to use assembly language later on; this informs how he looks at programs (atomic statements connected by jumps).

# Answer
> 5 votes
That text describes the following (Python) pseudocode:

```
subs = a list of string pairs
As = a list of integers
Bs = a list of integers

def f(state, pc):
  if pc == N: return (state, pc)
  if state.find(subs[pc][0]) != -1:
    return (state.replace(subs[pc][0],subs[pc][1],1), Bs[pc])
  else:
    return (state,As[pc])

```

The function f is presumably going to be applied repeatedly.

The last three bullet points is all you really need once you understand the notations. All that comes before is a bit analogous to explaining how Python works before giving the Python code.

---
Tags: formal-languages, turing-machines, computation-models
---


# Question
Title: Regular expression for all strings with at least two 0s over alphabet {0,1}
I was interested in finding regular expression for all strings with at least two $0s$ over alphabet $\\{0,1\\}$.

I attempted and formulated $$(0+1)^\* 0 (0+1)^\* 0 (0+1)^\*$$

Is this correct? And if not can somebody post and explain the correct one?

# Answer
It's incorrect for example because it does not match the string $100$.

The two zeroes would have to match the two zeroes in your regexp that are ouside the parentheses. Because of that, $(0\\!+\\!1)^\*$ would have to match $1$, but it doesn't. That's because $(0\\!+\\!1)^\*$ implies there has to be at least one zero for every $1$.

I think the regular expression that you meant is:

$$(0|1)^\* 0 (0|1)^\* 0 (0|1)^\*.$$
> -2 votes

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: $L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular
Suppose that $L(M) = L$ where $M$ is a $TM$ that moves only to the right side.

I need to Show that $L$ is regular.

I'd relly like some help, I tried to think of any way to prove it but I didn't reach to any smart conclusion. what is it about the only side right moves and the regularity?

# Answer
Hint -- You need to show that your TM has the same power as a finite-state automaton (as the commenter Dave Clarke said), that is, given such a TM, construct a FSA that accepts the same language.

But since the TM has no memory but the tape, ask yourself what a right-only TM can do with its tape. It should be relatively straightforward to actually construct the parts of the FSA you are looking for. Just go through them -- the states, the input alphabet and most crucially the move function (usually $\delta$) and define them in terms of the parts of the TM you started with. Then you have to show that the two accept the same language, in terms of the definition of "accept" for each, being sure to mention potential looping behavior in the TM.

BTW, this sort of problem is amenable to a pretty convincing "hand-waving" proof that would actually be of a type that is quite acceptable in a research paper. Your course, however, may be expecting a precise proof, using $\delta$ and the other components of the tuples that constitute the TM and FSA.
> 8 votes

# Answer
The only difference between a finite automaton and a Turing machine is the tape. The tape provides memory ability. If you can go only on one side, then you simply can't read what you have written.

To formally prove this you build an automaton from your machine $M$. Suppose $A$ is the automaton in $M$. Then your automaton $A'$ will be the same as $A$ with a one-cell memory, because you can still read the cell you are on in $M$. (Number of states of $A'$ = number of states of $M$ $×$ size of the alphabet of the tape).

Note that this is still true if you can only read the cells that are at a bounded distance from the visited cell the most on the right because you have still a bounded memory. Also, the number of tapes and whether you read from a tape or a "standard input" like a DFA does not matter.
> 7 votes

---
Tags: formal-languages, computability, turing-machines, regular-languages, computation-models
---


# Question
Title: Turn one string into another with single letter substitions
I want to turn one string into another with only single letter substitions. What is a good way to do this, passing through only valid words in between (this website has some examples)?

Valid here means "a word in English" as this is the domain I consider.

My current idea is that I could use a shortest path algorithm with the Hamming distance for edge weights. The problem is that it will take a long time to build the graph, and even then the weight is not so precise in terms of distance (though it will never underestimate it) unless the weight is one, so I would probably have to find a to build a graph that only had weights of one.

What would be the easiest way to build the graph? Am I taking entirely the wrong approach?

# Answer
> 6 votes
The graph I consider has the valid words for vertices and edges correspond to one-letter substitutions. In this graph the Hamming distance never *overestimates* the distance but can underestimate it (e.g. between $aa$ and $cc$ in the set of valid words ${aa,ab,bb,bc,cc}$)

You don't need an actual graph, you just need a representation of it. The hard part is computing the neighbors : you may want to store the valid words into a prefix tree. But for the search algorithm you already have a non-overestimating distance so you can use that as a admissible heuristic for the $A^\*$ algorithm. You can use an hash table to store the marked vertices.

### Building the prefix tree

To list all the neighbors of $w$ first use this function that computes all words $v$ such that $w$ and $v$ differs only on the $i$th letter. It runs in $O(|Σ||w|)$ if you implement it correctly : $w$ must be in the form of a list for the `tail()` dans `head()` operation to be in constant time. The operation `prefix . c . tail(w)` just has to be in linear time.

```
neighbors(i, prefix, w, trie) =
  if(i == 0) :
    for c in 'a' .. 'z' :
      if(tail(w) is a word of trie) :
        add(prefix . c . tail(w))
  else :
    neighbors(i-1, prefix . w[0], tail(w), trie[head(w)])

```

Then to list all the neighbors, just run:

```
for i in 0 .. length(w) - 1 :
  neighbors(i, emptyprefix, w, trie_of_valid_words)

```

Which runs in $O(|Σ||w|^2)$.

Compared to other methods, where $N\_V$ the number of valid words.

* if you use a hash table and enumerate all the potential neighbors: $O(|Σ||w|^2)$ in the *practical* case and $O(|Σ||w|^2N\_V)$ in the worst case. It might be faster in practice though.
* if you use a binary search tree: $O(|Σ||w|\log N\_V)$ in the worst and average case.

### Precomputation

At first the goal was to get all the neighbors in only one look up in time $O(|w|)$ by previously having computed some kind of prefix tree with wildcards. (I don't really know the name of this data structure) Then I realized that it can simply be done with just a reverse search.

I insist that this is only interesting if you only care about the look up time. I would probably be a good idea if you have to find the shortest path between several pairs of words. If it's only one time the method above will be enough.

This is really very simple : for each word $w$, enumerate all the possible neighbors $v$ of $w$ and check if they are valid. This is in $O(N\_V\log N\_V |w||Σ|)$ or $O(N\_V^2)$ if $N\_V$ is small enough for this to be interesting. Add them to your automaton / prefix tree / hash table with the key $v$ and the value $w$.

Then getting all the neighbors of $v$ is looking up in this structure and getting back all the $w$'s. So you can make your search algorithm with this.

Implementation details:

* generic binary tree : look up in $O(\log(N\_V|Σ||w|))$ which is $O(|w|+\log|Σ|)$ but you don't care about the $\log|Σ|$.
* trie : look up in $O(|w|)$
* hash : look up in $O(|w|)$ (and worst worst case)

### Conclusion

If the set of valid words does not change I would suggest precomputing and storing in a hash table and using the A\* with the hamming distance admissible heuristic.

# Answer
> 5 votes
I am not sure if I understood the problem setting correctly, but I think a breadth-first search works?

**Problem:** Given words $w$ and $w'$ from a dictionary $D$, is it possible to find a sequence of words $w\_0,...,w\_k$, such that each word is from $D$, $w\_0=w$, $w\_k=w'$, and $w\_i$ and $w\_{i+1}$ differ by exactly a single letter substitution.

**Algorithm:** Start a breadth-first search at $w$, where vertices are words in $D$, and edges connect words which differ by a single letter substitution. Find $w'$ in this way, and you found a shortest path between $w$ and $w'$. How to enumerate the neighbours of some vertex $v$? We can simply go through every position of the word and check for every letter substitution whether the resulting word is in $D$.

**Running time:** Simple BFS is running time $O(|V|+|E|)$, here $|V|=|D|$. However, enumerating the neighbours takes $|w|\*|\Sigma|$ steps, where $|\Sigma|$ is the size of your alphabet. Assuming alphabet size to be constant, and dictionary lookup cost of $O(|w|)$ (e.g. Hashsets), you have a running time of $O(|V||w|^2+|E|)$.

---
Tags: algorithms, strings, string-metrics
---


title: Quicksort to find median?

text:
# Question
Title: Quicksort to find median?
Why is the worst scenario $\mathcal{O}\left(n^2\right)$ when using quicksort to find the median of a set of numbers?

* If your algorithm continually picks a number larger than or smaller than *all* numbers in the list wouldn't your algorithm fail? For example if the list of numbers are:

$S = (12,75,82,34,55,15,51)$

and you keep picking numbers greater than $82$ or less than $12$ to create sublists with, wouldn't your set always remain the same size?
* If your algorithm continually picks a number that creates sublists of $1$ why is the worst case scenario $\mathcal{O}\left(n^2\right)$? Wouldn't efficiency be linear considering that according to the Master Theorem, $d\>\log\_b a$?\* (and therefore be $\mathcal{O}\left(n^d\right)$ or specifically in this case $\mathcal{O}\left(n\right)$)

\*Where $d$ is the efficiency exponent (i.e. linear, exponential etc.), $b$ is the factor the size of problem is reduced by at each iteration, $a$ is the number of subproblems and $k$ is the level. Full ratio: $T(n) = \mathcal{O}\left(n^d\right) * (\frac{a}{b^d})^k$

# Answer
> 9 votes
Quicksort is for sorting, the algorithm you refer to is a selection algorithm known as Quick Select.

* Since you can only pick as pivot a number that is in the list case #1 never happens.
* Worst case is that you continually pick a number that partitions the list into 2 lists: A list with just one element and a list with $n-1$ elements, if this is the case in each iteration you only rule out a single element.

So first iteration you do $n$ operations, second iteration $n-1$ operations, third one $n-2$ operations, ... last iteration 1 operation.

Which its the sum of the first $n$ natural numbers:

$1+2+3+... +(n-2)+(n-1)+ n = n(n-1)/2$ operations = $O(n^2)$

---
Tags: algorithms, algorithm-analysis, search-algorithms
---


title: subsets of infinite recursive sets

text:
# Question
Title: subsets of infinite recursive sets
A recent exam question went as follows:

> 1. $A$ is an infinite recursively enumerable set. Prove that $A$ has an infinite recursive subset.
> 2. Let $C$ be an infinite recursive subset of $A$. Must $C$ have a subset that is *not* recursively enumerable?

I answered 1. already. Regarding 2., I answered affirmatively and argued as follows.

Suppose that all the subsets of $C$ were recursively enumerable. Since $C$ is infinite, the power set of $C$ is uncountable, so by assumption there would be uncountably many recursively enumerable sets. But the recursively enumerable sets are in one-to-one correspondence with the Turing machines that recognize them, and Turing machines are enumerable. Contradiction. So $C$ must have a subset that is not recursively enumerable.

Is this correct?

# Answer
It is correct.

Every infinite set has an undecidable subset, you can use the cardinality argument: $\aleph\_0\leq C \implies \aleph\_0 \< 2^C$. In fact most of its subsets are undecidable (and you can replace undecidable with any countable class of languages, e.g. c.e., arithmetical, analytical, ...).

The bad thing about this argument is that it doesn't give any information about how difficult the subset is. We usually want a subset which is as easy as possible. One way to get this is using a diagonalization similar to the cardinality argument using the fact that $C$ is decidable:

Define $D = \\{ i \in C \mid i \notin W\_i \\}$, where $W\_i$ is the $i$th c.e. set. Obviously $D \subseteq C$. Moreover $D$ can be solved with an oracle for $C$ and $K = \\{ i \mid i\notin W\_i\\}$. So if $C$ is decidable then $D$ is a co-c.e. language.
> 11 votes

---
Tags: computability, check-my-proof
---


title: Fast Poisson quantile computation

text:
# Question
Title: Fast Poisson quantile computation
I am seeking a fast algorithm to compute the following function, a quantile of the Poisson distribution: $$f(n, \lambda) = e^{-\lambda} \sum\_{k=0}^{n} \frac{\lambda^k}{k!} $$

I can think of an algorithm in $O(n)$, but considering the structure of the series, there is probably a $O(1)$ solution (or at least a good $O(1)$ approximation). Any take?

# Answer
> 4 votes
Given a precision $ε\>0$ you want to compute $f(n,λ)$. When $n≤m$, let $g$ be the error function, that is the difference, between the sum of the $m-1$ first terms and the actual value $f(n,λ)$.

$$g(n,λ,m)=e^{-λ}\sum\_{k=m}^n\frac{λ^k}{k!}$$

You want to find a $m$ big enough to have $g(n,λ,m)≤ε$. Then you just have to remark that the following terms are not very big so you can go a little bit further:

$$g(n,λ,m)\<e^{-λ}\sum\_{k=m}^∞\frac{λ^k}{k!}=h\_λ(m)$$

Since the well-known corresponding series converges, $\lim h\_λ = 0$. So for all $ε$ and $λ$ you can find a $m\_{ε,λ}$ such that $m\_{ε,λ}$ steps are enough to compute $f(n,λ)$ with precision $ε$.

Given $ε$ and $λ$ your problem is in $O(1)$.

---
Tags: algorithms, numerical-analysis
---


# Question
Title: Why is a regular language called 'regular'?
I have just completed the first chapter of the *Introduction to the Theory of Computation* by *Michael Sipser* which explains the basics of finite automata.

He defines a regular language as anything that can be described by a finite automata. But I could not find where he explains why a regular language is called "regular?" What is the origin of the term "regular" in this context?

NOTE: I am a novice so please try to explain in simple terms!

# Answer
> 29 votes
As Kaveh says in a comment, Kleene bestowed the name way back when he kicked off automata theory and formal languages. I believe the term was arbitrary, though it has been many years since I read his original paper.

Mathematicians have a habit of hijacking common nouns and adjectives for mathematical objects and properties, sometimes with good reasons such as geometric or other analogies or metaphors, and sometimes arbitrarily. Just look at "group", "ring", "space", "sheaf", "atlas", "manifold", "field" and so on.

In fact, the term "regular" for finite-state languages, while still prevalent in automata theory, is not used very much in its algebraic cousin, finite semigroup theory or abstract algebra in general. Why? Because the term was already taken for a semigroup that is close to a group in a specific technical sense, so you couldn't match up a regular language in Kleene's sense with a corresponding regular semigroup. Third, Kleene defined another kind of event called "definite", which was much studied for a while, but has turned out to be not particularly fruitful. Today, finite sets of language play the role of definite events as the basis for regular events.

The preferred term in algebra is "rational" for both Kleene's class of languages and the more general semigroups and monoids. That usage also reflects an important analogy between the term "rational" in algebra as the solution of a linear equation with integer coefficients and the concept of rational power series in automata and formal language theory.

---

**Additional information.** Kleene's original paper of 1951, entitled "Representation of events in nerve nets and finite automata" may be found here. On p. 46 it settles the arbitrariness of the term "regular" with this statement:

> We shall presently describe a class of events which we will call "regular events". (We would welcome any suggestions as to a more descriptive term.)

Apparently, nobody came up with a more descriptive term. ;-)

As is often the case with seminal papers which lead to the intensive development of whole new areas, the terminology and concepts are almost unrecognizable in today's terms. First, the paper was about models of neurons, hence the use of "events" instead of "languages" or "sets". The term "events" persisted well into the 60's and 70's, even after the importance of Kleene's concepts for automata and formal languages vastly outweighed any value for neuroscience.

Second, there are some mathematical differences, such as defining what came to be called "Kleene Closure" as a binary operation, equivalent to $a^\*b$, instead of the simpler unary operation $a^\*$ or $a^+$ that we use today. Kleene's motivation was to avoid the empty string (or event with duration zero in his terms). That was a remarkably prescient intuition since subsequent theory has shown how crucial the choice is to include or exclude the empty string from definitions in many contexts. Third, Kleene defined a concept called "definite events" and developed regular events from them, but nowadays we use finite sets for the purpose. Definite events were studied for a while, but have turned out to be far less important than regular events/sets/languages.

Anyway, a complete reading of this paper is probably not worth anyone's time today, except for historical purposes. I just skimmed it for the crucial definitions and ideas, and that was fun.

# Answer
> 4 votes
I have always understood the term "regular" to mean that it is based on a pattern repeating itself. After you have enumerated all strings of a certain length, you have seen them all. There will be nothing new afterwards.

(It is only a vague intuition of course.)

---
Tags: formal-languages, regular-languages, terminology, finite-automata, history
---


# Question
Title: Probabilistic test of matrix multiplication with one-sided error
Given three matrices $A, B,C \in \mathbb{Z}^{n \times n}$ we want to test whether $AB \neq C$. Assume that the arithmetic operations $+$ and $-$ take constant time when applied to numbers from $\mathbb{Z}$.

How can I state an algorithm with one-sided error that runs in $O(n^2)$ time and prove its correctness?

I tried it now for several hours but I can't get it right. I think I have to use the fact that for any $x \in \mathbb{Z}^n$ at most half of the vectors $s \in S = \left\\{1, 0\right\\}^n$ satisfy $x \cdot s = 0$, where $x \cdot s$ denotes the scalar product$\sum\_{i=1}^{n} x\_is\_i$.

# Answer
If $AB=C$, then $A(Bx)=Cx$ for all vectors $x$. Generate vectors randomly and check. This known as Freivalds' algorithm. Wikipedia has details.
> 4 votes

---
Tags: algorithms, probabilistic-algorithms, matrices, linear-algebra
---


# Question
Title: Extracting non-duplicate cells in a particular matrix with repeated entries
Consider a board of $n$ x $n$ cells, where $n = 2k, k≥2$. Each of the numbers from $S = \left\\{1,...,\frac{n^2}{2}\right\\}$ is written to two cells so that each cell contains exactly one number.

How can I show that $n$ cells $c\_{i, j}$ can be chosen with one cell per row and one cell per column such that no pair of cells contains the same number.

This was an example problem for an exam I'm studying for. I tried it now for several hours but I can't get it right. I think random permutations can help here but I am not sure.

# Answer
Choose a permutation $\pi$ uniformly at random, and let $P = \\{ a\_{i, \pi(i)} \mid i\in \[n\]\\}$. The set $P$ contains exactly one element in each row and each column of given the matrix $A$.

Now consider any pair of entries in $A$ with the same value. If those two entries lie in the same row or the same column, they cannot both be in $P$. If those two entries are in different rows and columns of $A$, then the probability that both entries lie in $P$ is exactly $1/n(n-1)$.

There are $n^2/2$ different values in the matrix. So the expected number of values with both entries in $P$ is at most $n^2/2n(n-1) = n/2(n-1)$. If $n\ge 4$, this expected value is less than $1$, which implies that the probability of choosing *no* matching pairs must be positive.
> 6 votes

# Answer
There are $n!$ ways to choose cells. The number of different possible ways of choosing cells such that we have at least two cells with the same content is at most $n \cdot (n-2)!$. For $n\ge 4$, this number always satisfies $n! \gt n\cdot (n-2)!$, so by the pigeonhole principle there are always some selections with distinct numbers.

---

Why?

> First $n!$ is obvious, all permutations.But $n\cdot(n-2)!$: take one of a items from the first column, assume you want have a duplicate of this item, you can select it in at most $n$ different way (prove why at most). Find another column which has a same item, (if there is a column with this item in different row), fix that column, all other columns having $(n-2)!$ possible permutations, also this two fixed column will have at most $n$ permutation, so total possible ways is $n \cdot (n-2)!$.
> 4 votes

---
Tags: combinatorics, probability-theory
---


title: Is there a typed SKI calculus?

text:
# Question
Title: Is there a typed SKI calculus?
Most of us know the correspondence between combinatory logic and lambda calculus. But I've never seen (maybe I haven't looked deep enough) the equivalent of "typed combinators", corresponding to the simply typed lambda calculus. Does such thing exist? Where could one find information about it?

# Answer
The expressive completeness of the typed combinators compared to the simply typed lambda calculus has been demonstrated. For each untyped combinator, one needs a whole family of typed combinators. For example, one has

* $\mathbf{I}\_{\alpha\to\alpha}$
* $\mathbf{K}\_{\alpha\to(\beta\to\alpha)}$
* $\mathbf{S}\_{\alpha\to(\beta\to\gamma)\to(\alpha\to\beta\to(\alpha\to\gamma))}$

for all combinations of simple types $\alpha,\beta$ and $\gamma$.

Alternatively, just think of the types as type schemes (or polymorphic types) and enter them into Haskell and voila: combinators.
> 18 votes

---
Tags: reference-request, logic, lambda-calculus, type-theory, combinatory-logic
---


# Question
Title: Are universal types a sub-type, or special case, of existential types?
I would like to know whether a universally-quantified type $T\_a$: $$T\_a = \forall X: \left\\{ a\in X,f:X→\\{T, F\\} \right\\}$$ is a sub-type, or special case, of an existentially-quantified type $T\_e$ with the same signature: $$T\_e = \exists X: \left\\{ a\in X,f:X→\\{T, F\\} \right\\}$$

I'd say "yes": If something is true "for all X" ($\forall X$), then it must also be true "for some X" ($\exists X$). That is, a statement with '$\forall$' is simply a more restricted version of the same statement with '$\exists$': $$∀X, P(X) \overset?\implies ∃X, P(X).$$

Am I wrong somewhere?

> **Background: Why am I asking this?**
>
> I am studying existential types in order to understand why and how "Abstract \[Data\] Types Have Existential Type". I cannot get a good grasp of this concept from theory alone; I need concrete examples, too.
>
> Unfortunately, good code examples are hard to find because most programming languages have only limited support for existential types. (For instance, Haskell's `forall`, or Java's `?` wildcards.) On the other hand, universally-quantified types are supported by many recent languages via "generics".
>
> What's worse, *generics seems to easily get mixed up with existential types*, too, making it even harder to tell apart existential from universal types. *I'm curious why this mix-up occurs so easily.* An answer to this question might explain it: If universal types are indeed only a special case of existential types, then it's no wonder that generic types, e.g. Java's `List<T>`, can be interpreted either way.

# Answer
> 12 votes
First, from a mathematical point of view, $\forall x:T, P(x)$ does not imply $\exists x:T,P(x)$. The implication holds if and only if $T$ is not empty. However, in programming languages, it is uncommon to deal with empty types (though it happens).

Still from a mathematical point of view, even when $(\forall x:T, P(x)) ⇒ (\exists x:T, P(x))$, the two are not the same. If you give types a set semantics, then $T\_a$ is a superset of $T\_e$, not the same type. (Actually it's not a superset; it's close to isomorphic to a superset.)

Let's get closer to programming language theory and see what these types actually mean. $T\_a = ∀X.\\{a: X, f: X\rightarrow\mathsf{bool}\\}$ is a universal type: if you have a value $A$ of that type, you can construct $A(M)$ for any $M:X$. In particular, if you have $M\_1$ and $M\_2$ both of type $X$, you can construct $A(M\_1)$ and $A(M\_2)$. In essence (and possibly in effect, depending on the language) $T\_a$ is a function from types to terms. As such, the universal type provides type **parametrization**: one value working for all types. Universal types are at the heart of polymorphism.

The existential type $T\_e = \exists X.\\{a: X, f: X\rightarrow\mathsf{bool}\\}$ is quite a different beast. Given a value $B$ of type $T\_e$, there is only one term $N: X$ such that $\pi\_1(B) = N$, and for this term $\pi\_2(B) = \\{a:N, f:N\rightarrow\mathsf{bool}\\}$. The existential type provides a way to hide the nature of $N$; it's saying, “There exists a type! But I won't tell you which!”. As such, the existential type provides type **abstraction**: one specific hidden value. Existential types are at the heart of module systems.

Don't get mislead by Haskell's `forall`: despite its name, it's a form of existential quantifier.

For background, I strongly recommend *Types and Programming Languages* (chapters 23 and 24 discuss universal types and existential types respectively). It's will provide useful background to understand research articles.

# Answer
> 5 votes
Your intuition that $\forall X.\\, P(X)$ should be embeddable in $\exists X.\\, P(X)$ is generally right. It only fails if the entire collection of types is empty, which is rarely the case.

However, the specific example you gave $\forall X.\\, (X \times (X \to Bool))$ is not a good one. A value of this type should be able to produce an element of every type $X$ (for the first component of the pair). If you are thinking of types as sets, such a thing is not possible. So, this type is empty. It would be included in every type, in particular the existential type $\exists X.\\, (X \times (X \to Bool))$, but that is not very interesting. In any case, as a theoretical exercise, here is a term that constructs such a thing:

```
 f (p: \forall X. (X * (X -> Bool))) = PACK X = Bool WITH p[Bool]

```

The article you mention for existential types is a bit theoretical. A more tutorial article is Cardelli and Wegner's paper: On understanding types, data abstraction, and polymorphism. Most advanced text books on programming languages would also have some discussion of existential types. A good book to look up would be Mitchell's Foundations of Programming Languages.

You are right that most programming languages do not have existential types explicitly. However, many do have abstract types (or by some other name such as "packages" or "modules"). So, they are able to *express* values of existential types, even though they don't treat such values as first-class entities.

More importantly, $\exists X.\\, P(X)$ is equivalent to $\forall Y.\\, (\forall X.\\, P(X) \rightarrow Y) \to Y$. So, any language that treats polymorphic functions (of $\forall$ types) as first-class entities also has the ability to treat abstract types as first-class entities.

---
Tags: logic, type-theory, typing
---


# Question
Title: How many strings are close to a given set of strings?
This question has been prompted by Efficient data structures for building a fast spell checker.

Given two strings $u,v$, we say they are *$k$-close* if their Damerau–Levenshtein distance¹ is small, i.e. $\operatorname{LD}(u,v) \geq k$ for a fixed $k \in \mathbb{N}$. Informally, $\operatorname{LD}(u,v)$ is the minimum number of deletion, insertion, substitution and (neighbour) swap operations needed to transform $u$ into $v$. It can be computed in $\Theta(|u|\cdot|v|)$ by dynamic programming. Note that $\operatorname{LD}$ is a metric, that is in particular symmetric.

The question of interest is:

> Given a set $S$ of $n$ strings over $\Sigma$ with lengths at most $m$, what is the cardinality of
>
> $\qquad \displaystyle S\_k := \\{ w \in \Sigma^\* \mid \exists v \in S.\ \operatorname{LD}(v,w) \leq k \\}$?

As even two strings of the same length have different numbers of $k$-close strings² a general formula/approach may be hard (impossible?) to find. Therefore, we might have to compute the number explicitly for every given $S$, leading us to the main question:

> What is the (time) complexity of finding the cardinality of the set $\\{w\\}\_k$ for (arbitrary) $w \in \Sigma^\*$?

Note that the desired quantity is exponential in $|w|$, so explicit enumeration is not desirable. An efficient algorithm would be great.

If it helps, it can be assumed that we have indeed a (large) set $S$ of strings, that is we solve the first highlighted question.

---

1. Possible variants include using the Levenshtein distance instead.
2. Consider $aa$ and $ab$. The sets of $1$-close strings over $\\{a,b\\}$ are $\\{ a, aa,ab,ba,aaa,baa,aba,aab \\}$ (8 words) and $\\{a,b,aa,bb,ab,ba,aab,bab,abb,aba\\}$ (10 words), respectively .

# Answer
See Levenshtein's paper. It contains bounds on the number strings obtained from insertion and deletion of a string. If $n$ is the length of the string and the string is binary, then the maximum number of nearest neighbors in the Levenshtein distance is $\Theta(n^2)$. It is comparatively harder to say anything about $k$-nearest neighbours, but one can get bounds. These should give you an estimate on the complexity.
> 1 votes

# Answer
If your $k$ is fixed and you are allowed to do pre-processing, then this is something you might be able to try

1. Construct a graph such that the nodes are words and an edge exists between two nodes if the distance between those two words is 1.
2. Get the adjacency matrix corresponding to that graph (say $M$)
3. Compute $M^k$

Now, you may be able to use the final matrix to answer all the queries. If you can store $M, M^2, M^4, M^8 \ldots$ etc. You might be able to answer for larger range of $k$ instead of fixed $k$, of course one will pay here with the cost of matrix multiplication.
> 0 votes

---
Tags: algorithms, time-complexity, strings, word-combinatorics, string-metrics
---


title: Key secrecy vs Algorithm secrecy

text:
# Question
Title: Key secrecy vs Algorithm secrecy
it's a well known statement that

"*Cryptographic security must rely on a secret key instead of a secret algorithm*."

I would like to ask about some details about it. *And which are their differences?*

I see the obvious thing that for a multi user system, generating a key is overwhelmingly easier than generating a distinct alghorithm for every user pair, (and even for a single pair of users one could argue that updating the key is easier)

But, Is it the only argument?

I mean, if we define

```
AlgorithmA = AlgorithmX + key A
AlgorithmB = AlgorithmX + key B

```

Then a change on the key is not different from a change in the algorithm.

The only different I see is that for a new pair of users/keys

* *Most of* the Algorithm structure **remains constant** in the case of secret key,
* *Most of* Algorithm structure **need to change** in the case of secret Algorithm

But where is the limit? "most of" meaning?

I would like to have more views and clues to understand why this distinction is usually mentioned.

# Answer
> 4 votes
### Problem Definition

The goal of cryptography is to approximate a process whereby

```
crypt(x)

```

conveys no information about x but there exists a function `decrypt` such that

```
decrypt(crypt(x)) == x

```

If decrypt and crypt were only done in the same run of the same program, you could implement this perfectly using hidden state:

```
var map = {};  // A hidden hashmap.

function crypt(x) {
  var k = unique_unforgeable_value();
  map[k] = x;
  return k;
}

function decrypt(k) { return map[k]; }

```

In practice though, `crypt` and `decrypt` are called by different programs or different runs of the same program, so we need to approximate `crypt` using a deterministic function whose output is indistinguishable from random bits -- it has to be *incompressible* (in the Shannon coding sense) so there are no extra structure bits that can be used to glean information about x.

Algorithms are highly structured therefore compressible. So what we need is a way to get apparent randomness while retaining the determinism that is required for $decrypt \circ crypt = identity$.

### Answer

By currying a simple compressible algorithm with an incompressible secret

```
crypt = crypt_algo(secret)
decrypt = decrypt_algo(secret)

```

we can approximate the goal above. `crypt` and `decrypt` have high information content due to the high information content of secret even though `crypt_algo` and `decrypt_algo` have low information content.

`secret` needs to be kept from attackers for this to work since otherwise an attacker could simply do the currying above. The algorithm does not need to be kept secret since it only provides a small portion of the information content of the curried function.

### Caveat

> "Cryptographic security must rely on a secret key instead of a secret algorithm."

I disagree with the *instead of* part.

You might get some measure of defense-in-depth by keeping both secret, but testing `crypt_algo` is hard, so historically, secret algorithms developed in-house by amateurs have fared worse when subjected to attack than those which have been carefully reviewed by large numbers of professional cryptographers. This is why *security by obscurity* has gotten a deservedly bad name. The "obscurity" there refers to attempts to keep the algorithm secret as a substitute for properly protecting keys.

# Answer
> 5 votes
The distinction you want to make between the key and the algorithm proper is not based on whether most of the operation is contained in one or the other, but on where the complexity lies. I am not talking about algorithmic complexity here, but complexity in its everyday meaning: difficulty to understand and reason about.

The algorithm proper is complex and hard to reason about. It generally does a whole bunch of arbitrary-seeming bit manipulations, logical and arithmetic operations, and general shuffling of the data. It's very hard for a layperson or even for a cryptographer to know how much privacy all those manipulations actually buy you, and what kind of cryptanalysis it might be vulnerable to. So the best way to be confident about the algorithm's security is to put it out in the open and have it reviewed by experts as widely as possible. MAKE IT PUBLIC.

The key, on the other hand, is a simple concept: it's a bunch of bits which need to be random. There is no need to review the key to assure the correctness of the crypto. Any key is supposed to be as strong as any other key (and if this is not true then it can in principle be discovered by review of the algorithm, not the key). We know that the quality of randomness that is available to generate keys is less than perfect, so in practice some keys may be weak due to lack of randomness, but at least everyone can know without needing to be an expert cryptographer and without needing to make a difficult analysis of the key that good randomness WILL lead to a good key. So use the best randomness you've got available then you need not (MUST not!) share the key with everyone in order to have confidence in your crypto.

# Answer
> 2 votes
I asked the same question a few years ago from one of the well-known experts in cryptography.

The more interesting point here is that you can think of the key to contain the algorithm's code and the algorithm being a simple Universal Turing Machine (UTM). Remember that we want to do is having a fixed algorithm for the cryptographic task that doesn't change from one run of the algorithm to another run, if you consider the key to be part of the algorithm then the algorithm needs to change each time to make sure it is secure. With a fixed algorithm plus a randomly chosen key we don't have that problem.

The original difference is more clear if you think about the pre-modern cryptography. If the adversary knew the algorithm everything was lost, it would be of no use, keeping algorithm was essential. If in one particular case the algorithm was known everything would be lost for all future uses. In modern cryptography, *the key is **not** part of the algorithm*, it is chosen *randomly*, revealing the cryptographic algorithm (and even the previously used keys) doesn't compromise the security of its future uses since in the future runs the key will *just another randomly chosen string* and that would grantee the security, the previously used keys are of no help in breaking the new run.

So what happens if we consider UTM plus a random key? Unless the key has a *nice* structure you cannot prove that the algorithm will be secure, e.g. a key chosen randomly from the uniform distribution will not work. The key would need to be "essentially" a fixed algorithm plus a random string in which case it is not really different from moving the fixed algorithm part of the key into UTM, it is not changing from one run to another.

---
Tags: cryptography, security, encryption
---


title: From FACTOR To KNAPSACK

text:
# Question
Title: From FACTOR To KNAPSACK
1. If there were an algorithm that factored in polynomial time by means of examining each possible factor of a complex number efficiently, could one not also use this algorithm to solve unbounded knapsack problems since two factors can be viewed as one value, say within the set for the knapsack problem, and the other being the number of copies of the first factor?

FACTOR 15; 3, 5

Unbounded KNAPSACK with value of 15 and the set of all integers; {5,5,5} andor {3,3,3,3,3}
2. Would this mean FACTOR was NP-Complete?
3. Would solving unbounded knapsack problems in polynomial time in this way prove P=NP?

# Answer
(1) NP-complete only contains problems that can be answered by Yes or No, which are called decision problems. So FACTOR is not an NP-complete problem even your reduction is correct. In fact, if your reduction were correct, it proves that FACTOR is NP-hard.

(2) If you want to prove the NP-hardness of FACTOR by reducing UKP (unbounded knapsack problem) to it, you should find an integer $M$ (in polynomial time) for each instance $I$ of UKP and show that the answer of $I$ can be gotten (in polynomial time) using the factorization of $M$.

In your proof, you can only solve a specific subset of UKP instances by FACTOR, so it is not a correct reduction.
> 5 votes

# Answer
> If there were an algorithm that factored in polynomial time by means of examining each possible factor of a complex number efficiently

Starting from a self-contradicting statement like this, you can prove anything. Why is it self-contradicting?

Let $n$ be a natural number. The number of possible factors of $n$ is $\sqrt{n}$; there may be number theory that pushes this down more, but there is no such result that eliminates all but $\Theta(\log^k n)$ numbers¹. So, you have to consider $\Omega(n^\varepsilon)$ numbers for some $\varepsilon \> 0$. Note that the length of $n$ -- which is the input size! -- is $\lceil \log n \rceil$. Therefore, your assumed algorithm examines super-polynomially² many numbers in polynomial time³ -- impossible.

---

1. If there were such a result (and you could list those candidates in polynomial time), factoring would be possible in polynomial time, which would be well-known. As far as I know, the problem is still open.
2. $n^\varepsilon = 2^{\varepsilon\log n}$
3. Assuming you mean "in polynomial time" when you say "efficiently".
> 2 votes

---
Tags: complexity-theory, np-complete, integers, knapsack-problems
---


# Question
Title: An argument for error accumulation during complex DFT
I am doing FFT-based multiplication of polynomials with integer coefficients (long integers, in fact). The coefficients have a maximum value of $BASE-1, \quad BASE \in \mathbb{n},\quad BASE \> 1$.

I would like to put forward a formal argument that if we use complex DFT for computing a convolution on a physical machine, it will yield incorrect results at some transform length $n\in \mathbb{N}$.

What was easy to prove was the fact that at some big $n$ computing the convolution with DFT will not at all be possible, since, for example, the following difference of primitive roots modulo $n$: $\omega\_n^1 - \omega\_n^2 \rightarrow 0$ when $n \rightarrow \infty$, and if we are restricted by some machine epsilon $\epsilon$, at some $n$ it will make the values indistinguishable and interpolation impossible.

But the boundary I've received using such an argument was way too big: only for $n=2^{60}$ I've received $\omega\_n^1 - \omega\_n^2$ that had both components, $Re$ and $Im$, less than representable by $double$-precision type. This certainly is a boundary, but not very practical one.

What I would like to show (if it is possible), is that much earlier than interpolation becomes theoretically impossible, the round-off errors will start to give wrong coefficients in the convolution, so that

$$a\cdot b \neq IDFT(DFT(a)\times DFT(b)),$$

where $DFT$ and $IDFT$ are algorithm implementations that I use to calculate the Fourier transform.

Maybe it is possible to make use of the fact that the value of the primitive root modulo $n$, $\omega\_n = \exp(-2\pi i / n)$, is an irrational number for the majority of $n$'s. It will thereby be computed with inevitable error $\psi$, defined as the value needed to "round off" everything that's less than the machine epsilon $\epsilon$. Thus all the values used for DFT,

$$\omega\_n^0, \omega\_n^1, ..., \omega\_n^{n-1},$$

except for $\omega\_n^0$ will also be computed with errors.

Since I'm not a good mathematician at all, I don't know if and how I could use this fact to prove that the situation is going to worsen with increasing $n$ and that eventually the convolution is going to be computed incorrectly.

I would also like to have and argument for OR against the following claim: for fixed $n$, the maximal error will be produced when all the coefficients of both polynomials are $BASE-1$.

Thank you very much in advance!

# Answer
> 2 votes
Since the fourier coefficients might in general be complex numbers $xi + y$ with $x$ or $y$ or both irrational, a standard finite precision computer of course will not output the exact fourier coefficients. However, if you want to claim that you cannot get a good approximation, you are wrong.

Look at this answer. Markus shows that if you want to compute DFT of a vector of length $n$ up to $b$ bits of precision, then you need floating point numbers with $m$ bits where $m = \log n + \log \log n + b + C$ for $C$ some fixed constant. This is a fairly good bound. Also, there is no reason why the double type of the C language should be any hard limitation if you care about precision: there are libraries for high-precision arithmethic, and it's not even all that hard to code your own procedures to multiply and add floating point numbers of fixed high (higher than that of double) precision. Markus's answer shows that you won't lose much in running time: the running time will be roughly $n \log n (b/\log n)$ (for $b \> \log n$) arithmetic operations on standard C types.

---
Tags: algorithms, proof-techniques, numerical-analysis
---


# Question
Title: What is complexity class $\oplus P^{\oplus P}$
What does the complexity class $\oplus P^{\oplus P}$ mean? I know that $\oplus P$ is the complexity class which contains languages $A$ for which there is a polynomial time nondeterministic Turing machine $M$ such that $x \in A$ iff the number of accepting states of the machine $M$ on the input $x$ is odd.

But what does $\oplus P^{\oplus P}$ mean? I just can't follow what it actually does :)

What are practical consequences of such complexity class and how it is possible to show that $\oplus P^{\oplus P} = \oplus P$?

# Answer
> 11 votes
$\oplus P^{\oplus P}$ denotes the class $\oplus P$ equipped with what's known as an *oracle* for $\oplus P$ — we say that it has been given the ability to determine whether or not a string $s$ is a member of a language $L$ contained in the class $\oplus P$ in a single operation.

I see that another commenter (sdcwc) has linked to the proof of $\oplus P^{\oplus P} = \oplus P$ (see these notes on a lecture from CS 538 at Rutgers). A complexity class $C$ that is an oracle to a class $B$ such that $B^C= B$, is said to be *low* for the class $B$. In this case, we say that $\oplus P$ is low for itself.

---
Tags: complexity-theory, terminology, complexity-classes
---


# Question
Title: array median transformation using the min number of steps
Let $A\[1...N\]$ be an Array of size $N$ with maximum element $\max$.

I want to transform array $A$ such that after transformations all elements of $A$ contain $\max$, i.e. after transformation $A = \[\max,\max,\max,\max,\dots,\max\]$.

In one step, I can apply the following operation to any consecutive sub-array $A\[x..y\]$:

> Assign to all $A\[i\]$ with $x \leq i \leq y$ the median of subarray $A\[x..y\]$.

We consider as *median* always the $\left\lceil \frac{n+1}{2} \right\rceil$-th element in an increasingly sorted version of $A$.

What is the minimum number of steps needed to transform $A$ as desired? If it helps, assume that $N\leq 30$.

---

**Example 1:**

Let $A = \[1, 2, 3\]$. We need to change it to $\[3, 3, 3\]$. The minium number of steps is two, first for subarray $A\[2..3\]$ (after that $A$ equals to $\[1, 3, 3\]$), then operation to $A\[1..3\]$.

**Example 2:**

$A=\[2,1,1,2\]$.The min step is two. The median of subarray $A\[1..4\]$ is $2$ (3rd element in $\[1,1,2,2\]$. Apply the operation to $A\[1..4\]$ once and we get $\[2,2,2,2\]$.

# Answer
> 4 votes
In the comments, Wu Yin claimed an upper bound of $\lceil \log\_2 n \rceil$, although I think this is only true if the position of the maximum is known. In fact, consider the following argument. Assume $A$ is filled with $N-1$ ones and one maximal element $\max$. Any first step on a subarray $A\[x,y\]$ of more than 2 elements will necessarily set the subarray to all $1$'s. In particular, if we don't know the position of $\max$, we can only apply a step to subarrays of length 2, or otherwise we run the risk of "destroying" our maximum element. Hence, without knowing the position of our maximimal element, we can only probe the array by consecutively applying the operation to $A\[i,i+1\]$ for all $i$. This will necessarily create a subarray of length 2 that is filled with $\max$. Recurring leads to a linear time algorithm, which I think is optimal.

**Algorithm:**

Let $step(x,y)$ denote an operation on the subarray $A\[x,y\]$ as is defined in the question.

* Perform $step(i,i+1)$ for all $0\leq i \< N$. After that, there is some 2-length subarray containing only $\max$.
* Perform $step(i,i+3)$ for all $0\leq i \< N-3$. After that, there is some 4-length subarray filled with $\max$.
* Generally, we double in each such iteration the array size in each step. After that, the original array $A$ contains only $\max$.

**Running Time:**

In the first iteration, we perform $N/2$ steps, in the subsequent one, $N/4$, then $N/8$, etc. The sum over all this is smaller than $N$. I think this is optimal, since without looking at all elements (or at least $N/2$ elements), we don't know where $\max$ is, and can not use any step on any subarray larger than $2$.

---
Tags: algorithms, arrays
---


title: A context free grammar proof

text:
# Question
Title: A context free grammar proof
There is a problem which I cannot solve. If you give a tip I will be very glad.

Prove that following language is *not* context free:

$L= \\{ a^nb^m | \gcd(n,m) = 1 \\}$.

It can be proven using the pumping lemma, but how?

If I start with some prime numbers $m$ and $n$ where $m\>n\>2$ and pump it up from $uVxYz$, there are three possible outcomes: $a^{n + k} b^m$, $a^{n +k}b^{m +k}$, $a^n b^{m +k}$. Since I do not know whether $k$ is even or odd I cannot say something. It is certain that $a^n$ and $b^m$ will be odd. However after adding $k$ to some of them, how can I say something about whether their gcd is 1 or not?

# Answer
> 2 votes
Hint...

There may be a direct application of the pumping lemma, but I suggest you take a look at closure properties. Consider the non-CFL in the first answer to the reference post, $P=\\{a^p:p \text{ prime}\\}$, which is clearly a cousin of $L$. Can you find a (fairly simple) operation on $L$ that preserves CFLs and more or less yields $P$? If so, you are done, except perhaps to tidy up with some other operations to deal with special cases for $P$.

In general, when languages are relatively "dense", that is, have a high proportion of members to non-members for all given lengths, it's harder to apply pumping arguments, because it's more work to pump to get outside the "dense" set; in fact, sometimes it's impossible. $P$ is a nice "sparse" set, so pumping works well, as shown in the reference post. $L$ is quite a bit "denser", so transforming it to a "sparser" form is a good tactic to try.

The classical example of this principle (for non-regular languages) is the very dense set $\\{a^ib^j:i \neq j\\}$ and the corresponding sparse set is $\\{a^ib^i\\}$. The operation in this case is complement, again with a "cleanup" operation needed as well. As part of the above hint, the operation there is *not* complement, which doesn't work for CFLs anyway.

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


# Question
Title: Counting different words in text using hashing
I am still fighting with hashing and I am ask myself: what is the most efficient way to count the number of different words in a text using a hash table?

My intuition says that applying the hashcode function to every word in the text, as result we will have words with different hash values in different buckets and the same words will have the same bucket and therefore we will have a collision problem which we can resolve using the chaining method.

Does it work like that?

# Answer
If you really just want to count the number of distinct words in the document, you don't need to save each instance of the word to the hash table.

So, if you find a words that's already in the table, just don't add it there. This means you don't have to deal with chaining as often, which will speed things up.

But you still have to deal with collisions, because two different words can have the same hash code.

This way, the expected time complexity is $\mathcal{O}(n)$, where $n$ is the total count of characters in the text, assuming a good hash function.
> 6 votes

# Answer
Hash table is very good if you have few words that are repeated many times.

Let's suppose that your hash function is very good, that means that the distribution of elements inside various buckets is close to the uniform distribution. Even in that case, if the number of buckets is much smaller than the number of elements inside the table, the execution time of search in hash tables with buckets implemented as linked lists is $O(n)$, where $n$ is the number of different words that you have found.

This happends because in the simplest implementstions each bucket is a simple list and if inside a bucket you will have $k$ elements, the cost of the search would be the sum of the cost to calculate hash function plus the cost to find the right bucket plus the cost to find the right element inside the list. The first two costs are $O(1)$ the last one is $O(k)$ because you are performing linear search.

If you have few elements and lots of buckets, $O(k)$ will be close to $O(1)$, otherwise it will be close to $O(n)$ as stated above.

If the number of words is much bigger than the number of buckets, the best choices are:

* implementing buckets as binary trees or as other hash tables (with other hash functions);
* using a Self-balancing binary search tree, it would have $O(\log n)$ time to insert and $O(\log n)$ time to search.

For more discussion about hash table performance, see: Hash table vs Balanced binary tree

---

From wikipedia:

> For the best possible choice of hash function, a table of size n with open addressing has no collisions and holds up to $n$ elements, with a single comparison for successful lookup, and a table of size $n$ with chaining and $k$ keys has the minimum $\max(0, k-n)$ collisions and $O(1 + k/n)$ comparisons for lookup.
>
> \[...\]
>
> In more realistic models, the hash function is a random variable over a probability distribution of hash functions, and performance is computed on average over the choice of hash function. When this distribution is uniform, the assumption is called "simple uniform hashing" and it can be shown that hashing with chaining requires $Θ(1 + k/n)$ comparisons on average for an unsuccessful lookup, and hashing with open addressing requires $Θ(1/(1 - k/n))$.
> 3 votes

# Answer
This method seems to work and, if implemented efficiently, it must be O(n), because each word is processed once. As each word *must* be processed at least once, the problem is Ω(n). So, such a solution is also efficient.
> 0 votes

---
Tags: algorithms, strings, hash-tables
---


title: NP $\subsetneq$ EXP?

text:
# Question
Title: NP $\subsetneq$ EXP?
I think I heard in somewhere that it has been proven that $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$, that is $\mathsf{NP} \subsetneq \mathsf{EXP}$. Is this right? Wikipedia and book resources do not seem to bring me an answer..

I just found a post similar to this, but I am not sure whether $\mathsf{NP}$ is *strictly* contained in $\mathsf{EXP}$.

# Answer
> 5 votes
*Strictly contained* means $\subsetneq$, i.e. it is the definition, it is not a result. So what you are saying is $$\mathsf{NP} \subsetneq \mathsf{ExpTime} \implies \mathsf{NP} \subsetneq \mathsf{ExpTime}$$ which is trivially true.

If you are asking if $\mathsf{NP}\subsetneq \mathsf{ExpTime} $ then the answer is: *it is unknown*.

You may want to check the Wikipedia article about Exponential Time *Hypothesis* which many experts *believe* is true.

---
Tags: complexity-theory, complexity-classes, np
---


# Question
Title: How to prove that a constrained version of 3SAT in which no literal can occur more than once, is solvable in polynomial time?
I'm trying to work out an assignment (taken from the book Algorithms - by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Chap 8, problem 8.6a), and I'm paraphrasing what it states:

> Given that 3SAT remains NP-complete even when restricted to formulas in which each literal appears at most twice, show that if each literal appears at most once, then the problem is solvable in polynomial time.

I attempted to solve this by separating the clauses into multiple groups:

1. Clauses which did not have any variable in common with the rest of the clauses
2. Clauses which had only 1 variable in common
3. Clauses which had 2 variables in common
4. Clauses which had all 3 variables in common

My reasoning was attempted along the lines that the # of such groups is finite (due to the imposed restriction of no literal being present more than once), and we could try to satisfy the most restricted group first (group 4) and then substitute the result in the lesser restricted groups (3, 2 and then 1), but I realized that this wasn't quite getting me anywhere, as this doesn't differ much from the case for the constrained version of 3SAT in which each literal can appear at most twice, which has been proven to be NP-complete.

I tried searching online for any hints/solutions, but all I could get was this link, in which the stated hint didn't make sufficient sense to me, which I'm reproducing verbatim here:

> Hint: Since each literal appears at most once, convert this problem to 2SAT problem - hence polynomial time, if a literal $x\_i$ appears in clause $C\_j$ and complement of $x\_i$ (i.e., $\overline{x\_i}$) in clause $C\_k$, construct a new clause clause $C\_j \lor \overline{C\_k}$.

Both $C\_j$ and $C\_k$ have three literals each - I didn't get how I should go about converting it into 2SAT by doing $C\_j \lor \overline{C\_k}$ (or $\overline{C\_j \lor C\_k}$ if I read it incorrectly).

Any help in either decrypting the hint, or providing a path I can explore would be really appreciated.

# Answer
Without loss of generality, we can assume that each variables appears exactly once positively and exactly once negatively (if a variable only appears once set its value to satisfy the clause and remove the clause). We can also assume that a variable does not appear in a clause more than once (if a variable appears both positively and negatively in a clause, then the clause is satisfied and can be removed). These will not alter the satisfiability.

Now use the resolution rule to eliminate the variables one by one (since each variable appears exactly once positively and once negatively this is a deterministic process). If at any point we obtain the empty clause the set of clauses is unsatisfiable, otherwise it is satisfiable. This is because:

* resolution is a complete propositional proof system (i.e. if a clause is logically implied by the set of clauses then it is derivable from the set of clauses using only the resolution rule),
* a set of clauses is unsatisfiable iff it logically implies the empty clause.

This algorithm will take polynomial time since each variable is resolved exactly once. In particular, each application of resolution will reduce the total number of clauses by one, so the number of clauses does not increase. For example, applying resolution to $(x \lor B) \land (\overline{x} \lor C) \land \dots)$ yields $(B \lor C) \land \dots$, which has one fewer clause than before resolution. In contrast, if you applied this to a 3SAT formula with no restriction on the number of appearances of each literal, applying resolution could cause the number of clauses to increase exponentially.
> 14 votes

---
Tags: complexity-theory, satisfiability, 3-sat
---


title: Is a PDA as powerful as a CPU?

text:
# Question
Title: Is a PDA as powerful as a CPU?
This is a question I have stumbled upon in my exam revision and I find it intriguing:

**My computer is blue and it has a massive graphics card and a DVD and every- thing so which is more powerful: my computer or a Pushdown Automaton?**

---

## My Thoughts

When we talk about power I have assumed this to be computational power. I believe that a PDA has the computational power to equal the computational power of a CPU (cpu in this case is the core elements of a computer ie memory and processor). This is because a PDA utilises a stack which is memory(RAM) in a computer. The PDA has states as does a CPU and also the PDA calculates simple logic at each state. I realise that the PDA itself would be a complex series of states to emulate the computational power of the cpu and there would have to be a series of PDAs to compute different functions.

My Question: I know that Turing machines are best used to simulate the logic of a CPU but **am I right in saying that a PDA (Or PDA's) can be designed to be as powerful as a cpu?**

# Answer
> 13 votes
If you count a CPU (as you imply in your text) as an unbounded memory and the processor, then no you can't model it as a PDA. A push down automaton (with one stack) can only recognize context-free languages, for example $\\{a^n b^n c^n | n \geq 0\\}$ cannot be recognized by a PDA, but presumably could be recognized by your blue computer with massive graphics card and DVD.

Typically, we think of your blue computer with massive graphics cards and DVD as a Turing Machine, because that often proves to be the best way to model it.

On the other hand, if you model your CPU *without* unbounded memory, then PDA is still not the right model. If your CPU has no memory or only a small (i.e. bounded) amount of on-chip memory, then it can only be in a finite number of states, and is better modeled as a DFA.

# Answer
> 6 votes
This is a big subject, but there are two basic schools of thought on how to model real-life computers (which I assume you mean -- the CPU is only one part of a computer) with mathematical automata, and they lead to two different theoretical areas -- (a) finite-state automata; (b) infinite-state automata with various restrictions. Both Turing Machines and PDA's are examples of the latter, as are resource-bounded models of computation in complexity theory (P, NP and all that).

The argument for finite state automata is that all computers are inherently limited to a finite number of states, however large (and it is *large*, like $10^{12}$+, even without the disk, which takes it up to $10^{25}$ or so) because the world is a finite place, at least the corner of it that computers live in. The infinite-state perspective says that's true, but the number of states of an actual computer is so large that modelling it with infinite state mathematics leads to more useful insights on their structure and limitations. Both make some sense, but the infinite-state position is by far the predominant one today, especially with complexity theory. There is some research activity on finite-state models still going on, but the majority of it is concerned with the complexity of smaller circuits and devices rather than entire computers.

As for whether a PDA is a good model for a real computer, that's clearly a question in the latter category -- PDA's have infinite states structured and limited in a specific way. But that way -- a single, simple stack -- is pretty much unheard of in the world of real computers. There have been and still are real computers with built-in stacks, but many of them and they usually have features that exceed those of a simple PDA . Nevertheless, the theory of pushdown stacks has been useful in understanding such computers. Also, mathematical models of target machines for high-level languages invariably use stacks, and again the theory of how stacks work is very useful there for analyzing such models.

So, the answer to your question -- in brief -- is mostly no, the PDA is not generally a good mathematical model of real computers, but it has some relevance. But neither is a Turing Machine, since real computers don't use anything resembling the tape of a TM. On the other hand, both PDAs and TMs lead to useful mathematical models of different aspects of computation in general with many important theoretical and practical consequences.

# Answer
> 2 votes
You are right if your CPU has bounded memory. A CPU can do basically exactly what a turing machine can do. But: The reality it is build in gives the CPU limitations, such as the amount of memory it can access. If we assume the CPU has only finite memory available, it resembles to a TM with constant space, making your CPU as powerful as a DFA - which can be easily simulated by a PDA.

Note: The PDA to simulate your CPU and GPU that has access to Trillions of Bits of memory would be quite huge, to say the least.

---
Tags: computability, computation-models, computable-analysis
---


# Question
Title: Rule of thumb to know if a problem could be NP-complete
This question was inspired by a comment on StackOverflow.

Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like an NP-complete one?

I am not looking for something rigorous, but to something that works in most cases.

Of course, every time we have to prove that a problem is NP-complete, or a slight variant of an NP-complete one; but before rushing to the proof it would be great to have certain confidence in the positive result of the proof.

# Answer
> 19 votes
This is my personal approach to determine whether a problem (i.e. a language $L$) is NP-complete or not. If both these conditions are verified:

* I feel that testing if an instance $I$ is in $L$ implies that I need to check all combinations of some sort
* **and** that there is no way to split such a combination into two smaller ones

then $L$ may very well be NP-hard.

For example for the subset sum problem, I have to list all subsets of $S$ and check if there is one whose sum is zero. Can I split $S$ into two smaller subsets $S\_1$ and $S\_2$ on which I will check a similar property? Humm... not really. Maybe if I checked for all combination of $S\_1$ and $S\_2$ but that would be really long...

Usually the ability to break into smaller pieces is a good indicator for a problem to be in P. This is the divide and conquer approach. For example to find the shortest path between two points, you can use the property that if the shortest path from $A$ to $C$ go through $B$ then it is not longer than the shortest path from $A$ to $B$ plus the shortest from $B$ to $C$.

Quite frankly this approach is very basic: I try to find a (polynomial) algorithm for the given problem. If I can't find one then the problem becomes "hard" in my point of view. Then comes all the NP-completeness reasoning: will I be able to encode an existing NP-complete problem into this one? (And since this is usually much harder, I try once more to find a polynomial algorithm..)

I suspect that this is the usual way of thinking. However it remains quite hard to apply on unknown problems. I personally remember being surprised by one of the first examples of NP-completeness I was told: the clique problem. It seemed so simple to check! So I suppose that experience has a lot to do with it. Also intuition can be useless sometimes. I remember being told several times two almost identical problems but one was in P and the other one with a small variation was NP-complete.

I am yet to find a good example (I need help here), but this is like the post correspondence problem: this is an undecidable problem but some variants are decidable.

# Answer
> 15 votes
Another perspective on problem-hardness comes from the game and puzzle community, where the rule of thumb is that 'problems are as hard as they possibly can be' (and the exceptions come from hidden structures in the problem - Massimo's example of the determinant in comments is a good instance of this); the trick then comes in understanding how hard a problem can be:

* Puzzles involving the existence of a static configuration are in NP, and so they tend to be NP-complete; for instance, the polyomino packing problem (can a given set of $n$ polyominos pack a given rectangle of the appropriate area?) is NP-complete.
* Puzzles involving a sequence of moves within a bounded state space are in PSPACE (since the 'move tree' can generally be explored in standard depth-first manner needing only storage for a polynomial number of configurations), and tend to be PSPACE-complete; a classic example of this is Rush Hour.
* Games with a polynomially bounded depth are also in PSPACE; this uses the characterization of PSPACE as APTIME, since the usual min-max characterization of strategies perfectly mimics an alternating Turing machine with its characterization as 'there exists a move for player A such that for each reply move from player B, there exists a reply move for player A such that...', etc. They also tend to be PSPACE-complete; Hex and generalized Tic-Tac-Toe games are both examples of this.
* Games without a bound on tree depth but played in a (polynomially) bounded space are in EXPTIME, since there are exponentially many total positions and the entire graph can be built and explored in time polynomial in the number of positions (and thus exponential overall); these games are generally EXPTIME-complete. Chess, Checkers, and Go all fall into this category.

---
Tags: complexity-theory, np-complete, intuition
---


# Question
Title: Hoare triple for assignment P{x/E} x:=E {P}
I am trying to understand Hoare logic presented at Wikipedia, Hoare logic at Wikipedia Apparently, if I understand correctly, a Hoare triple $$\\{P\\}~ C ~\\{Q\\}$$ means

> if P just before C, then Q holds immediately after C, as long as C terminates. (A)

However, the assignment axiom schema seems to be interpreted in a different way:

$$\frac{}{\\{P\[x/E\]\\} ~~x:=E~~ \\{P\\}}$$

The wikipedia says:

The assignment axiom means that the truth of $\\{P\[x/E\]\\}$ is equivalent to the after-assignment truth of $\\{P\\}$. Thus were $\\{P\[x/E\]\\}$ true prior to the assignment, by the assignment axiom, then $\\{P\\}$ would be true subsequent to which. Conversely, were $\\{P\[x/E\]\\}$ false prior to the assignment statement, $\\{P\\}$ must then be false consequently.

I think the Hoare triple only affirms that if P\[x/E\] before x:=E, then P(x) holds after x:=E. It DOES NOT affirm, by its definition, that if P(x) holds after x:=E, then P\[x/E\] holds before x:=E.

My naive question is, how can $\\{P\[x/E\]\\}$ before the assignment can be equivalent to $\\{P\\}$ after the assignment? Does this contradict with point (A) at the beginning of my post?

# Answer
> 6 votes
Notice that what Wikipedia is saying is that

> The assignment axiom means that the truth of $\\{P\[x/E\]\\}$ is equivalent to the **after-assignment truth** of $\\{P\\}$.

In other words, ($P$ holds after the execution of $x:= E$) if ($P\[x/E\]$ holds before the execution). This is equivalent to the definition $A$ you provided, which is generally a more intuitive definition for Hoare triple.

# Answer
> 3 votes
It seems that the wording of the Wikipedia text is flakey to some extent:

> The assignment axiom means that the truth of {P\[x/E\]} is *equivalent* to the after-assignment truth of {P}.

The assignment axiom does not mean that. It only means that the truth of {P\[x/E\]} *implies* the after-assignment truth of {P}. It does not mean the "equivalence".

However, the equivalence is also a valid fact. It is just that the Hoare axiom for assignment doesn't say it.

A good source for a clear and rigorous treatment of Hoare-like proof systems is Apt and Olderog's Verification of Sequential and Concurrent Programs.

# Answer
> 2 votes
It means more something like

> if P was true before C then Q will be true after that.

There are time considerations because usually C will change the environment.

Think of this example: $C=(x := 42)$ and $P=(x \> 10)$. Then the instance of your rule makes sense.

EDIT: time considerations are important. Here, $P$ where "$x=E$" (i.e. after) is equivalent to $P\[x/E\]$ (before). Note that "$x=E$" is just to designate the "after": it is not a real equality since $x$ can appear in $E$.

For example

$$ \\{ 0 +42\>10\\} ~~ x:=0 ~~ \\{ x+42\>10 \\}$$ $$ \\{ x + 42 \> 10\\} ~~ x:=x+42 ~~ \\{ x\>10 \\}$$

can help you prove that

$$ \\{ \mbox{true} \\} ~~ x:=0 ~;~ x := x + 42 ~~ \\{ x\>10 \\}$$

On a side note, I personally found the notation $P\[x/E\]$ very confusing.

---
Tags: logic, programming-languages, semantics, hoare-logic, software-verification
---


title: Counting trees (order matters)

text:
# Question
Title: Counting trees (order matters)
As a follow up to this question (the number of rooted binary trees of size n), how many possible binary trees can you have if the nodes are now labeled, so that abc is different than bac cab etc ? In other words, order matters. Certainly it will be much more than the Catalan number.

What would the problem be if you have n-ary trees instead of binary ?

Are these known problems? reference ?

# Answer
As partially answered above by Syzygy, for labelled binary trees, it is $n!C\_n$, where $C\_n$ being the Catalan number. Generalized this to labelled $k$-ary trees, it is $n!C^k\_n$ where $C^k\_n$ is the Fuzz-Catalan number $ \begin{equation} C^k\_n= \binom{kn}{n}\frac{1}{(k-1)n+1} \end{equation} $
> 1 votes

# Answer
I am not sure, if I understood the question correctly, but are you asking for the number of rooted binary trees of size $n$, with nodes labeled from $1,...,n$, where isomorphic trees with different labelings are counted as different?

If so, isn't your labeling just adding $n!$ different possible labelings for each class of isomorphic trees? I.e. your total number of trees would be $n!C\_n$, where $C\_n$ is the $n$-th Catalan number.
> 6 votes

---
Tags: binary-trees, combinatorics, trees
---


# Question
Title: Reconstructing Graphs from Degree Distribution
Given a degree distribution, how fast can we construct a graph that follows the given degree distribution? A link or algorithm sketch would be good. The algorithm should report a "no" incase no graph can be constructed and any one example if multiple graphs can be constructed.

# Answer
> 9 votes
If you mean how to construct such a simple graph (no self loops and no parallel edges), maybe Havel-Hakimi theorem is what you are looking for. You can google it yourself, and the wikipedia page Degree (graph theory) is also helpful.

# Answer
> 11 votes
If the degree distribution is given as a list of degree, then you can do the following, given $n$ nodes with degrees $d\_1, ... ,d\_n$:

Create a complete graph $K\_n$ on $n$-vertices. For each vertex $v\_i$ in $K\_n$, split it into $d\_i$ copies. Split here means, create a number of copies with edges to every vertex $v\_i$ has an edge to, but no edges to other copies of $v\_i$. If $d\_i = 0$ then simply remove the vertex. In the new graph, call these vertices $v\_{ij}$ for $1 \leq j \leq d\_i$.

Once you are done, you have a very dense graph on $N = d\_1 + ... + d\_n$ vertices; call this graph $H$. Pick your favorite algorithm for maximum matching (since the graph is so dense, you should probably use one of the fast matrix-multiplication based algorithms) and run it on $H$. This will return a matching $M$. If the matching is not perfect (i.e. if it does not cover every vertexes) then your degree distribution was impossible; so return **no**.

If you have a perfect matching $M$, then remove all edges not in $M$ from $H$, and then for every $1 \leq i \leq n$ merge the $d\_i$ many vertices $v\_{i1}, ... , v\_{id\_i}$ into one vertex $u\_i$. Merging two vertices means combining them into one, such that the resulting vertex has edges to every vertex at least one of the original had an edge to. Call the resulting graph $G$; it has the desired degree distribution.

The resulting runtime is $O(N^\omega)$ where $\omega$ is the constant for the fastest matrix-multiplication algorithm (which at the time of writing is about $2.373$). In terms of number of vertices in the resulting graph, in the worst case of degree distribution being dense, we have $O(n^{2\omega})$.

---
Tags: algorithms, graphs
---


# Question
Title: If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I'm am stuck solving the next exercise:

Argue that if $L$ is context-free and $R$ is regular, then $L / R = \\{ w \mid \exists x \in R \\;\text{s.t}\\; wx \in L\\} $ (i.e. the right quotient) is context-free.

I know that there should exist a PDA that accepts $L$ and a DFA that accepts $R$. I'm now trying to combine these automata to a PDA that accepts the right quotient. If I can build that I proved that $L/R$ is context-free. But I'm stuck building this PDA.

This is how far I've made it:

> In the combined PDA the states are a cartesian product of the states of the seperate automata. And the edges are the edges of the DFA but only the ones for which in the future a final state of the original PDA of L can be reached. But don't know how to write it down formally.

# Answer
> 9 votes
Here is a hint.

You need your machine to initially accept part of a word from $L$, consuming the tape as it goes. Then, without consuming anything, you need to find some word from $R$ that will push the machine into a final state. The chosen word from $R$ plays the role of the input word for the second half of the computation.

Clearly, non-determinism will have a role, as will the product between the two machines. The trick in formalising this is adjusting the product to deal with the fact that the input comes from $R$ not from the input.

# Answer
> 8 votes
I am not sure what you are getting at with the cartesian product; this simulates both automata in parallel, which will give you the intersection. But you want it to identify all words in $L$ that have a suffix from $R$! On an intuitive level, that is.

Assume our input is $w \in \Sigma^\*$. Obviously, we can not check all possible continuations (for membership in $R$) but only a finite number of them. Artem's comment is most helpful here; we *guess* what the suffix $x$ is going to be, and run both automata on it.

> Let $A\_L$ and $A\_R$ the PDA for $L$ and NFA for $R$, respectively. Construct an automaton $A$ as follows. On input $w \in \Sigma^\*$, simulate $A\_L$. After $w$ is consumed, switch to a modified intersection $A\_{L,R}$ of $A\_L$ and $A\_R$, keeping the state from $A\_L$. Now, decide for every transition nondeterministically which symbol is next in the virtual input. Accept $w$ if and only if both components of $A\_{L,R}$ reach a final state simultaneously, that is if $w$ has a continuation $x$ so that $wx \in L$ and $x \in R$.

You can also use formal grammars. Do you see how you can derive in two grammars in parallel? In general, it is not clear how to adapt $G\_L$ so you get a handle on suffixes; using the Chomsky normal form helps.

> Assume both $G\_L$ and $G\_R$ are given in Chomsky normal form. Modify $G\_L$ such that the right-most non-terminal is distinguishable and make its start symbol the new start symbol. Introduce for the distinguished versions of the nonterminals new rules that lead to a grammar that derives in $G\_L$ and $G\_R$ in parallel (non-terminals are pairs of non-terminals); if both grammars agree on a terminal symbol, delete the composite non-terminal. That way, a suffix in $G\_L$ is deleted if and only if it can be derived in $G\_L$ and in $G\_R$, it remains $w \in L/R$.

# Answer
> 7 votes
I recommend to use Raphael's answer, which is much easier to understand, but here is an alternative one, using closure properties instead of automata:

> Let $L \subseteq A^{\ast}$ be a language. We want to read a word $w$, but ask $L$ whether $w x$ is in the language. So we want to create a new language from $L$ which has $x$ "erased". We can do it using a homomorphism, but it could remove letters from $w$. Solution: split the alphabet into two and use different letters for $w$ and $x$.

More formally:

> 1) Create $L' \subseteq (A \times \\{0,1\\})^{\ast}$ of words from $L$, with each letter tagged either 0 or 1.
> 2) Intersect it with regular language $(A \times {0})^{\ast} (R \times 1)$. This forces that all 0's come before all 1's, and the second part comes from $R$. The precise meaning of $\times$ is left for the reader.
> 3) Substitute $(a,0) \to a$ and $(a,1) \to \varepsilon$.
> Used closure properties: Homomorphic image, preimage, intersection with regular languages. Advantage: This proof works for other families (for example, replace context-free with regular).

---
Tags: formal-languages, context-free, finite-automata, closure-properties, pushdown-automata
---