title: Notions of efficient computation

text:
# Question
Title: Notions of efficient computation
A polynomial-time Turing machine algorithm is considered efficient if its run-time, in the worst-case, is bounded by a polynomial function in the input size. I'm aware of the strong Church-Turing thesis:

> Any reasonable model of computation can be efficiently simulated on Turing machines

However, I'm not aware of solid theory for analyzing the computational complexity of algorithms of $\lambda$-calculus.

Do we have a notion of computational efficiency for every known model of computation? Are there any models that are only useful for computability questions but useless for computational complexity questions?

# Answer
As far as I know, the main models of computability are λ-calculus, Turing machines and recursive functions. I am not aware of the situation regarding complexity in recursive functions, they may or may not be useless for complexity.

It may be seen as a fortunate coincidence that Turing machines, which are not so arguably very inefficient machines, are also a very good model of complexity. What made things natural is that there are a lot of transformations involving TMs that are polynomial. (Universal machine, simulation of a $n$-taped machine with a 1-taped machine, from an arbitrary alphabet to a binary one, simulating a PRAM, ...) and that polynomials are a class of functions stable by arithmetic operations and composition – which makes them a good candidate for complexity theory.

Pure λ-calculus was in itself useless for complexity. However a simple type system came into play and allowed guarantees of termination for some λ-terms in a very easy way. Then some other systems (systems , , ..) allowed a great expressiveness while keeping termination.

Efficiency or complexity being a refinement of termination and types being closely related to logic, later came light linear logics which characterizes several classes of complexity. (Elementary, P, and some variations for PSPACE and others). The research in this domain is very active and is not restricted to these complexity classes, and is not even restricted to the λ-calculus.

**tl;dr:** λ-calculus was useful for computability, termination and complexity theory.

However to give credit where credit is due Turing machines are a good and unanimous way to define what is complexity, but that's true only for loose bounds like "polynomial", not for tight bounds for which PRAM-like models are more suitable.
> 10 votes

# Answer
In terms of time complexity, I think this hard on lambda calculus. The reason is that the unit computational step in lambda calculus is $\beta$-reduction (wikipedia entry): $$(\lambda x.{\rm term})v \to {\rm term}\[x := v\]$$ All expressions, regardless of their length, would take $1$ computational time step under this model.
> 1 votes

# Answer
About including λ-calculus in the standard complexity model, here is the abstract from some (very) fresh research on the subject. It gives an answer to this question for some restricted form of β-reduction. Basically, complexity in the standard cost model is similar to counting β-reduction steps *when restricted to head reduction* (which includes call-by-name and call-by-value strategies).

*On the Invariance of the Unitary Cost Model for Head Reduction* by Beniamino Accattoli and Ugo Dal Lago. (WST2012, link to the proceedings)

> The λ-calculus is a widely accepted computational model of higher-order functional programs, yet there is not any direct and universally accepted cost model for it. As a consequence, the computational diffculty of reducing λ-terms to their normal form is typically studied by reasoning on concrete implementation algorithms. Here, we show that when head reduction is the underlying dynamics, the unitary cost model is indeed invariant. This improves on known results, which only deal with weak (call-by-value or call-by-name) reduction. Invariance is proved by way of a linear calculus of explicit substitutions, which allows to nicely decompose any head reduction step in the λ-calculus into more elementary substitution steps, thus making the combinatorics of head-reduction easier to reason about. The technique is also a promising tool to attack what we see as the main open problem, namely understanding for which normalizing strategies the unitary cost model is invariant, if any.
> 1 votes

---
Tags: complexity-theory, efficiency, computation-models
---


# Question
Title: Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?
Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$.

Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $x,y\in (\Sigma \cup N)^\*$ and $\mathcal{S}(G)$ are the sentential forms of $G$.

Given $G$, I'd like to determine a set $C = \\{ b \mid wabz \in \mathcal{S}(G), b \in \Sigma \cup N \\}$.

To clarify, in this case, $w, x, y, z, a, b$ are strings of terminals and non-terminals and $b$ is of length one.

I can see how to do this if $a$ is also of length one; each $b$ is a member of the follow set of $a$ (including non-terminals).

However, I am curious if it's possible for a sequence of characters. For my application, the string $a$ is not much longer than the right hand side of the productions in $G$.

The distinction between terminals and non-terminals is somewhat mute in my application because I am using a generative grammar; and I believe that this won't lead to much trouble since $b$ is of length one.

# Answer
I'll describe an algorithm that works. It's running time shouldn't be too bad. You can precompute quite a bit of this as well.

I'll assume that $a$ does not contain nonterminals (though it's probably easy to adapt to that case) and that you don't know $x$, $y$ or the derivation of $a$. I'll also assume your grammar doesn't contain productions that are never used in any derivation ($A \rightarrow A$ for example).

The main issue really is to parse $a$, as you want to know what kind of states you end up in, so you know what can follow $a$. This is not so easy as you don't know $x$.

We use an adaptation of Earley's algorithm. You'll want to understand that algorithm first. Our algorithm works in almost the same way, except our initialization and completion steps are different.

For the initialization, we seed our first set with an Earley item for every occurrence of $a\_1$ (the first character in $a$) in any production of your grammar. We set the back pointer of this item to -1, an invalid value. This is important in our modified completion. Essentially, the -1 means 'I have no idea where this production was started'.

Now, we perform the Earley algorithm separately for every possible such initial Earley item. We can't simply do all of them at the same time, as the parses may interfere with each other. I can't easily see a faster method than backtracking here.

For the completion step, we only have to make a modification to handle -1 back pointers. As we've completed a production whose origin we don't know, we are in trouble. However, the method used to compute $LALR(1)$ lookahead sets by Pennello and DeRemer saves us: what we need here is exactly the $LALR(1)$ lookahead sets. Every item in these lookahead sets has a corresponding position in the grammar, which in turn corresponds to a possible continuation of the completed production.

Unfortunately, I don't really see any other choice than to backtrack once again here. For every position in the lookahead set, you perform the completion step with this position, and continue the parse from there. You do this separately for every parse. Note that if your grammar is $LALR(1)$, your lookahead will uniquely determine which position you have to go to, so you don't have to backtrack.

You continue the above algorithm one character beyond $a$, where you consider this extra, virtual character to be the 'any character', which immediately gives you the 'follow' set you are looking for - any time the scanner phase finds something for this final set, you can add this character to your answer set.

***Edit:*** I think I've found the method that removes most of the overhead introduced by the backtracking. We associate with every Earley item a set of identifiers, which are strings, as we will need to use prefixes of these identifiers. On initialization, we add all initial items to the Earley set, and associate a unique identifier with every set.

On the scanner and predictor steps, identifiers are carried over to new items. Earley items in the same Earley set that only differ in their identifiers are merged together by merging their identifiers together. Note that we can perform scanner and predictor steps on these new items with identifiers, without having to perform this step for every identifier separately.

The completer considers the identifiers separately, and only completes an item if the corresponding item in the earlier itemset has an identifier that is a prefix of the identifier. For every possible completion (so for every item in the $LALR(1)$ lookahead set), we append a unique character to the identifiers of the completed items.

Essentially, we do the backtracking using these identifiers, so that we don't do double work in the scanner and predictor steps.
> 6 votes

---
Tags: algorithms, context-free, formal-grammars, compilers
---


# Question
Title: Expressing an arbitrary permutation as a sequence of (insert, move, delete) operations
Suppose I have two strings. Call them $A$ and $B$. Neither string has any repeated characters.

How can I find the shortest sequence of insert, move, and delete operation that turns $A$ into $B$, where:

* `insert(char, offset)` inserts `char` at the given `offset` in the string
* `move(from_offset, to_offset)` moves the character currently at offset `from_offset` to a new position so that it has offset `to_offset`
* `delete(offset)` deletes the character at `offset`

Example application: You do a database query and show the results on your website. Later, you rerun the database query and discover that the results have changed. You want to change what is on the page to match what is currently in the database using the minimum number of DOM operations. There are two reasons why you'd want the shortest sequence of operations. First, efficiency. When only a few records change, you want to make sure that you do $\mathcal{O}(1)$ rather than $\mathcal{O}(n)$ DOM operations, since they are expensive. Second, correctness. If an item moved from one position to another, you want to move the associated DOM nodes in a single operation, without destroying and recreating them. Otherwise you will lose focus state, the content of `<input>` elements, and so forth.

# Answer
I suggest taking a look at the edit distance algorithm. Instead of just calculating the distance, you'll want to record your minimum weight path through the array and return that.
> 10 votes

---
Tags: algorithms, combinatorics, string-metrics
---


# Question
Title: What is the complexity of these tree-based algorithms?
Suppose we have a balanced binary tree, which represents a recursive partitioning of a set of $N$ points into nested subsets. Each node of the tree represents a subset, with the following properties: subsets represented by two children nodes of the same parent are disjoint, and their union is equal to the subset represented by the parent. The root represents the full set of points, and each leaf represents a single distinct point. So there are $\log N$ levels to the tree, and each level of the tree represents a partitioning of the points into increasingly fine levels of granularity.

Now suppose we have two algorithms, each of which operates on all of the subsets of the tree. The first does $O(D^2)$ operations at each node, where $D$ is the size of the subset represented by the node. The second does $O(D \log D)$ operations at each node. What is the worst case runtime of these two algorithms?

We can easily bound the first algorithm as $O(N^2 \log N)$, because it does $O(N^2)$ work at each of $\log N$ levels of the tree. Similarly, we can bound the second algorithm as $O(N \log ^2 N)$, by similar reasoning.

The question is, are these bounds tight, or can we do better? How do we prove it?

# Answer
Apply the master theorem.

The first algorithm takes $O(N^2)$ time because your underlying recurrence is

\\\[ T(N) = 2T(N/2) + N^2 \\\]

The second algorithm takes $N\log^2N$ time as you mention. If your work per node is as indicated (and is tight) then this bound is tight as well.

Update: as commenters point out, the assumption here is that the tree is weight-balanced: each child has half the nodes of the parent. This would imply the log N height bound you indicate, but is not implied by it.
> 7 votes

---
Tags: algorithms, time-complexity, binary-trees
---


# Question
Title: Can every linear grammar be converted to Greibach form?
Can every linear grammar be converted to a linear Greibach normal form, a form in which all productions look like $A \rightarrow ax$ where $a \in T$ and $x \in V \cup \\{\lambda\\}$?

($T$ is the set of terminals, $V$ is the set of non-terminals, $\lambda$ is the empty sequence.)

# Answer
The more general answer is:

Blum and Koch showed a polynomial time transformation such that any context-free grammar can be converted to Greibach form.

Since a linear grammar is a special case of Context-free grammar, the answer is yes.

---

EDIT: the rest of this answer is out of scope since the question was about Linear GNF and not just GNF (thanks @hendrik-jan for spotting this)

A simpler transformation:

* Any rule $X \rightarrow a\_1 a\_2 \cdot a\_k Y$ you transform them in $k$ rules:

1. $X\rightarrow a\_1 X\_1Y$.
    2. $\cdots$
    3. $X\_{i-1}\rightarrow a\_{i}X\_i$
    4. $X\_{k-1}\rightarrow a\_{k}Y$
* Any rule $X \rightarrow a Y b$ should be transformed in two rules

1. $X \rightarrow a Y Y\_1$.
    2. $Y\_1 \rightarrow b$

where the capital letters belong to $V$ and the small letters to the alphabet (terminals).
> 9 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Why has research on genetic algorithms slowed?
While discussing some intro level topics today, including the use of genetic algorithms; I was told that research has really slowed in this field. The reason given was that most people are focusing on machine learning and data mining.
**Update:** Is this accurate? And if so, what advantages does ML/DM have when compared with GA?

# Answer
Well, machine learning in the sense of statistical pattern recognition and data mining are definitely hotter areas, but I wouldn't say research in evolutionary algorithms has particularly slowed. The two areas aren't generally applied to the same types of problems. It's not immediately clear how a data driven approach helps you, for instance, figure out how to best schedule worker shifts or route packages more efficiently.

Evolutionary methods are most often used on hard optimization problems rather than pattern recognition. The most direct competitors are operations research approaches, basically mathematical programming, and other forms of heuristic search like tabu search, simulated annealing, and dozens of other algorithms collectively known as "metaheuristics". There are two very large annual conferences on evolutionary computation (GECCO and CEC), a slew of smaller conferences like PPSN, EMO, FOGA, and Evostar, and at least two major high-quality journals (IEEE Transactions on Evolutionary Computation and the MIT Press journal Evolution Computation) as well as a number of smaller ones that include EC part of their broader focus.

All that said, there are several advantages the field more generally thought of as "machine learning" has in any comparison of "hotness". One, it tends to be on much firmer theoretical ground, which the mathematicians always like. Two, we're in something of a golden age for data, and lots of the cutting edge machine learning methods really only start to shine when given tons of data and tons of compute power, and in both respects, the time is in a sense "right".
> 35 votes

# Answer
Some decades ago, people thought that genetic and evolutionary algorithms were swiss-army-knives, fueled by spectacular early results. Statements like the building block hypothesis were made in an effort to prove that they were in general good strategies.

However, rigorous results were slow in coming and often sobering, most prominently the No Free Lunch Theorem. It became evident that genetic/evolutionary algorithms are often decent heuristics but never optimal in any sense.

Today we know that the more we know about a problem respectively its structure, the less sense it makes to employ genetic/evolutionary algorithms as other methods that *use* this knowledge outperform them by magnitudes. In cases where little is known about the problem at hand, however, they still remain a viable alternative because they work at all.
> 23 votes

# Answer
A critical part of the story, as I see it, is missing from the other answers so far:

Genetic algorithms are mostly useful for brute force search problems.

In many contexts, simpler optimization strategies or inference models (what you would broadly call machine learning) can perform very well, and do so far more efficiently than brute force search.

Genetic algorithms, like simulated annealing, are most effective as a strategy for dealing as-well-as-we-know-how with hard (e.g. NP complete) search problems. These domains tend to be so limited by the intrinsic hardness of the problems that tweaking and iterating on modest factors in the solution strategy, by incrementally improving genetic algorithms, is often not very much use, and so not terribly exciting.
> 14 votes

# Answer
To some extent, machine learning is becoming more mathematical and with algorithms able to be 'proven' to work. In some ways, GAs are very "wth happened in there" and you can't perfectly answer the question "so what did your program do?" (well in some people's eyes, anyway).

I personally advocate combining neural nets and GA = GANNs. In my honours thesis, I produced a drug prediction algorithm first using NNs, then a GA, and finally a GANN which took the best of both worlds and outperformed both other sets. YMMV, however.
> 13 votes

# Answer
Machine learning unveils a large portion of mathematical apparatus to be developed and applied. Genetics algorithms mostly done by heuristics.
> 4 votes

---
Tags: machine-learning, data-mining, evolutionary-computing, history
---


title: Late and Early Bisimulation

text:
# Question
Title: Late and Early Bisimulation
This is a follow up to my earlier questions on coinduction and bisimulation.

A relation $R \subseteq S \times S$ on the states of an LTS is a *bisimulation* iff $\forall (p,q)\in R,$ $$ \begin{array}{l} \text{ if } p \stackrel\alpha\rightarrow p' \text{ then } \exists q', \\; q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R \text{ and } \\ \text{ if } q \stackrel\alpha\rightarrow q' \text{ then } \exists p', \\; p \stackrel\alpha\rightarrow p' \text{ and } (p',q')\in R. \end{array} $$

This is a very powerful and very natural notion, after you come to appreciate it. But it's not the only notion of bisimulation. In special circumstances, such as in the context of the $\pi$-calculus, other notions such as open, branching, weak, barbed, late and early bisimulation exist, though I do not fully appreciate the differences. But for this question, I want to limit focus just two notions.

> What are *late* and *early* bisimulation and why would I use one of these notions instead of standard bisimulation?

# Answer
Late and early only make sense when building the LTS. The notion of bisimulation stays the same.

However there are several notion of *bisimilarities* in the π-calculus for example. These are related to how new names are handled. It happens in the π-calculus because it is a *name-passing* process calculus. There is no such thing in CCS where names cannot be sent.

Usually, the notion of barbed equivalence or congruence is more unanimous. Then you have to prove the equivalence with the late/early/open bisimilarity to give it some credit.

To be quick about it, early transitions are that way: $$ a(x).P \stackrel{a(b)}{\longrightarrow} P\[b/x\] \qquad \begin{array}{c} P \stackrel{a(b)}{\longrightarrow} P' \quad Q \stackrel{\overline ab}{\longrightarrow} Q' \\ \hline P\mid Q → P' \mid Q' \end{array} $$

and late are like this: $$ a(x).P \stackrel{a(x)}{\longrightarrow} P \qquad \begin{array}{c} P \stackrel{a(x)}{\longrightarrow} P' \quad Q \stackrel{\overline ab}{\longrightarrow} Q' \\ \hline P\mid Q → P'\[b/x\] \mid Q' \end{array} $$

You see the difference is subtle and is just about where the substitution is done. My preference go to the late one because when I reason about processes, I just remember that the $x$ in the transition $a(x)$ is bound. Also the late bisimilarity is the strongest one (beside the open one which is really not the same) and the processes that are early but not late bisimilar are kind of weird, so you don't lose much.
> 3 votes

---
Tags: semantics, formal-methods, process-algebras, pi-calculus
---


# Question
Title: Improve worst case time of depth first search on Euler graphs
How to improve the worst case scenario for a depth first search on an Euler graph, starting at some point and ending at that same point?

I need to do the whole search but it is not fast enough for large amounts of data. I have tried bidirectional search but I can not keep the result numerically ordered. Therefore I wonder if there is any other good method to smooth the worst case scenario for the depth first search.

# Answer
> 3 votes
If I understand correctly, the only way to have a numerically ordered eulerian path would be having a path looking like 1,2,3..,n,1. All nodes in the path must have degree 2 (since you can only get into the once), except perhaps for nodes with degree 0, that you can instead skip.

If this is the case, the algorithm would just be a matter of testing if the 1,2,3..n path is eulerian, with no need to find eulerian paths with a traditional algorithm.

---
Tags: algorithms, graphs, graph-traversal, eulerian-paths
---


# Question
Title: How can I prove this language is not context-free?
I have the following language

$\qquad \\{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\\}$

I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-sensitive grammar so I know it is atleast context-sensitive. It seems like it wouldn't be possible to make with a context-free grammar, but I'm having a problem proving that.

It seems to pass the fork-pumping lemma because if $uvwxy$ is all placed in the third part of any word (the section with all of the $2$s). It could pump the $v$ and $x$ as many times as you want and it would stay in the language. If I'm wrong could you tell me why, if I'm right, I still think this language is not context-free, so how could I prove that?

# Answer
You can force the pumping to be in some places, using Ogden's lemma, for example by marking all the 0's.

Suppose it is context free, then Ogden's lemma gives you a $p\>0$, you give it $w=0^p1^p2^p$ which is in the language, and you "mark" all the 0's. Then any factorisation $w=uxyzv$ must be such that there is a $0$ in $x$ or $z$. You can also assume $x=a^k$ and $z=b^m$ since $xx$ and $zz$ must be substrings of your language.

1. If $z=0...0$ then $w=ux^2yz^2v$ has more 0's than 1's
2. If $x=0..0$ and $z=1..1$ then $w=ux^2yz^2v$ has more 1's than 2's.
3. If $x=0..0$ and $z=2..2$ then $w=ux^2yz^2v$ has more 0's than 1's.

So $ux^2yz^2v$ is not a word of your language. Therefore, it is not context-free.

For other techniques, see the discussion: How to prove that a language is not context-free?
> 7 votes

# Answer
The pumping lemma should solve your problem regarding the third part of the word; note that when you split $z = uvwxy$, any combination of $uv^nwx^ny$ is also in the language, *including* when $n = 0$. Try that.

EDIT: As jmad states, the Pumping Lemma is like a game:

> 1. The pumping lemma gives you a $p$
> 2. You give a word $s$ of the language of length at least $p$
> 3. The pumping lemma rewrites it like this: $s=uvxyz$ with some conditions ($|vxy|≤p$ and $|vy|≥1$)
> 4. You give an integer $n≥0$
> 5. If $uv^nxy^nz$ is not in $L$, you win, $L$ is not context free.

So what you have to do is state a word, break down 3 into cases, and show that for each case you can find an $n$ such that the resulting word isn't in the language.

When you split $s=uvxyz$, think of all the cases that $vxy$ can fall into. You note that if $vxy$ does not fall into the 2's, then it is easy to pump the 0's and 1's until they outnumber the 2's, and then you have a word that's not in the language. My suggestion is that, if $vxy$ falls into 2 territory, you can also make $v$ and $y$ disappear by setting $n=0$, so $uv^nxy^nz = uxz$. Then by eliminating a 2 you could arrive at a word that doesn't fall in the language.
> 5 votes

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


title: What is beta equivalence?

text:
# Question
Title: What is beta equivalence?
In the script I am currently reading on the lambda calculus, beta equivalence is defined as this:

> The $\beta$-equivalence $\equiv\_\beta$ is the smallest equivalence that contains $\rightarrow\_\beta$.

I have no idea what that means. Can someone explain it in simpler terms? Maybe with an example?

I need it for a lemma following from the Church-Russer theorem, saying

> If M $\equiv\_\beta$ N then there is a L with M $\twoheadrightarrow\_\beta$ L and N $\twoheadrightarrow\_\beta$ L.

# Answer
$\to\_\beta$ is the one-step relation between terms in the $\lambda$-calculus. This relation is neither reflexive, symmetric, or transitive. The equivalence relation $\equiv\_\beta$ is the reflexive, symmetric, transitive closure of $\to\_\beta$. This means

1. If $M\to\_\beta M'$ then $M\equiv\_\beta M'$.
2. For all terms $M$, $M\equiv\_\beta M$ holds.
3. If $M\equiv\_\beta M'$, then $M'\equiv\_\beta M$.
4. If $M\equiv\_\beta M'$ and $M'\equiv\_\beta M''$, then $M\equiv\_\beta M''$.
5. $\equiv\_\beta$ is the smallest relation satisfying conditions 1-4.

More constructively, first apply rules 1 and 2, then repeat rules $3$ and $4$ over and over until they add no new elements to the relation.
> 21 votes

# Answer
It is elementary set theory really. You know what is a reflexive relation, what is a symmetric relation, and what is a transitive relation, right? An equivalence relation is one that satisfies all three of those properties.

You have probably heard of the "transitive closure" of a relation $R$? Well, it is nothing but the *least transitive relation* that includes $R$. That is what the term "closure" means. Similarly, you can talk about the "symmetric closure" of a relation $R$, the "reflexive closure" of a relation $R$ and the "equivalence closure" of a relation $R$ in exactly the same way.

With some thought, you can convince yourself that the transitive closure of $R$ is $R \cup R^2 \cup R^3 \cup \ldots$. The symmetric closure is $R \cup R^{-1}$. The reflexive closure is $R \cup I$ (where $I$ is the identity relation).

We use the notation $R^\*$ for $I \cup R \cup R^2 \cup \ldots$. This is the *reflexive transitive closure* of $R$. Now notice that if $R$ is symmetric, each of the relations $I$, $R$, $R^2$, $R^3$, ... is symmetric. Hence $R^\*$ will also be symmetric.

So the equivalence closure of $R$ is the transitive closure of its symmetric closure, i.e., $(R \cup R^{-1})^\*$. This represents a sequence of steps, some of which are forward steps ($R$) and some backward steps ($R^{-1}$).

The relation $R$ is said to have the Church-Rosser property if the equivalence closure is the same as the composite relation $R^\* (R^{-1})^\*$. This represents a sequence of steps in which all the forward steps come first, followed by all backward steps. So, the Church-Rosser property says that any interleaving of forward and backward steps can be equivalently carried out by doing forward steps first and backward steps later.
> 11 votes

---
Tags: logic, terminology, lambda-calculus, type-theory
---


# Question
Title: Decidablity of Languages of Grammars and Automata
*Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2.*

Here are the two questions I'm looking at from a past exam. They seem to be related, the first:

> Let
>
> $\qquad \mathrm{FINITE}\_{\mathrm{CFG}} = \\{ \< \\! G \\! \> \mid G \text{ is a Context Free Grammar with } |\mathcal{L}(G)|\<\infty \\} $
>
> Prove that $\mathrm{FINITE}\_{\mathrm{CFG}}$ is a decidable language.

and...

> Let
>
> $\qquad \mathrm{FINITE}\_{\mathrm{TM}} = \\{ \< \\! M\\!\> \mid M \text{ is a Turing Machine with } |\mathcal{L}(M)|\<\infty \\}$
>
> Prove that $\mathrm{FINITE}\_{\mathrm{TM}}$ is an undecidable language.

I am a bit lost on how to tackle these problems, but I have a few insights which I think may be in the right direction. The first thing is that I am aware of is that the language $A\_{\mathrm{REX}}$, where

> $\qquad A\_{\mathrm{REX}} = \\{ \<\\! R, w \\!\> \mid R \text{ is a regular expression with } w \in\mathcal{L}(R)\\}$

is a decidable language (proof is in Michael Sipser's *Theory of Computation*, pg. 168). The same source also proves that a Context Free Grammar can be converted to a regular expression, and vice versa. Thus $A\_{\mathrm{CFG}}$, must also be decidable as it can be converted to a regular expression. This, and the fact that $A\_{\mathrm{TM}}$ is **un**-decidable, seems to be related to this problem.

The only thing I can think of is passing G to Turing machines for $A\_{\mathrm{REX}}$ (after converting G to a regular expression) and $A\_{\mathrm{TM}}$. Then accepting if G does and rejecting if G doesn't. As $A\_{\mathrm{TM}}$ is undecidable, this will never happen. Somehow I feel like I'm making a mistake here, but I'm not sure of what it is. Could someone please lend me a hand here?

# Answer
1. Convert G to Chomsky Normal form. This way, the only empty derivation would be the start symbol that does not appears anywhere else and thus if there is some production that may able to eventually generate itself, then the grammar is infinite. If no such production exists, each symbol will only be able to generate a finite set of strings, and then the grammar is finite. So, build a directed graph where each production is a node and each symbol inside a production is an edge targeting that symbol. If the graph has some cycle, the CFG is infinite, otherwise it is not. Hence a Turing machine for $FINITE\_{CFG}$ could be construct doing exactly that, and then $FINITE\_{CFG}$ is decidable.
2. Suppose that $FINITE\_{TM}$ is decidable. Lets say that $H$ is a Turing machine that has some string as input and uses itself as an input to $FINITE\_{TM}$. If $FINITE\_{TM}$ returns true (i.e, $H$ accepts only a finite language), then $H$ accepts the input, which leads to a contradiction since the input set is infinite (the input's length is unbounded, so accept any possible string as input means accepting an infinite set of strings). If $FINITE\_{TM}$ returns false (i.e $H$'s language is infinite), then $H$ rejects the input, meaning that $H$'s language is finite because it does not accepts any input (i.e. its language is empty), which leads to a contradiction too. This way, the supposition that $H$ exists leads to contradiction, and this supposition is based in the supposition that $FINITE\_{TM}$ is decidable. So, by contradiction, we have that $FINITE\_{TM}$ is not decidable.

> The same source also proves that a Context Free Grammar can be converted to a regular expression, and vice versa.

I really doubt that Sipser would state that, you probably misread or misunderstood. This would mean that context-free grammars generate exactly the same langauges as right-linear grammars. This is false; the right-linear grammars generate are a proper subset of the languages context-free grammars dp. That said, the way you tried to use regular languages to answer the questions just leads you to nowhere.

As you can see above in my proofs, the two questions are indeed two very distinct, unrelated questions. It just happens that they were worded similarly.
> 9 votes

# Answer
Another way to decide $FINITE\_{CFG}$ is via the pumping lemma.

The pumping lemma says that each CFL $L$ has a number $N$ (which can be computed from the grammar, or at least an upper bound of it can easily be computed), such that any $x\in L$ which is longer than $N$ can be "pumped".

This means that if $L$ is finite, **all** the words in $L$ are shorter than $N$.

Now, all that one needs to check is words with lengths between $N$ and $2N$. If any such word exists, then $L$ is infinite. It is not too difficult to see that this statement is "if and only if", thus if you find no word withing this range, $L$ is finite. The efficiency here is much worse than the answer of Victor, but it teaches something about the structure of CFLs.
> 2 votes

---
Tags: formal-languages, computability, context-free, regular-languages, turing-machines
---


# Question
Title: Deciding on Sub-Problems for Dynamic Programming
I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal answer. How do you formally define a sub-problem for a problem that you would solve using dynamic programming?

# Answer
The principle of dynamic programming is to think top-down (i.e recursively) but solve bottom up. So a good strategy for designing a DP is to formulate the problem recursively and generate sub-problems that way.
> 39 votes

# Answer
As @Suresh pointed out, once you know that your problem can be solved by DP (i.e. it exhibits optimal substructure and overlapping subproblems), you may think of a divide and conquer recursive solution.

Of course, divide and conquer will be highly ineffecient because every subproblem encountered in the associated recursion tree will be solved again even if it has already been found and solved. This is where DP differs: each time you encounter a subproblem, you solve it and store its solution in a table. Later, when you encounter again that subproblem, you access in $\mathcal{O}(1)$ time its solution instead of solving it again. Since the number of overlapping subproblems is typically bounded by a polynomial, and the time required to solve one subproblem is polynomial as well (otherwise DP can not provide a cost-efficient solution), you achieve in general a polynomial solution.

Therefore, thinking about a divide and conquer solution will provide you with the insight about what a subproblem may be for your particular problem.
> 4 votes

# Answer
My experience is finding out a way to "cut down redundant enumerating with help of storing useful value already enumerated". By the way, Dynamic Programming is really popular in ICPC(International Collegiate Programming Contest. Anyone can have his own feeling about DP after practice several ICPC problems.
> 2 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: A Question relating to a Turing Machine with a useless state
OK, so here is a question from a past test in my Theory of Computation class:

> A useless state in a TM is one that is never entered on any input string. Let $$\mathrm{USELESS}\_{\mathrm{TM}} = \\{\langle M, q \rangle \mid q \text{ is a useless state in }M\\}.$$ Prove that $\mathrm{USELESS}\_{\mathrm{TM}}$ is undecidable.

I think I have an answer, but I'm not sure if it is correct. Will include it in the answer section.

# Answer
> 13 votes
This is clearly reducible from the Halting Problem. If a machine $M$ does not stop on input $x$ then any final state is "useless". Given an input $M,x$ for the Halting problem, it is easy to construct $M\_x$ that halts on every input (thus its final state is not useless) if and only if $M$ halts on $x$. That way you can decide Halting Problem if you can decide $\mathrm{USELESS}\_{\mathrm{TM}}$, which yields a contradiction.

# Answer
> 2 votes
For the purposes of this proof we will assume that $\mathrm{USELESS}\_{\mathrm{TM}}$ is decidable to display a contradiction.

Create TM $R$ that does the following:

* Converts TM $M$ to a pushdown automata $P$ with a relaxed stack (ie. no LIFO requirement). This is equivalent to a directed graph detailing the transition between $M$'s states.
* Mark the start state of $P$.
* From the start state commence a breadth-first search along each outbound edge marking each unmarked node.
* When the search terminates, if there are any unmarked nodes which match $q$, *accept*; otherwise *reject*.

Then create TM $S$ = "On input $$

1. Create TM $R$ as shown above.
2. Run $q$ on $R$.
3. If $R$ returns accept, *accept*; if $R$ rejects, *reject*"

Thus, if $R$ is a decider for $\mathrm{USELESS}\_{\mathrm{TM}}$ then $S$ is a decider for $A\_{\mathrm{TM}}$ (the acceptance problem). Since $A\_{\mathrm{TM}}$ is proven to be undecidable (see Michael Sipser *Theory of Computation* Theorem 4.11 on page 174), we have reached a contradiction. Therefore, the original hypothesis is incorrect and $\mathrm{USELESS}\_{\mathrm{TM}}$ is undecidable.

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


# Question
Title: Is there a difference between $\lambda xy.xy$ and $\lambda x.\lambda y.xy$?
I am currently learning the lambda calculus and was wondering about the following two different kinds of writing a lambda term.

1. $\lambda xy.xy$
2. $\lambda x.\lambda y.xy$

Is there any difference in meaning or the way you apply beta reduction, or are those just two ways to express the same thing?

Especially this definition of pair creation made me wonder:

> **pair** = $\lambda xy.\lambda p.pxy$

# Answer
These are just differences of notations. $λxyz.t$ is short for $λx.λy.λz.t$. No magic here.

Indeed, $\mbox{pair}=λxyp.pxy$ but you tend to emphasize that $\mbox{pair}\\,t\\,u$ is a function $λp.ptu$ by changing the way you write the definition. But it is really the same.
> 15 votes

# Answer
The first is an abbreviation for the second. It's a common syntactic convention to shorten expressions.

On the other hand, if you have tuples in the language, then there is a difference between

1. $\lambda x.\lambda y.xy$ and
2. $\lambda (x,y).xy$.

In the former case I can provide a single argument to the function, and pass the resulting function around to other functions. In the latter case, both arguments must be supplied at once. There is, of course, a function that can be applied to convert 1 into 2 and vice versa. This process is known as *(un)currying*.

The definition of $\text{pair}$ you mention is an encoding of the notion of pairs into the $\lambda$-calculus, rather than pairs as a primitive data type (as I hinted at above).
> 17 votes

# Answer
Transforming a function that takes multiple arguments to a chain of functions with single arguments is called **currying**. The two functions are essentially the same.

Wikipedia article about currying
> 2 votes

---
Tags: logic, lambda-calculus
---


# Question
Title: Logarithmic vs double logarithmic time complexity
In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ?

This is the case when one use for instance van Emde Boas trees instead of more conventional binary search tree implementations. But for example, if we take $n \< 10^6$ then in the best case the double logarithmic algorithm outperforms the logarithmic one by (approximately) a factor of $5$. And also in general the implementation is more tricky and complex.

Given that I personally prefer BST over VEB-trees, what do you think ?

*One could easily demonstrate that :*

$\qquad \displaystyle \forall n \< 10^6.\ \frac{\log n}{\log(\log(n))} \< 5.26146$

# Answer
Do not forget that $\log n$ still grows exponentially (in $\log(n)$) faster than $\log(\log n)$!

Indeed, if you look at the quotient of $\log(n)$ and $\log(\log(n))$, there is not much impressive to see:

\[source\]

But still, you get a factor five to six for sizes up to $100000$. Note that larger sizes are not uncommon in practice, and a speedup by that factor is *awesome*! It may make the difference between having results after lunch or only tomorrow. Be aware that part of the speedup may be eaten away by higher constants of the tree implementation; you would have to plot (or analyse) $c\cdot \log(n)$ and $d\cdot \log(\log(n))$ with $c,d$ the actual runtime constants to get a real picture.

Additionally, what Dave mentions is important: if the operation sped up thusly is executed, say, linearly often, constant speedups become linear speedups, i.e. you may decrease the leading constant of your entire algorithm! As I said above, that is awesome. Just look at what happens if you run the operation $n$ times:

\[source\]

Now if that's not worth the trouble I don't know what.
> 10 votes

# Answer
One could imagine that the difference in complexity really does not matter so much, and that the actual run-time is more important. But if the algorithm is at the core of another algorithm, then this difference may be important.

From a purely theoretical purpose, the difference of course does matter, especially if the algorithm is a part of another. It may put the larger algorithm in a different complexity class.
> 6 votes

# Answer
I've actually benchmarked the van Emde-Boas tree myself once. I compared it with an AA Tree, a hashmap and a bit array.

The tests perform `size` inserts with random numbers in the interval `[0, bound]`, then `size` searches, then `size` deletes and then again `size` searches. Deletes are done on random numbers as well, so you first have to figure out if they are in the structure at all.

Here are the results (`size`=2000000, `bound`=10000000) in seconds:

```
AATreeLookup - O(n log n)
Inserting... 3.3652452
Searching... 5.2280724
Deleting...  7.3457427
Searching... 9.1462039
HashLookup - O(n) expected
Inserting... 0.3369505
Searching... 0.6223035
Deleting...  0.9062163
Searching... 1.1718223
VanEmdeBoasTree - O(n log log n)
Inserting... 0.7007531
Searching... 1.1775800
Deleting...  1.7257065
Searching... 2.2147703
ArrayLookup - O(n)
Inserting... 0.0681897
Searching... 0.1720300
Deleting...  0.2387776
Searching... 0.3413800

```

As you can see, van Emde-Boas trees are about twice as slow as hash maps, ten times as slow as bit arrays, and 5 times as fast as binary search trees.

Of course the above needs a disclaimer: the tests are artificial, you can possibly improve the code or use a different language with a compiler whose output is faster, and so on and so forth.

This disclaimer is at the heart of the reason we use asymptotic analysis in algorithms design: as you have no idea what the constants are and as the constants can change depending on environmental factors, the best we can do is an asymptotic analysis.

Now, in the case of $\log n$ versus $\log \log n$: in the above example, my van Emde-Boas tree is able to contain $2^{32}$ elements. $\log 2^{32} = 32$, and $\log 32 = 5$, which is a factor 6 improvement, which is quite a bit in practice. Additionally, van Emde-Boas trees have good constant factors (it's all about constant factors in practice for differences this small) as they don't need to balance themselves.
> 6 votes

---
Tags: algorithms, complexity-theory, binary-trees, algorithm-analysis, search-trees
---


title: CPU frequency per year

text:
# Question
Title: CPU frequency per year
I know that since ~2004, Moore's law stopped working for CPU clock speed. I'm looking for a graph showing this, but am unable to find it: most charts out there show the transistor count or the capacity per year.

Where can I find some data showing the CPU frequency of computers (anything is fine, personal computers, servers, laptops, ...) from the last few decades to today?
Raw data that I can plot myself would be fine as well (hum, probably even better).

# Answer
Bob Warfield wrote a blog post (A Picture of the MultiCore Crisis) that has the kind of graph you're looking for.

**Update**

It sounds like the Stanford CPU DB has what you're looking for. You can browse visualizations and download the raw data.
> 8 votes

# Answer
The graphs you want are printed in the book “CMOS VLSI Design” Weste/Harris (2005), on page 5 of the freely available introduction.
> 10 votes

# Answer
See Sutter, The Free Lunch is Over (2005): it has graphs, discusses how various processor characteristics relate to performance of actual programs, and makes some predictions that turned out true, as far as I can tell.
> 4 votes

# Answer
The 5th edition of *Computer Architecture, A Quantitative Approach* has several related graphs.

The clock rate graphs is divided in 3 parts, from a 5MHz Vax in 78 to a Sun SPARC at 16 MHz in 86 (15% per year), to an Intel Pentium 4 Xeon in 2003 at 3200 MHz(40% per year) to an Intel Nehalem Xeon in 2010 at 3330 MHz (1% per year).

The performance graph is also divided in 3 parts, from the VAX 11/780 in 78 at relative performance 1 to the VAX 8700 in 86 at relative perf of 5 (25% per year), to an Intel Xeon in 2003 at relative perf of 6000 (52% per year) to an Intel Xeon in 2010 at relative perf of 2400 (22% per year). Note that SPEC on which the performance measure is based has automatic parallelization turned on and so multiple core of a processor are used here.
> 3 votes

---
Tags: computer-architecture, empirical-research, data-sets
---


# Question
Title: Language of the graph of an affine function
Write $\bar n$ for the decimal expansion of $n$ (with no leading `0`). Let `:` be a symbol distinct from any digit. Let $a$ and $b$ be integers, with $a \> 0$. Consider the language of solutions of the Diophantine equation $y=ax+b$:

$$L = \\{ \bar{x} \mathtt: \bar{y} \mid y = a\\,x + b \\}$$

Is $L$ regular? context-free?

(Contrast with Language of the values of an affine function)

<sub>(Follows on How can solutions of a Diophantine equation be expressed as a language?)</sub>

<sub> I think this would make a good homework question, so answers that start with a hint or two and explain not just how to solve the question but also how to decide what techniques to use would be appreciated. </sub>

# Answer
Hint:

$53 \cdot 100000010000000000 + 4 = 5300000530000000004$.

Sketch:

> Assume $a$ has $n$ digits and $b$ has $m$ digits.
> If $\overline{x}=10^k \underbrace{00\dots01}\_{n}0^l\underbrace{00\dots0}\_{m}$ for some $k,l$ then $\overline{ax+b}=\overline{a}0^k \overline{a} 0^l \overline{b}$.
> If $L$ was context-free, then $$L'=L \cap 10^{\ast}0^{n-1}10^{\ast}0^m \mathtt: (0+1+2+...+9)^{\ast} = \\{10^{k+n-1}10^{l+m} \mathtt: \overline{a}0^k\overline{a}0^l\overline{b}:k,l \in \mathbb N\\}$$ would be context-free as well. Given a PDA $M$ for $L'$ we could construct a PDA $N$ for $\\{a^n b^m c^n d^m\\}$ , a well-known non-context-free language. $N$ simulates $M$, but it is "feeding" different letters; it is a composition of $M$ with a transducer. Initially, $N$ behaves as if $M$ read $1$. Then, consecutive $a$'s are interpreted as $0$'s. Next, $N$ behaves as if $M$ read $0^{n-1}1$, and treats consecutive $b$'s as $0$'s, then as if it read $0^m \mathtt: \overline{a}$ etc.
> 6 votes

# Answer
Regarding "Is $L$ regular?": You should reflexively check the Pumping condition; can a long solution $\bar{x}:\bar{y}$ be pumped?

> No, it can not. Assume a pumping constant $p$. Because $y = ax + b$ has arbitrarily large solutions ($a\>0$ !), we can choose one solution $(x',y')$ with $|\bar{x'}| \> p$. Then, $xy$ (from the Pumping Lemma) has to be a prefix of $\bar{x'}$. Pumping $y$ now increases $x'$ but $y'$ remains unchanged; we leave $L$.

As for "Is $L$ context-free" (assuming above question was answered negatively) it is wortwhile to consider special cases of $L$, as the question implicitly asks wether $\\{L\_{a,b}\\} \subseteq \mathrm{CFL}$. Can you find a combination of $a,b$ that allows an easy proof?

> Indeed! $a=1$ and $b=0$ leads to $L = \\{\bar{x}:\bar{x} \mid x \in \mathbb{N}\\}$. We know that this language is not context-free by $\\{ww \mid w \in \\{a,b\\}^\*\\}$ (the canonical example).
> 2 votes

# Answer
**Hint 1**: What happens when $a=1$ and $b=0$?

OK, we nailed it for a specific pair $a,b$. Now, does it will become any different for other $a,b$?

**Hint 2**: Go on with $b=0$ and arbitrary $a$

**Hint 3**: Try to think what happens if $a=0$ and $b$ is not. This can't happen in this question, but it should give you the idea how to cope with $a,b \ne 0$.
> 1 votes

---
Tags: formal-languages, regular-languages, context-free, integers
---


# Question
Title: How can solutions of a Diophantine equation be expressed as a language?
I was given the question

> Where does the following language fit in the Chomsky hierarchy?
>
> Nonnegative solutions $(x,y)$ to the Diophantine equation $3x-y=1$.

I understand languages like $L = \\{ 0^n1^n \mid n \ge 1\\}$, but this language confuses me. What do the words in the language look like? How could I represent it using a grammar or regular expression?

# Answer
The first thing you'll want to do is look at the phrase itself, and ignore all the references to languages for a moment.

So, what are the non-negative solutions to the diophantine equation $3x-y=1$? If we fix some $x$, then $y = 3x-1$. This means that the set of solutions is $\\{ (x, 3x-1)\ |\ x \> 0 \\}$ (note that $x=0$ yields a negative $y$, and a positive $x$ yields a positive $y$).

Now, we can associate a string with any non-negative number pair $(x, y)$: for instance, $(100, 299)$ can be associated with the string `(100, 299)`. If we apply this to every pair in the set, the resulting set of strings is the language of this set. Note that the question does not really make it clear how to associate a string with a solution, but I'm pretty sure they mean the above.

Now all you have to do is figure out in which level of the Chomsky Hierarchy this language falls. As I have a mild suspicion that this is a homework question, I'll not immediately spill the beans. If you can confirm this is not a homework question and you still need help, I'll edit the answer in.
> 5 votes

# Answer
The problem statement is indeed incomplete, but when you see this, you can safely assume that “*representing integers in decimal notation*” or “*representing integers in binary notation*” was meant.

---

So here, if we assume binary notation, the alphabet is contains 5 characters: `0`, `1`, `(`, `)` and `,`. If we assume decimal notation, the alphabet would additionally contain the digits `2` through `9`.

The language in question is a subset of the language matched by the regular expression $\mathtt{(}(0|1)^\*\mathtt{,}(0|1)^\*\mathtt{)}$ (going with binary notation). If we assumed the simpler case of the equation $2x-y=0$, then the language would be all pairs of numbers $(x,y)$ such that $y = 2x$. In binary, this means $y$ is $x$ with an additional `0` at the end. In other words, the language would consist of words of the form `(`$x$`,`$x$`0)`. Where does this fit in the Chomsky hierarchy?

Here, we have a more complicated example: you have to recognize whether $y = 3x-1$. How do binary (or decimal) expansions of $x$ and $y$ compare when $y=3x-11$?
> 5 votes

# Answer
The question is not complete, since a language is a set of words, not pairs. If you encode it as $x\\$y$ where $x,y$ are in binary, it is context-sensitive but not context-free (see Gilles's answer), if you encode it as $x\\$y^R$ it is context-free but not regular (exercise), if you suitably intersperse bits of $x$ and $y$, it is regular! See here.
> 1 votes

---
Tags: formal-languages, computability
---


# Question
Title: A Case Distinction on Dynamic Programming: Example Needed!
I have been working on dynamic programming for some time. The canonical way to evaluate a dynamic programming recursion is by creating a table of all necessary values and filling it row by row. See for example Cormen, Leiserson et al: "Introduction to Algorithms" for an introduction.

I focus on the table-based computation scheme in two dimensions (row-by-row filling) and investigate the structure of cell dependencies, i.e. which cells need to be done before another can be computed. We denote with $\Gamma(\mathbf{i})$ the set of indices of cells the cell $\mathbf{i}$ depends on. Note that $\Gamma$ needs to be cycle-free.

I abstract from the actual function that is computed and concentrate on its recursive structure. Formally, I consider a recurrrence $d$ to be *dynamic programming* if it has the form

$\qquad d(\mathbf{i}) = f(\mathbf{i}, \widetilde{\Gamma}\_d(\mathbf{i}))$

with $\mathbf{i} \in \[0\dots m\] \times \[0\dots n\]$, $\widetilde{\Gamma}\_d(\mathbf{i}) = \\{(\mathbf{j},d(\mathbf{j})) \mid \mathbf{j} \in \Gamma\_d(\mathbf{i}) \\}$ and $f$ some (computable) function that does not use $d$ other than via $\widetilde{\Gamma}\_d$.

When restricting the granularity of $\Gamma\_d$ to rough areas (to the left, top-left, top, top-right, ... of the current cell) one observes that there are essentially three cases (up to symmetries and rotation) of valid dynamic programming recursions that inform how the table can be filled:

The red areas denote (overapproximations of) $\Gamma$. Cases one and two admit subsets, case three is the worst case (up to index transformation). Note that it is not strictly required that the *whole* red areas are covered by $\Gamma$; *some* cells in every red part of the table are sufficient to paint it red. White areas are explictly required to *not* contain any required cells.

Examples for case one are edit distance and longest common subsequence, case two applies to Bellman & Ford and CYK. Less obvious examples include such that work on the diagonals rather than rows (or columns) as they can be rotated to fit the proposed cases; see Joe's answer for an example.

I have no (natural) example for case three, though! So my question is: What are examples for case three dynamic programming recursions/problems?

# Answer
There are plenty of other examples of dynamic programming algorithms that don't fit your pattern at all.

* The longest increasing subsequence problem requires only a one-dimensional table.
* There are several natural dynamic programming algorithms whose tables require three or even more dimensions. For example: Find the maximum-area white rectangle in a bitmap. The natural dynamic programming algorithm uses a three-dimensional table.
* But most importantly, **dynamic programming isn't about tables**; it's about unwinding recursion. There are lots of natural dynamic programming algorithms where the data structure used to store intermediate results is not an array, because the recurrence being unwound isn't over a range of integers. Two easy examples are finding the largest independent set of vertices in a tree, and finding the largest common subtree of two trees. A more complex example is the $(1+\epsilon)$-approximation algorithm for the Euclidean traveling salesman problem by Arora and Mitchell.
> 15 votes

# Answer
Computing Ackermann function is in this spirit. To compute $A(m,n)$ you need to know $A(m,n-1)$ and $A(m-1,k)$ for some large $k$. Either the second coordinate decreases, or the first decreases, and second potentially increases.

This does not ideally fit the requirements, since the number of columns is infinite, and the computation is usually done top-down with memorization, but I think it is worth to mention.
> 3 votes

# Answer
This doesn't fit case 3 exactly, but I don't know if any of your cases capture a very common problem used to teach dynamic programming: Matrix Chain Multiplication. To solve this problem, (and many others, this is just the canonical one) we fill up the matrix diagonal by diagonal instead of row by row.

So the rule is something like this:
> 2 votes

# Answer
I know its a silly example, but I think a simple iterative problem like

> Find the sum of the numbers in a square matrix

might qualify. The the traditional "for each row for each column" kinda looks like your case 3.
> 0 votes

# Answer
This is exactly not the search space you are looking for but i've an idea of the top of my head which might be of help.

**Problem :**

Given a $n × n$ matrix say, $M$ with distinct integers in which the entries of each row (from left to right) and each column (from top to bottom) are both sorted in increasing order and the entries in each column are in increasing order . Give an eﬃcient algorithm to ﬁnd the position of an integer $x$ in $M$ (or say the integer is not present in the matrix).

**Answer**

This can be solved in the following recursive way :

We have an n×n matrix. Let $k = \lceil{\frac{1+n}{2}}\rceil$. Now compare $x$ with $m\_{k,k}$. If $x\<m\_{k,k}$ we can discard any element $m\_{i,j}$ for $k\leq i\leq n$ and $k\leq j\leq n$ i.e., the search space is reduced by $1/4$. Similarly, when $x\>m\_{k,k}$, the search space is reduced by $1/4$. So after the first iteration, the size of the search space becomes $\frac{3}{4} n^2$. You can do this recursively further as follows: we make 3 comparisons: $x$ with the middle element in each of the remaining three quadrants, and the size of the remaining search space then becomes $\left(\frac{3}{4}\right)^3 n^2$ and so on.
> -1 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Non-trivial tractable properties of triples
Many intractable $NP$-complete problems can be modeled as deciding whether a set of triples, $F=${$t\_1, t\_2, ..., t\_n$} where each triple $t\_i$ is a subset of three elements over base set $U=${$a\_1, a\_2, ..., a\_k$}, satisfy some non-trivial property. For example, 3-edge coloring of cubic graphs can be modeled as the problem of deciding whether sets of triples satisfy that the elements in each triple must have different color.

I'm looking for examples of non-trivial tractable properties ($P\_2$) of sets of triples (which have polynomial time algorithms) given that the sets of triples already satisfies some other non-trivial property $P\_1$. Non-trivial property means that there are infinite number of sets of triples that satisfy the property and infinite number of sets of triples that do not. Are all non-trivial properties $P\_2$ of sets of triples intractable?

Also, I'd appreciate a survey on the subject.

**EDIT:** Based on Ben's answer, I added the requirement that $F$ already satisfies some non-trivial property $P\_1$ and we are asking weather it satisfies another no-trivial property $P\_2$. For instance, in the 3-edge coloring example, the family of triples $F$ must represent the edges incident on the nodes of a cubic graph.

# Answer
I think your "non-trivial" property would need to be a property of *sets* of triples, not of triples themselves; i.e. you need that there are an infinite number of *sets* of triples that satisfy and do not satisfy the property.

Call a triple consists of 3 identical elements a 3-clone. Checking that a triple is a 3-clone can obviously be done in linear time, and checking that a set of triples are all 3-clones can also be done in linear time, because checking each triple is independent of every other triple. And there are an infinite number of 3-clones, and an infinite number of non-3-clone triples; so straightforwardly there are infinite numbers of sets of 3-clones and sets that aren't sets of 3-clones.

I think you need to strengthen the definition of non-triviality; any property of triples that is non-trivial can be lifted to a fairly boring non-trivial property of sets of triples, and there are lots of non-trivial properties of triples that are trivially easy to decide. Even the property of whether the first element of the triple is `1` works. I think the "interesting" properties of sets of triples are not just independently decidable for each triple and then combining the decisions. I'm not sure how to go about expressing that constraint in a rigorous way though.

As for a survey on the subject, I'm afraid I'd never heard of characterising NP-complete problems as properties of sets of triples, so I can't do much for you there.
> 3 votes

# Answer
Let $S \subseteq \mathbb{N}^3$ with $|S| \< \infty$ and $P\_1(S)$ where

$\quad \displaystyle P\_1(S)\ \ :\Longleftrightarrow\ \ \forall (i,j,k)\in S. i,j,k \text{ mutually coprime }.$

$P\_1$ is clearly non-trivial as requested. We say furthermore

$\quad \displaystyle P\_2(S)\ \ :\Longleftrightarrow\ \ \forall (i,j,k)\in S.\ i + j + k \text{ prime}.$

Clearly, $P\_2$ is non-trivial as there are both infinitely many primes and non-primes ($2\mathbb{N}$).

$P\_2$ is decidable in polynomial time as $S$ is finite and both addition and check for primality are polynomial.

As requested, consider this small example of a set of triples that fulfills $P\_1$ and $P\_2$:

$\quad \\{(1,3,7),(1,5,7),(1,5,11),(1,3,13),(5,7,19)\\}$
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Find shortest paths in a weighed unipathic graph
A directed graph is said to be *unipathic* if for any two vertices $u$ and $v$ in the graph $G=(V,E)$, there is at most one simple path from $u$ to $v$.

Suppose I am given a unipathic graph $G$ such that each edge has a positive or negative weight, but contains no negative weight cycles.

From this I want to find a $O(|V|)$ algorithm that finds all the the shortest paths to all nodes from a source node $s$.

I am not sure how I would go about approaching this problem. I am trying to see how I could use the fact that it contains no negative weight cycles and of course at most one simple path between any node $u$ to $v$.

# Answer
### Choose a data representation

First, look at the size of the result. You want the collection of shortest paths from $s$ to every other node. Unless the average length of a path is bounded by a constant (which it isn't: any list is unipath, and if you take the root for $s$ the total length of the paths is $n(n-1)/2$ where $n$ is the length of the list), you'll need to be careful in your data representation: the structure containing the paths will need to use sharing between paths.

> Excluding cycles, there is a single path from $s$ to any other node $u$. If that path goes through an intermediate node $t$, then the first segment of the path is the desired path from $s$ to $t$.

I propose to store the result in an array, indexed by nodes numbered from $0$ to $|E|-1$, with $s=0$. Each element in the array stores the index of the previous node on the path to that node (use e.g. $-1$ as a special marker for nodes that are unreachable from $s$). The path from $s$ to $t$ will be $(s=R\[\ldots R\[t\]\ldots\],\ldots,R\[R\[t\]\],R\[t\],t)$.

### Traverse the graph

Initialize $R$ to all $-1$.

Perform a depth-first or breadth-first traversal of the graph starting from $s$. Each time a node $u$ is reached, set $R\[u\]$ to its predecessor.

Since there are cycles, a node might be reached more than once. Having $R\[u\] \ne -1$ indicates that $u$ has already been visited.

### Prove the correctness

> Because of the unipathic property, it doesn't matter how we reach each node, as long as we haven't completed a cycle. There is only one simple path.

### Prove the complexity

The algorithm may reach each node more than once, so it's not clear that its complexity is $O(|V|)$. The work done is in fact $\Theta(|E\_0|)$ where $V\_0$ are the edges that are reachable from the source. More precisely, we reach a node more than once only in one circumstance: if the node is the first that we reach on a particular cycle, and in this case we reach it twice (once from a simple path, and once after completing the cycle).

Well then. Let's prove that in a unipathic graph, the number of elementary cycles grows at most linearly with the number of nodes. (An elementary cycle is one that does not contain a shorter cycle.) In the following discussion, I'll assume that the graph has no self-edge (no edge from a node to itself; such edges are irrelevant for the path construction anyway).

Unipathic graphs can have cycles, but in a very constrained way. It would be nice if we could somehow associate each cycle to a distinct node (or at least, at most a bounded number of cycles per node). Can cycles share a node? Unfortunately, yes.

> You can have $m$ cycles all sharing one node $a$ and no other nodes. The resulting graph is unipathic. With cycles of length 2, this is a star pattern with a central node $a$ and any number of nodes $b\_i$ such that $\forall i, a \leftrightarrows b\_i$.

So we'll need to work harder. Well, let's try to prove it inductively. Let $\\#V(G)$ be the number of nodes in a graph $G$, $\\#E(G)$ the number of edges and $\\#C(G)$ the number of elementary cycles that aren't self edges. I assert that if $G$ is unipathic and not empty then $\\#C(G) \le \\#V(G)-1$.

For a graph with one or two nodes, this is obvious. Suppose the assertion holds for all graphs such that $\\#V(G) \< n$ and let $G$ be a unipathic graph with $n$ nodes. If $G$ has no cycle, $0 = \\#C(G) \< \\#V(G)$, case closed. Otherwise, let $(a\_1,\ldots,a\_m)$ be an elementary cycle.

> Collapse the cycle: let $G'$ be the graph whose nodes are those of $G$ minus $\\{a\_1,\ldots,a\_m\\}$ plus a node $a$ and whose edges are all the edges of $G$ not involving the $a\_i$'s, plus $a \rightarrow\_{G'} b$ whenever $\exists i, a\_i \rightarrow\_G b$ and $b \rightarrow\_{G'} a$ whenever $\exists i, b \rightarrow\_G a\_i$. Every path in $G'$ induces a path in $G$ (if the path involves $b \rightarrow a \rightarrow c$, then replace this by $b \rightarrow a\_i \rightarrow a\_{i+1} \rightarrow \ldots \rightarrow a\_j \rightarrow c$ in $G$). Therefore $G'$ is unipathic. Furthermore, since cycles in $G$ do not share edges, $G'$ has all the cycles in $G$ except for the one we eliminated: $\\#C(G') = \\#C(G)-1$. By induction, $\\#C(G') \le \\#V(G')-1$. Since $\\#V(G') = \\#V(G) - m + 1$, we have $\\#C(G) = \\#C(G')+1 \le \\#V(G) - m = n-m \le n-1$.

This concludes the proof. The traversal follows at most $2|V|-2$ edges.
> 10 votes

---
Tags: algorithms, graphs
---


# Question
Title: Is there an equivalent of van Emde Boas trees for ropes?
Someone I know is planning on implementing a text editor in the near future, which prompted me to think about what kind of data structures are fast for a text editor. The most used structures are apparently ropes or gap buffers.

Van Emde Boas trees are just about the fastest priority queues around, if you don't mind an upper bound on the number of items you can put into it and a large initialization cost. My question is whether there exists some data structure that is just as fast as the van Emde Boas tree, but supports text editor operations.

We only need to support up to $m$ characters in our data structure (so if $\log m = 32$, then we support up to 4GB worth of ASCII characters). We are allowed $\sqrt{m}$ time to initialize a new data structure. We'd like to support the following operations:

* Insert a character at position $i$ in $O(\log \log m)$ (and thereby increasing the position of every subsequent character by 1).
* Delete a character at position $i$ in $O(\log \log m)$.
* Return the character at position $i$ in $O(\log \log m)$.

So, insert(0,'a') followed by insert(0,'b') results in "ba".

Even better would be this:

* Return a 'pointer' to some index $i$ in $O(\log \log m)$.
* Given a 'pointer', return the character at this position in $O(1)$.
* Given a 'pointer', remove the character at this position in $O(1)$.
* Given a 'pointer', add a character at this position in $O(1)$ and return a pointer to the following position.
* (optional) Given a 'pointer', return a 'pointer' to the next/previous character in $O(1)$.

# Answer
Fredman and Saks show in "The cell probe complexity of dynamic data structures" that you cannot do better than $\Theta\left(\frac{\lg m}{\lg \lg m}\right)$ amortized time for the operations you are looking for. They call this problem "list representation".

Dietz presented a data structure in "Optimal Algorithms for List Indexing and Subset Rank" that achieves this bound.
> 14 votes

---
Tags: data-structures
---


# Question
Title: What are the uses of Markov Chains in CS?
We all know that Markov Chains can be used for generating real-looking text (or real-sounding music). I've also heard that Markov Chains has some applications in the image processing, is that true? What are some other uses of MCs in CS?

# Answer
> 5 votes
Markov Chain Monte-Carlo is a technique for efficiently sampling from a complicated probability distribution. No matter what your (discrete) probability distribution, you can set up a markov chain so that the steady-state distribution of a random walk is the distribution you wish to sample from. You can then approximate this distribution by simulating the random walk on the markov chain. If the markov-chain happens to have small mixing time, then the empirical distribution of your simulation will quickly converge to the steady state distribution, giving you an efficient algorithm for sampling from it.

# Answer
> 4 votes
An important application are Hidden Markov Models which essentially assume the underlying random distribution follows a Markov chain. One exiting application of HMMs is gene prediction in bioinformatics. The task is to consume a long (as in millions of symbols) DNA sequence and predict where important parts (genes) are located. One approach is using a Hidden Markov Model that is trained to model a certain distribution.

A related, but more concise problem is detecting when an unfair die is used in a casino. Assume that the game master switches between fair and unfair dice with a certain probability $p$ after every roll. This can be modelled like this:

\[source\]

States `fair` and `unfair` have *emission* probabilities for die rolls; in state `fair`, every number between $1$ and $6$ is emitted with probability $\frac{1}{6}$, in state `unfair` something different happens. All these probabilities can be trained , either using observed relative counts if we have access to some roll histories (and when which die was used) or using for instance forward-backward algorithm if we have not.

For a given sequence of die rolls, Viterbi algorithm can be used to obtain the most likely underlying path that emits this sequence; from this path, we can read off when the unfair die was (most likely used). If we do this online, we can guess when the unfair die is used and exploit this knowledge.

# Answer
> 3 votes
> Markov chains appear everywhere. Why? Because the model is so general: You are interested in a large set of objects, and you can handle local manipulations on these objects, eg. modifying an object slightly to get a new one. You want to study global properties of this set of objects, such as its approximate size. This very natural problem, which is an abstraction of problems in many fields, can be modeled by a random walk on a graph, the nodes of which are the objects of interest. Starting from an arbitrary node, an elementary step is to move to a neighboring node with a certain (say uniform over all neighbors) probability. This very simple elementary step applied many times, results in a wonderful phenomenon- the distribution over the nodes converges to a limiting distribution depending only on the structure of the graph, and not on the arbitrary node we started with. This limiting distribution can tell us a lot about the global properties of the set of objects of interest, such as the size or structure of the graph. The time it takes for convergence, or the "mixing time" is thus of crucial importance for algorithmic and modeling applications. One of the more active fields in probability and theoretical computer science is the analysis of Markov chains for various applications. Many clever and beautiful mathematical tools have been developed to analyze the mixing time in the various cases.

Source: http://www.cs.huji.ac.il/~doria/markovchains.huji2002.html

# Answer
> 2 votes
In a nutshell, Markov chains are used to model correlated stochastic processes; a broad class of signals. If the value of the signal at any moment can be well approximated by a function of the signal values at a limited number of the the preceding moments, then a Markov model is appropriate.

---
Tags: probability-theory, markov-chains
---


# Question
Title: How to convert an NFA with overlapping cycles into a regular expression?
If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as alternatives and so on. But what to do in this case:

\[source\]

The overlapping cycles make it hard to see what this automaton accepts (in terms of regular expressions). Is there a trick?

# Answer
Rather than "reading off" you should employ one of several canoncial methods to do this. By far the nicest I have seen is one that expresses the automaton as equation system of (regular) languages which can be solved. It is in particular nice as it seems to yield more concise expressions than other methods.

I wrote this document explaining the method for students last summer. It directly relates to a specific lecture; the reference mentioned is typical definition of regular expressions. A proof of Arden's Lemma (a needed result) is contained; one for correctness of the method is missing. As I learned of it in lecture I don't have a reference, sadly.

In short: For every state $q\_i$, create the equation

$\qquad \displaystyle Q\_i = \bigcup\limits\_{q\_i \overset{a}{\to} q\_j} aQ\_j \cup \begin{cases} \\{\varepsilon\\} &,\ q\_i \in F \\ \emptyset &, \text{ else}\end{cases}$

where $F$ is the set of final states and $q\_i \overset{a}{\to} q\_j$ means there is a transition from $q\_i$ to $q\_j$ labelled with $a$. If you read $\cup$ as $+$ or $\mid$ (depending on your regular expression definition), you see that this is an equation of regular expressions.

Solving it (using Arden's Lemma) yields one regular expression $Q\_i$ for every state that describes exactly those words that can be accepted starting in $q\_i$; therefore $Q\_0$ (if $q\_0$ is the initial state) is the desired expression.

Application to the given automaton is left as an exercise; a complete example is included in above linked document.

*See also here where I posted a similar answer.*
> 6 votes

# Answer
If there was just a chain of states with no loop, would you know what to do?

If there was a simple loop without this overlapping branching, would you know what to do?

(If the answer is “no”, think about these cases first.)

Now, the idea is to transform the automaton progressively to put it in a form where you can spot those patterns: chains, loops, and diverging paths that reconverge in the end (leading to alternation). At every step of the transformation, take care that the transformed automaton still recognizes the same language.

Keep in mind that this is a **non**-deterministic automaton. The one you posted happens to be deterministic, but it doesn't have to stay that way when you transform it.

Since the sticky point is that $q\_2$ can be reached from two different points, split it in two. Keep $q\_1 \xrightarrow{f} q\_2 \xrightarrow{g} q\_3$, remove the transition from $q\_4$ to $q\_2$ and add instead a new state $q\_5$ with transitions $q\_4 \xrightarrow{j} q\_5 \xrightarrow{g} q\_3$. Now you should be able to spot a pattern.

> If you still have trouble at this point, notice that the loop involving $q\_3,q\_4,q\_5$ corresponds to a simple regular expression. When you get to $q\_3$, you can make as many runs around this loop as you like. In some sense (which can be made technical), you can replace the state $q\_3$ by the regular expression $(hjg)^\*$.

Take care to check which states are final. It can help to not worry about this at first and make one big loop, then duplicate parts that terminate partway through the loop.

This is not necessarily the most efficient technique or the one that generates the simplest regular expression, but it's simple.
> 3 votes

# Answer

> 3 votes

---
Tags: algorithms, formal-languages, finite-automata, regular-expressions
---


# Question
Title: What are the conditions for a NFA for its equivalent DFA to be maximal in size?
We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in worst case gives us $2^S$ states, if our NFA had $S$ states.

My question is: what is determining the worst case scenario?

---

Here's a transcription of an algorithm in case of ambiguity:

Let $A = (Q,\Sigma,\delta,q\_0,F)$ be a NFA. We construct a DFA $A' = (Q',\Sigma,\delta',q'\_0,F')$ where

* $Q' = \mathcal{P}(Q)$,
* $F' = \\{S \in Q' | F \cap S \neq \emptyset \\}$,
* $\delta'(S,a) =\bigcup\_{s \in S} (\delta(s,a) \cup \hat \delta(s,\varepsilon))$, and
* $q'\_0 = \\{q\_0\\} \cup \hat \delta(q\_0, \varepsilon)$,

where $\hat\delta$ is the extended transition function of $A$.

# Answer
The algorithm you refer to is called the Powerset Construction, and was first published by Michael Rabin and Dana Scott in 1959.

To answer your question as stated in the title, there is no *maximal* DFA for a regular language, since you can always take a DFA and add as many states as you want with transitions between them, but with no transitions between one of the *original* states and one of the new ones. Thus, the new states will not be reachable from the initial state $q\_0$, so the language accepted by the automaton will not change (since $\hat\delta(q\_0,w)$ will remain the same for all $w\in\Sigma^\*$).

That said, it is clear that there can be no conditions on a NFA for *its* equivalent DFA to be maximal, since there is no *unique* equivalent DFA. In contrast, the **minimal** DFA is unique up to isomorphism.

---

A canonical example of a language accepted by a NFA with $n+1$ states with equivalent DFA of $2^n$ states is $$L=\\{w\in\\{0,1\\}^\*:|w|\geq n\text{ and the \\(n\\)-th symbol from the last one is 1}\\}.$$ A NFA for $L$ is $A=\langle Q,\\{0,1\\},\delta,q\_0,\\{q\_{n+1}\\}\rangle$, with $\delta(q\_0,0)=\\{q\_0\\}$, $\delta(q\_0,1)=\\{q\_0,q\_1\\}$ and $\delta(q\_i,0)=\delta(q\_i,1)=\\{q\_{i+1}\\}$ for $i\in\\{1,\ldots,n\\}$. The DFA resulting of applying the powerset construction to this NFA will have $2^n$ states, because you need to represent all $2^n$ words of length $n$ as suffixes of a word in $L$.
> 25 votes

# Answer
The worst-case of $2^{s}$ comes from the number of subsets of states of the NFA. To have the algorithm from Kleene's theorem give an equivalent DFA with the worst-case number of states, there must be a way to get to every possible subset of states in the NFA. An example with two states over alphabet $\\{a, b\\}$ has a transition from the initial state to the sole accepting state on symbol $a$, a transition from the accepting state back to the initial on $b$, and a transition from the accepting state back to itself on either an $a$ or a $b$. The strings $\lambda$, $a$, $b$, and $ab$ lead to subsets $\\{q\_{1}\\}$, $\\{q\_{2}\\}$, $\\{\\}$, and $\\{q\_{1}, q\_{2}\\}$, respectively, and these would need separate states in the DFA Kleene gives.
> 9 votes

# Answer
I believe this is a question at the frontier of knowledge, i.e. basically a research question. From a quick google search, it appears to be mostly open. Also, for many years I have believed it to be important and linked to complexity theory lower bounds. You don't mention directly a statistical analysis but that is what is implied by your question. Here are two examples of statistical studies on DFAs/NFAs that are similar to show the general approach to questions of this type. It appears that basic empirical research into questions like this is still mostly unexplored. Admittedly the 2nd does not relate directly to your question but it's the closest I could find of current research.

To study your question, a statistical attack such as the following could be envisioned. Random NFAs are constructed. Then the minimal DFA is determined. Graph the histogram results of how many DFAs of size $x$ result. Separate out the "large" DFAs based on some threshold. Formulate some metric or measurement of the NFA that gives an estimate of the resulting DFA size.

This metric would be related to graph theory metrics such as edge density etcetera. There is probably some very important graph theory metric or mix of metrics that estimates the "blow-up" but its not immediately obvious to me. I could suggest something like graph coloring metrics or clique metrics maybe. Then test the metric against the two sets "blow-up" vs "not blown-up".

Other answers to your question so far only give an example case of a "blow-up" (useful for a case study) but do not address the key issue of a general metric.

Another area to look at a successfully developed program of empirical research is SAT transition point research. That has developed very deep links to physics and thermodynamics concepts. It seems likely to me that similar concepts are applicable here. For example, one is likely to find analogous transition point type metrics; probably edge density etc. Note parallels to Kolmogorov compressibility theory.

I conjecture also that NFAs that "blow-up" vs those that don't are quite analogous somehow to "hard" vs "easy" instances of NP-complete problems.

Yet another way to study this problem would be to formulate an NFA minimization problem. That is, given a DFA, find the minimal NFA, which last I heard (many years ago) was still an open problem.

---

\[1\] On the performance of automata minimization algorithms Marco Almeida, Nelma Moreira, Rogério Reis

\[2\] Automata Recognizing No Words: A Statistical Approach Cristian S. Calude, Cezar Câmpeanu, Monica Dumitrescu
> 0 votes

---
Tags: formal-languages, automata, regular-languages, finite-automata, nondeterminism
---


title: Ratio of decidable problems

text:
# Question
Title: Ratio of decidable problems
Consider decision problems stated in some “reasonable” formal language. Let's say formulae in higher-order Peano arithmetic with one free variable as a frame of reference, but I'm equally interested in other models of computation: Diophantine equations, word problems from rewriting rules using Turing machines, etc. An answer expressed in any classical formalization would be fine, though if you know how much the choice of formalization influences the answer, that would also be interesting.

Given the length $N$ of the statement of a decision problem, we can define the number $D(N)$ of decidable statements of length $N$ and the number $U(N)$ of undecidable statements of length $N$.

What is known about the relative growth of $U(N)$ and $D(N)$? In other words, if I take a well-formed decision problem at random, what is the probability of its being decidable for a given statement length?

<sub> Inspired by this question which asks whether “most problems and algorithms \[are\] decidable”. Well, if you don't filter by interest, are they? </sub>

# Answer
> 2 votes
See Chaitin's research into Omega that shows, as I understand it, that undecidable problems are \[paraphrasing\] quite numerous, rampant or dense among statements chosen at random. However you have to be careful how you define $U(N)$ and $D(N)$ because they may be actually uncomputable functions. There is also some connections to busy beaver research. Identifying decidable and undecidable statements seems quite analogous to proving that busy beavers halt or do not halt. (e.g. some of all statements are in the form, “busy beaver \[x\] halts”).

---
Tags: computability, undecidability
---


# Question
Title: How does a two-way pushdown automaton work?
Note that by "two-way pushdown automaton", I mean a pushdown automaton that can move its reading head both ways on the input tape.

I recently had the question of determining the computational power of two-way PDAs in the Chomsky hierarchy. I don't entirely understand two-way PDAs, but I can see how with the ability to read in both directions on the input, it could handle languages of the form $L=\\{0^n 1^n 2^n\\}$. I can't say that for sure, but it seems that would make it powerful enough to least handle context-sensitive languages.

This is all a guess because I don't know exactly how they work. Can someone explain the process of how a two-way PDA operates, maybe even on my example?

UPDATE:

> The model is a generalization of a pushdown automaton in that two-way motion is allowed on the input tape which is assumed to have endmarkers.

# Answer
> 7 votes
A two-way PDA can accept the canonical context-sensitive language $\\{0^{n}1^{n}2^{n} | n \geq 1\\}$. Such an automaton could work by checking whether the largest prefix of the form $0^{i}1^{j}$ had $i = j$, using the stack, after which it could empty the stack, and check whether the largest suffix of the form $1^{j}2^{k}$ had $j=k$, again using the stack. So $CFL \subsetneq L(2PDA)$.

In more detail, the 2-way PDA would read from left to right as many 0 symbols as it finds, pushing a 0 onto the stack for each 0 it reads on the input tape. If it reads any 0 symbols and finds a 2 symbol before finding a 1, it crashes. When it gets to a 1, it changes state, and begins reading all the 1 symbols, until it comes to a 2. If it reads a 0 symbol while doing this, it crashes. It pops a 0 symbol from the stack for each 1 it reads on the input tape. If, when it reaches the first 2, the stack is empty, the PDA moves the tape head to the end of the input tape. Otherwise, it crashes. If it encounters any 0s or 1s, it crashes. It then reads the input tape left to right, pushing a 2 for each 2 it reads on the input tape. When it gets to a 1, it switches states and begins reading 1s and popping 2s. If, when it gets to a 0, the stack is empty, the string is accepted.

The machine would crash if the input string weren't a string of 0s, followed by 1s, followed by 2s; and it would have crashed if the longest prefix of 0s and 1s weren't in the canonical CFL $\\{0^{n}1^{n}\\}$; and it would have crashed if the longest suffix of 1s and 2s weren't in the canonical CFL $\\{1^{n}2^{n}\\}$. In this case, the ability to rewind the tape allows you to accept languages which are the intersection of CFLs, by essentially stringing PDAs together, and rewinding the tape in between.

Therefore, the languages accepted by two-way PDAs are trivially closed under intersection, a property not shared by languages accepted by regular PDAs.

---
Tags: formal-languages, computability, automata, pushdown-automata
---


# Question
Title: Turing Completeness + Dataflow Unification = Arbitrarily invertible (pure, nonrecursive) functions?
Assume we are working in a Turing-complete, referentially-transparent, higher-order language that supports arbitrary dataflow unification. Shouldn't it then be possible to construct the following function (using Haskell-like syntax, because that's what I'm most familiar with)?

```
-- Takes an arbitrary pure function and constructs its inverse.
-- If the passed-in function is recursive, the result is not guaranteed to terminate
invert :: (a -> b) -> b -> a
invert f r = declare a in let r =|= f a in a

```

(if `=|=` is the dataflow unification operator).

Is this indeed possible in such a language? If so, why haven't people leapt at this before? If not, where did my reasoning go wrong?

# Answer
> 6 votes
There is an even simpler definition of invert that works for all countable domains `a`, no exotic execution models needed:

```
invert(f,y) =
  for each x in a:
    if f(x) == y: return x

```

For example if the domain `a` consists of all binary trees, you have to have a method for enumerating binary trees. Functional logic languages are basically an optimization of the above method. They use lazy backtracking search over `a` instead of naive brute force search. Unfortunately, the preceding is not strictly true. The execution engines of some functional logic languages can get stuck in an infinite portion of the search space, which means that their `invert` will not terminate for all inputs.

Contrary to popular belief, the preceding algorithm works even for higher order data. On first sight, this would seem to be impossible, because a function domain is not countable. For example the domain `int -> int`. However, terminating programs can only invoke a function finitely many times. In other words, the continuation of `g = invert(f,y)` can only invoke `g` finitely many times. So if there is a function that would be a valid choice for `g`, there also is a *finite* function that is a valid choice for `g`, namely the function that only works on the values that the rest of the program actually calls it on. So in fact we only have to search over all finite functions, and this is a countable domain! Just represent a function as a finite list of `(input,output)` pairs, and when calling such a function with an input that's not in the list, backtrack back into the loop and continue with the next finite function (this jumping back into the loop can be done with continuations).

Rephrased so that it may be easier to understand: if there is no finite function that does it, then there is also no infinite function that does it, because the only way to observe the difference between a finite and an infinite function is to call it infinitely many times, which would mean that the program didn't terminate in the first place.

Note that, as a special case, we can also invert functions on infinite lazy data structures. And as a special case of this, we have Seemingly impossible functional programs. As you can see, in some sense, it is *easier* to invert a function on a domain containing infinitely large values than on a domain containing finite values! For instance we can compute an inverse on the domain `(int -> bool) -> bool` *or detect that such an inverse does not exist* in *finite time*, whereas we cannot detect for an arbitrary function of `int -> int` that it is not invertible at, say, y = 3. So in some sense, the space of all integers is harder to search than the space of all functions `int -> bool`! Not despite, but *because* the latter contains infinitely large objects.

# Answer
> 7 votes
Dataflow unification behaves as you expect on first-order data (numbers, booleans, lists, trees, etc.) but can fail for higher-order data such as functions. In general, unifying functions requires using full higher-order unification, which has terrible performance, up to and including frequent failure to terminate (as it must, since otherwise it would solve the halting problem).

Higher-order logic languages such as $\lambda$-Prolog and Curry typically use restricted forms of higher-order unification, to get better efficiency at the price of completeness.

---
Tags: programming-languages
---


# Question
Title: How does a wifi password encrypt data using WEP and WPA?
How does the password that we enter (to connect to a wireless network) encrypt the data on the wireless network?

Through my reading I am not sure if the password that we enter is the same as the passphrase. If that is right then how can the passphrase generate the four WEP keys?

I understand how the four keys work in WEP and how they encrypt the data. Also, I know how WPA's keys encrypt the data but the only thing I have to know is:

> what is the benefit of the password that we enter to get access to the network, and how does this password help in encrypting the data?

# Answer
> 8 votes
WEP uses the stream cipher $RC4$ for confidentiality and the CRC-32 checksum for integrity. All data frames sent by a router in a WEP protected network are encrypted. When a router sends a packet, the following steps are executed.

1. The router picks a $24$-bit value called the initialization vector $IV$. A new $IV$ is used for every packet.
2. The $IV$ is prepended to the key (password you enter) and forms the per packet key $K$.
3. A CRC32 checksum of the payload is produced and appended to the payload. This checksum is called an Integrity Check value ($ICV$).
4. The per packet key $K$ is fed into the $RC4$ stream cipher to produce a key stream $X$ of the length of the payload with checksum.
5. The plaintext with the checksum is XORed with the key stream and forms the cipher text of the packet.
6. The cipher text, the $IV$ and some additional header fields are used to build a packet, which is now sent to the receiver.

**Weaknesses of WEP and why to choose WPA**

An $IV$ size of $24$-bits provides only $16$ million different key streams for a given WEP key. If the $IV$ is reused, the key stream for a given $IV$ is found and hence an attacker can decrypt subsequent packets that were encrypted with the same $IV$ even without knowing the WEP key.

Since there are only $16$ million $IV$ values, how the $IV$ is chosen makes a big difference in the attacks based on $IV$. As explained above, some implementations choose $IV$s randomly and some are assigned sequentially. With a randomly chosen $IV$, there is a $50\\%$ chance of reuse after less than $5000$ packets and if assigned sequentially, collisions are inevitable if the values are re-initialized.

WEP’s integrity check field is implemented as a CRC-32 checksum, which is part of the encrypted payload of the packet. However, CRC-32 is linear, which means that it is possible to compute the bit difference of two CRCs based on the bit difference of the messages over which they are taken. In other words, flipping bit ‘$n$’ in the message results in a deterministic set of bits in the CRC that must be flipped to produce a correct checksum on the modified message. An attacker can therefore change a bit in an encrypted message and know which bit of the encrypted $ICV$ will change as a result.

# Answer
> 3 votes
As explained in Wikipedia:

> If ASCII characters are used, the 256 bit key is calculated by applying the PBKDF2 key derivation function to the passphrase, using the SSID as the salt and 4096 iterations of HMAC-SHA1.

For more information see WPA Key Calculation

---
Tags: cryptography, computer-networks, encryption, security
---


title: Is Directed Graph a Graph?

text:
# Question
Title: Is Directed Graph a Graph?
I came across an issue with the definition of a (directed) graph in Sipser's Introduction to the theory of computation, 2nd Ed.

On pp.10, An **undirected graph**, or simply a **graph**, is a set of points with lines connecting some of the points. The points are called nodes or vertices, and the lines are called edges, ...

On the same page,

> **No more than one edge is allowed between any two nodes**.

On pp.12,

> If it has arrows instead of lines, the graph is a **directed graph**,...

In Figure 0.16 on pp.12, there is an example of a directed graph, an arrow from node 1 to node 2 and an arrow from node 2 to node 1.

So, we have two arrows in opposite direction between two nodes.

I understand all of these basics.

My question is,

> Is directed graph a graph?

# Answer
> 12 votes
As is often the case, using a formal definition is helpful:

Let $V$ a finite set. $G=(V,E)$ is

* a *graph* if $E \subseteq \left\\{\\{v\_1, v\_2\\} \mid v\_1, v\_2 \in V \right\\}$ and
* a *digraph* if $E \subseteq \left\\{(v\_1,v\_2) \mid v\_1, v\_2 \in V\right\\}$.

Note the central difference: edges are sets in graphs and pairs in digraphs. In particular, simpleness is implied by this definition. Extending the definition is also easy:if $E$ was a multiset, you could have non-simple graphs. If the edges had more than two components, you'd have hypergraphs.

*Disclaimer:* People define (di)graphs in different ways; this is one very common variant. For example, if you are uncomfortable with digraphs (formally) not being graphs, you define them like this:

Let $V$ a finite set and $E \subseteq V^2$. We call the pair $G=(V,E)$ a *graph*. We say

* $G$ is *undirected* if and only if $(v\_1,v\_2) \in E \Longleftrightarrow (v\_2,v\_1) \in E$ and
* $G$ is *directed* otherwise.

This defines undirected graphs as special cases of directed graphs. Note that with this definition, extensions to *labeled* graphs (edges get markings) may be awkward: We want the complete digraph with to be different from the complete undirected graph (as the former has two labeled edges between between every pair of nodes, the latter only one); by this definition, they are the same. Note how the first definition I gave circumvents this issue nicely; sometimes definitions are (re)made with later needs in mind.

# Answer
> 9 votes
The word 'graph' has two meanings: it can be a shorthand for 'undirected graphs' (like how your book defines it) or it can refer to something that is 'graph-like', such as a directed or an undirected graph. The first meaning is most common.

Directed graphs and undirected graphs are not the same thing (arrows versus lines), although one can view undirected graphs as directed graphs if you replace every (undirected) edge by two arrows, one for either direction (so A -- B becomes A \<-\> B).

Additionally, for some problems, you can transform a directed graph to a similar-looking undirected graph on which your problem has the same solution. The proof that the Hamiltonian cycle problem is NP-hard on undirected graphs is usually done by a reduction from the directed version, by transforming the directed graph into an undirected graph that will have a Hamiltonian cycle if and only if the original graph had one.

---
Tags: graphs
---