# Question
Title: Is there a context free, non-regular language $L$, for which $L^*$ is regular?
I know that there are non-regular languages, so that $L^\*$ is regular, but all examples I can find are context-sensitive but not context free.

In case there are none how do you prove it?

# Answer
> 21 votes
$L = \\{a^n b^n \mid n\in\mathbb{N}\\}$ is context-free but not regular (classical example). So is $L' = \\{a^n b^n \mid n\in\mathbb{N}\\} \cup \\{a,b\\}$.

$L'^\ast = \\{a,b\\}^\ast$ is regular.

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


title: An oracle to separate NP from coNP

text:
# Question
Title: An oracle to separate NP from coNP
How to prove that $\mathsf{NP}^A \neq \mathsf{coNP}^A$ ? I am just looking for a such oracle TM $M$ and a recursive language $L(M) = L$ for which this holds.

I know the proof where you show that there is an oracle $A$ such that $\mathsf{P}^A \neq \mathsf{NP}^A$ and an oracle $A$ such that $\mathsf{P}^A = \mathsf{NP}^A$. I have a hint that I should find such oracle $A$ by extending the proof of $\mathsf{P}^A \neq \mathsf{NP}^A$ but wherever I search and read, it is "obvious" or "straightforward" everywhere but I just do not see how prove it at all.

# Answer
As Max said the modification is not difficult, I suggest that you do not read the rest of this answer and think about the problem a little bit more, there is only one part that needs modification and remembering the definition of when a $\mathsf{coNP}$ machine accepts will help you fix that part.

I will explain the required modification below, but first let's have a brief view at the original proof.

In the original proof $A=\bigcup\_n A\_n$ is built in steps where at step $i$ with make sure that $i$th machine in $\mathsf{P}$, $M\_i$, doesn't decide the language $\\{x \mid \exists y\in A \ |x|=|y| \\}$ correctly. Note that the set is in $\mathsf{NP}^A$.

We achieve this by simulating $M\_i$ using the part of $A$ we have built on a $0^m$ where $m$ is large enough (the string is longer than strings considered in previous steps). $M\_i$ accepts, we don't add anything, if it rejects we add a string of length $m$ that $M\_i$ doesn't make a query to the set (Such a string exists since there are exponentially many strings of length $m$ but $M\_i$ cannot ask about all of them in polynomial time). We will not modify this part of $A$ in future steps (i.e. strings of length $m$ or less will stay the same). This makes sure that $M\_i^A$ will not decide the language correctly and completes the proof.

> Now, assume that the machines $M\_i$ were in $\mathsf{coNP}$ in place of $\mathsf{P}$. We need to modify the proof to make sure that $M\_i^A$ will not recognize $L$. If it is accepting we keep $A$ as before and everything works fine as in the original proof. If it rejects, we need to add a string to the set to make sure it doesn't answer correctly. We still can simulate $M\_i$ with the part of $A$ we have, the problem is that $M\_i$ might query all strings of length $n$. Here the way a $\mathsf{coNP}$ machine works becomes important. It accepts if and only if *all* computation paths accept. Since it is rejecting in this case, there is a computation path that is rejecting. As long as we keep this path intact everything will work, so we only need to keep the answers to the queries in that path the same. The number of queries in this path is polynomial (since the machine runs in polynomial time), so there are strings of length $m$ that the path doesn't query about, just add one of them to $A$ and the rest of the proof works as before.

The steps are algorithmic, so the set $A$ is recursive (the essential part of the construction is being able to simulate machines which can be done in say $\mathsf{DSpace}(n^{\omega(1)})$).
> 9 votes

# Answer
You may also wish to consult the text *Computational Complexity* by Christos Papadimitriou. Specifically Chapter 14, Section 3 that delves into oracles. Proofs for $P^A = NP^A$ and $P^B \not= NP^B$ for some oracles $A$ and $B$ for instance are provided in detail, and may be helpful for your primary problem. Hope that helps.
> 3 votes

---
Tags: complexity-theory, relativization
---


# Question
Title: Efficient map data structure supporting approximate lookup
I'm looking for a data structure that supports efficient approximate lookups of keys (e.g., Levenshtein distance for strings), returning the closest possible match for the input key. The best suited data structure I've found so far are Burkhard-Keller trees, but I was wondering if there are other/better data structures for this purpose.

Edit: Some more details of my specific case:

* Strings usually have a fairly large Levenshtein difference from each other.
* Strings have a max length of around 20-30 chars, with an average closer to 10-12.
* I'm more interested in efficient lookup than insertion as I will be building a set of mostly static data that I want to query efficiently.

# Answer
> 19 votes
What you are looking for is "approximate near neighbor search" (ANNS) in the Levenshtein/edit distance. From a theoretical perspective, edit distance has so far turned out to be relatively hard for near-neighbor searches, afaik. Still, there are many results, see the references in this Ostrovsky and Rabani paper. If you are willing to consider alternative distance metrics for which there are simpler and better solutions, move on to the next paragraph. For ANNS in edit distance, there is a result due to Indyk, who shows how to build a data structure of size $n^{O(\sqrt{d})}$ that answers any query in time $O(d)$ and reports a string which is at most three times further than the string nearest to the query string (this generalizes to size $n^{O(d^\epsilon)}$ and approximation $3^{1/\epsilon}$). Here $n$ is the number of strings and $d$ is the maximum length of any string. The Ostrovsky and Rabani paper I linked above improve this result by mapping strings to vectors so that the $\ell\_1$-distance (a kind of natural geometric distance similar to the euclidean distance) between vectors approximates the edit distance between the corresponding strings (this is called a "low-distortion embedding"). Once this is done, an ANNS data structure for $\ell\_1$ can be used, and these turn out to be more efficient (see next paragraph).

If you are willing to consider other distances, then locality sensitive hashing (LSH) does a great job. Locality sensitive hashing is a technique pioneered by Indyk and Motwani for solving the ANNS problem, where points that live in a high-dimensional space (read long vectors, long strings, etc.) are hashed into a small number of buckets so that points that are near each other are mapped to the same bin with good probability and points that are far from each other are mapped to different bins, also with good probability. There is a great and very accessible survey article by Indyk and Andoni in CACM. This technique is simple and fast, and has small space requirements; there is code out there too (I think the article links to the code). It works well for things like Hamming distance (and in certain regimes $\ell\_1$ distance) and Euclidean distance, cosine distance. Also, Muthu and Sahinalp design LSH schemes for a very natural generalization of edit distance, the *block edit distance* (where a some edit operations can operate on a block of symbols).

This kind of question is a good fit for cstheory.SE. There is a related question there, but it seems to ask for exact near neighbor.

# Answer
> 13 votes
The data structures you are interested in are metric trees. That is, they support efficient searches in metric spaces. A metric space is formed by a set of objects and a distance function defined among them satisfying the triangle inequality. The goal is then, given a set of objects and a query element, to retrieve those objects close enough to the query.

Since search problems are literally everywhere in computer science, there is a *huge* amount of different metric trees. However, they can be divided at least into two groups: pivot-based and clustering based (and surely there are hybrids as well). A good survey is E. Chavez et al., Searching in Metric Spaces, 2001. See for example Chapter 5: Current Solutions to Metric Spaces, page 283.

There, in Table 1, Chavez et al. consider 16 different metric trees. They present space complexity, construction complexity, claimed query complexity and extra CPU query time for each (if known). If you don't care about the construction complexity too much, the query complexity for the BK-tree is $O(n^\alpha)$, where $0 \< \alpha \< 1$ depending on the range of the search and the structure of the space. Or if you don't have a huge number of elements, have a look at AESA (approximating eliminating search algorithm). It is unacceptedly slow to build and store for huge spaces ($O(n^2)$ time and space), but it has been shown experimentally to have $O(1)$ query time.

Chavez et al. also give a nice overview of the other trees, and naturally more references if any one in particular sparks your interest. In practice, the performance of different trees is often evaluated experimentally. This I think depends a lot on the structure of the space. Therefore it is hard to say which tree in particular would be the most efficient in your case. Nevertheless, I think it is a good idea to go with the easiest one first. If BK-trees are the easiest one to build, try them out first. If they don't satisfy your requirements, invest time (and perhaps programming time) into gathering more facts about your space that could help you make more informed decisions.

---
Tags: data-structures, strings, efficiency
---


# Question
Title: Simple explanation as to why certain computable functions cannot be represented by a typed term?
Reading the paper An Introduction to the Lambda Calculus, I came across a paragraph I didn't really understand, on page 34 (my italics):

> Within each of the two paradigms there are several versions of typed lambda calculus. In many important systems, especially those a la Church, it is the case that terms that do have a type always possess a normal form. By the unsolvability of the halting problem this implies that not all computable functions can be represented by a typed term, see Barendregt (1990), Theorem 4.2.15. This is not so bad as it sounds, because in order to find such computable functions that cannot be represented, one has to stand on one's head. For example in 2, the second order typed lambda calculus, only those partial recursive functions cannot be represented that happen to be total, but not provably so in mathematical analysis (second order arithmetic).

I am familiar with most of these concepts, but not the concept of a partial recursive function, nor the concept of a provably total function. However, this is not what I am interested in learning.

I am looking for a simple explanation as to why certain computable functions cannot be represented by a typed term, as well as to why such functions can only be found 'by standing on one's head.'

# Answer
Given that you do not want to learn precise concepts, here is an intuitive explanation. In the discussion below "function" always refers to a function mapping natural numbers to natural numbers (possibly undefined at some arguments).

Any programming language which has

1. computable syntax and rules of evaluation, and
2. implements every *total* computable function

necessarily implements some *partial* functions.

To see this, suppose it were the case that every definable function in this language were total. Because the language has computable syntax, we can enumerate all definitions of functions (just enumerate all strings and filter out those that cause syntactic errors). Because the rules of evaluation are computable, the second assumption allows us to conclude that in our language we can define the total function `eval(n,m)` which evaluates the `n`-th definable function on `m` (essentially this is an mini-interpreter written in the language itself). But then the function

```
λ k . (1 + eval(k,k))

```

is a total definable function which is different from every total definable function, a contradiction.

The simply typed $\lambda$-calculus satisfies the first condition and it defines only total functions. Therefore it does not satisfy the second condition.

As far as "standing on your head" is concerned, for a strongly-normalizing $\lambda$-calculus it is fairly easy to provide a total function which is not definable in the calculus, namely *the normalization procedure* itself. It is not very important how fancy your strongly normalizing calculus is, it could be the polymorphic $\lambda$-calculus, or Martin-Lof type theory, or the Calculus of constructions. (Exercise: if you could implement the normalization procedure, you could implement `eval` above.)
> 9 votes

# Answer
I find that merijn's answer handles the first part of your question quite well. I shall try to answer the second part: why finding functions that are computable but not representable in the polymorphic $\lambda$-calculus requires "standing on ones head".

I'm afraid it requires some explanation of the concepts that you are not interested in. A *partial recusive function* is a $\lambda$-term which represents a function from $\mathbb{N}$ to $\mathbb{N}\cup\\{\bot\\}$. A $\lambda$-term $t$ applied to the representative of a natural number $n$ is sent to $\bot$ if and only if $t\ n$ does *not* have a normal form. If no number is sent to $\bot$ we say that the function is *total*. Now the idea is that no logical theory $T$ can prove that a term $t$ represents a total function for each total function $t$, there are always "blind spots" where $t$ terminates on all input $n$, but the statement

$$ \forall n, t\ n\ \mbox{terminates}$$

is undecidable in $T$. If the above statement *is* provable in $T$, we say that the function represented by $t$ is *provably total*. That not all total functions are provably total in $T$ is a consequence of (a variant of) the Godel Incompleteness Theorem for $T$.

Now the point is that the *vast majority* program we concretely wish to write (list sorting, graph traversal, operating systems) are not only total functions, but are *provably total* in reasonable logical systems, like Peano Arithmetic.

Now for the polymorphic $\lambda$-calculus. It can be shown that the terms one can type in this calculus are *exactly* the terms which represent the functions provably total in Second Order Peano Arithmetic. Second Order Peano Arithmetic is much, much more powerful than ordinary Peano Arithmetic.

This means by the above explanations that there are terms which are total but not provably total, but such functions are extremely rare, as they are already rare for Peano Arithmetic (and so much rarer in the second-order theory). Hence the "standing on your head" statement.
> 4 votes

# Answer
I'm finding it a bit hard to concisely write down the proof, but I hope this explanation provides you enough intuition to see why simple typed terms cannot represent all untyped terms.

The simply typed lambda calculus is strongly normalising. Every $\beta$ reduction will bring us closer to normal form. When the function $f :: \alpha \rightarrow \beta \rightarrow \gamma$ is applied to a value of type $\alpha$ it will $\beta$ reduce to a function of type $\beta \rightarrow \gamma$. Given a finite number of arguments it takes a finite number of reduction steps to reach $\beta$-normal form , in which there are no further possible reductions.

To contrast this with the untyped lambda calculus. One of the more famous UTLC combinators is the $Y$-combinator:

$Y = λf.(λx.f\\; (x\\; x))\\; (λx.f\\;(x\\;x))$

When we try to reduce the $Y$-combinator the following happens:

$$λf.(λx.f\\; (x\\; x))\\; (λx.f\\;(x\\;x))\\; g$$ $$(λx.g\\;(x\\;x))\\;(λx.g\\;(x\\;x))$$ $$g\\;((λx.g\\;(x\\;x))\\;(λx.g\\;(x\\;x)))$$ $$g\\;(g\\;((λx.g\\;(x\\;x))\\;(λx.g\\;(x\\;x))))$$

No matter what functions we pass in, we get stuck in an infinite sequence of reductions! If we would try to pin a STLC type on the UTLC $Y$-combinator, we quickly find this impossible, because the function application doesn't shrink the type as is required in the STLC. The $Y$-combinator is clearly computable (it represents, using recursion, the concept of an infinite loop), yet it cannot be represented in the STLC, as all STLC terms are strongly normalising.
> 3 votes

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


# Question
Title: Monitoring files in preservation archives
What are efficient and accurate techniques for monitoring the recoverability and integrity of files in very large preservation archives?

In very large archives, the time taken to recompute checksums periodically (scrubbing) is substantial, perhaps taking more than all the available time depending on the read bandwidth available! Also, each access to a preserved file increases the risk of damage due to hardware or software failure. Tapes are most stable in a cold, dark place far from exposure to the hazards of data centers. Disks are most at risk when the read/write head is flying close to the medium. All approaches are probabilistic, so which are most efficient and accurate?

To give the problem specificity, let's assume a fixed probability of local single-bit errors for each medium (one probability for tape, another for disk, SSD, etc) during a standard time period, and ignore all other types of errors (loss of an entire volume, for instance). We can also assume a fixed read bandwidth for each medium.

# Answer
> 1 votes
This is not an answer to the question per se, but an extended comment.

There was an interesting set of slides regarding CERN's Advanced Storage (CASTOR) at CHEP'2010. This is a large mixed media archive with some 25 PB of tape archives (ca. 2010). One of the presentations: "Tape archive challenges" highlights some of the issues that seem to question the assumptions set in the OP.

> Tapes are most stable in a cold, dark place far from exposure to the hazards of data centers.

Not quite. Even if you have a controlled environment in the tape storage you should expect a very small percentage of the tapes to fail. Therefore it makes sense to keep repacking the data constantly. Also older tape drives may fail making the data on old tapes inaccessible.

The latter reason makes archivists keep copying tapes at a much higher rate than their physical life span would suggest. Marty Perlmutter, "The Lost Picture Show: Hollywood Archivists Can't Outpace Obsolescence".

> Disks are most at risk when the read/write head is flying close to the medium.

When the disk is spinning it constantly monitors itself for errors due to wear and errors due to defects in the manufacturing process. While rotation increases the probability of an error it also through predictive failure analysis reduces the chance of an error to occur undetected. On the contrary, as a mechanical unit a disk that was stored on a shelf might just fail to spin up.

A probabilistic approach to consistency checking has to be aligned with the statistical thresholds set for different actions. Suppose that a probabilistic model says that with probability 50% there is one error for a 1000 cartridges in a tape library. Does it give any hint on the possible action but to check consistency for the complete archive in order to find the possibly damaged part so that it can be rebuilt.

Many papers with statistical models of reliability of computer systems based on queuing theory have this problem. While they provide formulas to quickly estimate parameters of computer systems they often rely on some generic assumptions that may or may not apply in a particular setting.

---
Tags: filesystems, integrity, digital-preservation
---


# Question
Title: Need help understanding this optimization problem on graphs
Has anyone seen this problem before? It's suppose to be NP-complete.

> We are given vertices $V\_1,\dots ,V\_n$ and possible parent sets for each vertex. Each parent set has an associated cost. Let $O$ be an ordering (a permutation) of the vertices. We say that a parent set of a vertex $V\_i$ is consistent with an ordering $O$ if all of the parents come before the vertex in the ordering. Let $mcc(V\_i, O)$ be the minimum cost of the parent sets of vertex $V\_i$ that are consistent with ordering $O$. I need to find an ordering $O$ that minimizes the total cost: $mcc(V\_1, O), \dots ,mcc(V\_n, O)$.

I don't quite understand the part "...if all of the parents come before the vertex in the ordering." What does it mean?

# Answer
You can think of the parent sets as incident nodes; that is if $V\_i$ is in the parent set of $V\_j$, there is a (directed) edge from $V\_i$ to $V\_j$.

An ordering "consistent" with this graph in the sense of the exercise is a topological sorting, that is a topological ordering $V\_{\pi(1)}, \dots, V\_{\pi(n)}$ has no pair $(i,j)$ with $i\<j$ so that there is an edge from $V\_{\pi(j)}$ to $V\_{\pi(i)}$.

The problem is then to find an ordering as consistent with the graph as possible.
> 4 votes

---
Tags: algorithms, graphs, terminology, optimization
---


# Question
Title: Complete Problems for $DSPACE(\log(n)^k)$
We know that the $polyL$-hierarchy doesn't have complete problems, as it would conflict with the space hierarchy theorem. But: Are there complete problems for each level of this hierarchy?

To be precise: Does the class $DSPACE(\log(n)^k)$ have complete problems under $L$-reductions for each $k \> 0$?

# Answer
> 7 votes
A standard proof of the space hierarchy theorem is based on the space-efficient simulation of Turing machines. If I am not mistaken, this simulation implies that for every space-constructible function *f*: ℕ→ℕ, the following problem is in DSPACE(*f*(*n*)) (where *n* is the input length):

> Given an encoding of a deterministic Turing machine *M* with a read-only input tape and a read-write work tape with a fixed work alphabet (such as {0, 1, blank}), a string *x*, and a tally string 1*t*, decide whether *M* halts on input string *x* before using more than *f*(*t*) work space.

This problem is DSPACE(*f*(*n*))-hard under log-space many-one reducibility. Here is a proof in the case of *f*(*n*) = lg*k**n*. For each language *L*∈DSPACE(log*k**n*), there is a Turing machine *M* (of the form stated above) which accepts *L* in *c* lg*k**n* space for some *c*∈ℕ. Modify *M* to *M*′ so that when *M* rejects, *M*′ goes into an infinite loop instead. Then given an input string *x*, let *t* = |*x*|*c*, and we generate the instance (*M*′, *x*, 1*t*) of the problem above. (I think that the only slightly nontrivial part is that we cannot set *t* = |*x*|.)

Therefore this problem is DSPACE(*f*(*n*))-complete under log-space many-one reducibility.

# Answer
> 3 votes
Just an exetended comment.

In the paper "The Emptiness Problem for Intersections of regular Languages" it is showed that deciding the emptiness of the intersection of the languages recognized by $g(n)$ DFAs is complete for $NSPACE(g(n)\log{n})$; in particular the emptiness of the intersection of the languages recognized by $\log^{k-1}{n}$ DFAs is complete for $NSPACE(log^{k}{n})$, $k \geq 1$.

But it seems that the same result cannot be restricted to DPSACE if we consider the emptiness intersection of languages recognized by $g(n)$ Tally-DFAs (DFAs with only one symbol in the alphabet).

However $\emptyset = \bigcap^k DFA\_{lin}$ is complete for $DSPACE(\log{n})$ for each $k$.

---
Tags: complexity-theory, reductions, space-complexity
---


title: construct regular expression

text:
# Question
Title: construct regular expression
I need help with the following exercise:

Construct an $\varepsilon$-NFA for the following regular expression $(a|\varepsilon)(ba)^\*(c^\*a|bc)^\*$.

i already tried this exercise with nerode but i didnt come to a solution please help me thank you guys

Source wiki Nerode : (Given a language L, and a pair of strings x and y, define a distinguishing extension to be a string z such that exactly one of the two strings xz and yz belongs to L. Define a relation RL on strings by the rule that x RL y if there is no distinguishing extension for x and y. It is easy to show that RL is an equivalence relation on strings, and thus it divides the set of all finite strings into equivalence classes.

The Myhill–Nerode theorem states that L is regular if and only if RL has a finite number of equivalence classes, and moreover that the number of states in the smallest deterministic finite automaton (DFA) recognizing L is equal to the number of equivalence classes in RL. In particular, this implies that there is a unique minimal DFA with minimum number of states.)

# Answer
I wouldn't go for nerode. There is a standard proof for the equivalence of regular expressions and automata and building an automata for a given regexp is the easier part. Read it!

The basic idea: For the "A|B" operation, build an automata that "guesses" if to run the automata of A or the one of B; for "A\*B" build an automata that runs A, and whenever it reaches an accepting state "guesses" whether to jump to the start of B; and for A\* build an automata that runs A and whenever it reaches an accepting state "guesses" whether to start over or continue.
> 1 votes

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


# Question
Title: Depth-2 circuits with OR and MOD gates are not universal?
It is well-known that every boolean function $f:\\{0,1\\}^n\to \\{0,1\\}$ can be realized using a boolean circuit of depth 2 (over the variables, their negation and constant values) containing AND gates in the first level and one single OR gate in the upper level; this is simply the DNF representation of $f$.

Another type of gate which is of great interest in circuit complexity is the $MOD\_m$ gate. The usual definition is the following:

$$\mathrm{MOD}\_m(x\_1,\dots,x\_k)=\cases{ 1 & if \\(\sum x\_i \equiv 0 \mod m\\) \\ 0 & if \\(\sum x\_i \not\equiv 0 \mod m\\) \\ }$$

These gates sometimes have surprising power; for example, any boolean function can be represented by a depth-2 circuit having only $\mathrm{MOD}\_6$ gates (this is folklore but I can elaborate is someone is interested).

However, another folklore is that circuits with a single OR gate at the top and $\mathrm{MOD}\_m$ gates in the bottom layer (with $m$ being fixed once and for all, and in particular being the same for all the gates) is not universal, i.e. for any value of $m$, there are boolean functions that cannot be computed by $\mathrm{OR} \circ \mathrm{MOD}\_m$ circuit.

I'm looking for a proof for this claim, or at least some direction.

# Answer
The Boolean AND function can not be computed. Suppose actually that the AND function is computed by an $\text{OR} \circ \text{MOD}$ circuit. Then it follows that one of the MOD subcircuits must compute then AND function already, which is impossible.
> 10 votes

---
Tags: complexity-theory, logic, circuits
---


# Question
Title: Space bounded Turing Machine - clarification on Computational Complexity (book: Arora-Barak ) question 4.1
I have the following question from Computational Complexity - A modern Approach by Sanjeev Arora and Boaz Barak:

> *\[Q 4.1\]*
> Prove the existence of a universal TM for space bounded computation (analogously to the deterministic universal TM of Theorem 1.9).

That is, prove that there exists a Turing Machine $SU$ such that for every string $\alpha$ and input $x$, if the TM $M\_\alpha$ -- the TM represented by $\alpha$ -- halts on $x$ before using $t$ cells of its work tape, then $SU(\alpha, t, x) = M\_\alpha(x)$ and moreover, $SU$ uses at most $C\cdot t$ cells of its work tape, where $C$ is a constant depending only on $M\_\alpha$.

After checking theorem 1.9 and the universal TM with time bound, I see that the construct $SU(\alpha, t, x)$ means that the Turing machine SU stops after $t$ steps. However if this is the case, then it means that we can create a Turing Machine equivalent to $M\_\alpha$ such that the new Turing Machine stops in $t$ steps where $t$ is the "space" used in the original.

However, this seems a dubious interchange of space and time. If on the other hand, $t$ actually meant that the second machine stops within $t$ space, too, then the second part does not make sense any more because it says $SU$ uses $Ct$ cells, which is not $t$.

So my question is how do I interpret this? Is the first interpretation really possible?

# Answer
> 6 votes
I do not understand what you are trying to say after "--", but here is what you need to do:

Hopefully you understand the idea of turing machine encoding: i.e. you can assign a unique identifier (i.e. "label") $\alpha$ to each turing machine. So by $M\_\alpha$ we mean the Turing machine labeled by $\alpha$. So you need to design a *single* turing machine $SU$ which takes three inputs $\alpha$, $t$ and $x$ ($\alpha$ is a turing machine label, $t$ is a space bound, and $x$ is an input string) and:

* if $M\_\alpha$ uses more than $t$ bits of workspace on input $x$ before it halts, then we have no requirement for $SU$
* if $M\_\alpha$ uses at most $t$ bits of workspace on input $x$ we have two requirements for $SU$:

+ $SU$ uses at most $Ct$ units of workspace where $C$ is a function of $\alpha$ but not $t$ or $x$
    + $SU$ outputs $M\_\alpha(x)$

The idea is that for any machine and any input, $SU$ can simulate that machine while using only slightly more space than the original machine. Note that $t$ is a bound on the space that $M\_\alpha$ uses, not the space that $SU$ uses. $SU$ cannot be exactly as space efficient as the original machine because simulation requires some overhead, but the point is that the overhead is small as $C$ is fixed for every $\alpha$, no matter how large $x$ is in size.

Theorem 1.9. also has some overhead: a machine which stops in $T$ time steps is simulated in $CT\log T$ time steps where $C$ is again some constant independent of $T$ or of the input string.

---
Tags: complexity-theory, terminology, turing-machines, space-complexity
---


title: Determine missing number in data stream

text:
# Question
Title: Determine missing number in data stream
We receive a stream of $n-1$ pairwise different numbers from the set $\left\\{1,\dots,n\right\\}$.

How can I determine the missing number with an algorithm that reads the stream once and uses a memory of only $O(\log\_2 n)$ bits?

# Answer
> 11 votes
You know $\sum\_{i=1}^n i = \frac{n(n+1)}{2}$, and because $S = \frac{n(n+1)}{2}$ could be coded in $O(\log(n))$ bits this can be done in $O(\log n)$ memory and in one path (just find $S - \mathrm{currentSum}$, this is missing number).

But this problem could be solved in general case (for constant $k$): we have $k$ missing numbers, find out all of them. In this case instead of calculating just sum of $y\_i$, calculate sum of j'st power of $x\_i$ for all $1\le j \le k$ (I assumed $x\_i$ is missing numbers and $y\_i$ is input numbers):

$\qquad \displaystyle \begin{align} \sum\_{i=1}^k x\_i &= S\_1,\\ \sum\_{i=1}^k x\_i^2 &= S\_2,\\ &\vdots \\ \sum\_{i=1}^k x\_i^k &= S\_k \end{align}$ $\qquad (1)$

Remember that you can calculate $S\_1,...S\_k$ simply, because $S\_1 = S - \sum y\_i$, $S\_2 = \sum i^2 - \sum y\_i^2$, ...

Now for finding missing numbers you should solve $(1)$ to find all $x\_i$.

You can compute:

$P\_1 = \sum x\_i$, $P\_2 = \sum x\_i\cdot x\_j$, ... , $P\_k = \prod x\_i$ $(2)$.

For this remember that $P\_1 = S\_1$, $P\_2 = \frac{S\_1^2 - S\_2}{2}$, ...

But $P\_i$ is coefficients of $P=(x-x\_1)\cdot (x-x\_2) \cdots (x-x\_k)$ but $P$ could be factored uniquely, so you can find missing numbers.

These are not my thoughts; read this.

# Answer
> 16 votes
From the comment above:

Before processing the stream, allocate $\lceil \log\_2 n \rceil$ bits, in which you write $x:= \bigoplus\_{i=1}^n \mathrm{bin}(i)$ ($\mathrm{bin}(i)$ is the binary representation of $i$ and $\oplus$ is pointwise exclusive-or). Naively, this takes $\mathcal{O}(n)$ time.

Upon processing the stream, whenever one reads a number $j$, compute $x := x \oplus \mathrm{bin}(j)$. Let $k$ be the single number from $\\{ 1, ... n\\}$ that is not included in the stream. After having read the whole stream, we have $$ x = \left(\bigoplus\_{i=1}^n \mathrm{bin}(i)\right) \oplus \left(\bigoplus\_{i \neq k } \mathrm{bin}(i)\right) = \mathrm{bin}(k) \oplus \bigoplus\_{i \neq k } (\mathrm{bin}(i) \oplus \mathrm{bin}(i)) = \mathrm{bin}(k), $$ yielding the desired result.

Hence, we used $\mathcal{O}(\log n)$ space, and have an overall runtime of $\mathcal{O}(n)$.

# Answer
> 0 votes
HdM's solution works. I coded it in C++ to test it. I can't limit the `value` to $O(\log\_2 n)$ bits, but I'm sure you can easily show how only that number of bits is actually set.

For those that want pseudo code, using a simple $\text{fold}$ operation with exclusive or ($\oplus$):

$$\text{Missing} = \text{fold}(\oplus, \\{1,\ldots,N\\} \cup \text{InputStream})$$

Hand-wavey proof: A $\oplus$ never requires more bits than its input, so it follows that no intermediate result in the above requires more than the maximum bits of the input (so $O(\log\_2 n)$ bits). $\oplus$ is commutative, and $x \oplus x = 0$, thus if you expand the above and pair off all data present in the stream you'll be left only with a single un-matched value, the missing number.

```
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

void find_missing( int const * stream, int len );

int main( int argc, char ** argv )
{
    if( argc < 2 )
    {
        cerr << "Syntax: " << argv[0] << " N" << endl;
        return 1;
    }
    int n = atoi( argv[1] );

    //construct sequence
    vector<int> seq;
    for( int i=1; i <= n; ++i )
        seq.push_back( i );

    //remove a number and remember it
    srand( unsigned(time(0)) );
    int remove = (rand() % n) + 1;
    seq.erase( seq.begin() + (remove - 1) );
    cout << "Removed: " << remove << endl;

    //give the stream a random order
    std::random_shuffle( seq.begin(), seq.end() );

    find_missing( &seq[0], int(seq.size()) );
}

//HdM's solution
void find_missing( int const * stream, int len )
{
    //create initial value of n sequence xor'ed (n == len+1)
    int value = 0;
    for( int i=0; i < (len+1); ++i )
        value = value ^ (i+1);

    //xor all items in stream
    for( int i=0; i < len; ++i, ++stream )
        value = value ^ *stream;

    //what's left is the missing number
    cout << "Found: " << value << endl;
}

```

---
Tags: algorithms, integers, online-algorithms
---


# Question
Title: Similarities and differences in major process algebras
To my knowledge, there are three major process algebras that have inspired a vast range of research into formal models of concurrency. These are:

* CCS and $\pi$-calculus both by Robin Milner
* CSP by Tony Hoare and
* ACP by Jan Bergstra and Jan Willem Klop

All three seem to have to this day a quite active following and vast amounts of research has been done on them.

> What are the key similarities and differences of these approaches? Why has research in process algebra diverged instead of converged, in the sense that there is no one universal model to unify the field?

# Answer
I only know CSP and CCS/pi-calculus (not ACP).

CSP was motivated by imperative programming processes communicating via messages. Hoare then tried to abstract away a simple calculus out of it. CCS, on the other hand, was an effort to create a foundational calculus like lambda calculus. Given their original starting points, and given their final form, I would say that they have *converged* rather than diverged.

What I find common between CSP and CCS is that both of them are based on the notion of "process" (and, by that, I mean an abstract notion of events arranged in time). The main difference between them is that CSP has two forms of choice (internal/external or nondeterministic/deterministic). In CCS the two ideas are fused into one. I think that is an irreconcilable difference.

The distinction between internal and external choice allows CSP to have a semantics in terms of linear traces. The CCS semantics, on the other hand, has to be based on trees.

I think Hoare's current plan for "Unifying theories" is to put both of them into a single framework. We have to wait and see what he comes up with!
> 9 votes

# Answer
*Another partial answer.*

The approach to semantics taken by the various communities differed, at least originally.

* ACP semantics are axiomatic/algebraic.
* CSP semantics are denotational, generally in terms of traces.
* CCS/$\pi$-calculus semantics are operational, generally in terms of labelled transition systems.

Of course, since the original semantics, more models have been developed. But it is certainly interesting that the original researchers started out with different semantic approaches.
> 8 votes

# Answer
*Answering (at least) the part of your question regarding why research has diverged instead of converged.*

Being no expert on process algebras, I was once wondering the exact same thing: why are there so many theories? I was pointed to a survey by Parrow: Expressiveness of Process Algebras, 2008. I think it is very nicely written and even a novice could understand it.

Parrow investigates the expressiveness of algebras and answers the question. In short, different theories are different kind of tools for solving a huge task.
> 6 votes

---
Tags: logic, concurrency, process-algebras
---


title: Number of clique in random graphs

text:
# Question
Title: Number of clique in random graphs
There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X\_k$ be the number of cliques of size $k$ in $G(n, p)$.

I know that $\mathbb{E}(X\_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$, but how do I prove it?

How to show that $\mathbb{E}(X\_{\log\_2n})\ge1$ for $n\to\infty$? And how to show that $\mathbb{E}(X\_{c\cdot\log\_2n}) \to 0$ for $n\to\infty$ and a fixed, arbitrary constant $c\>1$?

# Answer
So basically there are three questions involved.

---

## I know that $E(X\_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$, but how do I prove it?

You use the linearity of expectation and some smart re-writing. First of all, note that $$ X\_k = \sum\_{T \subseteq V, \\, |T|=k} \mathbb{1}\[T \text{ is clique}\].$$ Now, when taking the expectation of $X\_k$, one can simply draw the sum out (due to linearity) and obtain $$ \mathrm{E}(X\_k) = \sum\_{T \subseteq V, \\, |T|=k} \mathrm{E}(\mathbb{1}\[T \text{ is clique}\]) = \sum\_{T \subseteq V, \\, |T|=k} \mathrm{Pr}\[T \text{ is clique}\]$$ By drawing out the sum, we eliminated all possible dependencies between subsets of nodes. Hence, what is the probability that $T$ is a clique? Well, no matter what $T$ consists of, all edge probabilities are equal. Therefore, $\mathrm{Pr}\[T \text{ is clique}\] = p^{k \choose 2}$, since all edges in this subgraph must be present. And then, the inner term of the sum does not depend on $T$ anymore, leaving us with $\mathrm{E}(X\_k) = p^{k \choose 2} \sum\_{T \subseteq V, \\, |T|=k} 1 = {n \choose k} \cdot p^{k \choose 2}$.

---

## How to show that for $n\rightarrow\infty$: $E(X\_{\log\_2n})\ge1$

I am not entirely sure whether this is even correct. Applying a bound on the binomial coefficient, we obtain

$$E(X\_{\log n}) = {n \choose \log n} \cdot p^{\log n \choose 2} \leq \left(\frac{n e p^\frac{(\log n)}{4}}{\log n}\right)^{\log n} = \left(\frac{ne \cdot n^{(\log p) / 4}}{\log n}\right)^{\log n}.$$ (Note that I roughly upper bounded $p^\frac{-1 + \log n}{2}$ by $p^\frac{\log n}{4}$.) However, now one could choose $p = 0.001$, and obtain that $\log\_2 0.001 \approx -9.96$, which makes the whole term go to $0$ for large $n$. Are you maybe missing some assumptions on $p$?
> 10 votes

---
Tags: graphs, combinatorics, probability-theory, random-graphs
---


# Question
Title: Transform regular grammar in linear grammar
My problem is how can I transform a *regular* grammar into a *linear* grammar?

I know that a linear grammar has the form

$\begin{align} A &\to w\_1Bw\_2 \\ A &\to w \end{align}$

where $A,B \in N$ and $w,w\_1,w\_2 \in \Sigma^\*$.

# Answer
A (right) regular grammar is one in which all production rules are of one of the following:

$$B \rightarrow a$$ $$B \rightarrow aC$$ $$B \rightarrow \lambda$$

Where $B$ is a non-terminal, $a$ is a terminal and $\lambda$ is the empty word. A regular grammar is a grammar which is either right-regular xor left-regular. As you have said in a linear grammar one does not require the nonterminals to appear on the far side of the right of the production rules. Therefore, every regular grammar is already a linear grammar.
> 1 votes

# Answer
*regular* in what sense?

* If you mean *regular* in the sense of a regular language then the question is trivial since regular grammar is already a linear grammar.
* If you mean *regular* in the sense of a *customary* or *usual* i.e.

> How to transform an arbitrary context-free grammar into a linear grammar?

then this is not possible since there are examples of context free grammars that generate languages that are not recognizable by a linear context free grammar. (e.g. the Dyck language)

(Both answers can easily be found in the corresponding wikipedia article.)
> 1 votes

# Answer
Note that your definition is equivalent to the more informal one from Wikipedia:

> \[A\] grammar is linear if it is context-free and all of its productions' right hand sides have at most one nonterminal.

So every regular grammar is linear *by definition*. That is why regular grammars are also called right- or left-linear (depending on which one you choose).

Formally, choose $w\_1=\varepsilon$ (or $w\_2=\varepsilon$) *for all rules* to obtain a left-regular (or right-regular) grammar.
> 0 votes

---
Tags: terminology, formal-grammars
---


# Question
Title: Context-free grammar for $\{ a^n b^m a^{n+m} \}$
I've got a problem with this task. I should declare a context-free grammar for this language:

$\qquad \displaystyle L := \\{\\, a^nb^ma^{n+m} : n,m \in \mathbb{N}\\,\\}$

My idea is: We need a start symbol, for example $S$. I know that I can generate the first $a$ and the last $a$ by $S \to a a$. I don't know what is the next idea to solve this task.

# Answer
First, rewrite $a^nb^ma^{n+m}$ as $a^nb^ma^ma^n$. Now, from the outside in, you need rules to (1) add an $a$ to the front and back of your strings, and (2) to add $b$ to the front and $a$ to the back. It's also helpful to imagine building strings from the inside out... you can either add a $b$ to the front and an $a$ to the back, or an $a$ to both ends.

The first, working from the outside, rule is straightforward:

```
S := aSa

```

Notice that once you start adding $b$, you cannot go back to adding only $a$... so we need a new nonterminal:

```
S := B
B := bBa

```

Since the empty string is in your language, add another production to allow $B$ to generate the empty string. So we get:

```
S := aSa | B
B := bBa | -

```
> 9 votes

# Answer
Hint: Develop grammars for the simple languages $\\{a^nb^n \mid n \in \mathbb{N}\\}$ and $\\{a^nb^m \mid m,n \in \mathbb{N}\\}$, respectively, and combine (variations of) them to generate your $L$.
> 3 votes

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


# Question
Title: What is the branch of Computer Science that studies how Anti Virus programs work?
It is a trivial exercise in finite automata to show that there is no algorithm that can detect all the viruses, yet there are many software companies selling Anti Virus Software.

Is there any part of CS that deals with Viruses and Anti Viruses ?

PS : I am not asking about non CS related justification of to have AV or not, but only what category/subject within CS they come under, if any. If AV is not a subject within CS then that is also an acceptable answer, are there any refrences within CS context to Viruses and AV's?

# Answer
There is a subarea of computer security called Computer Virology. The Journal of Computer Virology is devoted to the topic. Studying how anti-virus software works only scratches the surface of what the area is about.

For instance, there is even some work applying logic to malware: *A General Definition of Malware* by S. Kramer and J.C. Bradfield. Journal of Computer Virology (6) 2010.
> 12 votes

# Answer
Viruses and antivirus technology have a lot to do with CS. Your question reminded me of something I recently read. Here's an excerpt from the book by Williamson & Shmoys, The Design of Approximation Algorithms, page 6. It's justifying the (practical) importance of approximation algorithms, and uses the well-known set cover problem as an example in the context of viruses:

> The set cover problem was used in the development of an antivirus product, which detects computer viruses. In this case it was desired to find salient features that occur in viruses designed for the boot sector of a computer, such that the features do not occur in typical computer applications. These features were then incorporated into another heuristic for detecting these boot sector viruses, a neural network. The elements of the set cover problem were the known boot sector viruses (about 150 at the time). Each set corresponded to some three-byte sequence occurring in these viruses but not in typical computer programs; there were about 21,000 such sequences. Each set contained all the boot sector viruses that had the corresponding three-byte sequence somewhere in it. The goal was to find a small number of such sequences (much smaller than 150) that would be useful for the neural network. By using an approximation algorithm to solve the problem, a small set of sequences was found, and the neural network was able to detect many previously unanalyzed boot sector viruses.

Surprising or not, this example shows that at least techniques in AI and combinatorial optimization are useful. After reading this, one could easily believe that many areas of CS have things that can be applied in the context of viruses and their detection. To answer your question more directly, many things in CS deal with viruses, at least indirectly.
> 9 votes

# Answer
You should be careful when using theoretical result to argue something cannot be done in practice. There are several dangers that one can fall in:

1. the theoretical result has assumptions that doesn't apply,
2. the problem in practice is not modeled well by the theoretical model,
3. in practice a solution doesn't need to be perfect to be useful.

You haven't given a formal definition of what is a virus so expanding on your claim about the trivial exercise can be helpful in understanding what you really mean.

A large part of what an antivirus software do is detecting *known* viruses (and their variants), and this is done by comparing strings (in files, memory, etc) with a finite list of strings (virus signatures). That is why we need to update the database of the antivirus software regularly.

There are additional capabilities on detecting potential viruses based on their "behavior", but these methods are neither complete nor sound (and they don't need to be sound/complete to be useful). Designing a antivirus software seems to fall more in computer engineering than computer science so far (though computer science and computer engineering are closely related).

Generally these studies would fall in more applied part of computer-security (and more generally system areas: computer networks, operating systems, etc.) of computer science, but using ideas from other parts of computer science (machine learning, etc.) is typical.

You may want to check The Art of Computer Virus Research and Defense.
> 7 votes

---
Tags: reference-request, security
---


# Question
Title: How to prove correctness of a shuffle algorithm?
I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased).

The first method I use is to construct the entire list of elements and then do a shuffle on it (say a Fisher-Yates shuffle). The second method is more of an iterative method which keeps the list shuffled at every insertion. In pseudo-code the insertion function is:

```
insert( list, item )
    list.append( item )
    swap( list.random_item, list.last_item )

```

I'm interested in how one goes about showing the fairness of this particular shuffling. The advantages of this algorithm, where it is used, are enough that even if slightly unfair it'd be okay. To decide I need a way to evaluate its fairness.

My first idea is that I need to calculate the total permutations possible this way versus the total permutations possible for a set of the final length. I'm a bit at a loss however on how to calculate the permutations resulting from this algorithm. I also can't be certain this is the best, or easiest approach.

# Answer
> 22 votes
First, let us make two maybe obvious, but important assumptions:

1. `_.random_item` can choose the last position.
2. `_.random_item` chooses every position with probability $\frac{1}{n+1}$.

In order to prove correctness of your algorithm, you need an inductive argument similar to the one used here:

* For the singleton list there is only one possibility, so it is uniformly chosen.
* Assuming that the list with $n$ elements was uniformly chosen (from all permutations), show that the one with $n+1$ elements obtained by your technique is uniformly chosen.

---

From here on, the proof is wrong. Please see below for a correct proof; I leave this here because both the mistake and the following steps (which are sound) might be educational.

It is useful to derive a local (i.e. element-wise) property that has to hold, because arguing about the whole permutation is painful. Observe that a permutation is uniformly chosen if every element has equal probability of being at each position, i.e.

$\qquad \displaystyle \mathop{\forall}\limits\_{\pi \in \mathrm{Perm}\_n} \operatorname{Pr}(L = \pi) = \frac{1}{n!} \quad \Longleftrightarrow \quad \mathop{\forall}\limits\_{i=1}^n\ \mathop{\forall}\limits\_{j=1}^n \operatorname{Pr}(L\_i = j) = \frac{1}{n} \qquad (1)$

where $n = |L|$ and we assume for the sake of notational simplicity that we insert $\\{1,\dots,n\\}$ into the list.

Now, let us see what your technique does when inserting the $n+1$st element. We have to consider three cases (after the swap):

1. One of the elements in the list, not swapped, i.e. $i \in \\{1,\dots,n\\}$ and $j \in \\{1,\dots,n\\}$
2. One of the elements in the list, swapped, i.e. $i = n+1$ and $j \in \\{1,\dots,n\\}$
3. The new element, i.e. $i \in \\{1,\dots,n+1\\}$ and $j = n+1$

For each case, we compute the probability of element $j$ being at position $i$; all have to turn out to be $\frac{1}{n+1}$ (which is sufficient because of $(1)$). Let $p\_n = \frac{1}{n}$ be the probability of one of the first $n$ elements being at any position in the old list (induction hypothesis), and $p\_s = \frac{1}{n+1}$ the probability of any position being chosen by `random_item` (assumptions 1, 2). Note that the coice of the list with $n$ elements and picking the swap position are independent events, so the probabilities of joint events factor, e.g.

$\qquad \displaystyle \operatorname{Pr}(L\_i=j, i \text{ swapped}) = \operatorname{Pr}(L\_i=j)\cdot \operatorname{Pr}(i \text{ swapped}) = p\_np\_s$

for $i,j \in \\{1,\dots,n\\}$. Now for the calculations.

1. We only consider the old $n$ elements. Such an element $j$ is at position $i$ if and only if it was there before the last insertion and $i$ is not selected as swap position, that is

$\quad \displaystyle \operatorname{Pr}(L\_i = j) = p\_n(1-p\_s) = \frac{1}{n}\cdot\frac{n}{n+1} = \frac{1}{n+1}$.
2. Here we consider that one of the old elements is swapped to the last position. Element $j$ could have been at any of the old positions, so we sum over all probabilities that $j$ was at position $i$ and $i$ is chosen as swap position, that is

$\quad \displaystyle \operatorname{Pr}(L\_{n+1} = j) = \sum\_{i=1}^n p\_np\_s = \sum\_{i=1}^n \frac{1}{n}\cdot\frac{1}{n+1} = \frac{1}{n+1}$.
3. The new element ends up at position $i$ if and only if $i$ is chosen as swap position, that is

$\quad \displaystyle \operatorname{Pr}(L\_i = j) = p\_s = \frac{1}{n+1}$.

All turned out well, your insertion strategy does indeed preserve uniformity. By the power of induction, that proves that your algorithm creates uniformly distributed permutations.

A word of warning: this proof breaks down if the inserted elements are not pairwise different resp. distinguishable, because then the very first equation is no longer valid. But your algorithm is still valid; *every* permutation with duplicates is generated by the same number of random executions. You can proof this by marking duplicates (i.e. making them distinguishable), perform above proof and remove the markings (virtually); the last step collapses equal sized sets of permutations to the same.

---

As Steven has remarked correctly in the comments, above proof is fundamentally flawed as $(1)$ does not hold; you can construct distributions on the set of permutations that fulfill the right-hand, but not the left-hand side¹.

Therefore, we will have to work with probabilities of permutations, which turns out to be not that bad after all. The assumptions on `random_item` and the inductive structure outlined in the very beginning of the post remain in place, we continue from there. Let $L^{(k)}$ denote the list after $\\{1,\dots,k\\}$ have been inserted.

Let $\pi' \in \mathrm{Perm}\_{n+1}$ an arbitrary permutation of $\\{1,\dots,n+1\\}$. It can be written *uniquely* as

$\qquad \displaystyle \pi' = (\pi(1), \pi(2), \dots, \pi(i-1), n+1, \pi(i+1), \dots, \pi(n), \pi(i))$

for some $\pi \in \mathrm{Perm}\_n$ and $i \in \\{1,\dots,n+1\\}$. By induction hypothesis, $\operatorname{Pr}(L^{(n)} = \pi) = \frac{1}{n!}$. Furthermore, `random_item` picks position $i$ with probability $\frac{1}{n+1}$ by assumption. As the random choices of $\pi$ and $i$ are (stochastically) independent, we get

$\qquad \displaystyle \operatorname{Pr}(L^{(n+1)} = \pi') = \operatorname{Pr}(L^{(n)} = \pi) \cdot \operatorname{Pr}(i \text{ swapped}) = \frac{1}{(n+1)!}$

which we had to show. By the power of induction, that proves that your algorithm creates uniformly distributed permutations.

---

1. For example, assign every permutation in $\\{(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)\\}$ probability $\frac{1}{4}$ and all others $0$. There are also examples that assign every permutation a non-zero probability.

---
Tags: algorithms, proof-techniques, randomized-algorithms, correctness-proof, randomness
---


# Question
Title: Proving NP is a subset of the union of exponential DTIME
I need to prove that $\mathsf{NP}$ is a subset of the union of $\mathsf{DTIME}(2^{n^c})$ for all $c \> 1$.

Let $L$ be a language/decision problem in $\mathsf{NP}$. Then $L$ can be decided given a polynomial-size certificate in polynomial time with a turing machine $M$. So then we enumerate all possible certificates of polynomial size. There are $2^l$ possible certificates for a certificate of length $l$. For a certificate of length up to $n^c$, there are $\sum\_{l=0}^{n^c} 2^l = 2^{n^c + 1} - 1$ many certificates. Each certificate can be decided in polynomial time, so we get that each problem in $\mathsf{NP}$ can be done in $\mathsf{DTIME}(2^{n^c}n^c)$. What am I doing wrong?

# Answer
You are on the right track. To finish the proof you need to show that

$\qquad \displaystyle \mathsf{DTIME}(2^{n^k} n^k) \subseteq \mathsf{DTIME}(2^{n^c})$

for some constant $c$.
> 6 votes

---
Tags: complexity-theory, check-my-proof
---


title: How to read typing rules?

text:
# Question
Title: How to read typing rules?
I started reading more and more language research papers. I find it very interesting and a good way to learn more about programming in general. However, there usually comes a section where I always struggle with (take for instance part three of this) since I lack the theoretical background in computer science: Type Rules.

Are there any good books or online resources available to get started in this area? Wikipedia is incredibly vague and doesn't really help a beginner.

# Answer
> 30 votes
In most type systems, the type rules work together to define judgements of the form:

$$\Gamma\vdash e:\tau$$

This states that in context $\Gamma$ the expression $e$ has type $\tau$.
$\Gamma$ is a mapping of the free variables of $e$ to their types.

A type system will consist of a set of axioms and rules (a formal system of rules of inference, as Raphael points out).

An axiom is of the form

$$\dfrac{}{\Gamma \vdash e:\tau}$$

This states that the judgement $\Gamma \vdash e:\tau$ holds (always).

An example is

$$\dfrac{}{x:\tau\vdash x:\tau}$$

which states that under the assumption that the type of variable $x$ is $\tau$, then the expression $x$ has type $\tau$.

Inference rules take facts that have already been determined and build larger facts from them. For instance the inference rule

$$\dfrac{\Gamma\vdash e\_1:\tau\to\tau' \quad \Gamma\vdash e\_2:\tau}{\Gamma\vdash e\_1\ e\_2:\tau'}$$

says that if I have a derivation of the fact $\Gamma\vdash e\_1:\tau\to\tau'$ and a derivation of the fact $\Gamma\vdash e\_2:\tau$, then I can obtain a derivation of the fact $\Gamma\vdash e\_1\ e\_2:\tau'$. In this case, this is the rule for typing function application.

There are two ways of reading this rule:

* top-down - given two expressions (a function and another expression) and some constraints on their type, we can construct another expression (the application of the function to the expression) with the given type.
* bottom-up - given an expression that is, in this case, the application of a function to some expression, the way this is typed is by first typing the two expressions, ensuring that their types satisfy some constraints, namely that the first is a function type and that the second has the argument type of the function.

Some inference rules also manipulate $\Gamma$ by adding new ingredients into it (view-ed bottom up). Here is the rule for $\lambda$-abstraction:

$$\dfrac{\Gamma x:\tau\vdash e:\tau'}{\Gamma\vdash \lambda x.e:\tau\to \tau'}$$

The inference rules are applied inductively based on the syntax of the expression being considered to form a derivation tree. At the leaves of the tree (at the top) will be axioms, and branches will be formed by applying inference rules. At the very bottom of the tree is the expression you are interested in typing.

For example, a derivation of the typing of expression $\lambda f.\lambda x.f\ x$ is

$$\dfrac{\dfrac{}{f:\tau\to\tau',x:\tau\vdash f:\tau\to\tau'} \qquad \dfrac{}{f:\tau\to\tau',x:\tau\vdash x:\tau}} {\dfrac{f:\tau\to\tau',x:\tau\vdash f\ x:\tau'}{ \dfrac{f:\tau\to\tau'\vdash \lambda x.f\ x:\tau'}{\vdash \lambda f.\lambda x.f\ x:\tau'}}}$$ Two very good books for learning about type systems are:

Both books are very comprehensive, yet they start slowly, building a solid foundation.

# Answer
> 12 votes
There is cute interactive online tutorial on sequent calculus, which may help to build some intuitions and to feel how inference works: An Interactive Tutorial of the Sequent Calculus

# Answer
> 7 votes
In that Wikipedia page it is recommended "Type Systems, Luca Cardelli, ACM Computing Surveys", which is a 2-pages survey that can help you to understand how to read a rule. Anyway, how to read a rule is perfectly explained in that Wikipedia page (or even better in the 2-pages survey). However to understand the whole thing, you need to understand what is a typing system (composed by several rules), for which the "Type system" Wikipedia article is a good start (and you have several books in the section "References" of that page if you want to go further).

---
Tags: logic, reference-request, terminology, type-theory
---


# Question
Title: Swap space management during pure demand paging
The following is a doubt that I came across while doing a OS home assignment - however, it seems more concept-based than a straightforward coding question, so IMHO I don't think the homework tag is appropriate for this.

In a pure demand paging scheme for multiple processes running at the same time, given a fixed amount of RAM and Swap memory, what happens in the following 2 cases w.r.t the swap space, when

1. A process encounters a page-fault, and there are no free frames available in the RAM, hence requiring one of the pages from the process' chunk of Kernel Frames to be written out to swap (for simplicity, I'm not considering the copy-on-write case). Explicitly, where in the Swap space would this frame be written, and what data structures need to be updated for that?
2. When a process needs to page-in a particular page, where does it look in the Swap memory, and how would it know if that particular page be present in Swap at all ?

As you can well imagine, I'm having difficulty understanding in what way to manage the Swap space during pure demand management scheme, and what data structures would be essential. It would be great if you could refer to any links in your answer (I searched in "Operating System Concepts - 8th edition by Silberschatz, I couldn't find an explicit answer for my question).

# Answer
To answer this question I will visit some prerequisite understanding. Pure demand paging cannot be accomplished without hardware support. All modern computer architectures support paging, however many have different implementation details.

x86 processors use what is called a page table to keep track of virtual address spaces and page mappings, as well as bits about access privilages and, more relevant, whether or not that page is even *present* in physical memory. Violations trigger page faults which are trapped by the OS.

For more information on that, see this article.

In order to answer the question of page swapping, we must first visit the question of how the operating system keeps track of what pages are used by what process and how they are allocated. There are many different data structures that can be used for such. A flat bit array marking whether a frame is allocated or not is one way. Linked lists or stacks is another. With pure demand paging, allocated pages are not actually marked as present when they are allocated. This has the effect that no physical ram is set aside for a process until it actually writes to it. Once it does, the hardware throws a fault which the OS traps, and then the OS uses a swapping algorithm if there are no available physical pages to assign to the already allocated virtual page.

For more information on page frame allocation, see here. There you will see a general overview of some suitable datastructures.

Once a suitable algorithm for page allocation is implemented, another for allocating disk space for swapping must be chosen. Windows, as an example, has historically used a flat file in the filesystem for page swapping. I would imagine that for each node in the datastructure keeping track of allocated pages there is an assocated pointer to an offset in the file, indicating the position of the page in the disk. Unix-like operating systems have traditionally used separate partitions for page swapping which is arguably faster since there is no filesystem layer.

It is also possible to divorce the swapping algorithm datastructures from those of the allocation algorithm, however the two are related so this is probably not often done.

I hope that answers your question despite the relative brevity with which I have treated it. I found that the best way to learn about operating systems is to dive into the sometimes nasty architectural specific details that can be found in sites like wiki.osdev.org and www.osdever.net which specifically deal with hobby OS making and provide excellent tutorials on such details.
> 9 votes

---
Tags: operating-systems, memory-allocation, virtual-memory, paging, memory-management
---


title: Transform in linear grammar

text:
# Question
Title: Transform in linear grammar
i have the following regular grammar : $$S \rightarrow aS | cS | bQ\_1$$ $$Q\_1 \rightarrow bQ\_2$$ $$Q\_2 \rightarrow aQ\_3 | cQ\_3 | bQ\_1$$ $$Q\_3 \rightarrow aQ\_4 | cQ\_4$$ $$Q\_4 \rightarrow \varepsilon$$

The question is to transform that into a linear grammar with less nonterminals than the regular grammar and my idea was: $$S \rightarrow aSa | cSc | aSc | cSa | bQ\_1a | bQ\_1c$$ $$Q\_1 \rightarrow b$$

and the rest i don't know. Could you help me to solve this problem?

# Answer
Judging from the wording of your question you are still confused about what it means for a grammar to be linear but I wont address that here. If you want to make the grammar smaller you could do the following: remove $Q\_4$ from the right hand side of all production rules and remove all rules which start with $Q\_4$. You can do this because $Q\_4$ doesn't generate anything so it is effectively useless. Next, notice that $Q\_1$ serves only to increase the number of $b$'s by one, so you can remove that, too. We can also do a similar trick to remove $Q\_3$ as now all $Q\_2$ does is give us one of the following strings by rewriting $Q\_3$: $$aa, ac, ca, cc$$.

So the resulting grammar looks like this:

$$S \rightarrow aS | cS | bbQ\_2$$ $$Q\_2 \rightarrow aa | ac | ca | cc | bbQ\_2$$.

I'm not claiming that this is the fewest number of non-terminals for this language, maybe you could/should prove that it is/isn't?
> 3 votes

# Answer
It can be useful to first figure out what *language* the grammar generates and then tailor a grammar. In this case, try and find a (concise) regular expression that describes the generated language.

> $(a\mid c)^\* (bb)^+ (a\mid c)^2$
> 1 votes

---
Tags: formal-grammars
---


title: generation of linear grammar

text:
# Question
Title: generation of linear grammar
We have the following linear grammar: $$E \rightarrow aO | bO | bbE | bb$$ $$O \rightarrow aE | bE | abaE | aba$$ Does the linear grammar generate a regular language, if yes why ? Our alphabet is $\Sigma$ = {a,b} and our nonterminals are E and O. We begin by E.

# Answer
Yep, this generates a regular language. We can show this fairly easily by constructing an equivalent regular grammar. We start with

$$E \rightarrow aO | bO | bbE | bb$$ $$O \rightarrow aE | bE | abaE | aba$$

Introduce new nonterminal symbols as follows:

$$V \rightarrow bE | b$$ $$W \rightarrow bX$$ $$X \rightarrow aE | a$$

Then we can rewrite the rules for $E$ and $O$ as

$$E \rightarrow aO | bO | bV$$ $$O \rightarrow aE | bE | aW$$

Now the rules for $E, O, V, W, X$ are such that (a) they produce the same language as the linear grammar and (b) they constitute a regular grammar. Since regular grammars produce regular languages, you're done. Also see the Wikipedia entry for Regular Grammars; a right-regular grammar is given above. To see that it generates the same language as the linear grammar, notice that $V, W, X$ can be eliminated via substitution to recover the original.
> 1 votes

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


# Question
Title: Massalin's Synthesis Quajects equivalent to ASM generating macros used in Game Oriented Assembly LISP?
Alexia Massalin's Dissertation on Synthesis was a Phd thesis on Operating Systems that contained a concept called 'Quajects' (see Chapter 4).

This is some additional commentary on the Phd Thesis.

Best I can work out - a Quaject is construct that generates Assembler customised for the function being used at the time. (Perhaps like a JIT).

The project that I've seen that came closest to this was Game Oriented Assembly LISP (GOAL), a framework used in Crash Bandicoot that used ASM-generating LISP macros to speed up the development iteration process and generate the production code.

Can we say that the Macros generating ASM in GOAL were quajects? (yes or no question - please explain why if yes, and reasons if no.)

# Answer
As I see it, a Quaject is a kind of *software component* in the sense that it has a **provided** interface (the *callentry* functions), which contains the functions it offers, and a **required** interface (the *callout* functions), which contains the functions it needs to operate. The *callback* part of the interface is for **call back** functions, which are functions that are available to call the caller of a function. (In Java you cannot call the caller unless an explicit reference is passed.)

I don't think it is correct to say that "a Quaject is construct that generates Assembler customised for the function being used at the time." For example, in Section 4.1.4 of the thesis it states that

> Higher-level kernel services are built by composing several basic quajects.

So the quajects are the ingredients that are used to build the custom services. They do not build them.

GOAL seems to be a variant of Scheme that allows inline assembly language, which I can image allows quite some flexibility in the programming. The language is compiled to assembly. The assembly language it includes is not in the shape of any sort of component, as far as I can tell.

Based on this, I would say that the answer to your question is **no**.
> 1 votes

---
Tags: operating-systems
---


title: Dependency Graph - Acyclic graph

text:
# Question
Title: Dependency Graph - Acyclic graph
I have a directed acyclic graph where edge (A,B) means that vertex A depends on vertex B.

Vertex deletions have the following restrictions:

1. When vertex B is removed, all dependent vertexes should also be removed.
2. When vertex A is removed and vertex A was the only vertex that depends on B, vertex B should also be removed.

I need to list the vertixes which are deleted when

1. Vertex B is deleted. My solution is B, E and J because

* B -- deleted
    * E -- because of condition 2, B is removed and B was the only vertex that depends on E
    * J -- because of condition 2
2. Vertex C is deleted. My solution is C, F, A, G, ... ?

* C -- deleted
    * F -- because of condition 2 (C is the only vertex to F)
    * A -- condition 1 (depends on C)
    * G -- condition 2 (C is the only vertex to G)
    * I think here the process goes on and cascades. Is that correct?

What could be an algorithm for such vertexes dependency network which allows for the vertex deletion?

PS: this is an old exam exercise (2008/09); I use it as exercise for my one middle of June.

# Answer
The deletion process has two phases, one for each condition.

1. Delete the specified node and all nodes that have a directed path to it.
2. Delete all nodes that have no incoming edges anymore and are no sources (iterate).

There are two imporant observations that make this correct:

* During phase two, we create no new nodes with dangling outgoing edges, that is we do not break more dependencies that would cause nodes to be removed by condition 1.
* Phase two is a fixed-point iteration.

How you would implement this depends on your graph representation. For example, if graphs have a node list, a list of sources and every node has lists of incident nodes via incoming (`pred`) and outgoing (`succ`) edges, respectively, you can do it like this:

```
  void removeFancy(g : Graph, n : Node) {
    rem = collectReverse(g,n)
    g.removeAll(rem)
    removeRedundant(g)
  }

  Node[] collectReverse(g : Graph, n : Node) {
    result = [n]
    foreach ( n' in n.pred ) {
      result ++= collectReverse(g,n')
    }
    return result
  }

  removeRedundant(g : Graph) {
    oldSize = 0
    while ( oldSize != g.size ) {
      oldSize = g.size
      for ( n in g.nodes ) {
        if ( n.pred.empty? && !g.sources.contains(n) ) {
          g.remove(n)
        }
      }
    }
  }

```

You can also do it in a more recursive fashion:

```
  void removeFancy(g : Graph, n : Node) {
    for ( n' in n.pred ) {
      removeFancy(g, n')
    }

    succ = n.succ.copy
    g.remove(n)

    for ( n' in succ ) {
      if ( n'.pred.size == 0 ) {
        removeFancy(g, n')
      }
    }
  }

```

Here it is more challenging to see correctness because the two phases are interleaved. The essential argument is that nodes deleted in the second loop never cause new dependency breaks, therefore all nodes that have to be deleted because of condition 2 are identified thus by recursion spanned by the calls in the first loop.

If you apply any of those to your second example, you will see that in addition C, F, A and G also D will be deleted, but no other nodes.
> 6 votes

---
Tags: algorithms, graphs
---


title: Finding lambda of Master Theorem

text:
# Question
Title: Finding lambda of Master Theorem
Suppose I have a recurrence like $T(n)=2T(n/4)+\log(n)$ with $a=2, b=4$ and $f(n)=\log(n)$.

That should be case 1 of the Master theorem because $n^{1/2}\>\log(n)$. There is also a lambda in case 1: $f(n)=O(n^{(1/2)-\lambda})$. Is this correct? And how can I find this lambda?

# Answer
> 5 votes
As you correctly noted, the case 1 of the Master theorem applies here. In other words, the case 1 applies if $f(n) = O(n^{\log\_b a - \lambda})$ for some constant $\lambda \> 0$.

Indeed, we will have to see if we can find *some* $\lambda \> 0$ so that in this case, $\log n = O(n^{\log\_4 2 - \lambda}) = O(n^{1/2-\lambda})$. Easy, we can pick any $\lambda \< 1/2$. Finally, be careful what the Master theorem now tells you: the solution to the recurrence

$$T(n) = \Theta(n^{\log\_4 2}) = \Theta(n^{1/2}) = \Theta(\sqrt n).$$

---
Tags: proof-techniques, asymptotics, recurrence-relation, master-theorem
---


# Question
Title: How can I prove that a complete binary tree has $\lceil n/2 \rceil$ leaves?
Given a complete binary tree with $n$ nodes. I'm trying to prove that a complete binary tree has exactly $\lceil n/2 \rceil$ leaves. I think I can do this by induction.

For $h(t)=0$, the tree is empty. So there are no leaves and the claim holds for an empty tree.

For $h(t)=1$, the tree has 1 node, that also is a leaf, so the claim holds. Here I'm stuck, I don't know what to choose as induction hypothesis and how to do the induction step.

# Answer
If the statement you're trying to prove by induction is

> For all positive integers $n$, a complete binary tree with $n$ nodes has $\lceil{n/2}\rceil$ leaves.

then the induction hypothesis must be

> For all positive integers $k\<n$, a complete binary tree with $k$ nodes has $\lceil{k/2}\rceil$ leaves.

Similarly, if the statement you're trying to prove by induction is

> For all positive integers $n$, a hoosegow with $n$ whatsits has $2^{\lfloor\sqrt{n}\rceil!}\cdot n^\pi$ nubbleframets.

then the induction hypothesis must be

> For all positive integers $k\<n$, a hoosegow with $k$ whatsits has $2^{\lfloor\sqrt{k}\rceil!}\cdot k^\pi$ nubbleframets.
> 5 votes

# Answer
First, it might help to be a little more specific with your terminology. I'll assume you mean "complete" in the way that \[CLRS01\] defines it:

> All leaves have the same depth and all internal nodes have degree 2.

Second, is this homework?

You can prove this using structural induction. Show your claim holds for a "base" tree and then think about how other complete binary trees are built up from these.

As you build larger trees in this fashion, how does the total number of nodes increase? How does the number of leaves increase?

Hint:

> Does $\lceil n+1 \rceil = 2 \lceil n/2 \rceil$ ?
> 2 votes

---
Tags: data-structures, graphs, proof-techniques, combinatorics, binary-trees
---


title: Weighted subset sum problem

text:
# Question
Title: Weighted subset sum problem
Given an integer sequence $\\{ a\_1, a\_2, \ldots, a\_N \\}$ that has length $N$ and a fixed integer $M\leq N$, the problem is to find a subset $A =\\{i\_1, \dots, i\_M\\} \subseteq \[N\]$ with $1 \leq i\_1 \lt i\_1 \lt \dots \lt i\_M \leq N$ such that

$\qquad \displaystyle \sum\_{j=1}^M j \cdot a\_{i\_j}$

is maximized.

---

For instance, if the given sequence is $-50; 100; -20; 40; 30$ and $M = 2$, the best weighted sum arises when we choose positions 2 and 4.

So that we get a value $1 \cdot 100 + 2 \cdot 40 = 180$.

On the other hand, if the given sequence is $10; 50; 20$ and $M$ is again 2, the best option is to choose positions 1 and 2 that we get a value $1 \cdot 10 + 2 \cdot 50 = 110$.

---

To me it looks similar to the maximum subarray problem, but I can think of many examples in which the maximum subarray is not the best solution.

Is this problem an instance of a well studied problem? What is the best algorithm to solve it?

This question was inspired by this StackOverflow question.

# Answer
> 5 votes
This problem can be solved by means of dynamic programming. One of the best known dynamic programming algorithms is for the knapsack problem. It may be instructive to compare the two problems.

Let $C(n,m)$ denote the solution to the maximal weighted sum problem for the sequence $a\_1, a\_2, \ldots a\_n$ with a subsequence of length $m$ where $1\leq n\leq N$ and $1\leq m\leq M$.

Then $C(n,m+1) = \mathop{max}(C(n-1,m+1), C(n-1,m) + (m+1) \cdot a\_n)$.

To compute $C(N,M)$ this algorithm can be implemented in $O(N M)$ time and $O(N)$ space.

---
Tags: algorithms, optimization
---


title: Efficient subtype testing

text:
# Question
Title: Efficient subtype testing
Languages like Java, C#, Eiffel, and C++ have subtype hierarchies which are directed acyclic graphs, due to interfaces in Java and C# and multiple inheritance in Eiffel and C++. An obvious way to check whether type $A$ is a subtype of type $B$ is to traverse the graph of the subtype hierarchy starting at $A$ to see whether type $B$ appears 'above' it. This surely is not the most efficient way to implement subtype tests.

> What techniques exist to efficiently implement subtype testing for modern OO languages?

I'm interested in efficiency both in terms of time and memory and any trade-offs between the two.

# Answer
> 2 votes
Yves Caseau gave a method for efficiently encoding type hierarchies as bit vectors. See Efficient handling of multiple inheritance hierarchies.

---
Tags: programming-languages, compilers, typing
---


title: Optimal myopic maze solver

text:
# Question
Title: Optimal myopic maze solver
I was fooling around with Google Blocky's Maze demo, and remembered the old rule that if you want to solve a maze, just keep your left hand to the wall. This works for any simple-connected maze and can be implemented by a finite transducer.

Let our robot be represented by a transducer with the following actions, and observables:

* Actions: go forward ($\uparrow$), turn left ($\leftarrow$), turn right ($\rightarrow$)
* Observables: wall ahead ($\bot$), no wall ahead ($\top$)

Then we can build the left-hand maze solver as (pardon my lazy drawing):

Where seeing an observable will make us follow the appropriate edge out of the state while executing the action associated with that edge. This automaton will solve all simply-connected mazes, although it might take its time following dead ends. We call another automaton $B$ *better than* $A$ if:

1. $B$ takes strictly more steps on only a finite number of mazes, and
2. $B$ takes strictly fewer steps (on average; for probabilistic variants) on an infinite number of mazes.

My two questions:

1. **Is there a finite automaton *better than* the one drawn above?** What if we allow probabilistic transducers?
2. **Is there a finite automaton for solving mazes that are not necessarily simply-connected?**

# Answer
> 6 votes
If I understood well the question, I think that you can apply a speedup trick to get faster automata on an infinite number of mazes (providing that the exit is placed on one of the border): you can simply use the internal states to store a finite number of steps and recognize dead ends like the one in the figure:

When a right-hand following automaton is in position $A$ and its state "signals" that it has just followed a closed square (*with fixed size encoded, not an arbitrary large square*), then it can safely turn left and avoid visiting the dead end zone. As underlined in my comment below, the automaton will apply the shortcut on every maze that contains one (or more) "submazes" like the one in the figure, so it will perform better on infinitely many mazes. On the mazes that don't contain a submaze like the one in the figure it will perform like a standard right-hand following automaton.

In a similar manner you can encode a finite number of different fixed size shapes to avoid dead ends and speed up your automaton. As a consequence, there is no "optimal" myopic maze solver for simply-connected mazes with the exit placed on the border.

The trick works if the entrance is placed inside the maze and the exit on the border, too; but if the exit is placed inside the maze, then it doesn't work because all locations must be visited and in this case your myopic solver is optimal.

Obviously you can't apply the same trick to solve non-simply connected mazes (but it should work if there is a fixed upper bound on the size of each unconnected component).

# Answer
> 5 votes
**Question 1**

I think your definition of *better* is too strict in the sense that *finite* is too restrictive (but I don't have any better definition).

We build a family of mazes $R=(R\_i)\_i$. Each one $R\_i$ is a corridor of length $i$ that ends with a turn on the right. The same with $L$ and left, respectively. We can build a transducer $A\_R$ and $A\_L$ that optimally solve the subsets $R$ and $L$, respectively. Then no transducer is better than $A\_R$ or $A\_L$.

Now the other way around : given $A\_R$ we can build $R$ that proves that no solver is better than $A\_R$. My point is that I think we can do the same for the left-hand maze solver, but the set of mazes would be more complex.

Probabilistic transducers can probably ruled out since a deterministic transducer will be faster on these infinite sets of mazes.

**Question 2** (thanks to the discussion with OP)

No. (source: this groundbreaking paper by Lothar Budach. The theorem is more clearly stated in the abstract of this article by Frank Hoffmann.)

---
Tags: automata, finite-automata, artificial-intelligence
---


# Question
Title: Show that the halting problem is decidable for one-pass Turing machines
$L=\\{\<\\!M,x\\!\>\\, \mid M's \text{ transition function can only move right and } M\text{ halts on } x \\}$. I need to show that $L$ is recursive/decidable.

I thought of checking the encoding of $M$ first and determine whether its transition function moves only right (Can I do that?). If so then try to simulate $M$ on $x$ for $|Q|+1$ steps, if it stops then $\<\\!M,x\\!\>\\, \in L$ otherwise it is not.

Is this correct?

# Answer
> 6 votes
I assume $Q$ is state set of $M$. If so, this runtime bound does not make much sense; in particular, a Turing machine with three states can move to the end of the input and check whether $x$ is an even number; it is clearly not enough to wait three steps.

The next question is whether there *is* a computable bound on the runtime of halting one-pass machines. Unfortunately, there is not: $M$ might be nondeterministic and halt after an arbitrary amount of steps.

So we determinise $M$ while simulating (that is computable) and look for a bound for all paths. Now we are getting somewhere: after having consumed the input, there are two cases. Either $M$ halts or it enters a loop. As it only moves right (into empty tape), such loops can be detected.

> Putting things together, we simulate a determinisation of $M$. We run every branch until $x$ is consumed¹ and then for another $|Q|\cdot|\Sigma\_T|$ steps, $Q$ the set of states and $\Sigma\_T$ the tape alphabet of $M$. At this point $M$ has either stopped or loops (in this branch), which we detect by a pair of current state and tape symbol occuring for the second time. We only have to check finitely many branches up to a computable bound, therefore $L$ is recursive.

---

1. $M$ might loop here already if not moving the head is allowed, but that can be detected, too.

---
Tags: formal-languages, computability, turing-machines, check-my-proof
---


title: Streaming algorithm and random access

text:
# Question
Title: Streaming algorithm and random access
Consider an array $X$ of $n$ cells, each containing a number from $\\{1,..., n\\}$. There is at least one duplicate number, i.e., a number that appears at least twice. I want output *some* duplicate number. When streaming we may pass over $X$ more than once. The inspection of a cell generates cost $1$. The cost of a run of an algorithm is the sum of all individual costs. I can at most store $\log\_2n$ bit numbers. I tried to do that with a streaming algorithm that uses additional memory $O(1)$ with costs $O(n^2)$. Is it possible to state a ramdom access algorithm that uses additional memory $O(\log\_2n)$ with costs $O(n)$?.

Which algorithm solves the problem by using additional memory $O(1)$ with costs $O(n^2)$?. Which algorithm solves the problem by using additional memory $O(\log\_2n)$ with costs $O(n)$?.

My problem is similar to the cycle detection problem, but I don't know how to use the cycle detection problem to solve mine. Is there maybe a simpler way that I can't see now?

# Answer
> 2 votes
Here's how to reduce your problem to cycle detection. Your array is a mapping $f$ from $\[n\]$ to $\[n\]$. From each starting point $x$, you can iterate $f$. Using a cycle detection algorithm, you can either find out that the iterates of $x$ form a cycle, or find two iterates that map to the same point (your duplicate). For *some* starting point, you will find a duplicate.

---
Tags: algorithms, randomized-algorithms, randomness, streaming-algorithm
---


# Question
Title: Turing machine and language decidability
The document I am reading is here: Turing Machines

Before getting into the question, here is the notation used on the picture:

> Here $\Delta$ denotes the blank and R, L and S denote move the head right, left and do not move it, respectively. A transition diagram can also be drawn for a Turing machine. The states are represented by vertices and for a transition $\delta( q, X ) = ( r, Y, D )$ , where D represents R, L or S , an arc from q to r is drawn with label ( X/Y , D ) indicating that the state is changed from q to r, the symbol X currently being read is changed to Y and the tape head is moved as directed by D.

According to the document:

> A Turing machine T is said to decide a language L if and only if T writes "yes" and halts if a string is in L and T writes "no" and halts if a string is not in L

Here is the three examples:

* Case 1:

* Case 2:

* Case 3:

I just want to verify my understanding. According to the definition, in case 1 and case 2, its turing machines cannot decide because the machines cannot tell whether invalid inputs rather than { a } (such as aa, aaa, aaaa....) is in L or not.

In case 2, if another a appears after the first a, or if the input is empty, the machine goes to state S and loop forever.

In case 3, if `a` is detected and only a single `a` exists, that `a` is replaced by `1` and the machine accepts. Otherwise, a `0` is replaced and the input is decided not in the language.

Am I correct on all of these? However, in case 3, what if I give any input which contains other character rather than `a` (such as string `ab`, `bc`...)? Or is it said that TM decides only languages over a set of alphabet $\Sigma$ allowed by the Turing Machine?

If a string which is longer than a single `a` (like `aa`, `aaa`,`ab`,`bc`...), the machine may loop forever (like in case 2) or halt without accepting (in other words, it is "crashed", where it does not have transition rules for a symbol in the input such as `b` in the case of above Turing Machines). Is this correct also?

# Answer
> 8 votes
A TM *decides* a language if it enters the *accepting* state for word in the language and it enters the *rejecting* state if it is not. Thus it halts on all inputs. **Note** the machines defined above are not entirely standard. They way they denote acceptance and reject is by writing a $1$ or $0$ and then by entering a halting state. This is equivalent to the standard definition, but less elegant.

Machine 1 does not reject words not in the language. It only accepts the language.

Machine 2 does not halt for words not in the language. It only accepts the language.

Machine 3 rejects and hence halts for words not in the language, therefore it decides the language.

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


# Question
Title: Alpha-Beta Pruning with simultaneous moves?
I have a game I'm building some ai for that has 2 players making simultaneous moves. In this game there is exactly one move where, if they both make it at the same time, the outcome is different than if they'd made it separately (all other moves are pretty independent).

Anyway, I'm trying to find a good algorithm to throw at it. Minimax with alpha-beta pruning seems like it would be a good candidate if the players were making alternating moves, but not for simultaneous ones. I found a paper(pdf) on the topic, but it's a little over my head- I'm having trouble reading the pseduocode.

So, can someone either help clarify that approach, suggest another way to accomplish alpha-beta pruning on such a game, or suggest a better algorithm entirely?

# Answer
The thing is that with simultaneous moves, the optimal strategy is harder to guess, because you need to compute something that is not always obviously winning.

Have a look at Nash equilibrium and the prisoner's dilemma if you don't know them yet. This is the kind of reasoning that you will need *each time* you are considering two simultaneous moves, instead of simply choosing a move that goes into a winning configuration in games with non-simultaneous moves. The concept of dominance replaces the concept of winning.

The algorithm in your reference does that when referring to figures 4 and 5 but first try to figure out what those figures are supposed to do before understanding how they do it.
> 9 votes

---
Tags: algorithms, artificial-intelligence, search-algorithms, game-theory
---


# Question
Title: How do I test if a polygon is monotone with respect to an arbitrary line?
> **Definition**: A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice.

Given a polygon $P$, is it possible to determine if there exists any line $L$ such that the polygon $P$ is monotone with respect to $L$? If yes, how?

Previously, I asked a related question (where I asked how to determine if a polygon is monotone with respect to a particular line), but now I am interested in the case when $L$ is **not** given or specified in advance.

# Answer
> 16 votes
It is possible.

Consider you polygon and consider the "concave" vertices. They define exactly which lines will intersect the polygon more than twice. In the following figure I marked the intervals (in red) of forbidden angles. If you put them together and see a hole in the red disk, then there are authorized angles $δ$ (in blue). The polygon is then monotonous with respect to any line of slope $-1/\tan δ$ (in green).

Now the algorithm.

Let $v\_i=(x\_i, y\_i)$ be the $i$th vertex of the polygon. First compute the absolute angle $α\_i$ of the edge $(v\_iv\_{i+1})$ and the inner angle $β\_i$ of the vertex $v\_i$. Use the function `atan2` available in all good programming languages.

$$α\_i=\mbox{atan2}(y\_{i+1}-y\_i,x\_{i+1}-x\_i)$$ $$β\_i = α\_{i+1}-α\_i+ \left\\{ \begin{array}{ll} 0 & \mbox{ if } α\_{i+1} ≥ α\_i \\ 2π & \mbox{ if } α\_{i+1} \< α\_i \\ \end{array} \right. $$

Reverse the order of the vertices if they are not in the counterclockwise order, i.e. if $s=\sum\_i β\_i-nπ$ is not negative. ($s=-2π$: counterclockwise, $s=2π$: clockwise).

The following is only for the $m$ inner angles bigger than $π$ that is, $β\_j\>π$. The red ones in my pic. The goal is to find an angle $δ$ that is not in $∪\_j\[α\_{j+1},α\_j\]$ modulo $π$. Namely such that for all $j$ such that $β\_j\>π$:

$$(δ\<α\_{j+1} ∨ α\_j\<δ) \mbox{ if } α\_{j+1}\<α\_j$$ $$(α\_j\<δ\<α\_{j+1}) \mbox{ if } α\_j\<α\_{j+1}$$

where $α\_j$ is here the normalized value of $α\_j$ in $\[0,π)$. The second case correspond to an interval that goes beyond $π$ (so this time $δ$ must be "inside").

There is probably a faster way to do this but one in $O(n^2)$ is to sort the values $α\_j\mbox{ mod }π $ into $γ\_1,…γ\_m$ and to test for $δ∈\\{\frac{γ\_1}2,\frac{γ\_1+γ\_2}2,…,\frac{γ\_{m-1}+γ\_m}2,\frac{γ\_m+π}2\\}$.

If you have find some $δ$ then $L$ exists and is of slope $-1/\tan δ$. Otherwise $P$ is not monotonous.

---
Tags: algorithms, computational-geometry
---


# Question
Title: Point Location Problem in Polygon in Repetitive Mode for a Simple Polygon
I consider Point Location Problem in Polygon in repetitive mode in the case of simple polygon.

In computational geometry,Point Location Problem in Polygon problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon.

There are few method that work in Single-Shot approach, where the input is a polygon $P$ and a single point $q$ (no preprocessing time). Ray casting algorithm is the famous algorithm for single-shot, it takes $O(n)$ to determine whether a point $q$ belongs to polygon $P$.

In addition, there is a repetitive approach, where instead of single point $q$ we should check the sequence of points, therefore the preprocessing is required. Division wedge is a algorithm that works in repetitive mode. Query time of division wedge is $O(\log n)$ and preprocessing time is $O(n)$. Division wedge assumes that there is a central point in polygon, visible from every vertex of polygon (part of the kernel of the polygon). The problem is a central point can be easily determined in convex polygon as well as in star-shaped polygon, but what to do in the case of simple polygon.

If division wedge is applied in the case of simple polygon how we can determine a central point in simple polygon? If division edge in not applied if there is the more efficient way to solve a problem in simple polygon than in arbitrary planar subdivision.

# Answer
> 2 votes
First question:

By (my interpretation of the) definition, a "central point" exists if and only if the polygon is star-shaped; this condition can be tested in $Θ(n)$ time. So the only thing you can do is run this algorithm, apply division wedge if you find a non-empty kernel, and apply another algorithm if you find an empty kernel.

---
Tags: algorithms, computational-geometry
---


# Question
Title: Resolution complexity versus a constrained SAT algorithm
EDIT: ad hoc speed-ups are excluded.

We have the result that propositional resolution requires exponential time. The resolution result uses the proof of the pigeonhole principle as an example of a proof that takes exponential time.

Let's also say we have a hypothetical algorithm M for SAT that runs in polynomial time. **EDIT : M is correct, complete, sound, and general-purpose; it contains no ad hoc speed-up rules for the pigeonhole principle or any other theorem that requires exponential length in resolution.** M takes its input in clausal form; we'll set up the input like a resolution proof where the consequent is negated to lead to unsatisfiability if the theorem is true. Now let's consider how the proof of the pigeonhole principle works in algorithm M with a strong condition C added:

C. We are given that M simply transforms one clause (or set of clauses) to another clause (or set of clauses). Every such transformation is logically sound.

Some questions; please point out the most fatal flaws:

1. Given condition C above, and since M's rule system must be finite, correct, and complete, can we conclude that there is a translation from M's rule system to an equivalent set of expansions based on resolution?
2. Are we now in a place where we can conclude that M would produce a computation that could be mapped by the translation in point 1 above into an impossible polynomial-time resolution proof of the pigeonhole principle?

# Answer
> 5 votes
1. While the deductions made by $M$ can have equivalent (possibly exponentially bigger) resolution proofs, I'm not sure what you mean by translating the rule system of $M$ into resolution form. If $M$ has a rule saying that if the problem is a PHP (pigeonhole principle) problem then output unsat if number of pigeons \> number of holes, how would you translate that rule into resolution form?
Edit: To elaborate on the last point, we know that Extended Resolution (ER) which in a nutshell, allows one to add new variables, has polynomial-size PHP proofs. Now suppose, $M$ uses ER to prove PHP. Such reasoning cannot be "directly" translated into a resolution proof as that would require adding new variables to the formula which is not allowed in pure resolution proofs.
2. As I mentioned in point 1, you can translate the deductions by $M$ into resolution proofs of those deductions but the resolution proof might be exponentially larger.

---
Tags: complexity-theory, logic, satisfiability, sat-solvers
---


# Question
Title: Automata that recognizes Kleene closure of permutations of three symbols
This is an automata theory homework question.

I need to create DFA that meets the following criteria:

* Alphabet $\Sigma = \\{ a, b, c \\}$
* Machine accepts empty string and strings of length that is a multiple of three, with every block of three containing one $a$, one $b$ and one $c$.

So far, I came up with this machine, it is obvious:

However, I can't get it to accept empty string. Does it mean there is a transition q0 → q3?

**Update1:** Following corrections by Dave Clarke I made some corrections.

1. A regular expression for this machine is $(www)^\*$ where $w = \\{abc,acb,…\\}$. Therefore to represent multiple of three, I need to copy this (on the picture) machine 3 times. Final state should have arrows pointing to the first copy, for transitions marked 'a', 'b','c'.
2. As it was pointed out, since this is DFA, I need to add missing states. This can be accomplished by adding "dead" states.
3. Empty string should correspond to $\varepsilon$-transition from qStarting → qFinal.

**Update2:** As it was pointed out, my regular expression is wrong ! It should be $(w)^\*$. Here is the final machine, that I think should be correct.(I didn't include "dead" state)

# Answer
There are a few things wrong with this automata:

1. It does not accept the empty string.
2. It is not a DFA – there should be no undefined transitions in a DFA.
3. It only accepts strings of length three, not multiples of three.

You are on the right track. Dealing with 1. and 3. above are fairly straightforward.
Feed in an empty string. What state do you end up in? What does it mean to accept?
Feed in some longer strings. What's the pattern?
Dealing with 2. is rudimentary too, just a matter of filling in the missing transitions.

It's a good idea to read and understand again the definition of DFA, in particular, understanding what is allowed and what is not allowed.

**EDIT**: Here is a prettier solution:
> 6 votes

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