# Question
Title: Algorithm Request: "Shortest non-existing substring over given alphabet"
I'm looking for an (efficient) algorithm to solve the following problem:

> Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is *not* contained in $S$.

Try as I might, I can't seem to map this problem to any of the standard CS string problems.

# Answer
Here is the clean presentation (after going in circles around it).

First you consider all substrings of S that are in M\*. From that you build a trie, which may be understood as a tree structured FA that recognizes these substrings. You build it so that you complete first the transitions of nodes that are closest to the root. As soon as you have a node from which there is no arc for a given character in M, you have your answer which is the string associated with that node concatenated with the missing character. Complexity is $O(n^2)$ where $n$ is the length of the string S, because that is the maximum number of characters you may have to consider while building the trie.

*Note regarding complexity*: In the trie construction you have to consider only the longest substring in $M^\*$ starting at each position in $S$, since shorter ones are automatically taken care of. Each state thus created is an accepting state recognizing one substring. There are at most $n$ substrings in $M^\*$, each having at most $n$ characters. Each is considered in constant time.
> 6 votes

# Answer
Here's another approach that takes only linear time.

1. Construct a suffix tree for $S$ (and alphabet $M$).
2. Perform a breadth-first traversal and stop at the first missing edge or non-singleton label $ab\dots$ (if there is no missing edge on that level).
3. The path from the root to (and including the) missing edge resp. $ax$ with $x \neq b$ is your result.

This is correct since every substring of $S$ is the label sequence of some path from the root downwards, and breadth-first traversal finds the shortest sequence that does not label such a path.

Regarding the non-singleton labels, if such label $ab\dots$ exists there was no continuation of the current substring other than $ab$, so $\dots ax$ is indeed not a substring. If there was no missing edge on the level of the non-singleton label, the resulting string is as long as any we can find on the next level, so it's shortest.

Using Ukkonen's algorithm, step 1 takes linear time (assuming $M$ is fixed) and the result is a tree of linear size. Therefore, step 2 runs in linear time as well, and 3 three clearly does, too.
> 5 votes

# Answer
Let $n = |w|$ and $m = |\Sigma|$, where $w$ is the input string and $\Sigma$ is the input alphabet. There are $n - k + 1$ substrings of $w$ of length $k$, and $m^k$ strings over $\Sigma$ of length $k$. If $n - k + 1 \< m^k$ then, by the pigeonhole principle, there must be a string over $\Sigma$ of length $k$ that is not a substring of $w$.

There are on the order of $m^i$ strings of length less than $i$ over $\Sigma$. Determining whether an arbitrary string is a substring of $w$ can be done in time $n$. Thus we have, at most, $nm^i$ work to do, where $i = k + 1$ in the worst case. We can extrapolate from the inequality that $n \< m^k$, so $k \> \log\_m n$; so $k = 1 + \log\_m n$ always works. *Note: if we can rule out $k = 1$, we can go even further and let $k = \log\_m n$.*

Taken altogether, this means that the total amount of work that the naïve method (enumerate strings in lexicographic order, and check the input for each string over $\Sigma^\*$ until you find one that's missing) would never do more than $O(n^2m^2)$ (\*fixed an algebraic mistake; had $O(n^3m)$ previously, but should have been $O(n^2m^2)$) work in the worst case, although this bound may not be tight. *Note that if we rule out $k = 1$ and take $k = \log\_m n$, we lose an $n$ and get $O(n^2m)$.*
> 2 votes

# Answer
Here is another approach that is conceptually simple (you are asking for "standard string problems").

1. Construct an NFA $A$ for $M^\*$ (two states).
2. Construct an NFA $B$ for $\\{ w \mid vwx = S; v,w,x \in \Sigma^\* \\}$ ($n+2$ states).
3. Compute $\overline{B}$.
4. Compute $\overline{B} \cap A$.
5. Find a shortest path from the starting state to a final state (breadth-first search). The traversed edges make up your solution.

Per se, the time for 3. might be huge (and then also 4.) since inverting NFA takes exponential time in the worst case.
> -1 votes

---
Tags: algorithms, data-structures, strings, substrings
---


# Question
Title: PDA with N-Stacks comparison with Turing Machines
Is it possible to compare PDA having N-Stacks with Turning Machines. Are they equally powerful in this situation?

It's been told that PDA with 2-Stacks is equally powerful to Turning Machine. But what if we add more stacks i.e. 3, 4, 5...N to PDA; will it become more powerful or it can serve same purpose.

# Answer
> 0 votes
2 stacks is enough for a PDA to be as powerful as a Turing Machine. Basically, you can pop from one stack and push into the other to simulate moving across the tape head, writing, etc.

In fact, a 2-counter machine is as powerful as a Turing Machine, though the proof is much more involved. There's a sketch of it on Wikipedia

---
Tags: turing-machines, pushdown-automata
---


# Question
Title: Confusion about example in Raft consensus paper
In part (c) of Figure 8 in this paper http://ramcloud.stanford.edu/raft.pdf, I am confused how S1 knows that the current term is 4 when it restarts and is elected leader.

Here is the sequence as I currently understand it:

1. S1 is elected leader for term 2, partially replicates a request, and then dies.
2. S5 is then elected leader for term 3, receives but does not replicate a request and then dies.
3. S1 restarts, (still thinking it is term 2), is elected leader (for term 4?), and then replicates a term 2 request to a majority of nodes, but does not commit.

My confusion is in step 3. When S1 reawakens, it is elected leader for term 4, even though it hasn't been active since term 2. How does S1 know that it is now term 4?

Citation for linked paper:

O NGARO , D., AND O USTERHOUT, J. In search of an understandable consensus algorithm. In Proc ATC’14, USENIX Annual Technical Conference (2014), USENIX.

# Answer
> 3 votes
Server 1 does not immediately know the term when it starts up. Terms and other state such as commit indexes are (normally) held in memory and shared only via RPCs. Therefore, even though server 1 died when it was the leader for term 2, it won't even know about term 2 when it starts back up, let alone term 4.

The way server 1 will learn the term is via AppendEntries and RequestVote RPCs. When server 1 starts, it will initialize its term to 1. If it receives a heartbeat from node 5 before it dies, the heartbeat (an AppendEntries RPC) will contain server 5's term: 3. Given that information, when server 5 dies and server 1's election times out, it will transition to candidate, increment its term to 4, and start the election. This is the likely way in which this scenario might occur since server 2 could also win an election with or without server 1 being alive.

The reason server 1 would need to have been alive for some period of time prior to server 5 crashing is because of server 1 starts a new election immediately after it starts (without having communicated with any other node) it will lose the election since its term (1) will be less than the term of all other servers. In that scenario, server 2 would also start an election and ultimately win before server 1 can update its term and start another election.

---
Tags: distributed-systems
---


# Question
Title: How can I generate first n elements of the sequence 3^i * 5^j * 7^k?
How can I efficiently generate the first N elements of the sequence $3^i 5^j 7^k$, where $i,j,k \in \mathbb{N}$?

I've googled around a bit and found the sequence in OEIS, but I don't really see a simple way of generating it.

# Answer
> 15 votes
Here I assume $0\in \mathbb N$. If you disagree start with $105$.

Let $S$ be the sequence of numbers of the form $3^i5^j7^k$. Our task is to generate these numbers in order. Apart from $1$ each number added is of the form $3\cdot x$, $5\cdot y$ or $7\cdot z$ where $x,y,z$ are previous numbers in the sequence. We can generate $S$ by shifting $x,y,z$ along the sequence.

So, first put $1$ into $S$, and set $x,y,z$ equal to $1$.

Now repeat: Take the minimum value $m$ of $3\cdot x$, $5\cdot y$ and $7\cdot z$, and add $m$ to the sequence $S$. The $x,y,z$ for which the minimum was taken are shifted to the next element of $S$. This might be more than one, or even all three.

$\newcommand{\ul}\[1\]{\underline{#1}}$ $\begin{array}{r|rr|rr|rr} S & x & {}\*3 & y & {}\*5 & z & {}\*7 & \\\hline 1 & 1 & \ul{3} & 1 & 5 & 1 & 7 \\ 3 & 3 & 9 & & \ul{5} & & 7 \\ 5 & & 9 & 3 & 15 & & \ul{7} \\ 7 & & \ul{9} & & 15 & 3 & 21 \\ 9 & 5 & \ul{15} & & \ul{15} & & 21 \\ 15 & 7 & \ul{21} & 5 & 25 & & \ul{21} \\ 21 & 9 & 27 & & \ul{25} & 5 & 35 \\ 25 & & \ul{27} & 7 & 35 & & 35 \\ 27 & 15 & 45 & & \ul{35} & & \ul{35} \\ 35 & & \ul{45} & 9 & \ul{45} & 7 & 49 \\ 45 & 21 & 63 & 15 & 75 & & 49 \end{array}$

Works in linear time, as we need to take the minimum of three numbers in each step.

# Answer
> 5 votes
Consider a weighted, directed graph, with a vertex $v\_i$ for $i\in\mathbb{N}$. There is an edge with weight $j-i$ from $v\_i$ to $v\_j$ if $j\in\\{3i,5i,7i\\}$.

Now run Dijkstra's shortest path algorithm. It will expand exactly the nodes from your sequence and do so in order. This gives an $n\log n$ algorithm to enumerate the first $n$ elements, since the graph has maximum out-degree $3$.

---
Tags: algorithms, efficiency, number-theory, enumeration
---


# Question
Title: Can all packing/covering problems be rephrased as set packing/covering problems?
Can all packing problems be rephrased as set packing problems?

Can all covering problems be rephrased as set covering problems?

In other words, I was wondering if set packing/covering problems are the most general forms of packing/covering problems?

# Answer
> 2 votes
If we restrict ourselves to problems in NP, then yes. There are NP-complete problems of either category, so (many-one poly-time) reductions exist; we can view these as "rephrasing".

Since integer programming is also NP-complete, these same is true for that one.

Problems outside of NP do not reduce to integer programming, but I am sure that any (meaningful) complexity class contains examples of both covering and packing problems.

It's not the "type" of a problem that determines its hardness. There are satisfiability problems all the way from linear complexity to undecidability, to name just one example.

---
Tags: terminology, optimization
---


title: Complement and Context Free Surprising

text:
# Question
Title: Complement and Context Free Surprising
Anyone can describe why $L\_{1}$ is not the complement of $L\_{2}$, and why $L\_{2}$ is not context free?

$$L\_{1}= \\{w\_{1}cw\_{2} : w\_{1},w\_{2} \in \\{a,b\\}^{\ast}, w\_{1} \neq w\_{2}\\}$$ $$L\_{2}= \\{w\_{1}cw\_{2} : w\_{1},w\_{2} \in \\{a,b\\}^{\ast}, w\_{1} = w\_{2}\\}$$

# Answer
> 3 votes
If two languages $A$, $B$ are complements of each other, then their disjoint union $A \uplus B$ must be the set of all strings $\Sigma^{\ast}$ over the given alphabet $\Sigma$. That is, every string in $\Sigma^{\ast}$ has to be in $A$ or $B$ but not both. So if we want to show that $L\_{1} \neq \overline{L\_{2}}$, all we have to do is find a string that is either in both or neither.

In this case it's fairly trivial. All strings in $L\_{1}$ and $L\_{2}$ have a $c$ in them, so pick any string that doesn't have a $c$ it in. For example $\varepsilon$, it's in neither $L\_{1}$ nor $L\_{2}$.

A construction for a PDA for $L\_{1}$ is given here.

As for proving $L\_{2}$ is not context free, everything you need is here.

# Answer
> 0 votes
The intuitive idea is in the quantifiers, but that is not a formal proof.

Nonequality $w\_1 \neq w\_2$ if there is *some* position in which both words differ. We can chack this position by *guessing* it in the first word $w\_1$, storing the number on the pushdown, and checking it for $w\_2$. According to this "intuition" we have to use nondeterminism, and we cannot use the position on the pushdown more than once.

For equality $w\_1=w\_2$ we must verify that *all* positions are equal. There is no good way to do that. A formal proof of this must take into account all possible strategies (not just this intuition).

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


title: Proving a string is random

text:
# Question
Title: Proving a string is random
I am reading Kolmogorov Complexity by Li and Vitányi:

"Let $x$ be a finite binary string. We write '$x$ is random' if the shortest binary description of $x$ with respect to the optimal specification method $D\_0$ has length at least $x$." By length $x$ I understand the natural number that the binary string maps to canonically.

\[proof which I do not understand follows\]

"This shows that although most strings are random, it is impossible to effectively prove them random."

However, I am able to produce a counterexample and can find a proof that $x$ is random effectively (there is an algorithm). Iterate over all the words of size up to $x-1$ of a description language. If you find a description $\alpha\_x$ such that $D\_0(\alpha\_x)=x$ ($\alpha\_x$ describes $x$) then terminate with verdict that $x$ is not random. If you exhaust all the words of length $\<x$(there are finitely many since $x$ is finite so the program halts) and none of them describes $x$ and then terminate with result that $x$ is random.

What is wrong in my counterexample?

# Answer
> 2 votes
The catch is that $D\_0$ is only a *partial* recursive function and it may not be possible to verify that $D\_0(\alpha) = x$ in finite time. There is no way around that because $D\_0$ must be universal, and there is no way a machine implementing it would halt on every input, because not every Turing machine halts on every input.

---
Tags: computability, kolmogorov-complexity
---


# Question
Title: Find the shortest string that is not a sub-string of a set of strings
Alphabet: `abc`

Sample input:

1. `abc`
2. `cba`
3. `aabbcc`
4. `aaabbbccc`
5. `caac`

Sample good outputs: `acb`, `cab`, `cac` and others, since they are not substrings of any other, and because all strings of length 1 and 2 are present.

Sample bad outputs:

* `aab` since it is a substring of 3)
* `aaaa` because it is not minimal: we have other solutions with 3 characters only

Questions:

* What are the best ways to solve it?
* Does the problem have a well known coined name?
* What is the complexity of the calculation in terms of the input size (number of strings N and maximum string length M)?
* What is the average asymptotic size of the output considering random uniformly distributed inputs?

Related questions:

Applications:

# Answer
Here's one possible solution, similar to the linked question: Algorithm Request: “Shortest non-existing substring over given alphabet”

Use a sliding window over each input string to build your `trie`.

* For `n=1` to `n=max(length(s))` where `s` is an input string, do:
* For each `s`, construct window of size `n`, slide window over `s` adding each window (substring of size `n`) to the `trie`, then
* Visit each `parent` of the `leaf set` of the `trie`. If there exists a `parent` node whose set of `child` nodes is smaller than the size of the `alphabet`, then you can form your desired string from this `parent` by appending a `character` from the `alphabet` that does not result in a string identical to one of the `leaf` nodes
* If no such `parent` node exists, continue to next larger `n`
> 2 votes

---
Tags: algorithms
---


# Question
Title: Hoare logic - partial/total correctnes and strength invariant
I'm studying Hoare logic and I can't understand the relation between partial and total correctness regarding loop invariant. Suppose for example that I have the following program:

```
{X ≥ 0}
Y := 0;
Z := 0;
{Y =2Z}
while (Z ̸= X) do (
Z := Z + 1;
Y := Y + 2 )
{Y =2X}

```

The solutions says that for partial correctness I can use the invariant Inv = 2Z. But when I have to prove total correctness the invariant must be strengthened with X - Z \>= 0. Which is the hoare logic property that let me strength the invariant, adding the condition to it, only for total correctness?

# Answer
You're misunderstanding. It's not that when you try to prove total correctness, Hoare logic somehow magically finds a stronger invariant for you. Hoare logic doesn't find the invariant for you -- either way, you have to find the invariant yourself and then prove it.

Rather, it's that you need to prove a stronger invariant if you want to prove total correctness. A weaker invariant can suffice to show partial correctness. Therefore, total correctness can often be harder to prove than partial correctness (proving total correctness requires more work, because you have to prove a stronger, more detailed invariant).
> 3 votes

---
Tags: proof-techniques, program-correctness, hoare-logic, software-verification
---


# Question
Title: Why do computers use binary, instead of ternary, or some other logic system?
In binary a unit (bit), can store 2 separate values.

if you have ternary, then a unit can store 3 separate values.

why then don't computers use higher bases, for example in ternary you could have 3 different voltages, and even if transistors got a little bigger, wouldn't it still be more efficient?

# Answer
> 2 votes
* 3 different voltage levels makes building circuits harder and it is easier for little errors to occur in the signals.
* Circuits need complex logic instead of the easy boolean logic which works perfectly.
* Ternary is not compatible with binary that all computers use.

---
Tags: efficiency, storage
---


# Question
Title: Language intersections (set theory) - Understanding better
I've joined computer science classes at high school because I have a wide knowledge and a few years of experience in programming in multiple of languages, however I didn't fit in the requirements of the class, which is a specific mathematics level. I am a low level mathematics student, I don't really know formal mathematics or any proofs besides a simple proof like proving that an angle is 90 degrees.

So besides programming, there is this subject we started studying about finite deterministic automatons, stack automatons, turing machines and regular languages, etc.

I understand the concept very well, especially when it comes to building turing machines, finite and stack diagrams. At the class, we solve these automatons with diagrams, not in a formal way.

So besides that, my teacher gives us a lot of questions about union, intersection and I am getting really confused with intersection.

Surely I can understand the basic intersections with set of words:

$L = \\{aab, bba, aa\\}$ $L' = \\{a, bbba, aab, aa\\}$

So $L\cap L'$ would be $\\{aab, aa\\}$

I also understand basic language intersections like this:

$L = \\{a^n b^n \mid n \ge 0\\}$, $L' = \\{a^n \mid n \ge 0\\}$

$L\cap L'$ would be $\\{a^n \mid n \ge 0\\}$

But when it comes to something like this:

$L = \\{a^{2n} b^m a^k \mid n,m \ge 0, k = m \mod 2\\}$

$L'$ = set of string elements such that the length $|w|$ is even

$L\cap L'$ = I don't know the answer for

The second part of the language which defines the length of the elements (e.g on $n$, of $m$, of $k$) really confuses me in intersections and unions, I am not really sure why. Does that part matters in intersections? I am always getting lost in these cases.

How can I understand this concept a bit better mathematically?

# Answer
In your last example, when trying to deduce $L \cap L'$, the trick is to trying to understand which strings in $L$ have even length. You can do this as follows:

$$L = \\{a^{2n} b^m a^k | n,m \>= 0, k = m \pmod 2\\}.$$

We can forgot about the first substring of $a$'s, because they always come in pairs (or there are none. In either case, they contribute an even number of characters. Now consider $\\{b^m a^k | m \>= 0, k = m \pmod 2\\}$. The length of the strings in this set is $m+k$. Since $k = m \pmod 2$, we have $m+k = m + m = 2m = 0 \mod 2$. Therefore, $m+k$ is always even, and so $b^m a^k$ always contributes an even number of characters as well. Since $even + even = even$, every string in $L$ is even. Therefore, $L \cap L' = L$.
> 4 votes

---
Tags: sets
---


# Question
Title: Given a PRAM may use arbitrarily many processors, why is Hamiltonian Cycle not in NC?
In my parallel algorithms class, the PRAM model is described as having an "arbitrary number of processors, bounded by some polynomial in the input size."

I think that this may be missing a constraint. For example, this would imply that finding a Hamiltonian cycle is in NC:

If I give all of the permutations of the vertices of a graph as input, then I can assign a processor to each permutation, and each processor can then check for the appropriate edges in O(|E|) time, which would mean that finding a Hamiltonian cycle would be in NC.

So is there some constraint that is missing from the definition we are using in class, or am I missing something else?

# Edit

**For clarification:** Consider a classical TM, which accepts as input a sane representation of a graph, followed by all of the permutations of a graph's vertices. It then performs the best currently known algorithm for finding Hamiltonian Cycles, and as output writes out a permutation of the vertices describing such a cycle.

The algorithm would perform in time linear in the input size, but in time factorial in the order of the input graph. (The extra inputs don't seem to count as *computations* for a classic TM.)

In the PRAM model (as I have described it), the algorithm would perform in time linear in both the input size, and in the order of the graph. (The extra inputs seem to count as computations for the PRAM model... Which makes me think that "computation" means something subtly different here...)

If this is the way it is supposed to work: awesome. If not, than am I missing some constraints on what the allowed inputs are?

# Answer
> 2 votes
> If I give all of the permutations of the vertices of a graph as input

That's not the input for Hamiltonian Cycle; you only get the graph.

> then I can assign a processor to each permutation

Since there are $n! \in \omega(c^k)$ many permutations, you don't have that many processors.

Here's the twist: if you *were* allowed to use all permutations as input, you'd of course have polynomially many processors *in $n!$* at your disposal. But since your input is the graph you only get polynomially many *in $n$*.

---
Tags: complexity-theory, parallel-computing, computation-models, nc
---


# Question
Title: Decomposition of the set of computable functions into base functions
Say I have some computation model/programming language $M$ (e.g. Turing machine or equivalent), and let $C\_M$ be the set of all partial or total functions $f : \mathbb{N} \to \mathbb{N}$ computable by that model. Also, assume that $C\_M$ is countable.

Now let $B = \\{ B\_1, B\_2, ... , B\_n \\}$ a finite set of computable base functions and $\cdot : C\_M \times C\_M \to C\_M$ an binary operator, which serves as a combination function. Thus, $(B,\cdot)$ is a magma.

I can now choose $B$ and $\cdot$ in such a way that I can decompose each computable function $f \in C\_M$ into a finite product from $(B,\cdot)$, i.e. $\forall f \in C\_M : \exists b\_1, b\_2, ..., b\_k \in B : f = b\_1 \cdot b\_2 \cdot ... \cdot b\_k$.

To show that, I consider that my programming language consists of a set of instructions $I$ and programs are words over $I$. Then, I choose exaclty one base function $b\_{i,m}$ for each instruction $i\_m$. Because each computable function $f$ has at least one program computing it, I can just pick one of those $f$-computing programs $P\_f \in I^\*$ and define $b\_{i,a} \cdot b\_{i,b} \cdot b\_{i,c} ... = f$ when the program is the word $P\_f = i\_a i\_b i\_c ...$.

This decomposition is obviously not very useful, because it makes the base vectors arbitrary and the definition of $\cdot$ an infinite list of special cases. To consider it useful, the operator $\cdot$ should have some form of structure/finite definition, or in other words, be computable. My interest would be an element-wise function, so that given two values $f(x)$ and $g(x)$, it should be possible to compute $(f\cdot g)(x)$.

My question: Assuming $M$ is turing-complete, is it possible to choose $(B,\cdot)$ in such a way that $\cdot$ is elementwise computable, i.e.

$\exists h \in C\_M : \forall f,g \in C\_M : \forall x \in \mathbb{N} : (f\cdot g)(x) = h(f(x), g(x))$

and still have each computable function being decomposable into a finite product from $(B,\cdot)$?

# Answer
> 4 votes
Unlambda is an example of a Turing-complete programming language that implements your requirements.

* Unlambda has only one type, functions. They are also its only basic syntactic elements. In particular there are no variables.
* Its expressive power only requires two *base* terms, `s`, and `k`. They would be your base $B$. `k` takes two arguments and returns the first, while `s` takes three arguments, and applies the result of applying the first one to the third one, to the result of applying the second one to the third one.
* It has an additional construct, ```, which represents function application. It would be your binary operator $(\cdot)$. It is written in a prefix manner.
* So for any term `X`, `Y` and `Z` we have ```kXY = X`, and ````sXYZ = ``XZ`YZ`. These simple rules, believe it or not, are sufficient to make Unlambda Turing-complete.
* Unlambda has a few more built-ins but they are just here to make the programmer's life easier (although mentioning *easy* anywhere in the context of this language is probably an overstatement).

Natural numbers can be represented using Church's method, e.g. $3$ can be written as ```s``s`ksk``s``s`kski` (note `i`, the identity, can be written as ```skk`). Pretty simple, no? Recursion can be defined by building a fixed point combinator, and from there the usual techniques can be applied to define more and more complex functions until an universal Turing machine has been simulated.

This language is based on SKI combinator calculus, which itself finds its source in Combinatory Logic. There is a simple mapping between the Lambda and SKI calculi, which luckily makes proving Turing completeness much easier than actually doing the work!

---

Now that I've introduced the programming language, which is the most interesting part and the crux of this answer, let's go through the tedious details of how to use it to formally answer your question.

* First define an embedding $\phi$ of unlambda programs (restricted to `s` and `k`) into the natural numbers. We could use base-4 encoding by mapping its alphabet $\Sigma = \\{\text{k}, \text{s}, \text{\`}, \text{^}\\}$ with $\\{0, 1, 2, 3\\}$ ($\text{^}$ is the start-of-string character). So for example $\phi(k) = \phi(\text{^k}) = 30\_4 = 12$, and $\phi(i) = \phi(\text{^\`\`skk}) = 322100\_4 = 3728$.
* We can then define $\phi^{-1}$ as the opposite operation, except that for convenience, we'll remove the starting $\text{^}$. So $\phi^{-1}(12) = \text{k}$
* Let's also define an unlambda evaluation function $\text{uneval}$, partially defined on $\mathbb{N}\times\mathbb{N}$ and mapping to $\mathbb{N}$. For any $p$, $q$, $\text{uneval}(p,q)$ is defined as the number of stars printed when compiling and running $\text{\`\`}||\phi^{-1}(p)||church(q)||.\*$ as an Unlambda program, where $church(q)$ is the representation of the $q$-th church numeral in Unlambda, $.\*$ is the Unlambda function which prints one star, and $||$ represents string concatenation. If the Unlambda program thus defined doesn't compile or never halts, then $\text{uneval}$ isn't defined on $(p,q)$.
* Then define the following functions
    + $k : \mathbb{N} \to \mathbb{N}, n \mapsto 2\phi(\text{^k})+1 = 25$
    + $s : \mathbb{N} \to \mathbb{N}, n \mapsto 2\phi(\text{^s})+1 = 27$
    + $init : \mathbb{N} \to \mathbb{N}, n \mapsto 2n$
* Let $B = \\{k, s, init\\}$
* Define $h : \mathbb{N}\times\mathbb{N} \to \mathbb{N}$ as follows
    + $h(2p, n)$ is undefined
    + $h(2p+1,2q+1) = 2\phi(\text{^\`}||\phi^{-1}(p)||\phi^{-1}(q))+1$, if $\phi^{-1}$ is defined on $p$ and $q$, and undefined otherwise
    + $h(2p+1,2q) = \text{uneval}(p,q)$, if $\text{uneval}$ is defined on $(p,q)$
* Define $(\cdot)$ as $(f\cdot g)(n) = h(f(n),g(n))$.

Using these definitions, we have

* $h \in C\_M$, because $\phi$, $\phi^{-1}$, $||$, $\text{uneval}$ and basic arithmetic are all computable.
* and $\forall f,g \in C\_M : \forall x \in \mathbb{N} : (f\cdot g)(x) = h(f(x), g(x))$, by definition of $(\cdot)$

Finally, $(B, \cdot)$ generates $C\_M$ entirely, because

* Unlambda (restricted to `s` and `k`) is Turing-complete, so I can build a (restricted) Unlambda function for any computable function in $C\_M$.
* I can build a constant function whose value is the representation of that Unlambda function using $s$, $k$ and $(\cdot)$. For example, for `add1 = `s``s`ksk`, I can build $s\cdot((s\cdot(k\cdot s))\cdot k)$ whose constant value is $2\cdot3212212010\_4+1 = 1889033$
* I can build a function that evaluates any function $f$ built by the above process on $\mathbb{N}$, simply as $f \cdot init$.

---
Tags: computability, computation-models
---


# Question
Title: Intersection of a language with a regular language imply context free
Lets say you have a language $L$ and you want to determine if it is context free. Context free languages intersected with regular languages are context free. Is that enough to prove that $L$ is context free?

Meaning, given a regular language $P$, if $$L \cap P = T$$ where $T$ is context free, is $L$ is context free?

Let $A =\\{x \in \\{a,b\\}^{\ast} \mid |x|\_a \< |x|\_b \< 2|x|\_a\\}$ how can I show this is context free? Is the only way to create a PDA or a CFG?

# Answer
> 3 votes
## In a nutshell

1. Using closure with one regular language ($\exists P \text{ regular such that }L\cap P$ is context-free) as apparently envisioned in the question does not work. Indeed, for any language $L$ there is a regular language $P$ such that $L\cap P$ is context-free. So there is no way a family of languages can be characterized by this property, other than the family of all languages on an alphabet $\Sigma$, i.e., $2^{\Sigma^\*}$.
2. Using a more universal closure property with all regular languages (universal quantification: $\forall P \text{ regular, }L\cap P$ is context-free) does not work either. But, to prove the context-free (CF) property for intersection with any regular set, you have to prove it in particular for the regular set $\Sigma^\*$. But $L\cap\Sigma^\*=L$, so that you are back to the initial problem of proving that $L$ is CF. This is quite simple, and is not further developed below.
3. The language you are interested in, $A =\\{x \in \\{a,b\\}^{\ast} \mid |x|\_a \< |x|\_b \< 2|x|\_a\\}$, is indeed context-free. A simple way to establish that is to build a non-deterministic PDA that recognizes it. Intuitively, such a PDA could first work as if recognizing $A\_1=\\{x \in \\{a,b\\}^{\ast} \mid |x|\_a = |x|\_b \\}$, then switch non-deterministically to the transitions of a PDA recognizing $A\_2=\\{x \in \\{a,b\\}^{\ast} \mid 2|x|\_a = |x|\_b \\}$ while keeping the same stack.
4. Following site policies, I would also suggest you look at the reference answers to frequently asked questions on this topic, and in particular to *How to prove that a language is context-free?*.

## Using closure as proposed in the question does not work

This is an answer to the first question, since you are actually asking two questions, about using the property of clusre of CF languages with regular sets. You are actually using the property backward, which is not permissible.

There is a very simple counter-example. If you take any language $L$, and any finite subset $R\subset L$, the language $R$ is regular, since all finite languages are regular, and is also context-free since all regular languages are context-free. But $R\subset L$ implies $R\cap L=R$. There is always such a subset $R$ since the empty language $\emptyset$ is regular and is a subset of any other language.

Hence for any language $L$ there is a regular language $P$ and a CF language $T$ such that $L\cap P=T$. You only lave to take $P=T=R$ for some finite subset $R\subset L$ (including the empty one).

Note that this still works when $L=\emptyset$.

The property you are trying to use is a *trivial property*, in the sense that is is true of any language, without exception. Hence, you cannot infer from it alone any specific property that is not equally trivial.

I use finite subsets because they always exists, while some languages do not have infinite regular subset. Infinite regular subsets work too, when they exist.

## Proving that your language $A$ is Context-free

$A =\\{x \in \\{a,b\\}^{\ast} \mid |x|\_a \< |x|\_b \< 2|x|\_a\\}$

There are various ways a language can be proved to be CF. It is always possible to do it with closure properties, because of the Chomsky-Schutzenberger representation theorem ... but that does not mean it is easy.

My suggestion is to build a PDA, actually a non-deterministic one. I have not proved it (so take this with care), but I suspect it cannot be recognized by a deterministic PDA.

If you had to have as many $a$ and $b$, you would use the stack to count the extra $a$'s or the extra $b$, so that you can match the numbers. If you wanted twice as many $b$'s, you would count 2 $b$'s for one $a$, which you can achieve by pushing two $a$'s on the stack for each extra $a$, and matching each with a later $b$, or by matching the $a$ just read with two $b$'s from the stack (I am skipping details). Since you want something in between, you can arbitrarily decide for each $a$ whether it matches one $b$ or two $b$'s.

*There is however a much simpler solution (at least simpler to explain) which I give in the next section. But I decided to leave this one as it may be instructive too. So you may choose to skip to the next section.*

You also have to be careful that at least one $a$ matches two $b$'s, so that you have strictly more $b$'s than $a$'s, and that at least one $a$ matches a single $b$ so that the number of $b$'s is strictly less than twice the number of $a$'s.

The stack bottom is supposed to be $\\$$. The behavior is the same for all states, which are used only to remember an $a$ has matched one $b$, and whether another $a$ has matched two $b$'s.

So you have 4 states: initial $q\_0$, then $q\_1$ when an $a$ has matched a single $b$, $q\_2$ when an $a$ has matched two $b$'s, and $q\_b$ when both have occured, which is a requirement to accept thhe string.

When reading an $a$, you decide non-deterministically whether it must match one $b$ or two $b$'s, and possibly change the state acordingly.

* If you decide for a single $b$:

+ If the top of stack is $b$, you just pop that $b$
    + otherwise you push the $a$ on the stack to be matched with a later $b$.
* If you decide for two $b$'s:

+ If the top of stack is $bb$, you just pop these two $b$ (this can be decomposed into two pops, if your PDA model requires it, by introducing other states)
    + if the top of stack is $b$ with no other $b$ in second position, you pop that $b$ and push an $a$.
    + if the top of the stack is not a $b$, you just push 2 $a$'s.

When reading a $b$, you just try to match it on the stack:

* if the top of the stack is an $a$, just pop it.
* otherwise push a $b$ on the stack.

If you reach the end of the input with an empty stack and state $q\_b$, then you accept.

## Alternative simpler solution

Actually, you do not need to have a PDA that is non-deterministic on each input $a$, and you can make a single non-deterministic choice.

The idea is that you start the PDA working as if it were recognizing $A\_1=\\{x \in \\{a,b\\}^{\ast} \mid |x|\_a = |x|\_b \\}$

Then, after reading at least one $a$, you continue recognition as if you were recognizing $A\_2=\\{x \in \\{a,b\\}^{\ast} \mid 2|x|\_a = |x|\_b \\}$ and must scan at least one $a$ in that phase.

Of course, this is a single PDA. and you do not change the stack as you switch the recognition mode.

You accept on empty stack.

Note that this does not imply that the string recognized is the concatenation of a string in $A\_1$ and a string in $A\_2$. The string could be all $a$'s followed by all $b$'s, or the reverse, as long as the number of $a$'s and $b$'s is right.

# Answer
> 2 votes
No, we can construct (heavy-handedly) a counter example by letting $L = L\_{1} \cup L\_{2}$ where $L\_{1}$ is regular (and hence context free) and $L\_{2}$ is not context free.

Let $L\_{1} = \\{1^{n}\mid n\in\mathbb{N}\\} = 1^{\ast}$ and $L\_{2} = \\{\langle M,x\rangle \mid M\text{ is a Turing Machine that halts on input }x\\}$.

Then letting $L = L\_{1} \cup L\_{2}$, clearly $L$ is undecidable, however $$ L\cap L\_{1} = L\_{1} $$ Clearly $L\_{1}$ is regular, and hence context free, even though $L$ is not.

So this approach can't be used to show that $A$ is context free. If you could find a context free language $B$ and a regular language $C$ such that $B\cap C = A$, that would work, but (at a glance) that seems a difficult approach. In this case it should prove simpler to construct a PDA or CFG for $A$, although it is a little fiddly.

**The construction below is incorrect, I'll come back and fix it when I have time, in the meantime, Babou's answer has lots of options for PDAs**

Taking the PDA approach, we need to keep track of if we have enough $a$s, with the catch that the $b$s might come first, so we need three stack symbols, $\\$$ to mark the bottom of the stack, $\alpha$, which we will use (twice) when we see an $a$, and $\beta$ which we will use when we see a $b$, but don't have an $\alpha$ to take off the stack (so it's like a $-\alpha$ that we have cancel out, in some sense).

So the basic operation is:

* If we see an $a$ and there is not $\beta$ on the stack push two $\alpha$s.
* If we see an $a$ and there *is* a $\beta$ on the stack, pop the $\beta$.
* If we see a $b$ and there is an $\alpha$ on the stack, pop the $\alpha$.
* If we see a $b$ and there is no $\alpha$ on the stack, push a $\beta$.
* When we run out of input, unwind the stack and check for $\beta$s; if there are, go to a sink state, if we find $\\$$ without seeing a $\beta$, accept.

If you think about it, or just play around a little, you'll see that there is actually more structure - we can't have a $\beta$ above an $\alpha$ on the stack, which suggests another approach (but that's an exercise).

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


title: Why is it O(1) (and not, say, O(2))?

text:
# Question
Title: Why is it O(1) (and not, say, O(2))?
If the running time of an algorithm scales linearly with the size of its input, we say it has $O(N)$ complexity, where we understand `N` to represent input size.

If the running time does not vary with input size, we say it's $O(1)$, which is essentially saying it varies proportionally to 1; i.e., doesn't vary at all (because 1 is constant).

Of course, 1 is not the only constant. *Any* number could have been used there, right? (Incidentally, I think this is related to the common mistake many CS students make, thinking "$O(2N)$" is any different from $O(N)$.)

It seems to me that 1 was a sensible choice. Still, I'm curious if there is more to the etymology there—why not $O(0)$, for example, or $O(C)$ where $C$ stands for "constant"? Is there a story there, or was it just an arbitrary choice that has never really been questioned?

# Answer
"$O(1)$" is used because it is simple, clear and unambiguous. "$O(C)$" would be a poor choice of notation because in any given context, $C$ might have a specific meaning, such as the number of clauses in a CNF formula, the number of components in a graph.
> 11 votes

# Answer
There is no reason why you can't write $O(2)$ instead. $O(1)$ can equally be expressed as $O(2)$, or $O(1/2)$ or $O(2\pi)$, etc. (Untitled explained why it can't be $O(0)$.) It's purely a matter of convention.
> 9 votes

# Answer
Others have already answered but I thought I should correct a comment by @Untitled that answers have referred to: $f(x) = O(0)$ does not imply that $f$ becomes negative close to the limit considered.

Indeed the definitions are in absolute value: $|f(x)| \leq c\cdot0$ implies $f$ is $0$ close to the limit considered.
> 5 votes

# Answer
The notation $O$ is frequently used to analyze the running time of an algorithm. It is a convenient notation because it gives a simple scale for comparing algorithms. The functions $n^k$, for $k \geqslant 0$ are part of this scale and the case $k = 0$ corresponds to the constant function $1$. So this choice is just an instance of "the simpler, the better".
> 1 votes

# Answer
You can write $O(k)$ as well, what it conveys is the fact that the asymptotic runtime is independent of the size of the input $n$, and is bound by some constant times $k$.

The Landau notation puts great emphasis on the ease of analysis. Suppose you have to compute $O(1) + O(13) + O(123)$. That can become quite messy, so instead you say $O(1)+O(1)+O(1) \in O(1)$. Again, the intuition here is there is a constant that put a bound on their sum, and is independent of the size of the input.
> -1 votes

---
Tags: terminology, asymptotics, landau-notation
---


# Question
Title: Computing a Sequence of People Entering and Leaving a Room
I've been working on a problem for my Algorithms class, but I've found myself stuck. The prompt is as follows.

> You start with an empty room and a group of n people waiting outside. At each step, you may either admit one person into the room, or let one out. Please design an algorithm which generates a sequence of $2^n − 1$ steps, so that every possible combination of people is achieved exactly once. For example, for $n = 3$, one possible sequence would be
>
> $\qquad\displaystyle e\_1, e\_2, x\_1, e\_3, e\_1, x\_2, x\_1$.
>
> where $e\_i$ means person $i$ enters the room and $x\_j$ means person $j$ exits the room
>
> Hint: study the Hanoi Tower algorithm.

In my research on the prompt, I've found many people referencing Gray Code, but I don't understand how to implement it in an algorithm to compute this combination. I also found a very similar problem, but there wasn't an actual implementation of it.

It would be greatly appreciated if you could point me in the right direction on where to go with this algorithm.

# Answer
**Base case** It's easy to generate the combinations when $n=1$: just use the operation $e\_1$.

**Recursion** Now assume that you have a sequence $ops\_n$ that will generate all the combinations of $n$ people. Define $rops\_n$ to be the sequence of operations that "undoes" $ops\_n$, namely first form the reverse of $ops\_n$ and then replace all "enter" operations with "leave" operations and *vice versa*. For example, if $ops\_2 = \langle\\, e\_1, e\_2, x\_1\\,\rangle$, then $rops\_n =\langle\\, e\_1, x\_2, x\_1\\,\rangle$. It's not difficult to see that $ops\_n, rops\_n$ will generate all the combinations of $n$ people and then produce the same combinations in reverse order.

Finally, show that if $ops\_n$ generates all the $n$-combinations, then the sequence $ops\_n, e\_{n+1}, rops\_n$ will generate all the $(n+1)$-combinations: first all the ones without person $n+1$ and then all the ones with person $n+1$. From this construction it's clear inductively that you can generate all $n$ combinations with $2^n-1$ operations.

---

As per the hint you were given, this is very similar in spirit to the Towers of Hanoi problem: To move $n+1$ disks from peg 1 to peg 2, you first move $n$ disks from peg 1 to peg 3, then move the largest disk to peg 2, and finally move the $n$ disks on peg 3 to peg 2.
> 1 votes

---
Tags: algorithms, combinatorics, permutations, towers-of-hanoi
---


# Question
Title: C(++) library for DFAs - free for academic use
(I'm aware that software questions are better suited for stackoverflow, but since DFAs are not something that software developers usually care about, I hope it's alright if I ask here.)

I'm currently working on a project to do with regular overapproximations for context free languages. For this purpose, I need to implement stuff that requires me to represent regular languages in a minimized form, intersect them, complement them, etc. - i.e. everything that's easy and quick to do with DFAs. However, I'm having a hard time finding still-maintained libraries for DFAs in C++. I could find libfa which does everything quite nicely, but that's as far as I've gotten. Grail hasn't been maintained in 15+ years and the download link is dead. FAdo seemed interesting initially, but it's in Python and I can't determine whether there's a way to use it as a C++ library, or whether it offers the functionality I mentioned above (the Docs are a bit slim).

Do you know of C(++) libraries for DFAs that offer minimization, intersection and complementation that are free for academic use? I'd like to have at least one alternative to libfa that I can use.

# Answer
I don't know of a full blown library, but based on \[1\] there is a really fast practical C++ implementation available from the author's homepage here.

---

\[1\] Valmari, Antti. "Fast brief practical DFA minimization." Information Processing Letters 112.6 (2012): 213-217.
> 2 votes

---
Tags: reference-request, automata, finite-automata, mathematical-software
---


# Question
Title: Pseudo-polynomial time algorithm for NP-Complete Problems
For problems like Knapsack there is a pseudo-polynomial time algorithm and it is NP-complete. So we reduce every other problem in NP in polytime to Knapsack.

But why don't we have then a pseudo-polynomial time algorithm for all problems in NP?

# Answer
An algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric values in the input. It doesn't make sense to talk about pseudo-polynomial time algorithms for all problems in $NP$ since many of them do not have numeric values in their input at all.

However, if you are looking at two problems for which the definition does apply (for instance 2-Partition (weakly $NP$-complete, has a pseudopolynomial time algorithm) and 3-Partition (strongly $NP$-complete, not believed to have a pseudopolynomial time algorithm) then how is it possible a polynomial reduction from 3-Partition to 2-Partition does not result in a pseudopolynomial algorithm for 3-Partition?

The answer is that a polynomial reduction may create very large numeric values. Every known reduction from 3-Partition to 2-Partition creates numbers that are exponentially bigger than the orignal numbers. Exponentially larger numbers only take polynomially more space to represent, so a polynomial reduction can very easily create exponential numeric values.

So even though we have a pseudopolynomial time algorithm (that runs in polynomial time in the numeric values of the input) for 2-Partition it does not work as a pseudopolynomial time algorithm for 3-Partition, because the reduction makes the numbers much larger, so the algorithm is no longer pseudopolynomial in the original numbers.
> 5 votes

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


# Question
Title: Monograph or survey paper on smoothed analysis of algorithms
The paper by Spielman and Teng, *Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time* (JACM 51(3):385–463, 2004), won a Gödel award in 2008.

Since then, has there been a monograph or substantial survey paper written on the subject?

The best I could find was a book chapter in Algorithm Engineering by Müller-Hanneman and Shirra.

# Answer
To the best of my knowledge, the most recent survey is the following:

Spielman, Daniel A., and Shang-Hua Teng. "Smoothed analysis: an attempt to explain the behavior of algorithms in practice." Communications of the ACM 52.10 (2009): 76-84.

It contains a lot of discussion.
> 2 votes

---
Tags: algorithm-analysis, reference-request
---


# Question
Title: Generate scale-free networks with power-law degree distributions using Barabasi-Albert
I'm trying to reproduce the synthetic networks (graphs) described in some papers.

It is stated that the **Barabasi-Albert** model was used to create "scale-free networks with power-law degree distributions, $P\_A(k) ∝ k^{-λ}$".

$P\_A$ is a probability distribution that returns the probability of a node having degree $k$. For instance, $P\_A(2)$ indicates the probability of randomly choosing a node from the network and getting a node with degree 2.

The average degree $k$ stroke seems to be 4 in one paper, with a the minimum $k$ of 2. No word about the maximum $k$. In the other paper it is not specified. It does not seem that important to define the network.

Lambda λ values are given, as is the number of nodes $n$. Combinations are

1. n = 50000, λ = 3, 2.7, 2.3, with in a paper
2. n = 4000 and λ = 2.5, or n = 6000 and λ = 3 in the other paper

I looked for libraries implementing the Barabasi-Albert algorithm and they seem to require different parameters than lambda and the average degree. One is NetworkX, another is GraphStream (implementation here). They work in similar ways and ask for:

* **n** : int - number of nodes
* **m** : int - number of edges to attach from a new node to existing nodes; the number of edges to be added at each step

How can I calculate the settings m to generate a comparable graph?

Here are some references:

* Catastrophic cascade of failures in interdependent networks, Buldyrev et al. 2010, with a separately provided Supplementary Information
* Small Cluster in Cyber Physical Systems, Huang et al. 2014
* Catastrophic cascade of failures in interdependent networks, Havlin et al. 2010, this is on the Arxiv and somewhat clarifies the first

Note that these papers used "generating functions" to analytically study some properties of those graphs. However, they also run simulations on those models, so they must have generated those networks somehow.

Thanks.

# Answer
> 7 votes
The short answer is that you can't use that software as-is to get what you want. For a fixed $m$, the Barabasi-Albert model always has the degree distribution $P\_k \sim k^{-3}$, regardless of $m$. The exact formula for the probability degree of what those pieces of software implement (which is the BA model) is

$$ P\_k = \frac{2m(m+1)}{k(k+1)(k+2)}$$

The papers (with $\lambda \neq 3$) are probably talking about some kind of generalized BA model, I presume. It would help to give more details (full citations) on them.

EDIT: OK, I'll have at look at those refs. In the meantime, I've discovered there's R package called igraph that can do what you want. The relevant theory paper/cited used there is:

It has some 400 citations in Google Scholar, so it's probably a widely used method. The later, 2009 paper cited on that R package page clearly says "SF networks contain heterogeneous degrees, and their distribution follows a power law, $P\_d(k) \sim k^{-\lambda}$. To construct artificial SF networks, a stochastic model called the Chung and Lu (CL) model is used."

EDIT2: I think you have misread Huang et al. "We build synthetic random, scale-free and small-world networks using Erdos-Renyi model, Barabasi-Albert model and Watts and Strogatz model \[9\] respectively." It doesn't say anywhere they got BA to do any power other than 3. There's a figure caption which says "We use ‘k-n’ interdependence model to couple two synthetic scale-free networks $G\_p$ and $G\_c$ with the power law exponents 2.5 and 3 respectively." But that doesn't mean they used BA for those 2.5-degree graphs. There's one later figure which only says "Barabasi-Albert model is used to generate scale-free network with power law exponent 3."

EDIT3: The paper by Buldyrev et al. doesn't say anywhere they've used any BA graphs. "Simulation results for P8 as a function of p for for SF networks with $\lambda$ = 3, 2.7, 2.3". They don't say how they got those graphs. The do cite the BA papers, but only in long list of 10 papers about various random network models. The second paper of this group by Havlin et al. does indeed give on p. 5 the BA model as having an indeterminate/unspecified $\lambda$, citing the 1999 BA paper. I don't really want to call this paper wrong, but the only correct reading of it is $\lambda = 3$. Again it doesn't say how they generated their $\lambda = 2.7$ graphs from their Fig 8. I can see how reading this paper you can conclude that BA can generate such graphs... but it can't.

EDIT4: Yes, I found it now in the actual version published in *Nature* "For two interdependent scale-free networks2 with power-law degree distributions, $P\_A(k) \sim P\_B(k) / k^{-\lambda}$, we find that the existence criteria for the giant component are quite different from those in a single network." The citation is indeed misleading in the same way as in the Halvin et al., but they don't say they've used the BA process to generate the graphs. The passage can be interpreted as only a citing BA 1999 reference for what scale-free network means and/or who originated the concept. In any case, trust the math... you can find the derivation for the BA degree formula in numerous places, including BA's own paper or in more detail in a later book\[let\]. BA obviously understood the generality of what they observed, so they stated a law that is more general (arbitrary $\lambda$) than what their construction provides, i.e. $\lambda = 3$. As I said before, there are other methods (subsequently published by others, e.g. Chung and Lu) to get a different $\lambda$, but they are not using the BA construction, even though their graphs are correctly called scale-free too.

---
Tags: algorithms, graphs, randomness, sampling
---


title: Static scope and dynamic scope

text:
# Question
Title: Static scope and dynamic scope
I am perpetually confused when it comes to static scoping and dynamic scoping and their differences and Wikipedia isn't of any help, so here's my question:

> Given the following pseudo code in a hypothetical programming environment, what are the outputs under the following conditions?
>
> * call by need using static scope
> * call by name using dynamic scope
>
> ```
> global int n = 100, m = 5;
> void fun(x){
>     int n = 10;
>     print(x + 10);
>     n = 200;
>     m = 20;
>     print(x);
> }
> main(){
>     fun(n + m);
> }
>
> ```

Additionally, what would be two environments where I can run this code to check the output with the conditions?  uses lexical scope, but it does not support call by need while Bash supports dynamic scope, I guess!

# Answer
> 4 votes
Here is the simulation by hand.

* call by need using static scope

The function receives as x parameter the thunk \[n+m\] bound to the globals. Then local n gets 10. The print statement requires evaluation of the thunk, which becomes 100+5, i.e. 105. It prints 105+10, i.e. 115. Local n and global m are changed, but this cannot affect x for two reasons: the thunk does not depend on the local variable n (because statically bound to the global variables n and m), and it is already evaluated to 105 anyway, which is printed by the second print.

Note that, if the first print statement were removed, then x would be evaluated after changing the global variable m, which would then be 20 instead of 5, and the answer for the remaining print statement (formerly the second one) would be 120.

result: 115 105
* call by name using dynamic scope

The function receives as x parameter the unbound expression \[n+m\]. Then local n gets 10. Then x gets evaluated, with local n=10 and global m=5, i.e. 15, and added 10 to print 25. Then local n=200 and global m=20. The parameter x is reevaluated as 200+20, i.e. 220, which gets printed.

result: 25 220

How to test it? One would have to check various implementations of programming languages. I do not remember off hand.

Call by need is usually found in functional languages, which normally do not have assignment. But some still allow it. So I would look for that regarding the first case. I think CAML may provide it.

Call by name is fairly rare, and rather weird in a dynamic scope context. I do not know of any language that will offer that combination. The best is to use a dynamic binding langage and simulate the example by explicitly replacing the call by name argument by a parameterless function that has the parameter as body.

In the example, you would call in `main()`: `fun(lambda().n+m)`, and in the body of the function `fun` you would replace `x` by the call `x()`.

# Answer
> -3 votes
resault of static and dynamic scope:

step 1 : print 115

then n=200 , m=20 it is not affect on x so :

step 2 : print 105

---
Tags: programming-languages, semantics, variable-binding
---


title: Are class methods closures?

text:
# Question
Title: Are class methods closures?
In the wiki article about closures one can read:

> closure ... is a function or reference to a function together with a referencing environment

At the same time in the wiki article about class methods:

> Accessor methods are used to read data values of an object. Mutator methods are used to modify the data of an object.

So, can I say that data is *environment* and class methods (accessors and mutators) are *closures*?

# Answer
> 1 votes
A closure is a piece of code together with an environments providing a binding for its identifiers. In the case of a method, the identifiers (at least some of them) are bound to data in specific instances of the class, not just to the class itself.

The method provides only the code, of the function (in your first quote), while the environment is provided by an instance of the class (an object in your second quote). So it is the method together with the object (class instance) that forms a closure.

Indeed, **the class instance may be seen as the closure**, since it naturally carries the methods with itself formally, considering that it is a closure for a tuple of functions, rather than a single one. That is actually necessary, since the code of each function may refer to the other function, meaning implicitly for the same environment.

Some of the first implementations of object orientation were actually produced that way with higher order language. The creation of an instance of a class was done by calling a creation function $Foo$ with proper parameters. This function would return an instance represented by a tuple of functions closed over the local environment of $Foo$, each function being one of the methods for the class. Actuallly these method function were declared inside $Foo$ so as to see all the local identifiers in $Foo$, which are the data for this instance being created, and otherwise invisible outside $Foo$.

Each new call of $Foo$ would create a new call instance, i.e. a new environments on which execute the methods.

But the syntactic sugar may vary significantly.

**Historically**, afaik, the name closure was used for a function value $g$ returned by a call to a function $F$, though it is created (declared, to say it approximately) inside $F$ and can thus see and use any entity $x$ declared in $F$. Normally, what is declared in $F$ ceases to exist, to be accessible, as soon as $F$ is exited. But when $F$ returns such a function valued result $g$, the system has to preserve any identifier $g$ may be using since $g$, as a function value, survives the termination of the call to $F$. All identifiers used by $g$ are preserved in an environment and $g$ together with this environment is called a closure.

Note that $g$ is a function value, not anything being called. The environment of this closure is preserved as long as the function is callable. Several function can be closed at the same time on the same environment.

# Answer
> 1 votes
There is a parallel between instance methods of an OOP class and a group of closures that all close over the same group of variables.

One way to implement objects is to create a group of closures within a function (the constructor) that binds the variables (acting as instance variables). This approach will return those closures in a data structure such as a JavaScript "map" that allows other code to select and call the closures by method name.

This approach does not allow creating subclasses with direct access to their inherited instance variables, nor debuggers that can access the instance variables. That's because they're tightly locked up by the closures.

Conversely, one way to implement a closure is with an object instance that contains the closed-over state and has the desired `call()` method with the desired arguments, implementation, and and results.

---
Tags: terminology, programming-languages, object-oriented
---


# Question
Title: Does any one know what this problem is called?
We are given finite sets $A$ and $B$ and a set $S\subseteq \mathcal{P}(A)$. The members of $\mathcal{S}$ may have arbitrary intersections with one another and their union is not necessarily $A$. We wish to determine whether there is a function $A\to B$ so that no member of $B$ is the image of more than $k$ members of any $T\in S$.

# Answer
> 2 votes
This is an example of a constraint satisfaction problem. The variables of the problem are the "colors" of the elements of $A$, where $B$ is the set of colors. For each set $T \in S$ and each $(k+1)$-subset $T'$ of $T$, there is a constraint stating that the elements of $T'$ cannot all have the same color.

If $k=1$ and all $T \in S$ have cardinality $2$, then this is just graph coloring. You can similarly put graph hypercoloring in this framework.

---
Tags: terminology, sets
---


# Question
Title: Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree
I'm trying to reproduce the synthetic networks (graphs) described in some papers.

The topic is the same as a previous question of mine, but with a different focus.

It is stated that the **Erdos-Renyi** model was used to create $2$ networks with average degrees $\langle k\_a \rangle$ and $\langle k\_b \rangle$.

In the first paper, the **average degree** is $k = 4$ , while the number of nodes $n$ is 50000.

In the second paper the average degree is not called $k$, but it's stated that the **mean degree** is $1.999$ for $n = 200$ (in Fig. 2), while it is $2.45$ for $n = 4000 $ and $ n = 6000$ (in Fig. 7).

I looked for libraries implementing the Erdos-Renyi algorithm and they seem to require different parameters than average degree. One is NetworkX, another is igraph. They work in similar ways and ask for:

* $n$ - number of nodes
* $0 \leq p \leq 1$ - the probability for drawing an edge between two arbitrary vertices
* $m$ - the number of edges in the graph (in alternative to $p$, only in igraph)

How can I calculate the settings to generate a graph with the same average degree as the ones described in the papers?

Here are the references:

* Catastrophic cascade of failures in interdependent networks, Buldyrev et al. 2010, with a separately provided Supplementary Information
* Small Cluster in Cyber Physical Systems, Huang et al. 2014
* Catastrophic cascade of failures in interdependent networks, Havlin et al. 2010, this is on the Arxiv and somewhat clarifies the first

Note that these papers used generating functions to analytically study some properties of those graphs. However, they also run simulations on those models, so they must have generated those networks somehow.

# Answer
> 7 votes
Average degree and mean degree are the same. In the $G(n,m)$ model, the average degree is $2m/n$. In the $G(n,p)$ model, the *expected* average degree is $np$. The actual average degree has normal distribution with mean $np$ and standard deviation $\sqrt{2(1-\tfrac{1}{n})p(1-p)}$, so it is pretty close to $np$ with high probability.

When $p=c/n$ for fixed $c$, the degree of a single vertex has roughly Poisson distribution (with mean $c$); formally, as $n\to\infty$ the distribution tends to Poisson. In practice, this means that for "small" $c$ and "large" $n$, the degree will be Poisson. Furthermore, while there is some dependency between vertices, we still expect the entire empirical degree distribution to be close to the same Poisson distribution (i.e., we expect the fraction of coordinates having degree $d$ to be roughly $e^{-c} c^d/d!$); this is probably proved formally in the literature.

When $p$ is constant, the degree of a single vertex has roughly Gaussian distribution, and it is probably the case that the joint distribution is also close to the appropriate multivariate Gaussian.

---
Tags: algorithms, graphs, randomness, sampling, modelling
---


# Question
Title: Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?
The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}$ such that $L = h(D\_\Sigma \cap R)$, where $D\_\Sigma$ is the Dyck language over $\Sigma$. This is a necessary and sufficient condition for a language to be context-free, so in principle it seems like it should be possible to show that a language is *not* context-free by showing that there are no valid choices for $h$, $\Sigma$, and $R$ satisfying the theorem.

This earlier question talks about approaches for showing that a language is not context-free, but doesn't mention this approach. Additionally, I can't seem to find any constructive examples of proofs of non-context-freeness along these lines.

Are there any known examples of languages that have been shown not to be context-free by means of the Chomsky-Schutzenberger theorem?

# Answer
here is a construction not *exactly* as requested but related/ somewhat similar. the contrapositive of the Chomsky-Schutzenberger theorem can be used to prove a language is not *unambiguously CFL*. it describes the close connection of the construction to generating functions that yields key insight into the problem.

see ORDINARY GENERATING FUNCTIONS OF CONTEXT-FREE GRAMMARS / TANNER SWETT, EDWARD ABOUFADEL, sec 2.6 p 6
> -3 votes

---
Tags: formal-languages, reference-request, context-free, proof-techniques
---


title: What type is this sorting algorithm?

text:
# Question
Title: What type is this sorting algorithm?
I needed to sort vertices into buckets as an optimization for collision detection later. I came up with this:

1. Go over all the vertices and count the size that each bucket needs to be to contain them into an array.
2. Shift the size array index by -1 unit and use it as offset array instead.
3. Create a single array for all the indices, go over all the vertices again and place their indices according to the offsets while bumping the offset each time.
4. Use the index list to translate vertices to their new positions (or optionally move the vertices on step 3 if you don't need a map but I did for transforming other primitives).

Surprisingly enough, it's much faster than std::sort (by 10x) or a gpu bitonic sort (by 13x) that I implemented earlier. It can't be a new idea since it's so simplistic in its concept. So what is it called? I want to see what other people have done with it to perhaps make it even faster.

# Answer
This is known as counting sort. On a domain of size $d$, counting sort runs in time $O(dn)$, compared to $O(n\log n)$ of comparison-based sorts. When $d\ll\log n$, i.e., when the domain is small compared to the total number of elements, we would expect counting sort to be faster. Counting sort can even be iterated, and this is known as radix sort.

If $d = o(\log n)$, then counting sort runs in time $o(n\log n)$, which might seem to contradict the well-known $\Omega(n\log n)$ lower bound on sorting. There is no contradiction, however, since the lower bound only holds for comparison-based sorts, which counting sort evidently isn't.
> 5 votes

---
Tags: algorithms, terminology, sorting
---


# Question
Title: Can a quantum computer (theoretically) do things a classical computer (literally) can't?
I've been searching the net for an answer to this question, but it's guetting quite confusing. I want to know if there are some undecidable problems for a classical computer that a quantum computer could do. The examples I've seen are things like Shor's algorithm, but that's "just" because the quantum computer is more powerfull than the classical one, and can do stuff like Integer factorization faster. Or at least that's how I understand it so far. Basically my question is this : is there anything a quantum computer can do that a regular one can't if said regular computer had infinite power (or processing speed or whatever)? Examples, explanations, sources would be greatly appreciated, but a simple yes/no would please me also.

# Answer
No. Quantum computers cannot solve undecidable problems.

A quantum computer can be simulated by a classical computer. So, if a quantum algorithm could solve an undecidable problem, then we could also solve it classically via simulation. However, we already know that if a problem has no classical solution, then it must not have a quantum solution either.

Also, you said:

> that's "just" because the quantum computer is more powerful than the classical one.

This is an open problem. We do not yet know if $BPP \subset BQP$.
> 13 votes

# Answer
I quantum computer isn't more powerful than a classical one, according to Church-Turing's thesis, a function on the natural numbers is computable if and only if it is computable by a Turing machine, that means that there isn't a computer model that is more powerful than a Turing Machine.
> -2 votes

---
Tags: computability, undecidability, computation-models, quantum-computing
---


title: Text features in decision tree

text:
# Question
Title: Text features in decision tree
Right now I am doing some problems on application of decision tree/random forest. I am trying to fit a problem which has numbers as well as strings (such as country name) as features. Now the library, scikit-learn takes only numbers as parameters, but I want to inject the strings as well as they carry significant amount of knowledge.

How do I handle such scenario, I can convert string to numbers by some mechanism such as hashing in python. But I would like to know the best practice on how strings are handled in decision tree problems.

# Answer
> 1 votes
Random forests don't allow you to use strings as features. Instead, if you want to use random forests, you'll need to select new features and do some feature extraction, so that all of your features are numbers. The features might be some function of the strings, e.g., a histogram of the lengths of the strings, or a count of the number of times each possible word appears in your document (see e.g. bag of words model).

The features that make sense for your application will depend heavily upon your specific application, so we can't give a one-size-fits-all answer. The right set of features will be heavily domain-specific and application-specific, so you'll need to do some brainstorming about possible features and try out your ideas to see how well they work. That said, if you want some hints or ideas to jumpstart your brainstorming about possible features that might make sense, the NLP (natural language processing) community might be a good place to start.

---
Tags: machine-learning
---


# Question
Title: Interpretation of '1/3' in IEEE floating point representation
For a rational number `1/3` below is the floating point representation(64 bit) of decimal expansion 0.3333333....

##

As per the above bit structure, I would like to interpret the value of exponent(11 bits) and value of fraction(52 bits).

*exponent* has 11 bits. **How do I interpret exponent value**?

*fraction* has 52 bits. Here 0101 is decimal `5`. Am not sure if we captured fractional part 33333333... of decimal expansion? To capture fractional part am I suppose to expect `0011` pattern instead of `0101`. **How do I interpret fractional part**?

# Answer
> 4 votes
The fractional part is in binary: $(0.01010101\ldots)\_2 = (0.333333\ldots)\_{10}$. To convince yourself of this, try multiplying the binary $0.0101010101\ldots$ by $3$: you will get $0.111111\ldots = 1$. In a similar way, the decimal $0.0101010101\ldots$ equals $1/99$.

The mantissa (fractional part) in fact has an implicit $1.$ in front, so it actually equals $(1.01010101\ldots)\_2 \approx 4/3$. The exponent should therefore be $-2$, since $1/3 = 4/3 \cdot 2^{-2}$. The exponent itself is stored with an *offset* of $1024$ (or more generally, $2^{w-1}$, where $w$ is the width of the exponent field), that is, instead of $-2$ we actually store $1022$, which in binary reads $01111111101$.

You should note that the floating point number doesn't represent $1/3$ exactly, rather a number pretty close to $1/3$. The only numbers representable exactly in floating point (given enough precision) are dyadic numbers, which are numbers of the form $A/2^B$ (for integer $A,B$).

---
Tags: floating-point, number-formats
---


# Question
Title: What is the name for this search algorithm?
A colleague came up with the following search algorithm:

* We have an array of *sorted*, *distinct* integers \[$i\_0$ \< $i\_2$ \< ... \< $i\_n$\]
* We are looking for the index of $i\_k$ (for simplicity suppose that $i\_k$ is in the array)
* We suppose that the elements are pretty uniformly distributed between $i\_1$ and $i\_n$

The algorithm:

1. let "position" be initially be 0
2. if $i\_k$ == $i\_{position}$, stop
3. otherwise:
    * calculate distance = $i\_k$ - $i\_{position}$
    * if we have just switched direction (eg. the previous distance was positive and this one is negative or vice-versa), make sure that abs(distance) \< abs(previous distance) by adding/subtracting 1 from distance such that it gets closer to 0. Note: if distance is already is 1 or -1, it isn't adjusted.
    * let position be position + distance (see note below for possible optimization)
    * if position is positive, let position be min(position, n) (ie. don't overshoot the end)
    * if position is negative, let position be max(position, 0) (ie. don't undershoot the beginning)

I would be interested if somebody studied this algorithm and if so, what's its name? The best I could come up with is that it's a variant of "interpolation search", however I expect the above algorithm to be faster on x86 hardware because it only uses addition/subtraction which is faster than the division/multiplication used by "standard" interpolation search.

**Note**:

Instead of updating position by adding the distance (ie. position = position + distance) we can use the "average distance between consecutive elements" as a scaling factor: $$position \leftarrow position + distance / {i\_n-i\_0 \over n+1}$$

This should give a more precise estimate about the element position.

A disadvantage of the above is that it involves a division which is slow(er) on x86/x64 platforms. Perhaps we can get away with finding the closes power of two to the scaling factor (average distance between consecutive elements) and use shift to perform the division (ie. if $2^t$ is the power of two closes to the scaling factor we can do $position \leftarrow position + distance \>\> k$.

**Update**:

* as people have pointed out the initial element needs to be $i\_0$
* added steps to avoid oscillating indefinitely between undershooting / overshooting the target
* discovered the "galloping search" from Timsort which seems related but not the same

# Answer
> 1 votes
You may be interested to a related algorithm, known as Interpolation Search, which achieves on average the complexity of $O(\log \log n)$ for searching $n$ keys. This is the usual search you do when you scan a phone book for example.

This paper discusses the algorithm, which was originally introduced earlier (1957) by Peterson.

Related data structures: dynamic interpolation search and interpolation search for non independent data.

---
Tags: algorithms, terminology, search-algorithms
---


# Question
Title: For the time hierarchy theorem, how is the input translated efficiently?
I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book. The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular, it is assumed that the encoding of N's tape alphabet using M's alphabet causes only a constant factor slowdown. This seems plausible since if N's alphabet is size k then M can use $\log k$ cells to represent each symbol that N writes to the tape.

But my question is this: If this is how the simulation works then before the simulation starts M will have to change the input so that each bit is repeated $\log k$ times and I don't know how to do this without adding a quadratic term to the time. I should say its assumed that N's computation is no faster than $O(n\log(n))$.

# Answer
> 2 votes
This has been clarified in the book's online errata:

> **Page 369, Proof of the Time Hierarchy Theorem 9.10.**
>
> The proof requires some additional technical discussion at one place. In Stage 4 of D, it simulates M on w. This simulation may require representing each cell of M's tape with several cells on D's tape because M's tape alphabet is arbitrary and D's tape alphabet is fixed. However, initializating the simulation by converting D's input w to this representation involves rewriting w so that its symbols are spread apart by several cells. If we use the obvious copying procedure for spreading w, this conversion would involve O(n^2) time and that would exceed the O(t(n)) time bound for small t. Instead, we observe that D operates on inputs w of the form x10^k where x = ‹M›, and we only need to carry out the simulation when k is large. We consider only k \> |x|^2. We can spread w by first using the obvious copying procedure for x and then counting trailing 0s and rewriting these by using that count. The time for spreading x is O(|x|^2) which is O(n). The time for counting the 0s is O(n log n) which is O(t(n)) because t is time constructible.
>
> *Reported 11/15/12 by Kaveh Ghasemloo of the University of Toronto.*

---
Tags: complexity-theory, turing-machines, simulation
---


title: Pumping lemma of regular language

text:
# Question
Title: Pumping lemma of regular language
I was wondering in how to solve this question, I feel a bit confused: for $\Sigma = \\{1,\\#\\}$, consider

$$D=\\{w \mid w=x\_1 \\# x\_2 \\# \cdots \\# x\_k \text{ for } k \geq 0, \text{ each } x\_i \in 1^\*, \text{ and } x\_i \neq x\_j \text{ for } i \neq j\\}.$$

I want to know how to prove this is not regular using pumping lemma.

# Answer
This is another classical example in which the pumping lemma is the wrong way to go. Here are two cheap alternatives.

1. Use the Myhill–Nerode theorem. For any $i \neq j$, the words $1^i$ and $1^j$ are inequivalent, since $1^i\\#1^i \notin D$ while $1^i\\#1^j \in D$. Since there is an infinite pairwise inequivalent collection of words, the language is not regular.
2. Use closure operators. If $D$ were regular, then so would $\overline{D} \cap 1^\*\\#1^\* = \\{1^i \\# 1^i\\}$ be. Now it's easy to use the pumping lemma.

It's also possible to use the pumping lemma directly. Suppose that the pumping length is $p$. Take $w = 1^p\\#1^{p!+p} \in D$. According to the pumping lemma, we can write $w = xyz$ so that $0 \< |xy| \leq p$ and $xy^iz \in D$ for all $i$. Let $y = 1^q$, so that $1 \leq q \leq p$. Choose $i = p!/q + 1$. Then $xy^iz = 1^{p!+p} \\# 1^{p!+p} \notin D$, contradiction.

The trick of using factorials here is standard. Now that you've seen it, you can use it whenever it's needed.
> 1 votes

---
Tags: pumping-lemma
---


# Question
Title: Relationship between #of cores and Dynamic Power
The book I'm currently reading specifies that `Dynamic Power = (1/2) * Capacitive Load * (V^2) * frequency` However, that is assuming it's a single-core system. I wonder if we're calculating the Dynamic Power of a dual-core system, would that be twice the formula of `Dynamic Power` above ?

# Answer
The capacitive load of a dual-core system would be (roughly, ignoring, e.g., sharing parts of the memory hierarchy) twice that of a single core system (with the same core implementation), so the formula would be unchanged.

(Of course, the frequency and even the voltage for different cores might be independently adjustable.)
> 1 votes

---
Tags: computer-architecture
---


title: Build-Max-Heap vs. HeapSort

text:
# Question
Title: Build-Max-Heap vs. HeapSort
I'm not sure whether my definition for these 2 terms are correct. Hence, could you help me verify that:

**HeapSort:** A procedure which sorts an array in place.

**Build-Max-Heap:** A procedure which runs in linear time, produces a max- heap from an unordered input array.

Is worst-case input = worst-case running time?

If so, given the size *n* for Build-Max-Heap, would its worst case input be the same as the HeapSort which is $\mathcal{O}(n \log n)$?

# Answer
> HeapSort: A procedure which sorts an array in place.

Can be in-place or not in-place, the point is it's using a heap data structure to help sort.

Building heap is linear with a careful analysis

See more here
> 4 votes

---
Tags: algorithms, data-structures, heaps, heap-sort
---


# Question
Title: What's the purpose of ANDing a bit mask with all bits set to a value?
I'm adapting an algorithm for calculating a CRC 16-bit CCITT (XModem) value from an ASCII input. I've found some code here. I'm using the function the poster has in his question, but I've noticed at the bottom he does this:

```
calcrc = crc And &HFFFF

```

What's the purpose of applying such a bit mask that is all 1s to a value? Doesn't that just return the value again?

# Answer
> 9 votes
The reason is crc that it's calculating is defined to be a 16-bit value, the `And &HFFFF` will truncate the most significant bit outside the 16-bit range if there is any overflow during the calculation.

---
Tags: logic
---


title: A finite automaton accept no string

text:
# Question
Title: A finite automaton accept no string
How can a finite automaton over(0,1) doesn't accept any string? I only can think of

```
s->a->q->F

```

Where the final state F is empty set. Is that true please?

# Answer
> 2 votes
A finite automaton does not accept any string if and only if all its final states are unreachable from the start state.

This is true if there is no final state, or if you cannot go from the start state to the final state.

---
Tags: automata, finite-automata
---


title: FNP ⊂ FPSPACE or FNP ⊆ FPSPACE?

text:
# Question
Title: FNP ⊂ FPSPACE or FNP ⊆ FPSPACE?
It is clear, that NP ⊆ PSPACE holds and that it is unknown if the strict inclusion holds. How is it if one looks at the corresponding functional complexity classes? Does FNP ⊂ FPSPACE hold?

# Answer
It is indeed the case that $FNP\subseteq FPSPACE$. Recall that a function in $FNP$ is of the form

> Given an input $x$ and a polynomial-time predicate $F(x,y)$, if there exists a $y$ satisfying $F(x,y)$ then output any such $y$, otherwise output 'no.'

source: Complexity Zoo

To see that every problem in $FNP$ is also in $FPSPACE$, note that we may enumerate over all possible $y$ (which can have at most polynomial length) and test whether the predicate holds for any of them. This all can be done in polynomial space, since $y$ is of polynomial size and computing the predicate is polynomial-time (and thus polynomial-space).

Whether the inclusion is strict depends on how you view an $FPSPACE$ machine. The most common definition is to have a polynomial "working" tape and an unbounded (write-only) output tape and in this case, $FNP\subsetneq FPSPACE$ because the output can be exponential. If you restrict the output to what is on the working tape (and thus the output is polynomially bounded), then the question is open (and depends on whether $NP=PSPACE$).
> 5 votes

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


title: How many words loaded on a cache miss

text:
# Question
Title: How many words loaded on a cache miss
Regarding Processor Direct Cache, what is the proper mathematical technique for discovering how many words are loaded on a cache miss?

For example if you have a direct mapped cache with a total data cache size of 32 words and a direct mapped cache of 4-word blocks. I believe I have a cache index of 8 cache blocks:

32/4 = 8

Example: Finding a block in python:

```
var1 = 56
print ((var1 / 8)% 8)

```

The answer: 7

So finding where to store the blocks is simple enough but I'm uncertain on a miss exactly how **MANY** words will be loaded?

# Answer
> 2 votes
In a typical cache design an entire block is loaded (in your example 4 words). While it is possible to include separate valid bits for smaller chunks (sometimes called sectors, though Intel uses sector to designate the larger group and line for the smaller unit), making it unnecessary to load the entire block, even in that case typically the entire block is loaded on a miss.

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Construction of a counter automaton for the complement of the palindromes
How would I go about constructing a nondeterministic 1-counter automaton for the language $L$ that is the complement of the palindromes $\overline{L}=\\{ww^{rev}\\}$ over a 2 symbol alphabet $\Sigma = \\{0,1\\}$?

The definition I am using for 1-NCAs consists of:

* $S$, the set of states,
* $\Sigma$, the alphabet ($\Sigma = \\{0,1\\}$ in our case),
* $s\_{0} \in S$, the initial state,
* $F \subseteq S \times \\{\text{zero},\text{nonzero}\\}$, the set of accepting states, and
* $\delta : S\times\\{\text{zero},\text{nonzero}\\}\times A \rightarrow S \times \\{-1,0,1\\}$, the transition function.

Given a word $w = x\_1x\_2\ldots x\_ny\_1y\_2\ldots y\_n$, I know that if $x\_i$ is not equal to $y\_{n-i+1}$, the palindrome requirement fails. I have a feeling that the counter has something to do with that distance in between those letters but formalizing this is what I am stuck at.

Since a 1-NCA is the same thing as a NPDA (nondeterministic pushdown automaton) with only one symbol in the stack alphabet, I would accept answers using such PDAs also. This is especially since I find very few texts discussing counter automata.

# Answer
If you know that $L$ can not be recognised by a $k$-DCA for any $k$, this gives the hint that you need to use nondeterminism to do it with 1 counter.

What we can do then is guess where the mismatch characters are, in particular, what we'll do is check that $x\_{i} \neq y\_{n-i+1}$ by using the counter to determine first that we're at position $i$ in the input (or rather, nondeterministically guessing that some $i$ is the right index to remember), then guessing nondeterministically that we've reached position $n-i+1$, checking that the two symbols at those positions are different, then counting down to check that we actually were at the right spot (i.e. the counter will have to be back to zero exactly when we reach the end of the input).

One version of this looks like:

So $s\_{0}$ counts up until the symbol just before the one we're interested in. We nondeterministically guess to stop and record what symbol we see by moving to a different state, then $s\_{1}$ and $s\_{2}$ basically ignore the rest of the input until we guess we've reached the $(n-i+1)^{th}$ symbol, at which point we make sure it's different to the one at $i$, then $s\_{3}$ counts down for the rest of the input. If there's no input left when the counter hits zero, we can move to $s\_{4}$ and accept. If we move to $s\_{4}$ too early, we can't accept because there's still input to be processed (so you could take some of the nondeterminism out by putting in an explicit sink state etc.), if we guessed to early which one was the mismatched symbol, then we can't reduce the counter to zero, so we can't get to $s\_{4}$.
> 1 votes

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


# Question
Title: Set Intersection with asymmetric set sizes
I'm looking for an algorithm to perform set intersection where set $N\_1$ is very small and set $N\_2$ is very large.

Due to the constraints of the problem I am solving, I cannot rely on an algorithm which sorts or depends on sorted elements. Further, the simple method of performing $N\_1$ hash look ups in a hash table of size at least $N\_2$ will also not work.

Are there any non-naive approaches to this problem that I am missing? They do not have to be as efficient as either approach, but obviously the more performant the better.

Edit: Since my constraints were a bit vague, I'll go ahead and spell them out.

The application I have in mind is one type of MPC. Here, I would like to perform a set intersection while neither party reveals anything about the elements that are not in the intersection. One party will be performing the comparisons, and the other party will be transmitting the elements of their set in an encrypted format.

Sorting is out because an encrypted value cannot be evaluated for anything besides equality. Doing so would either reveal more about the elements in the set or would come with significant computational overhead.

Hash table look ups have great promise, but all approaches involving them require that both parties pretend they have a set size of $max(N\_1, N\_2)$. The most effective way to optimize the communication between the parties is hash tables, but privacy requires inserting enough false elements so that each bin of the hash table has the same number of items.

Bloom filters also suffer from similar problems as hash tables. To be correct and secure, the size of the smaller bloom filter must be large enough to fit the larger set.

I'm really just looking for a fundamentally different algorithm that I can use to design a different approach to the problem. I would like for the communication and computation to be dominated by the size of the smaller set. I recognize that this is a research problem that no one will have a perfect solution to. Instead, I am trying to find different types of structure that can be used to improve on the naive approach.

# Answer
> 2 votes
If you have exactly one intersection to compute, building a hash table from $N\_1$ and doing $N\_2$ lookups goes through the same number of hash operations as building one from $N\_2$ and doing $N\_1$ lookups.

---
Tags: algorithms, data-structures, sets
---


title: Some Algorithm on Decidablitly

text:
# Question
Title: Some Algorithm on Decidablitly
Anyone could correct me that Why just (1) is False. i'm not sure why others are true: ( G is a Context Free Grammar). any brief description?

1. There is an algorithm that decides whether the complement of $L(G)$ (language generated by $G$) is empty or not.
2. There is an algorithm that decides whether the reverse of $L(G)$ is empty or not.
3. There is an algorithm that decides whether $L(G)$ is finite or not.
4. There is an algorithm that decides whether $L(G)$ is empty or not.

# Answer
> 0 votes
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer.

(2) to (4) is True, because this algorithms is Decidable, and (1) is false because is not decidable. (undecidable).

---
Tags: computability, context-free, formal-grammars, undecidability, decision-problem
---


# Question
Title: How to find out if a piecewise function is partially computable?
I know exactly what a partially computable function is, but I've seen a few functions that I really can not understand why they are not partially computable. As an example in Davis book page 78, he says the following function is not partially computable: ($\uparrow$ means undefined and $\downarrow$ means defined)

Given an infinite set C such that $\phi(c,c) \uparrow$ for all $c \in C$ and such that

> $$ H\_4(x) = \begin{cases} 1 & IF \phi (x,x) \downarrow \\ 0 & x \in C \\ \uparrow & Otherwise \\ \end{cases} $$

is not partially computable.

Or in page 77 he says the following is partially computable while I cannot understand what is difference between these two functions!

Given an infinite set B such that $\phi(b,b) \uparrow$ for all $b \in B$ and such that

> $$ H\_3(x) = \begin{cases} 1 & IF \phi (x,x) \downarrow \\ 0 & x \in B \\ \uparrow & Otherwise \\ \end{cases} $$

Or between these two functions which one is partially computable? ($K=\\{ n \in N | \phi(n,n) \downarrow \\}$)

> $$ f\_1(x) = \begin{cases} 2 & x \in K \\ \uparrow & Otherwise \\ \end{cases} $$
>
> $$ f\_2(x) = \begin{cases} \uparrow & x \in K \\ 2 & Otherwise \\ \end{cases} $$

So I would like to know what makes a piecewise function to be partially computable?

---

**UPDATE**:

Since $K$ is recursively enumerable (in face m-complete), it is not recursive so checking membership in this set is semi decidable. I guess $f\_2(x)$ should be partially computable but I'm not sure!

# Answer
> 1 votes
A function $f : X \to Y$ is computable iff there is an algorithm that outputs $f(x)$ for every $x \in X$ after finite time. It's only *partially* computable if it does so for *some* $x$ but is undefined (i.e. the algorithm does not terminate) for the others¹.

As an example, consider the indicator function $\chi\_A$ of some set $A$. $A$ is decidable iff $\chi\_A$ is computable, semi-decidable (recursively enumerable) iff $\chi\_A$ is partially computable, and neither if $\chi\_A$ is not even partially computable.

So, in your first example, you have to determine for which infinite sets $A$ with $\Phi(a,a)\\!\uparrow$ for all $a \in A$ the function

$\qquad\displaystyle H\_A(x) = \begin{cases} 1, &\phi (x,x)\\!\downarrow \\ 0, & x \in A \\ \uparrow & \text{ otherwise} \\ \end{cases}$

is partially computable. I assume that $\Phi$ is an enumeration of all partially computable functions, so $A$ is a set of indices of functions (TMs) that are undefined (don't terminate) on their own index. In other words, an infinite subset of $\overline{K}$, itself not semi-deciable.

> $H\_A$ is partially computable if and only if $A$ is semi-deciable.

In your second example, note that $K$ is the halting problem/language, $f\_1 = 2 \chi\_K$ and $f\_2 = 2 \chi\_{\overline{K}}$.

> The rest is applying what you (should) already know, i.e. that $K$ is semi-decidable but $\overline{K}$ is not. That leaves a trivial reduction.

---

1. Depending on your definition, "partially computable" may be the more general definition, i.e. "(totally) computable" is a special case.

# Answer
> 1 votes
Page 3 of the book says: "partial function on a set S is a simply function whose domain is a subset of S."

The difference between $H\_3(x)$ and $H\_4(x)$ are the sets of $B$ and $C$ that you are going to make. for example if you give $B$ such that for all $x$ the *other wise* don't happen, then $H\_3(x)$ will be a total function and we know every total functions are partial functions since $S \subseteq S$.

between $f\_1(x)$ and $f\_2(x)$ the one is partial computable which gives output **for some** $x$s in its domain.

---
Tags: terminology, computability, semi-decidability
---


# Question
Title: LL(k) Prediction Techniques (and Insight on method applied)
> I'm requesting references for `LL(k)` in situations where `k > 1` for reasons described below.

I'm looking for research/notes/anything involving LL(k) predictions.

Any time I look up `LL(k)` I end up with the description starting about `LL(k)` and focusing on `LL(k)` where `k = 1`.

Is there a formal description for the process to predictions where k can be greater than one, sometimes even as high as `7` to `15`? Granted I can't vouch for or against the performance implications of the `k` being so high as that, but I just wanted to know if there's been any literature on the subject.

# Answer
> 2 votes
It turns out someone wrote half a book about LL(k) parsing, which wasn't mentioned on Wikipedia until I added it a coupe of minutes ago.

* *Parsing Theory: LR(k) and LL(k) Parsing* by Seppo Sippu; Eljas Soisalon-Soininen (1990).

I've looked briefly through it and it does have LL(2) examples too.

EDIT: As rici says below, this is the 2nd volume of a two-book series by the same authors; the first volume in the series is titled *Parsing Theory: Languages and Parsing* (1988).

And you can obviously find some level of info on LL(k) in most compiler books, but Sippu and Soisalon-Soininen have the most extensive treatment I found of LL(k). More recent introductory textbooks generally punt the proofs on anything to do with LL(k) with to Sippu & Soisalon-Soininen's 2nd volume.

LL(∗) however is not covered by Sippu & Soisalon-Soininen (as far as I can tell), but that's probably understandable given the book's age. For LL(∗) the 2011 ANTLR PLDI paper is probably the best reading.

---
Tags: reference-request, finite-automata, compilers, parsers, ll-k
---


# Question
Title: If $A \cap B$ or $A \cup B$ or $A \times B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?
Sets $A$ and $B$ are given but we don't know what kind of sets they are. If we know that $A \cap B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

what about $\cup$ and $\times$ operators? If $A \cup B$ or $A \times B$ is recursively enumerable is it true to say both $A$ and $B$ are R.E.?

# Answer
Notice that $\mathsf{RE}$ is not closed under complementation. Therefore there exists an $A\in\mathsf{RE}$ such that $B=A^c\notin\mathsf{RE}$, while $A\cap B$ and $A\cup B$ are trivially recursively enumerable.

However, when $A\times B\in\mathsf{RE}$, there is a Turing machine $\mathcal{M}$ accepts $(x,y)$ iff $x\in A$ and $y\in B$. Therefore $\mathcal{M}(x,y\_0)$ for fixed $y\_0\in B$ accepts the language $A$, and hence $A\in\mathsf{RE}$. For $B$ it is the same.

**Update:** I notice that I missed something in the case of $A\times B$. The conclusion holds only when both $A,B$ are not empty, since otherwise $A\times B=\varnothing\in\mathsf{RE}$ whatever the other one is.
> 10 votes

---
Tags: computability, sets
---