# Question
Title: Names of power-of-two bit operations on bitsets that would not assume any number interpretation
Three commonly used functions when it comes to bit manipulation are :

* `is_pow2`: Checking that an integer is a power-of-two (only one bit is set): $00010000 \Rightarrow yes$
* `floor_pow2`: Finds the largest integer power of two not greater than the given value $00010010 \Rightarrow 00010000$ (msb on the left, lsb on the right)
* `ceil_pow2`: Finds the smallest integer power of two not less than the given value $00010010 \Rightarrow 00100000$ (msb on the left, lsb on the right)

However, the concept of a power of two requires to assume a numeric interpretation of sets of bits. But fundamentally the functionality provided by these functions stay valid on bitsets without a numeric interpretation. For example, what `is_pow2(x)` is really asking is whether `popcount(x) == 1`. And `popcount` does not require to define any concept of power of two.

I was wondering if the three functions `is_pow2`, `floor_pow2`, `ceil_pow2` had commonly accepted names in mathematics, computer science or computer engineering which do not rely on the concept of a power of two.

# Answer
You can think of a bitvector as a set, by giving names to the various bits. For example, if we name the bits in an 8-bit integer using the numbers $0,\ldots,7$ (where $0$ is the LSB and $7$ is the MSB), then $00010010$ is the same as $\\{1,4\\}$.

Your first function asks whether the set has size $1$. If we name the bits using numbers as above, the second function is maximum and the third is minimum.
> 2 votes

---
Tags: integers, software-engineering, bit-manipulation, assembly
---


title: Clique-or-almost reduction to clique

text:
# Question
Title: Clique-or-almost reduction to clique
I saw the posted question here about a direct reduction from near-clique to clique.

Clique-or-almost is like near-clique but with the option for a complete clique of size $k$, I mean that perhaps an edge is missing and perhaps not.

I can't figure out how to change the proof in the link to fit to the reduction from Clique-or-almost to Clique.

> $$\text{CLIQUE-or-almost} = \\{(G,k) \mid \text{ $G$ contains a $k$-clique with possibly one missing edge}\\}.$$

# Answer
> 1 votes
If $G=(V, E)$ is the graph of an instance of CLIQUE-or-almost to CLIQUE, then you can create a new graph $G'$ as the disjoint union of $G$ with all the graphs $G + e$ for $e \in \binom{V}{2} \setminus E$.

Then $G$ has a clique or an almost-clique on $k$ vertices if and only if $G'$ has a clique on $k$ vertices.

This shows that CLIQUE-or-almost $\le\_p$ CLIQUE. You can also show a polynomial reduction from CLIQUE to CLIQUE-or-almost.

Start with the graph $G=(V,E)$ in the instance of CLIQUE and build a graph $G'$ in which there are two copies $v\_1, v\_2$ of each vertex $v \in V$ along with the edge $(v\_1, v\_2)$. For each $(u,v) \in E$ add to $G'$ the four edges $(u\_1, v\_1), (u\_1, v\_2), (u\_2, v\_1), (u\_2, v\_2)$.

If there is a clique $C$ of size $k$ in $G$ then there is a clique of size $2k$ in $G'$ (consider all the copies of the vertices in $C$).

If there is a clique $C$ of size $2k$ in $G'$ then there is a clique of size at least $k$ in $G$ (consider all the vertices $v \in V$ such that $C$ contains at least one of $v\_1$ and $v\_2$).

Finally, if there is a clique $C$ minus one edge $(u\_i ,v\_j)$ of size $2k$ in $G'$, then $C$ cannot contain $v\_{3-j}$, as otherwise the edge $(u\_i, v\_{3-j})$ would be missing too. This means that $C \setminus \\{v\_j\\}$ contains $2(k-1)+1$ vertices. Thus, the set of vertices $w$ such that $C \setminus \\{v\_j\\}$ contains at least one of $w\_1$ and $w\_2$ is a clique of size at least $k$ in $G$.

# Answer
> 1 votes
Here is a reduction from CLIQUE to CLIQUE-or-almost.

Let $G$ be an arbitrary graph. Form a new graph $G'$ by adding two new vertices $x,y$ connected to all vertices of $G$, but not to each other. If $G$ contains a $k$-clique, then $G'$ contains a $(k+2)$-clique with a missing edge.

Conversely, suppose that $G'$ contains a $(k+2)$-clique $S$, possibly with a missing edge. If the clique doesn't contain a missing edge, then $S \setminus \\{x,y\\}$ is a clique of size at least $k$ in $G$. If $x,y \in S$ then the missing edge is $(x,y)$, and again $S \setminus \\{x,y\\}$ is a $k$-clique of $G$. In the remaining case, $|S \setminus \\{x,y\\}| \geq k+1$. Remove one vertex from the missing edge to obtain a clique of size at least $k$ in $G$.

---

For a reduction in the other direction, it is well-known that CLIQUE is NP-hard. Since CLIQUE-or-almost is clearly in NP, by definition there is a reduction from CLIQUE-or-almost to CLIQUE. One can construct such a reduction via the proof of the Cook-Levin theorem.

---
Tags: reductions, np-hard
---


# Question
Title: Turing machine with k-tape, tape of output
Consider a Turing machine with input alphabet $\\{a,b\\}$ that computes the following function:

$$ f(w, v) = \begin{cases} w & \text{if } \operatorname{length}(w) \> \operatorname{length}(v), \\ v & \text{otherwise}. \end{cases} $$

I wish to use a TM with two tapes, the first of which contains the input string, say encoded as $\*w\*v\*$. I'm not sure, having read several books, which tape is the output tape in this case. For example, the output tape for a TM of two tapes is the input tape or the second tape? If I use three tapes, is it correct that one of them contains the input, another is a working tape, and the third is the output tape?

# Answer
> 3 votes
There is no generally accepted definition of Turing machine. Various authors use various models. One author's definition might specify the output tape, another's might leave the choice to the Turing machine designer.

The reason that we don't care about this "calling convention" is that it doesn't matter from the point of view of computability (and, to a large extent, from the point of view of complexity). All of the different variants of Turing machine are Turing-equivalent; the languages they decide are the computable languages, and the languages they recognize are the recursively enumerable languages.

If you're writing a paper, the choice of which model to use is up to you. But this hardly ever comes up, since Turing machines are usually described very informally. The informal description can be implemented in any reasonable variant of the Turing machine model.

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


# Question
Title: Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack?
I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with two stacks. I also know that you can’t simulate a Turing machine with a PDA, because a professor challenged a student when he suggested the treating a stack as a matrix, that is, as if it were two arrays. What’s the roadblock?

# Answer
> 2 votes
The comment of @Yuval tells the intuition behind the answer (the shortcoming of a PDA is that you can iterate only once over the word and you cannot read the second letter in the stack before popping the first one, note that you can keep only constant amount of data in the state).

However, a very concise formal proof why we can not simulate all Turing machines with PDAs is that you can build to each PDA a corresponding context free grammar such that a given word is accepted by a given PDA if and only if it can be constructed with the corresponding grammar source.

Now since CFL is a proper subset of CSL which is again a proper subset of recursive languages which all can be decided by Turing machines, Turing machines can simulate all PDAs but not vise versa. To see why, for a given recursive but not context-free language, say the standard example $a^nb^nc^n$, there is no PDA to compute this language since else there would be a context free grammar to compute it which would make it CFL. On the other hand it is not hard to build a Turing machine that decides this language.

---
Tags: turing-machines, pushdown-automata, simulation, chomsky-hierarchy
---


title: Parity vs Parity bit vs Parity sum

text:
# Question
Title: Parity vs Parity bit vs Parity sum
Assume that $B\_b$ denotes the finite set of bitstrings of length $b$, if we are given its subset $A = \\{e\_i\\}, i \in \\{0,... n\\}$, such that $e\_i \in B\_b$, what is "the parity sum of As bitstrings" ($parity\_A$)?

Is it a single bit $parity\_A = parity(concat(parity(e\_1), parity(e\_2), ..., parity(e\_n)))$?

Or is it a bitstring $parity\_A = concat(parity(e\_1), parity(e\_2), ..., parity(e\_n))$?

Or is it something else?

# Answer
I don't think the term has a clear standard accepted meaning, so if you are reading it somewhere, you'll either have to infer from context or hope they defined the term. But as a general guideline, I would guess your former choice is much more likely than your second choice; I think it's much more likely to be a single bit than a bitstring.

If you are thinking of using that term in your own writing, I encourage you to define that term before using it.
> 1 votes

---
Tags: information-theory
---


title: Regular expressions with cycles

text:
# Question
Title: Regular expressions with cycles
A knob is used to select one of three positions A, B, C.

The knob can never be turned from A to C, or from C to A, without spending at least one second in position B. The initial position of the knob can be any of A, B, C.

Give a regular expression for this language.

I tried starting from B, and ended up with:

BB\*((AA\*(BB\*)\*) u (CC\*(BB\*)\*)\*

But, it seems impossible to express all possible transitions.

# Answer
> 1 votes
We can build it up from smaller pieces:

How can you describe sequences made up of only a's? Just $a^\*$

How about sequences made up of only a's and b's? $(a|b)^\*$ These can be thought of as turning the knob from A to B, then going back to A, etc..

Similarly for b's and c's: $(b|c)^\*$

Say we stay in positions A-B for a while, and then we want to go to C; this can be expressed as: $(a|b)^\* (bb^\*) c$

Now let's say we stay in positions A-B for a while, and then we switch to C, and stay in B-C for a while. Then the rule means we must pass through b at least once: ${(a|b)^\* (bb^\*) (b|c)^\*}$

Now what if we want to stay in A-B, then switch to C, stay in B-C, then switch back to A, and stay in A-B again? ${(a|b)^\* (bb^\*) (b|c)^\* (bb^\*) (a|b)^\*}$

The pattern starts to appear. You can see that whenever we want to transition we need to stick a $bb^\*$ in between.

To get full sequences, we could try:

$(\\, (a|b)^\*(bb^\*) \\, | \\, (c|b)^\*(bb^\*) \\, )^\*$ which you can check, obeys the transition rule. The only problem is that this assumes the sequence ends with b. To fix that, we just include options to end at a or c; naming the above as $$ L=(\\, (a|b)^\*(bb^\*) \\, | \\, (c|b)^\*(bb^\*) \\, )^\*, $$ we arrive at an answer: $L\\, | \\,La^\* \\,| \\,Lc^\*$

---
Tags: regular-expressions
---


# Question
Title: Finding two store typings that make the same store valid (lambda-calculus with references)
Problem 13.5.2 of Pierce's TAPL's book (page 167) asks:

> Can you find a context $\Gamma$, a store $\mu$ and two different store typings $\Sigma\_1,\Sigma\_2$ such that both $\Gamma | \Sigma\_1 \vdash \mu$ and $\Gamma | \Sigma\_2 \vdash \mu$?

I'm not getting the proposed solution:

But how can this be the case? I mean should not $l$ be of a reference type $Ref(T\_1)? $ How can it be of function type?

# Answer
> 1 votes
The store $\mu$ indicates the type of what is stored in the reference. If $\Sigma(\ell) = T$ then the expression $!\ell$ has the type $T$, and the expression $\ell$ has the type $\mathsf{Ref}(T)$.

If all you need is for $\lambda x:\mathsf{Unit}. (!\ell)(x)$ to be well-typed, then $\ell$ must be a reference to a function whose argument type is $\mathsf{Unit}$, with no constraint on the return type.

---
Tags: lambda-calculus, semantics, types-and-programming-languages
---


# Question
Title: Pumping Lemma on Language with subtracted length
My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given

$$ L = \\{ a^k b a^{m-1} \mid k,m \in \mathbb{N} \\} $$

Questions:

1. How does $m-1$ affect my choice of the word to be pumped? There must be a way to rule out $m=0$ because otherwise my length would be negative.
2. Would it be wrong to choose $w = a^{n-1}ba^n$ with the intent of pumping down $y = b$?

Every answer is highly appreciated.

# Answer
> 1 votes
You could argue with a reasonably straight face that L is not well-defined, since it supposedly contains the word $a^0ba^{-1}$, so L wouldn't be a language at all, therefore not a regular language and not an irregular language either.

If you change it slightly to $$ L = \\{ w: w = a^k b a^{m-1} \mid k,m \in \mathbb{N} \\} $$ then it is definitely regular; there's a very simple FSM with just two states for it.

# Answer
> 0 votes
Your language is regular. You won't be able to prove that it's not regular using the pumping lemma.

Regarding your first question, you're right that the language is present in a sloppy manner. We should add the condition $m \geq 1$. We can then notice another way of writing the language: $$ L = \\{ a^k b a^m \mid k,m \in \mathbb{N} \\}. $$ This is just the language of the regular expression $a^\*ba^\*$.

The reason that you can't "pump down" the word $a^{n-1}ba^n$ is that *you don't get to choose the decomposition of the pumping lemma*. This word can be decomposed as $a^{n-2} . a . ba^n$ (we can force $n \geq 2$ by choosing the pumping constant), and then the middle part can be pumped down or up while keeping the word in $L$.

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Finding potential function for dynamic array
About dynamic array, doubling it's size with every element that is beying its limit:

From what I understand, the number of operations between the $n$th element and the $n+1$th depending on if $n+1$ is $2^k + 1$ (for some $k \in \mathbb{N}$).

If so, we need to allocate a new array and copy the last n elements + the new element. From what I see, if I define a potential function $\phi(n)$ then it should be $\phi(n+1) = \phi(n/2) + n/2 + 1$

Explanation: $\phi(n/2)$ is the last time we expanded the array, $n/2$ are the next elements that were inserted to only one (the last) array, and $1$ is the current element.

However, from what I saw (*wikipedia*) the actual function is $\phi(n) = 2n - N$ where $n$ is number of elements and $N$ is array length.

Either way, $\phi(n) \le 2n$, and my HW assignment was to show it is bounded by $3n$ :(

1. Is $3n$ a too big bound or am I missing something?
2. Is the $\phi$ equal to the one *wiki* has (I can't see how...)? how do they differ

**EDIT:** I now have a new notion about the answer - using the bank / accounting method. My initial array has size of 2. The assignment is to show that paying 3 for each insertion will ensure I'm never in "overdraw". I know that if I only pay 2 for each insertion, then when I insert the first 2 elements, I paid 4 and used only 2, when I insert the 3rd, I use 3 and pay only 2 (so I use 1 from the bank, which leaves only 1 there). In the 4th insertion I'll add another 1 to the bank, but in the 5th insertion I'll have to overdraw!

So, clearly $2n$ isn't enough!! which makes me think $3n$ will do.

I know what I added here might contradict my first notion, and I don't understand to actually answer this. Any help will be appreciated. Thanks

**$2nd$ EDIT:**

The HW assignment is to show a specific $\phi(n)$ so that $a(n) = t(n) + \phi(n) - \phi(n-1)$, where:

1. $a(n)$ is the amortized value of the $n$th insertion
2. $\phi(n)$ is the potential function
3. $t(n)$ is the actual value the insertion is worth ($1$ or $n+1$)

It's easy to see that, using the Wikipedia function ($\phi(n) = 2n - m$ \[m is the array's size\]$)$, if $t(n) == 1$ then $a(n) = t(n) + \phi(n) - \phi(n-1)$ is actually $a(n) = 1 + \[(2n - m) - (2(n-1) - m)\]$ which is $1 + 2 = 3$. But what about when $t(n) = n+1$?

# Answer
When $t(n)=n+1$ it's the case when the array is full and we need to double the size of our array, so:

As you mentioned our potential function is $\phi(n) = 2n - m$, but now the array size doubled, thus $m = 2n$ and that means that $\phi(n) = 0$.

Our potential function for the before state is $\phi(n-1) = 2(n-1)-m$, and $m=n$ (because the array is full), thus $\phi(n-1) = 2(n-1)-n = n-2$.

And the final result is: $a(n)=t(n)+\phi(n)-\phi(n-1)=n+1+0-(n-2)=n+1-n+2=1+2=3$
> 3 votes

# Answer
You've already proved it! You said you were meant to bound it by $3n$ and you've bound it by $2n$. Well, $2n \leq 3n$, right?
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis, amortized-analysis
---


# Question
Title: Is GAP NP-hard with at most two balls per bins?
The generalized assignment problem (GAP) \[1\] is given by:

* **Instance:** A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and for each item $i$ and bin $j$, we are given a size $s(i, j)$ and a profit $p(i, j)$.
* **Objective:** Find a subset $U ⊆ S$ that has a feasible packing in $B$ and maximizes the profit of the packing.

In \[1\], the authors proved that GAP is NP-hard even when:

* $p(i,j) = 1$ for all items $i$ and bins $j$.
* $s(i,j)=1$ or $s(i,j)=1+δ$ for all items $i$ and bins $j$.
* $c(j)=3$ for all bins $j$.

Analyzing this instance, I can see that GAP is NP-hard when $p(i,j)=1$ for all items $i$ and bins $j$ and each bin can pack at most ***three*** balls. This observation raises the following question for me.

**My question:** Is GAP NP-hard when $p(i,j) = 1$ for all items $i$ and bins $j$ and each bin can pack at most ***two*** balls?

---

\[1\] A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

# Answer
> 2 votes
You can reduce numerical 3-dimensional matching (N3DM) to your problem.

Given an instance of N3DM $X\times Y\times Z$ with the bound $b$, say $X=\\{x\_1,\ldots,x\_k\\},Y=\\{y\_1,\ldots,y\_k\\},Z=\\{z\_1,\ldots,z\_k\\}$, you can construct $k$ bins with capacities $b-x\_1+M+M^2,\ldots,b-x\_k+M+M^2$, and $2k$ balls with sizes $y\_1+M,\ldots,y\_k+M, z\_1+M^2,\ldots,z\_k+M^2$, where $M$ is a very large number. Now there is a valid solution to the N3DM instance if and only if you can pack all the $2k$ balls.

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


# Question
Title: Add edges to undirected graph to make connected and minimize longest path
I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the number of vertices on the longest path in the resulting connected graph. As a result I need the number of vertices on the longest simple path in the resulting graph.

For example, given a graph with the following edges:

```
1 0
2 0
4 3
5 3

```

There are multiple ways to add edges to make it a connected graph. But since I want to minimize the number of vertices on the longest path in the resulting graph, I have to add an edge between 0 and 3. Now the path with the most vertices contains 4 vertices (2 -\> 0 -\> 3 -\> 5). If I had added an edges between 2 and 4 then the path with the most vertices would've been 1 -\> 0 -\> 2 -\> 4 -\> 3 -\> 5.

Another example, given a graph with the following edges:

```
0 1
1 2
3 4
5 6

```

Here two edges need to be added: between 1 and 3 and between 3 and 5. The path with the most vertices then contains 5 vertices.

My approach was to first use DFS to identify all components. Then, for each component, I find the longest path in that component, I take the vertex that is in the middle of each of those paths and connect them. This results in one connected graph. In that resulting graph I can find the path with the most vertices. I suspect that there must be a more efficient approach to this, especially since it needs to work for a disconnected graph with at most $10^6$ vertices. Hopefully someone has a better idea on how to solve this.

# Answer
> 1 votes
Clearly, the number of added edges is one less than the number of connected components in the graph, since we can decrease this number by one by adding an edge and we seek the minimum number of added edges.

The trick is to add the edges between central vertices of the connected components. A central vertex of a connected component is a vertex that has minimum distance to the farthest vertex to this vertex in the component (we call this distance the eccentricity). So it is a vertex that minimises the eccentricity.

Here goes the algorithm. In each step we find the connected components of the graph and we handle them as different graphs say $G\_1, \dots, G\_l$. Note that the task is to add $l-1$ edges between these graphs in a way that makes them connected. Each time we add an edge we will combine two graphs and decrease $l$ by one until it gets to the value 1.

After we found the connected component we find a central vertex in each of them (central vertices might not be unique but we can choose any of them). We keep for each component a central vertex and the value of its eccentricity. Now in each step we combine to graphs, we distinct two cases. \- The minimum eccentricities are equal, then any of the two central vertices can be chosen as a central for the new graph and the new eccentricity is the previous one plus one. (Try to prove the correctness and optimality of this statement). \- The minimum eccentricities differ. Keep the central with the greater eccentricitiy. Its eccentricity does not change. (Also try to prove this).

The eccentricity of each component can be built using a BFS from each vertex in total quadratic time in the size of the input graph. Each iteration can be implemented in constant ime (for example keep a stack of pairs (central, eccentricity) and in each step pop two elements, unify them and push thr new pair back to thr stack. each step decreases the size of the stack by one and hence we end after $l-1$ steps.

The correctness of the previous two cases implies the correctness of the algorithm and that it does not matter in which order you process the components. Hence we get a total quadratic running time. There are some heuristics to improve the running time of computing central vertices if connected components (which is the only quadratic factor in our algorithm and gence the bottleneck) including pruned BFS. However, as far as I know, this is the best achievable asymptotic running time.

---
Tags: algorithms, graphs, efficiency, connected-components
---


title: find total components in a graph

text:
# Question
Title: find total components in a graph
I have a graph with N nodes and M edges. It is a single component.

Now I have to delete a single node from graph, deleting that node might split graph into 1,2 or more components. The count of such components is required for each deleted node. Note that only a single node is deleted at any point of time.

I need to do this for all the nodes of the graph in a linear time.

Is this possible in linear time? I am able to do this in O(n^2) by running dfs for each node.

# Answer
Yes, this can be done in linear time. The vertices whose removal causes the graph to split into multiple components are called articulation points. The number of such components for each vertex is the number of biconnected components that the vertex belongs to. For biconnected components and algorithms for computing them see the wikipedia page https://en.wikipedia.org/wiki/Biconnected\_component.
> 2 votes

---
Tags: algorithms, graphs
---


title: What is the denotation for identifiers?

text:
# Question
Title: What is the denotation for identifiers?
I am trying to understand what is the domain for denotational semantics.

Right now the way I understand denotational semantics is that given some syntax of a program that maps to some mathematical object that represents its meaning. e.g. for example give some arithmetic expression AExp the denotation $\[\\\_\]:AExp \to (State \rightharpoondown Int)$ :

$$ \[ 1 + x \]\sigma = 1+x $$

if the state is $\sigma = \\{ x:2\\}$ then:

$$ \[ 1 + x \]\sigma = 3 $$

So indeed given the syntax AExp using the state we can fully determine what the integer should be returned.

I also understand the denotations for statements $\[\\\_\]:State \rightharpoondown State $ which makes a lot of sense since that states the state of the program to the next after executing some code in the statement. e.g. $\[\\{ \\}\] = 1\_{identity}$ the empty statement does not change the state so:

$$ \[\\{ \\}\](\sigma) = \[\\{ \\}\]\sigma = 1\_{identity}(\sigma) = \sigma $$

But I can't figure out what the type should be for the denotation for identifiers. From the notes I am reading CS522 I see this:

$$ x\in Identifier \implies \[\sigma\] = \sigma(x) $$

which intuitively makes sense but I am having difficulties matching it to the fact that denotaitons should be CPO (Complete Partial Sets). How is the above a CPO? (or the poset, the technicality of existence of LUB/sumpremum is not that important to me). I can't see the POSET.

I guess I am not 100% how the other two are also CPOs...any enlightening comments?

# Answer
> 1 votes
> But I can't figure out what the type should be for the denotation for identifiers.

That is because you are implicitly tracing the denotation function $⟦\\\_⟧$. It might get easier to see the type if you explicitly trace the denotation function by tagging them appropriately. $⟦x + y⟧\_{AExp}\sigma = ⟦x⟧\_{AExp}\sigma + ⟦y⟧\_{AExp}\sigma$.

Similarly, if you have an boolean expression with identifiers, for example: $$⟦a\_1 \< a\_2⟧\_{BExp}\sigma = \begin{cases} True &\text{if} ⟦a\_1⟧\_{AExp}\sigma \< ⟦a\_2⟧\_{AExp}\sigma\\ False &\text{if} ⟦a\_1⟧\_{AExp}\sigma \geq ⟦a\_2⟧\_{AExp}\sigma\\ \bot &\text{otherwise} \end{cases}$$

In this case $\sigma : Identifier \rightharpoondown Int$. The type of $\sigma$ would also be implicitly traced by the denotation function because, the object language construct makes it obvious. You can, if you want to be even more pedantic, carry around a tuple of $\sigma$'s, one for each type of variable lookup. So, if your language has integer variables and boolean variables, your $\sigma = (\sigma\_{Int}, \sigma\_{Bool})$ and the correct component would be chosen depending on which $⟦\\\_⟧$ is being used.

> I guess I am not 100% how the other two are also CPOs...any enlightening comments?

Now, the poset structure is on the co-domain of the denotation function i.e. if you have a denotation $⟦\\\_⟧\_{Stmt}$ the signature of the poset structure will be $(\alpha: State \rightharpoondown State, \preceq, \bot)$ similarly for $⟦\\\_⟧\_{AExp}$ the structure poset structure would be $(\alpha: State \rightharpoondown Int, \preceq, \bot)$, where $\preceq$ allows you to compare the amount of information contained by the information bearers $\alpha$, as explained on pg 159-160 in the notes you have linked.

---
Tags: programming-languages, semantics, denotational-semantics
---


# Question
Title: How does Rabin fingerprint finds breakpoints (chunk boundary)?
I was reading up on chunking and found Rabin fingerprinting is also used to break files into chunks. After reading about this algorithm, I understood how rolling hash is computed using Rabin fingerprint. This is explained almost everywhere. What I don't get is how in Rabin fingerprinting, we know to end one chunk here and start another? And how does insertion doesn't affect original chunks? Some sources mention the following, which I didn't get. (Although it's given with reference to LBFS, I think for de-duplication also chunking will be done in similar way.)

When the low 13 bits of the fingerprint are zero LBFS calls those 48 bytes a breakpoint and ends the current block and begins a new one. Since the output of Rabin fingerprints are pseudo-random the probability of any given 48 bytes being a breakpoint is 2^{-13}. This has the effect of shift-resistant variable size blocks.

We are checking if low 13 bits are 0 or not, because fingerprint is basically a remainder, after dividing by an irreducible polynomial? But even then, how does inserting something in chunk-1, still makes sure chunking will be shift-resistant?

Thanks in advance for the help!

**Edit** : I am talking about application of Rabin fingerprinting in breaking files into chunks for de-duplication. (Not for string search, I understood that one)

# Answer
> 3 votes
Note that any hash algorithm can be used to break files into chunks where chunk boundaries don't change much after inserts/deletes. Rabin fingerprinting (and RabinKarp rollsums) are just hash functions that are good for this purpose.

The trick is you calculate the hash of a small window of data bytes (say 64 bytes, but I've heard even as low as 16 works fine) at every single byte offset, and the chunk boundaries are whenever the last N bits of the hash are zero. This gives you an average block size of 2^N bytes. Typically you also have a min and max blocksize, which allows you to skip over the min-blocksize after block boundaries, and avoid having blocks that are too small or too big.

The main reason Rabin (or RabinKarp, which I believe is a more generalized form that highlights the rolling property) is useful for this, is it can efficiently be updated and "rolled" over the data with cheap/fast updates to rotate the first byte out and the next byte into the small "window". This makes it very cheap to calculate the hash at every byte offset.

The bit you may have missed in your LBFS example of this, is the rabin fingerprint is only of the last 48 byte "window" of each chunk. Inserting a byte anywhere before that window will not change the fingerprint of that window, and thus it will still be a chunk break point.

It is possible that a combination of min-block size and a coincidence of multiple break points in the data, that an insert/delete could find another different break point that affects the following break point (typically by masking it because it's within the min-block size), but in practice the breakpoints will quickly re-synchronize after that.

# Answer
> 2 votes
I know I'm very late to this question, but I want to try and provide an answer for anyone who stumbles across this as I have. I went and deciphered the original paper by Michael Rabin, and found that the Rabin-fingerprint was designed to NOT be shift-resistant. In his paper (http://www.xmailserver.org/rabin.pdf) he used the fingerprint to detect any data-modification in files as the fingerprint would be different if any bit was changed. So, I have no idea why the LBFS paper is claiming to use fingerprinting for dynamic chunk borders because that's exactly what it is not meant for. Look for a different rolling hash if you want shift-resistant chunk borders. That being said fingerprinting would be a great way to check whether two chunks are the same or not.

# Answer
> 1 votes
It depends on what you are using the Rabin rolling hash for. If you want to check whether a string P of length k is contained in a large string S, then the Rabin algorithm computes the Rabin hash of all substrings of S of length k. So, there are no decisions to make: *every* substring of length k gets hashed.

Other systems may use the Rabin hash for other purposes. There's more than one algorithm that uses this hash function. We can't tell you how "the algorithm" decides where to begin/end chunks without knowing what algorithm you are referring to.

---
Tags: algorithms, hashing, rolling-hash
---


# Question
Title: What is meant by a full abstract model of a lambda-calculus like language?
> The simply typed lambda-calculus with numbers and fix has long been a favorite experimental subject for programming language researchers, since it is the simplest language in which a range of subtle semantic phenomena such as full abstraction arise.

I tried to find a definition for full-abstract model but I haven't found such. This quote is from Pierce's TAPL book. Note that there is also a related question: What is a "model" of lambda calculus? on the site that has not been answered.

# Answer
In denotational semantics, you want to be able to map each of your language terms to some object in your semantic domain or model. Now, it cannot be any arbitrary domain/model as you like, but, informally speaking, something that gives a good intuition about how the language works (its computational behavior).

Milner tried to formalize what this "intuition" should be and called it full abstraction. Formally, a model is fully abstract if all observationally equivalent terms in the object language represent the same object in the model. Equationally: $$\text{if } ⟦t\_1⟧ = ⟦t\_2⟧ \text{then } t\_1 \rightsquigarrow t\_2 $$ where $\rightsquigarrow$ represents observational equivalence. In case of lambda-calculus observational equivalence would be $\beta\eta\alpha$ conversions and $⟦\\\_⟧$ is the denotation function.

There are few papers that you might want to take a look at if you are interested in seeing some full abstract models of lambda like languages:

1. Plotkin's paper that gives a full abstract model of the lambda like language called LCF
2. Mulmuley's paper gives a full abstract model of typed lambda calculus.
3. Hyland and Ong's papers give a full abstract model of PCF using game semantics
> 8 votes

---
Tags: lambda-calculus, semantics, types-and-programming-languages
---


# Question
Title: Network flow - minimum flow through edge
In my max flow network, I would like to have an edge with upper bound of the flow (a.k.a. edge capacity) $c\_{max}$. However, I would also like to add a lower bound for the flow through the edge, $c\_{min}$.

I need to be sure that the minimum flow satisfies not only all the upper bounds (capacities), but also all the lower bounds.

Is it even possible? And if yes, which changes do I need to make to my flow network so that the max flow algorithm takes these lower bounds into account?

# Answer
Yes, it is possible to solve such problems efficiently. The minimum-cost circulation problem is a generalization of the standard network flow problem, which allows you to set both lower bounds and upper bounds on the flow through each edge. (You can set all costs equal to 1.) There are polynomial-time algorithms to solve instances of the minimum-cost circulation problem.

I don't know if there's a simple way to do with a standard algorithm for network flow.
> 2 votes

---
Tags: network-flow
---


title: Oblivious Machines and Input Dependency

text:
# Question
Title: Oblivious Machines and Input Dependency
So I know the Oblivious Turing Machines head position depends on the size of the input word and a number of steps. Can it be modified in such a way that it's not dependent on the size of the input word?

# Answer
According to the WP article on Turing machine equivalents, oblivious machine head position is independent of input and is a function of time instead. To wit:

> An oblivious Turing machine is a Turing machine where movement of the various heads are \[sic\] fixed functions of time, independent of the input. In other words, there is a predetermined sequence in which the various tapes are scanned, advanced, and written to.

REFERENCES

https://dl.acm.org/citation.cfm?doid=322123.322138

SEE ALSO

Head Position Function of Oblivious Turing Machines
https://stackoverflow.com/questions/14847080/how-does-an-oblivious-turing-machine-work
> -1 votes

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


# Question
Title: Regular Expressions to accept strings where every two successive 0s are followed by a 1
How do I define a Regular Expression for the language L = {w|every two successive 0s are followed by a 1} ?

I don't have any idea on how to even approach this problem, primarily because it says "**every two 0s**".

# Answer
Take either 1, or 01, or 001 and repeat any number of times. Plus there can be a single 0 at the end.
> 0 votes

---
Tags: regular-expressions
---


title: Show that the union of Θ and o is not O

text:
# Question
Title: Show that the union of Θ and o is not O
> Show that: $\Theta(n\log n)\cup o(n\log n)\neq O(n\log n)$

I tried to start this in many ways but I don't really know how... intuitively isn't $\Theta \cup o = o$? So that would mean that I would have to just show that $o(n \log n) \neq O(n \log n) $ Which would be easier I think. But I don't know how to go about this formally..

# Answer
An obvious function is $$ f(n) = \begin{cases} n \log n & \text{if $n$ is even}, \\ 0 & \text{if $n$ is odd}. \end{cases} $$

It's in $O (n \log n)$, it's not in $o (n \log n)$ and not in $\Theta(n \log n)$.

By the way: Every function in $\Theta(f(n)))$ is in $O(f(n))$, just take the larger constant from the $\Theta$ definition. And every function in $o(f(n))$ is also in $O(f(n))$, choose $c = 1$ and make $n$ large enough. But not the other way around.

$O(f(n))$ contains functions that have infinitely many values between $c\_1 f(n)$ and $c\_2 f(n)$, but also infinitely many small values. So a function $g(n) = f(n)$ for infinitely many $n$, and $g(n) = 0$ for infinitely many $n$ where $f(n) \ne 0$ is in $O (f(n))$, but not in $\Theta(f(n))$ and not in $o (f(n))$.
> 4 votes

---
Tags: asymptotics, big-o-notation
---


title: Variable derives itself

text:
# Question
Title: Variable derives itself
In Sipser's Introduction to the theory of computation (3rd edition), I found the following claim.

Consider the grammar:

$$ \begin{align\*} &R \to XRX \mid S \\ &S \to aTb \mid bTa \\ &T \to XTX \mid X \mid \epsilon \\ &X \to a \mid b \end{align\*} $$

In this grammar, it holds that $T \Rightarrow^\* T$.

Can anyone explain how this is true?

# Answer
We say that $\alpha \Rightarrow^\* \beta$ if $\beta$ can be derived from $\alpha$ in zero or more steps. (More fancily, $\Rightarrow^\*$ is the reflexive-transitive closure of $\Rightarrow$.) In particular, it is always that case that $\alpha \Rightarrow^\* \alpha$, for every $\alpha$, due to a derivation of zero steps.

In contrast, in your case it doesn't hold that $T \Rightarrow^+ T$. (This is derivation in one or more steps, or the transitive closure of $\Rightarrow$.)
> 2 votes

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


# Question
Title: Regular expression for containing 010 as a subword
I am studying for a test in computer science, and am encountering difficulties with regular expression. Here is example of a question I don't understand.

I managed to solve the following question:

> Give a regular expression for the language of all words over $\\{a,b\\}$ which contains one of $aa,bb$ as a subword.

My solution: $$(a ∪ b)^\*(aa ∪ bb)^\*(a ∪ b)^\*.$$

I am having trouble with the following question:

> Give a regular expression for the language of all words over $\\{0,1\\}$ which contains $010$ as a subword.

# Answer
> 1 votes
In the first one, L1 = (a+b)\*(aa+bb)(a+b)\* not (a+b)(aa+bb)(a+b)\* because in the second one, it is possible only to have one character of a or b and then we have to find the occurrence we need. Your L1 denies any word that does start with (aa+bb). It also forces all the words to start with a or b.

By the way, I use + for | and ∪.

So for the second one, it is in the same manner:

L1 = (0+1)\*(010)(0+1)\*

010 might occurs in the beginning, the middle or the end of the word.

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


# Question
Title: You have K amoebas and one amoeba can divide into A,B,C amoebas after one instruction then find the minimum no. of instruction to have N amoebas
. You have developed an artificial amoeba, and you can control exactly how it divides. Each individual amoeba can be instructed to divide into A, B, or C amoebas. That is, if you instruct an amoeba to divide into A, this amoeba will disappear, and A different new amoeba will appear. You start out with K amoeba initially, and you want to give them instructions such that at the end, you have exactly N amoeba left. Giving an instruction is a costly affair because it requires you to produce some biochemicals, and so you want to give as few instructions as possible. Find and write the minimum number of instructions that you should give to end up with exactly N amoebas. If it cannot be done, write −1 instead. Note that each instruction is given to a single amoeba, and not all of them together. For example, suppose K = 1, A = 1, B = 2, C = 3, N = 4. Then, you can take the single amoeba, instruct it to divide into B(2) amoebas. Now, there are 2 amoebas. Then take one of these amoebas and instruct it to divide into C(3) amoebas. So now, you have 4 total amoebas, which is what we want, and we used 2 instructions. You can check that you can’t get 4 amoebas with fewer than 2 instructions, and hence 2 is the minimum, and so the answer is 2. Find the minimum number of instructions needed for these instances:

(a) K = 23, A = 7, B = 12, C = 16, N = 114 (b) K = 9, A = 7, B = 15, C = 16, N = 76 (c) K = 10, A = 9, B = 12, C = 26, N = 138

# Answer
> 0 votes
The problem is equivalent to that of finding $$\begin{array}{l} \min x\_1 + x\_2 + x\_3 \quad \mbox{s.t.} \\ x\_1 (A-1) + x\_2 (B-1) + x\_3 (C-1) = N - K \\ x\_1,x\_2,x\_3 \in \mathbb{N} \end{array}$$

Assuming $A,B,C \ge 1$, this can be solved in $O(N-K)$ time (for $N-K\>0$) via dynamic programming and, depending on the values of $A$, $B$, and $C$, the greedy algorithm might work too. See the change making problem. A slight modification of the dynamic programming algorithm also works if any of $A,B,C$ is $0$.

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


# Question
Title: I cannot find an invariant for the following program
I have the following:

(|$y=0; x=c$|) `while(x > 0){y=y+a; x=x-1;}` (|$y= a\*c$|)

This seems like a fairly simple program and I can intuitively tell that the post condition $y=a\*c$ is true when the loop terminates, but I cannot a find a good invariant. Of course, I think I can say the variable $a$ is an invariant, but I don't think that it would prove the partial correctness of this program.

Any help is greatly appreciated.

# Answer
> 3 votes
Figure out what the value of y is, depending on x, a, and c. Prove that your formula is correct before the first iteration, and prove that if it is true before an iteration then it is also true after the iteration.

---
Tags: correctness-proof, loops, loop-invariants, hoare-logic
---


title: Pumping Lemma with Prime Number

text:
# Question
Title: Pumping Lemma with Prime Number
$\text {Could someone please help me with this proof: }$ $L:=\left\\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\\}$

$\text {Maybe we can say, that } w=a^{n}d^{m\_s}b^{k} \text { and } d^{m\_s} \text{ is a prime number with } |w| \ge n. \text{And we choose xyz arbitrarily with } w= xyz \text { } \wedge |y| \ge1 \wedge |xy| \le n\text {. And now I don't know how to go on. Maybe someone can help me, please.}$

# Answer
Helpful property of prime numbers: The gaps between consecutive prime numbers become arbitrarily large. That means for every r, there is a prime p such that none of the numbers p+1 to p+r are primes. That means $a^nd^mb^k$ is not in the language for p+1 ≤ m ≤ p+r.

That would generally work for "m is a member of an infinite set with arbitrarily large gaps between members of the set", like "m is a square, a cube, a factorial" and many others.
> 1 votes

# Answer
You can prove it by carefully picking $w$ and a bit of counting.

Let $q$ be the first prime greater than or equal to $p$, and let $w = d^{q}$ (the $a$s and $b$s are really a bit of a red herring - here we're just choosing $n=k=0$ to get rid of them).

Then by the rules of the pumping lemma, $y = d^{t}$ for some $1 \leq t \leq p \leq q$. We can then pump up $q$ times, giving $w' = d^{q-t}d^{t}d^{t\times q} = d^{(t+1)\cdot q}$. Clearly $(t+1)\cdot q$ is not a prime, so $w' \notin L$.
> 0 votes

---
Tags: regular-languages, finite-automata, pumping-lemma, primes
---


# Question
Title: Database Theory - Does the dependency preservation and lossless join properties hold for every decomposition of a relation into 3NF?
I was reading *Database Systems*, 6th ed by Ramez Elmasri and Shamkant Navathe. In the textbook they make a claim (in Chapter 15, section 15.2 *Properties of Relational Decompositions*) which I quote below:

> **Claim 1.** It is always possible to find a dependency-preserving decomposition $D$ with respect to $F$ \[$F$ is the set of FDs of a relation $R$\] such that each relation $R\_i$ in $D$ is in 3NF

I have a few questions regarding this.

1. Is it possible to have multiple (different) decompositions of a relation into 3NF, as the claim seems to imply?
2. Is it the case that every decomposition (assuming the answer to first is Yes) of a relation into 3NF is dependency preserving? If not, please provide an example where a decomposition into 3NF does not uphold the dependency preserving property. Also, what about lossless join property?

Thanks!

# Answer
> 1. Is it possible to have multiple (different) decompositions of a relation into 3NF, as the claim seems to imply?

Yes, consider for instance the relation schema `R(A, B, C, D)`, with `F`, a cover of the functional dependencies holding in `R`, equal to:

```
A → B
C A → D
D → A

```

Both the decomposition:

```
R1(A B)
R2(A D)
R3(C D)

```

and

```
R1(A B)
R2(A C D)

```

are in 3NF (actually the first is also in BCNF).

> 2. Is it the case that every decomposition (assuming the answer to first is Yes) of a relation into 3NF is dependency preserving?

No, in the first decomposition the functional dependency `AC → D` is not preserved. Note that both decompositions are lossless (in general, there is no interest in lossy decompositions).

Final note: since there are different possible decompositions, these and their properties depends on the algorithm used to find them. For instance, the classical “analysis” algorithm for BCNF is guaranteed to produce a lossless decomposition, but it is not guaranteed to preserve the dependencies, while the classical “synthesis” algorithm to produce the 3NF is guaranteed to be lossless and preserve the dependencies, as well (but it could find a decomposition in which not all the anomalies are eliminated).
> 0 votes

---
Tags: database-theory, databases, functional-dependencies
---


# Question
Title: Optimal root in shortest path tree (SPT)
I would like to find the "optimal" shortest path tree (SPT) in some undirected weighted graph. As "optimal" SPT, I mean so its maximal path from root to leaf is minimal from any other potential SPTs.

It is quite easy to find SPT from 1 root via Dijkstra's algorithm. So I can run Dijkstra from all vertices and find the "optimal" SPT and its root.

Is there any faster algorithm?

# Answer
> 3 votes
This problem is equivalent to computing the radius of a graph. The best known algorithms for computing radius essentially compute all pairs shortest paths, so the method that you suggest cannot be improved much. If the number of edges is large, maybe Floyd–Warshall algorithm could be faster.

References:

https://en.wikipedia.org/wiki/Distance\_(graph\_theory)

https://arxiv.org/abs/1506.01799

---
Tags: graphs, shortest-path
---


# Question
Title: Does every regular language have a linear grammar?
**Some definitions and facts (from Wikipedia):**

1. A **linear grammar** is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.
2. the **left-linear** or **left regular grammars**, in which all nonterminals in right hand sides are at the left ends;
3. the **right-linear** or **right regular grammars**, in which all nonterminals in right hand sides are at the right ends.
4. Collectively, these two special types of linear grammars are known as the regular grammars; both can describe exactly the regular languages.

**Doubts**

1. Fourth fact used word "collectively" and then "both". What does it actually mean?

* there is both right linear and left linear grammar for all regular languages
    * there is either right linear or left linear grammar for all regular languages
2. Can all non-linear regular grammars be converted into linear regular grammars? (Is there any systematic procedure for that?)

**Update**

I got it now how we can translate RLG to LLG and vice versa. So any given regular language has both RLG and LLG. Now the second question is remaining: Can all non-linear regular grammars be converted into linear regular grammars?

# Answer
Answer to the last question of the update.

The grammar $S \to aSb + 1$ is linear, but it generates the nonregular language $\\{a^nb^n \mid n \geqslant 0\\}$. Therefore, it cannot be converted into a regular linear grammar.
> 1 votes

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


title: Improve algorithmic complexity

text:
# Question
Title: Improve algorithmic complexity
We have an array of N size. We have to perform Q queries on it, in which each Query contains and Index I for which we do:

```
for j=I+1 to N:
  if A[j]<A[I]:
    A[j]=0

```

The Queries are not independent of each other so we need to use the changed Array everytime.

I have given a lot of thought but was able to come up only with brute force solution with complexity of O(Q\*N). Can anyone tell a better solution?

Eg:-

```
Array- 4 3 4 3 2, Query-3 2
After Query 1(Index 3, element 3)- 4 3 4 3 0
After Query 2(Index 2,element 4)-4 3 4 0 0

```

# Answer
Solving this problem benefits from geometrical intuition. Think that for each index $i$, the pair $(i, A\[i\])$ represents a point in 2D-space. Also we can think that assigning $A\[j\]=0$ is the same as removing the point $(j, A\[j\])$ from this space. Now a query with index i means removing all points that are left and below of point $(i, A\[i\])$.

Now the set of removed points can be represented with a set of points $(i\_1, A\[i\_1\]), (i\_2, A\[i\_2\]), \ldots, (i\_k, A\[i\_k\])$, for which $i\_p \< i\_{p+1}$ and $A\[i\_p\] \< A\[i\_{p+1}\]$ for all $1 \le p \< k$. A point $(j, A\[j\])$ is removed if there is some $p$ for which $i\_p \< j$ and $A\[i\_p\] \> A\[j\]$. The picture https://en.wikipedia.org/wiki/Maxima\_of\_a\_point\_set#/media/File:Maxima\_of\_a\_point\_set.svg from Wikipedia might gives intuition for this (though it is left-right mirrored compared to our definition). This set representation can be maintained with a balanced binary search tree. We can check in $O(\log n)$ time if a point $(j, A\[j\])$ is removed by finding the largest $i\<j$ such that $(i, A\[i\])$ is in the set, and checking if $A\[i\] \> A\[j\]$. For performing the query in your problem, first check if the given point $(i, A\[i\])$ already is removed. If it's not, insert it into the set in $O(\log n)$ and repeatedly check if the next element with $j\>i$ has $A\[j\] \< A\[i\]$, and remove it. This can be done in $O(k \log n)$, where $k$ is the number of removed elements, so the amortized complexity if $O(\log n)$.

In summary, your queries can be answered in $O(\log n)$ amortized complexity.
> 1 votes

---
Tags: algorithms, optimization, sorting, arrays
---


# Question
Title: Every regular language has a finite index
For a language $L$ over an alphabet $\Sigma$, we say that two words $v,w \in \Sigma^\*$ are equivalent, denoted $v\sim w$, if for every word $z \in \Sigma^\*$, $vz \in L$ iff $wz \in L$. We define $\[w\]\_L$ to be the equivalence class of $w$ under this relation. The index of $L$ is the number of equivalence classes of strings in $L$.

How can I prove that every regular language has a finite index? can I use the Myhill-Nerode theorem?

I tried to use the fact that if $\delta^\*(v) = \delta^\*(w)$ then $v \sim w$.

# Answer
The Myhill-Nerode theorem suggests that a language $L\subseteq \Sigma^\*$ is regular iff $L$ has a finte index, and this clearly implies that a regular language has a finite index. So, let's prove this direction of the Myhill-Nerode theorem directly. Assume that a language $L$ is regular, and let $\mathcal{A} = \langle Q, \Sigma, q\_0, \delta, F\rangle$ be a DFA for it.

The idea is to define an equivalence relation, denoted $\sim\_{\mathcal{A}}$, over $\Sigma^\*$, and then prove that:

1. The number of equivalence classes of $\sim\_{\mathcal{A}}$ equals $|Q|$.
2. The Myhill-Nerode equivalence relation w.r.t $L$, which i denote by $\sim\_L$, is coarser than the relation $\sim\_{\mathcal{A}}$: for every two words $x, y\in \Sigma^\*$, if $x\sim\_{\mathcal{A}} y$ then $x\sim\_L y$.

Note that $2$ implies that the index of $L$ is at most the number of the equivalence classes of $\sim\_{\mathcal{A}}$, and thus by $1$ and the fact that $|Q|$ is finite, we get that $L = L(\mathcal{A})$ has a finite index.

To begin with, the transition function $\delta$ which is a funtion from $Q\times\Sigma$ to $Q$ can be generalized to $\delta^\*$ inductively to read words as follows. The generalized transition function $\delta^\*: Q\times \Sigma^\*$ is defined by:

* $\delta(q, \epsilon) = q$, for every state $q$.
* and, $\delta(q, u\sigma) = \delta(\delta^\*(q, u), \sigma)$ for every word $u$ and letter $\sigma$.

Intuitively, $\delta(q, w)$ is the state that is reached from $q$ upon reading the word $u$.

Now we define the relation $\sim\_{\mathcal{A}}$ over $\Sigma^\*$. For every two words $x, y \in \Sigma^\*$ we say that $x \sim\_{\mathcal{A}} y$ iff $\delta^\*(q\_0, x) = \delta^\*(q\_0, y)$. In words, $x$ and $y$ are equivalent iff the automaton $\mathcal{A}$ reaches the same states upon reading $x$ and upon reading $y$.

The following lemma can be proved by induction and i leave it to you.

**Lemma**: $\delta^\*(q, u\cdot v) = \delta^\*(\delta^\*(q, u), v)$, for every state $q$ and words $u$ and $v$.

Let's prove 1 and 2:

1. Follows immediately by the definition of $\sim\_{\mathcal{A}}$. Indeed, every state $q$ of $\mathcal{A}$ defines an equivalence class.
2. Assume that $x$ and $y$ are such that $x \sim\_{\mathcal{A}} y$. By definition we have that $\delta^\*(q\_0, x) = \delta^\*(q\_0, y)$. Let $z\in\Sigma^\*$ be a word. We need to show that $xz\in L$ iff $yz\in L$: using the above lemma and what we have so far, we get the following:

$$xz \in L$$ $$iff$$

$$\delta^\*(q\_0, xz) \in F$$ $$iff \ \ (\text{By the lemma})$$

$$\delta^\*(\delta^\*(q\_0, x), z) \in F$$ $$iff \ \ (\text{By the fact that $\delta^\*(q\_0, x) = \delta^\*(q\_0, y)$})$$

$$\delta^\*(\delta^\*(q\_0, y), z) \in F$$ $$iff \ \ (\text{By the lemma})$$

$$\delta^\*(q\_0, yz) \in F$$ $$iff$$

$$yz\in L$$.

thus, $x \sim\_L y$ and so we are done.
> 1 votes

---
Tags: regular-languages
---


# Question
Title: What does it mean by "not recursively enumerable"?
I came across following therem:

> There exists a recursively enumerable language whose complement is not recursively enumerable.

Now, I know following definitions:

> * **Recognizable language** is one which have one-to-one correspondence with the natural number with the additional property that we could specify an algorithm to enumerate the language elements.
> * Given the string not in the **co-recognizable language**, we can give Turing machine which can eventually confirm that the string indeed does not belong to the language.

Then what does the above theorem mean?:

1. $L'$ does not have one-to-one correspondence with the natural numbers?
2. We cannot give an algorithm to enumerate the $L'$s elements?
3. $L'$ is co-recognizable.

# Answer
I'm using r.e. to mean "recursively enumerable" and co-r.e. to mean "the complement is recursively enumerable". I'm assuming by $L'$, you mean the complement of $L$.

To answer your questions directly:

1. This is not correct. Every language over a finite alphabet $\Sigma$ has a one-to-one correspondence to the natural numbers. To show this, you would have to construct a one-to-one function that maps the words of your language to natural numbers. This isn't difficult at all, but a bit technical, so I'm only going to sketch the construction: Pick some well-founded total order $\leq$ on $\Sigma^\*$, for example the lexicographic order. For $w \in L$, define $$predecessors(w) := \\{ v \in L \mid v \lneq w\\}$$ to be the set of words in $L$ preceding $w$ according to your order. Define a mapping $f: L \to \mathbb N$, by $f(w) := |precedessors(w)|$, assigning to each word the number of its predecessors. You could then show that $f$ is in fact a one-to-one mapping. This construction works for any language, though it is not necessarily computable for all languages.
2. Correct, when $L$ is not co-r.e., by definition $L'$ is not r.e., so there cannot be an algorithm that enumerates $L'$.
3. Correct, your theorem says $L$ is r.e., therefore $L'$ is co-r.e. Note this follows from the first premise of your theorem, not from the latter premise. In general, $L'$ being not r.e. on its own does not imply $L'$ being co-r.e. In other words, there are languages that are neither r.e. nor co-r.e., see here.

To elaborate a bit more on what the theorem means: It says there is a language $L$ that is r.e. but not co-r.e.

The important insight is that if a language $L$ is r.e. and co-r.e., then it is decidable. Assume you have a TM $M$ for enumerating $L$ and a TM $M'$ for enumerating its complement $L'$. Then you can build a new TM $M^\star$ for deciding $L$: For a given input $w$, $M^\star$ simulates $M$ and $M'$ in parallel. Since either $w \in L$ or $w \notin L$, one of $M$ or $M'$ has to enumerate $w$ eventually. At this point, $M^\star$ stops the simulation and accepts or rejects $w$ based on which of $M$ and $M'$ enumerated it. It follows that $M^\star$ halts on all inputs and accepts $w$ iff $w \in L$. Therefore, $L$ is decidable.

Based on this insight, if you can find a language $L$ that is r.e. and undecidable, you can then conclude that it cannot be co-r.e. Since if it would be co-r.e. it could not be undecidable.

The usual example would be some variant of the halting problem, e.g. $H = \\{ \langle M,w\rangle \mid M$ is a Turing Machine that halts on input $w\\}$. You should know that $H$ is undecidable. To show that $H$ is r.e., you would have to construct a TM that enumerates $H$. I'm only going to sketch the proof: Your TM $M^\*$ would iterate over triples of the form $\langle M, w, n \rangle$ for a TM $M$, $w \in \Sigma^\*$ and $n \in \mathbb N$ in some fixed order (e.g. lexicographic order). When looking at such a triple, $M^\*$ would simulate $M$ on $w$ for at most $n$ steps. If $M$ halts on $w$ within these $n$ steps, $M^\*$ prints $\langle M, w \rangle$. It's not difficult to see that $M^\*$ will eventually print every pair $\langle M,w \rangle$ for which $M$ halts on $w$, as for every such pair, there is some $n \in \mathbb N$, such that $M$ halts on $w$ within $n$ steps. Therefore, $M^\*$ enumerates $H$, thus $H^\star$ is r.e.

Based on knowing that $H$ is r.e. and undecidable, you can conclude that $H$ cannot be co-.r.e. which proofs your theorem.
> 4 votes

---
Tags: formal-languages
---


# Question
Title: Number of spanning trees in undirected simple graph
> What is the number of spanning trees in an undirected simple graph?

My attempt:

Let $m$ be the number of edges in a simple graph, and let $n$ be the number of vertices.

Then number of spanning trees is $\binom{m}{n-1}$ minus the number of cycles of length $n-1$.

I read on Wikipedia that the number of spanning trees in the complete graph $K\_n$ is $n^{n-2}$.

According to the formula I stated above, it should be $\binom{n(n-1)/2}{n-1} - \binom{n}{n-1} (n-1)!$.

How do I show that this is equal to $n^{n-2}$ for $K\_n$?

# Answer
You cannot show this since it isn't true. I encourage you to try out some actual numbers (e.g. $n=2$) and see for yourself that the numbers don't match. The problem is that what you should be subtracting is not the number of cycles of length $n-1$, but rather the number of collections of $n-1$ edges which contains at least one cycle. Such a collection need not be a cycle of length $n-1$.

In addition, the formula for the number of cycles of length $n-1$ is wrong. The number is $n(n-2)!$ rather than your $n(n-1)!$, and even this formula is only valid for $n \geq 4$ (for smaller $n$ there are no such cycles). However, even after replacing $n(n-1)!$ by $n(n-2)!$, the numbers don't match.
> 1 votes

---
Tags: graphs, spanning-trees
---


# Question
Title: Recognizable vs co-recognizable languages
I understand following about recognizable (aka recursively enumerable) and co-recognizable languages:

1. **Definition 1: Recognizable language** is one which have one-to-one correspondence with the natural number with the additional property that we could specify an algorithm to enumerate the language elements.
2. For recognizable language, we can specify Turing machine which can enumerate the language elements.
3. Given the string in the recognizable language, Turing machine can eventually confirm that the string indeed belongs to the language.
4. Language L is called co-Turing-recognizable, if L’ is Turing-recognizable.
5. Given the string not in the co-recognizable language, Turing machine can eventually confirm that the string indeed does not belong to the language.

**Doubt**

**Q1.** What is definition 1 equivalent of co-recognizable languages?

**Q2.** Do they also have one-to-one correspondence to natural numbers?

**Q3.** Do they also have Turing machine associated with them which can enumerate their elements?

**Q4.** If answer to Q2 and Q3 is true, then doesnt it make them same as recognizable?

# Answer
A language is recognizable if there is a Turing machine that enumerates all words in the language. It is co-recognizable if there is a Turing machine that enumerates all words *not* in the language.

Every language has a one-to-one correspondence to the natural numbers, simply because the number of possible words is countable.

To see the difference between recognizable and co-recognizable, let's take the prototypical example of a recognizable language: it is the language of Turing machines which halt on the empty input. It is easy to enumerate this language: run in parallel *all* Turing machines on the empty input, and whenever one of them halts, print its index. There is provably no similar way to enumerate the complement of this language.

If a language is both recognizable and co-recognizable, then it is decidable, meaning that there is a Turing machine that always halts and tells you whether the input belongs to the language or not. Indeed, if $L$ is recognizable and co-recognizable, then there is a Turing machine $T\_1$ which enumerates all words in $L$, and other Turing machine $T\_0$ which enumerates all words not in $L$. Using these, we construct a decider $T$: on input $w$, run $T\_1$ and $T\_0$ in parallel, until one of them prints $w$. If it were $T\_1$, answer "Yes", and if it were $T\_0$, answer "No".
> 2 votes

---
Tags: formal-languages
---


# Question
Title: Show that: $0.01n \log n - 2000n+6 = O(n \log n)$
> Show that $0.01n \log n - 2000n+6 = O(n \log n)$.

Starting from the definition: $O(g(n))=\\{f:\mathbb{N}^\* \to \mathbb{R}^\*\_{+} | \exists c \in \mathbb{R}^\*\_{+}, n\_0\in\mathbb{N}^\* s. t. f(n) \leq cg(n), \forall n\geq n\_0 \\}$

For $f(n) = 0.01n \log n - 2000n+6$ and $g(n) = n \log n$

Let $c = 0.01\implies 0.01n \log n - 2000n + 6 \leq 0.01 n \log n$

Subtract $0.01 n \log n$ from both sides: $$-2000n +6 \leq 0$$ Add $2000n$ on both sides: $$2000n \geq 6$$ Divide by $2000$: $$n\geq 6/2000$$

If $n \in \mathbb{N}^\*\implies n \geq 0\implies n\_0 = 0$

Thus,

$$0.01n \log n - 2000n+6 = O(n \log n)$$

I'm not sure if what I did is completely correct and if $n\_0 = 0$ is actually a good answer.. If it's correct, can it be done another easier way? and if it's not correct, where did I go wrong?

# Answer
Definition of big-O with c = 0.01 and n0 = 1. For a proof of big-theta you’d show the limit of f(n) / (n log n) exists and is \> 0.

If you had the function f(n) = 0.01 n log n + 2000n + 6, where c = 0.01 doesn't work, a nice large c = 2019 will make the O(n) proof very easy.
> 0 votes

# Answer
Here's a different way of proving that $0.01 \log n - 2000n + 6$ is $O(n \log n)$.

If $f$ and $g$ are monotonically increasing functions and there exists some $x\_0$ such that $g(x\_0) \> 0$, then $f \in O(g)$ if and only if $\exists a, b \colon \forall x \colon f(x) \leq ag(x) + b$. (Proof left as an exercise to those readers who feel up to the challenge. It's not hard, and it also works for continuous functions if you demand something slightly more general from $g$.)

However, the $-2000n$ term makes your functions not satisfy this requirement. However, we can rewrite:

$$0.01n \log n − 2000n + 6 = n(0.01 \log n - 2000) + 6$$

When $n$ is large enough you'll have $0.01 \log n - 2000 \> 1$, and from that point onwards $f$ is monotonically increasing. In particular:

$$0.01 \log n - 2000 \> 1 \Leftarrow 0.01 \log n \> 2001 \Leftarrow \log n \> 200100$$

Which holds when $n = 2^{\log n} \> 2^{200100}$, assuming $2$ is the base of your logarithm.

Apply the theorem at the top of my post with $a = 1$ and $b = 6$, except $N$ has to be at least $2^{200100}$, and argue that the restriction to $n \> 2^{200100}$ doesn't invalidate the conclusion of the theorem.

Alternatively, observe that both functions are continuous and that $n \log n$ satisfies the extra property which I left as an exercise for the reader. Then the theorem applies directly.

Of course, if your problem is homework and your teacher hasn't proven the theorem to you, you should probably prove it yourself.
> 0 votes

---
Tags: complexity-theory, time-complexity, asymptotics
---


# Question
Title: Why can we ignore the constant factor in Weis's proof of the Master Theorem
In the 4th edition of his Data Structures textbook, Weis gives a proof of part of the Master Theorem. This proof says "Let us ... ignore the constant factor in $\theta(N^k)$ ... I don't understand why it ignoring that constant is valid. (I know that the real Master Theorem is broader than the version presented in the text. I'm just having trouble understanding the argument presented in the text.)

Specifically, the relevant part of Theorem 10.6 on page 469 is

The solution to the equation $T(N) = aT(N/b) + \Theta(N^k)$ is $T(N) = O(N^{log\_b} a)$ if $a \> b^k$

The proof includes the phrase "ignore the constant factor in $\theta(N^k)$ ..." and then goes on to use a telescoping sum to get

$T(N) = T(b^m) = a^m \sum\_{i=0}^m (\frac{b^k}{a})^i$

At this point, he argues that because $a \> b^k$, then the sum is a geometric series with a ratio less than 1. However, if we don't ignore the constant in the $\Theta$ expression, isn't there a constant inside the summation that would affect whether the geometric series converges?

# Answer
> 1 votes
Suppose that your function is always in the range $cN^k$ to $CN^k$. Consider the three recurrences $$ s(N) = as(N/b) + cN^k, S(N) = aS(N/b) + CN^k, R(N) = aR(N/b) + N^k. $$ For appropriate initial conditions, $s(N) \leq T(N) \leq S(N)$ will hold, as a straightforward proof by induction would show. On the other hand, for appropriate initial conditions, $s(N) = cR(N)$ and $S(N) = CR(N)$, as another straightforward induction shows. This explains Weis's remark.

What it happening here? As you unroll the recursion, you add various terms which are $\Theta(N^k)$, for various values of $N$. The contribution of the big Theta to the final sum is at most a constant factor. Instead of $a^m \sum\_{i=0}^m (\frac{b^k}{a})^i$, you get $\Theta\bigl(a^m \sum\_{i=0}^m (\frac{b^k}{a})^i\bigr)$. Crucially, the additional constant factor is *global* and doesn't accumulate throughout the recursion.

As an example, consider the generic recurrence $s(N) = 2s(N-1) + f(N)$, with base case $s(0) = 0$. The solution is $$ s(N) = f(N) + 2f(N-1) + 4f(N-2) + \cdots + 2^{N-1} f(1). $$ If we multiply $f(N)$ by a constant factor, the solution of this recurrence will be multiplied by the same constant factor, while the constant $2$ stays the same.

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Is unification over regular expression equations doable?
By way of example, suppose I know that $X + a = b + Y$ where $X$ and $Y$ are variables standing for regular expressions, then $(X, Y) = (b, a)$ is a solution to this set of equations.

Generalizing over all such equations, is there a computable (decidable) procedure for calculating the regular expressions which the variables must stand for in order for the equation to be solvable? Is there some kind of uniqueness, e.g. of minimal solutions?

In case the alphabet size matters: you can represent $\\{1, \ldots, n\\}$ in unary using just two symbols, so I *assume* the answer for $k$\- and $m$-symbol alphabets are the same when $k \geq 2 \land m \geq 2$, in which case I care primarily for alphabets of size $\geq 2$—the reason I stress the word "assume" is that I know some properties of regular languages don't hold for regular expression equations (when suitably translated).

The application I have in mind is miniKanren-style logic programming.

Since families of sets closed under union form a semilattice, and the family of regular languages is one such closed family, programming with regular languages seems straightforward. For example, let each logic variable $V$ represent some indeterminate language $L$. For each $V$ store a pair of bounds $(sub, disj)$ expressing the knowledge $sub \subseteq L \land (L \cap disj) = \emptyset$, i.e. store two sets of strings for which the membership-ness is known. Grow them in the variable unification part and fail when $sub \cap disj \not= \emptyset$.

It would be nice to add logic over regular *expressions* and not just regular *languages*. No obvious approach occurs to me, and I suspect it's a whole other ballgame.

# Answer
I'm fairly sure this is possible. This seems to me as a special case of set constraints over tree languages: we can view regular expressions as a restriction of regular tree languages where each node has 0 or 1 children. These can handle union, concatenation, and recursion (star), and you can solve for variables like you describe.

They're decidable, even when we allow negation. You can see a great survey here: https://theory.stanford.edu/~aiken/publications/papers/ppcp94.pdf In general, Alexander Aiken has a lot of great papers on set constraints.

You might find more of what you're looking for with "word constraints" or "set constraints over words". The complexity situation isn't great for trees, but it might be better for words.
> 1 votes

---
Tags: regular-languages, logic, regular-expressions, equality, unification
---


# Question
Title: Space complexity for storing integers in Python
So I was watching this mock interview by an Airbnb engineer on interviewing.io (https://youtu.be/cdCeU8DJvPM?t=1224) and around ~20:11 seconds he raises an interesting point.

The question that the interviewee was trying to solve was -

```
Array 1 has all unique integers.
Array 2 has the same integers as array 1, except one integer missing.
The code has to find that missing integer.

```

The interviewee suggested we can just subtract the sum of the second array from that of the first array and that'd give us the missing integer, and since these are just sums (integers), they'd take `O(1)` space. But the interviewer then said it's not actually constant since a sufficiently large sum can take more space than a smaller sum.

While that is true, and I double-checked it, via -

```
In [1]: import sys

In [2]: sys.getsizeof(90)
Out[2]: 24

In [3]: sys.getsizeof(9000000000000000000000000000000000)
Out[3]: 40

```

what complexity is it then?

Is saying constant space complexity for these algorithms wrong then?

# Answer
It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the size of input in bits. In this assumption, the sum of the input can be represented with 1 word, so the space complexity is $O(1)$ words. Measured in bits, the space complexity is $O(\log N + \log M)$, where $N$ is the number of integers in input and $M$ is maximum value in input. However note that normally we don't measure space complexity in bits: if we did, then the space complexity of most linear time algorithms, like DFS and BFS would have an extra $O(\log n)$ factor.

In my opinion, there is no single right answer when talking about space complexities like this in an informal setting like job interview. However you should keep in mind that having a single right answer is not the goal of job interviews.
> 7 votes

# Answer
Resource usage always depends on your model of computation. If you're in a situation where integers can grow arbitrarily large then, yes, you need to take that into account.

One way of doing this is by assuming that integer variables take an amount of space that depends on the value stored. Another way is to use something like the word RAM model, which more or less assumes that integer variables are big enough to hold whatever numbers come up in the instances you care about. Another is to explicitly assume that whatever size of integer variable you fix is big enough. What solutions might be appropriate depends on what you're doing.
> 3 votes

# Answer
No, breaking the algorithm by increasing n (the amount of numbers) makes this 100% not working in constant space.

**To the question nobody asked:**

You could easily modify the algorithm to get the space to be constant. (Only the solution given in the interview has this problem. The "best" solution does not have this problem.)

Basically the size of the sum should not be a problem either. Assuming that each number can be stored in constant space of b bits you could easily modify the algorithm to use less space by doing this:

1. calculating the sum for each list/array mod $2^b$ ($r\_1$ and $r\_2$, with $r\_1 ≥ r\_2$)
    * if $r\_1 = r\_2$ -\> either the result is $0$ or the input is broken
2. getting the difference ($d = r\_1 - r\_2$)

Thanks to a possible overflow caused by the number missing:

3. calculate the inverted result $d' = 2^b - d = r\_2 - r\_1 + 2^b$ (mod $2^b$)
4. search for both numbers $d$ and $d'$ in both lists - the one found exactly once is the result

If space was limited (for any reason) this would be an option. It comes at a price: looping again over the input - which might not be possible if the data comes from a server and you do not have the storage to save it.

So almost constant space that only scales with size of the input - I would ignore it in this case because the size of numbers is often ignored. (-\> 2 ints and 2 bools). For doubling the steps in the loops. (And 2\*O(n) = O(n).)

**Example:**

* b = 3 -\> mod 8
* list1 = 3,5,7 -\> 15 (mod 8) = 7
* list2 = 3,5 -\> 8 (mod 8) = 0
* d = 7 - 0 = 7
* d' = 0 - 7 + 8 = 1

**Example 2:**

* b = 3 -\> mod 8
* list1 = 1,3,5,7 = 16 (mod 8) = 0
* list2 = 1,3,5 = 9 (mod 8) = 1
* d = 1 - 0 = 1
* d' = 0 - 1 + 8 = 7

For both: So either 7 or 1 should be exactly once in the 2 lists. Here 7 is both times the result and the 1 can be found only in amounts that are even.

(Writing a function to flip a bit when you find a given number while looping over those 2 lists should be easy.)

---

**Optimization:**

By using the length of the 2 arrays and comparing them you could easily get some information about which value ($d$ or $d'$) is not important. Calculate sum(longer array) - sum(shorter array) and you will have the number.

-\> Single loop over both "arrays" **in parallel** and $2$ numbers of space would be the best case scenario. (And this would even work with some data stream that can't be repeated for some reason.)

In case you cannot use both arrays in parallel you would need one extra number ($≥2$ bits). Then you would add $1$ for each number in array1 and substract $1$ for each number in array2. The result is either $1$ or $-1$ which gives you information which list is longer. (Other results: something is wrong.)

---

**As spitemaster suggested:** Using XOR can be used to improve this even more. His idea reduces the amount of work a bit on older machines (or slower machines you can buy today - like µC) and allows you to save about 50% of the RAM (or 66% of the registers) needed above.

(If you implement the algorithm in hardware this would be really interesting, because XOR is much smaller/faster than an adder.)

The algorithm would simply run over both arrays using XOR on all values. The result is a mix of all numbers that appear 1 + 2\*k times. So if there is only one such number you have the number.
> 1 votes

---
Tags: space-complexity, integers, python
---


# Question
Title: Are type variables really only used in mathematical conversation about types?
Are type variables really only used in mathematical conversation about types? i.e. are type variables (meta-variables that only contain the type classification label) only exist in proofs for types but not in real programming languages? At least is this true for monomorphic types? i.e. I can't actually define:

$$ \texttt{ let id x = x }: \tau$$

unless the type $\tau$ has already been defined or is built in? i.e. type variables only exist for symbolic manipulation of type proofs for humans (at least for monomorphism).

---

Extra thoughts:

I am trying to understand how one defines the identity function $\texttt{let id x = x}$ in monomorphic type systems. I believe the motivation for polymorphism is to allow to apply the same syntactic definition of a function to different data types that are NOT the same, like: $\texttt{id 2}$ and $\texttt{id true}$ without the type checker freaking out at us when it tries to run those (if the language is dynamically typed...I guess in static the compiler would complain at the first instance of the identity function being applied to the wrong type when we try to compile it to usable code).

So to my understanding, if we define types as a set of possible data values, so say $\texttt{int}$ defines the set of all integers. Then the set $Set\_{int \to int}$ is the set of all functions that can map integers to integers. But if we have $Set\_{\forall \alpha . \alpha \to \alpha}$ and we consider the identity function corresponding to both sets so $id\_{\forall \alpha . \alpha \to \alpha} \in Set\_{\forall \alpha . \alpha \to \alpha}$ and $id\_{int} \in Set\_{int \to int}$ then when both identity functions are applied to integers they will behave exactly the same BUT they are not the same function (because they are not the same data value, the data value for one is identity on only integers while the other is give me any type and I will act like its corresponding identity. So in particular $Set\_{\alpha \to \alpha} = Set\_{int \to int} \cup \dots \cup Set\_{string \to string}$ (i.e. the identity $id\_{\alpha \to \alpha}$ is just the identity function for a specific type but not actually a function that is able to process ANY type, its one and in this case this is why the for all is important).

So my question is, is $id\_{\forall \alpha . \alpha \to \alpha} \in Set\_{\alpha \to \alpha}$? I guess I am trying to clarify the dots ... What does it cover? Perhaps it depends on the context of how the types are formally defined? If the $\alpha$ stands for type variables, but type variables are only allowed to be monomorphic by definition (i.e. say the type constructor for the meta-langauge is recursive but only in the monomorphism where we can't introduce the forall quantifier) then the $id\_{\forall \alpha . \alpha \to \alpha} \not\in Set\_{\alpha \to \alpha}$. But if the recursive definition for polymorphic types is recursive at the polymorphic step then perhaps $id\_{\forall \alpha . \alpha \to \alpha} \in Set\_{\alpha \to \alpha}$ is true? Actually I don't think so...

---

Context: CS 421

---

Related:

# Answer
> 2 votes
I am not sure I understand your question, but I believe the answer is "yes". When describing monomorphic languages, an expression such as

```
let id x = x : τ

```

(where `τ` is understood as a type meta-variable) does not mean that you can write `τ` in the program text. Rather, it means an arbitrary expression of that shape, where the meta-variable is replaced by any type of the language:

```
let id x = x : int

let id x = x : string

```

etc. The "meta" in "meta-variable" means that the "variable" in question is not part of the syntax of programs, but a device we use to talk about types abstractly -- or, as you put it, in "mathematical conversation about types."

# Answer
> 0 votes
If you interpret a type $\tau$ as a set of values $Set\_\tau$, then a natural definition for the interpretation of a polymorphic type would be the following: $$Set\_{\forall \alpha.\tau} = \bigcap\_{\kappa \in Types} Set\_{\tau\[\alpha := \kappa\]}$$ You need an intersection because intuitively a polymorphic type should work *for all* its instantiations.

Of course, written like this, the definition of $Set\_\tau$ would be cyclic, so you actually need to quantify over the semantic set of types (i.e., sets of values in your case). So you get: $$Set\_{\forall \alpha.\tau} = \bigcap\_{\kappa \subseteq \Lambda} Set\_{\tau\[\alpha := \kappa\]}$$ Note that by doing this, we actually inject the semantic domain into the syntax (which is a common trick), so any any set of values $\kappa \in \Lambda$ can be directly seen as a "type". And so we take $Set\_\kappa = \kappa$.

To answer your question in that setting, it is obvious that: $$Set\_{\forall \alpha.\alpha \to \alpha} \subseteq Set\_{\tau \to \tau}$$ for all type $\tau$. And so, if $id \in Set\_{\forall \alpha.\alpha \to \alpha}$ then obviously $id \in Set\_{\tau \to \tau}$. And here, $id = \lambda x.x$ is a pure (untyped) term, no particular annotation is required. If on the other hand you had a syntax with type abstraction and type application, then this approach would not directly work, and the above implication regarding $id$ would not be true.

---
Tags: programming-languages, type-theory, type-checking, type-inference, polymorphisms
---


# Question
Title: Maximum number of configurations of Turing machine after $n$ moves
I came across following question:

> What are maximum number of configuration of Turing Machine after $n$ moves?

The answer given was:

> $k^n$, where $k$ is a branching factor.

And that "branching factor" left me confused. So I gave some thoughts: Given $Q$ be total number of states, $\Gamma$ be a tape alphabet and two moves, left and right $\\{L,R\\}$, for every transition function, we have $2^{Q\times \Gamma \times 2}$ possible transitions at each of those $n$ moves. Thus, $k$ must be $2^{Q\times \Gamma \times 2}$. So, total number of configurations of Turing machine after $n$ moves must be ${(2^{Q\times \Gamma \times 2})}^n$. Am I correct with this?

# Answer
> 1 votes
Note that you are bounding the maximal number of configurations, that the machine can be in, from above. To see it more clearly, when a TM $M$ runs on a finite word $w$ it induces a configuration tree $G = \langle V, E\rangle$ where:

* $V$ is the set of configurations that $M$ can be in when it runs on $w$,
* $q\_0w$ is the initial configuration of $M$ on $w$ and it is the root of the configuration tree,
* and the edges in $E$ are defined such that $u$ is a child of $v$ whenever $u$ a consecutive configuration of $v$ (by consecutive we mean that it is possible to reach $u$ from $v$ without violating the transition function of $M$).

As you have mentioned, $k$ is a branching factor, and we usually mean by that the maximal branching degree in the configuration tree. In this aspect you're not correct, $k$ is at most $|{Q\times\Gamma\times \\{L, R\\}}| = {2|Q|\cdot |\Gamma|}$, and this follows from the definition of the transition function. Indeed, $k$ bounds from above the number of consecutive configurations (which is a subset of configurations) and not the number of all possible subsets of configurations of the TM.

Considering the configuration tree, it is a tree of height ($n = |w|$) with branching degree $k \leq {2|Q|\cdot |\Gamma|}$. Now its not hard to see that such a tree has at most $k^n$ leaves which bounds from above the number of configurations that $M$ can be in when it runs on a word $w$ of length $n$.

A thing worth mentioning is that, $k$ is a **constant** that does not depend on the input word $w$ (on $n = |w|$) or on a specific configuration tree, and we know that it exists. This sometimes makes life a bit easier as some algorithms/proofs rely on its existence to conclude some upper bounds.

---
Tags: formal-languages, turing-machines, automata
---


# Question
Title: How to determine time complexity with a simple way?
I'm learning about time complexity but all the cases we did in class were rather simple. Now I'm working on my home work and the cases our teacher let us have was: $$f(n) = 4n(n + 2 \log^2 n^2) + e^{−n} + 8 \sin(2πn/256). $$

Is there a simple way how a I can determine which one of this is the true one? Because this look much more complicated then the ones we did in our class.

1. $f(n) =o(n\log\_2n)$
2. $f(n) =o(2^n)$
3. $f(n) =o(n^4)$
4. $f(n) =O(n\log\_2 n^n)$
5. $f(n) =O(2n + 1)$

# Answer
Don't use the equals sign! $o(n \log\_2 n)$ is the *set of functions* whose growth rate is strictly less than $n \log\_2\\,n$. So the proper expression is $f(n) \in o(n \log\_2 n)$. Similarly, $O(n \log\_2 n)$ is the *set of functions* whose growth rate is less than or equal to $n \log\_2\\,n$.

The simple way to determine which expressions are true is to look at the fastest growing terms. In $f(n)$ that is $4n^2$ which clearly grows faster than $2n + 1$ but slower than $n^4$.

I suggest using Python to find out for yourself:

```
>>> from math import *
>>> def f(n): return 4*n*(n + 2*log(n**2)**2) + e**(-n) + 8*sin(2*pi*n/256)
...
>>> n = 999999999
>>> f(n) < 2**n
True

```

So $f(n) \in o(2^n)$ is likely true.

```
>>> f(n) < 2*n + 1
False

```

So $f(n) \in O(2n + 1)$ is false. While this is not a rigorous method it allows you to get a feel for the numbers. See also the answer here https://stackoverflow.com/questions/1364444/difference-between-big-o-and-little-o-notation
> 1 votes

# Answer
Asymptotic notation satisfies the following two useful properties: $$ \Theta(f(n)) + \Theta(g(n)) = \Theta(\max(f(n),g(n)) \\ \Theta(f(n)) \Theta(g(n)) = \Theta(f(n)g(n)) $$ Using these, you can determine that $f(n) = \Theta(4n^2\log^2 n)$.

Now you can check each of 1.-5. individually, using the fact that $n^a\log^bn = O(n^c\log^dn)$ iff $a \< c$ or $a=c$ and $b \leq d$.
> 2 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: What programming languages always learned in computer science B.Sc.?
Even if programming by itself is not an integral part of computer science,
I would bet any B.Sc. student learns fundamentals of binary code, fundamentals of assembly code and at least one high programming language (above assembly).

What programming languages always learned in computer science B.Sc.?

I define programming as: *writing source code in one or more computer languages, of the programming language type*.

# Answer
There is no programming language that is taught in every computer science B.A. program. There is a lot of variation in what languages are used to teach material, in different programs. For instance, when I took computer science classes, I learned only C and Standard ML. There are other other programs where you might learn (for example) Python and Java. If you choose any one programming language, I would imagine you can find some B.A. programs that teach that language and others that don't.

Learning a specific programming language is usually not the main point of a computer science education. The goal is to learn concepts and skills, and teaching any one programming language is just a way to support that goal.
> 3 votes

---
Tags: formal-languages, education
---


# Question
Title: How to check rapidly if an element is present in a large set of data
I am trying to harvest scientific publications data from different online sources like Core, PMC, arXiv etc. From these sources I keep the metadata of the articles (title, authors, abstract etc.) and the fulltext (only from the sources that provide it).

However, I dont want to harvest the same article's data from different sources. That is, I want to create a mechanism that will tell if an article that I am trying to harvest is present in the dataset of the articles that I already harvested.

The first thing I've tried was to see if the article (which I want to harvest) has a `DOI` and search in the collection of metadatas (that I already harvested) for that that `DOI`. If it is found there then this article was already harvested. This approach, though, is very time expensive given that I should do a serial search in a collection of ~10 millions articles metadata (in XML format) and the time would increase much more for the articles that don't have a `DOI` and I will have to compare other metadatas (like title, authors and date of publication).

```
def core_pmc_sim(core_article):
    if core_article.doi is not None:      #if the core article has a doi
        for xml_file in listdir('path_of_the_metadata_files'):  #parse all PMC xml metadata files
            for event, elem in ET.iterparse('path_of_the_metadata_files'+xml_file): #iterate through every tag in the xml
                if (elem.tag == 'hasDOI'):
                    print(xml_file, elem.text, core_article.doi)
                    if elem.text == core_article.doi:  # if PMC doi is equal to the core doi then the articles are the same
                        return True
                elem.clear()
    return False

```

What is the most rapid and memory-efficient way to achieve this?

(Whould a bloom filter be a good approach for this problem?)

# Answer
> 0 votes
If you knew that every article had a DOI, you could just store a hashtable of the DOIs of the papers that you've already harvested. Of course, in practice, many papers don't have a DOI or don't list their DOI.

If you knew that the paper would be listed with the correct title and authors, you could use a hash of the titles and authors and store that in a hashtable. Of course, in practice it is common for titles to be mis-spelled, or for there to be variations in how they are listed (e.g., changes in capitalization; do you list the full first name of each author or just their first initial; and so on and so on).

If you knew the list of all variations, you could try to canonicalize the title and authors (e.g., lowercase the title, use only the last names of the authors, and so on). Of course, in practice we probably can't know all the variations.

If you figured that all variations would be at small edit distance, you could use fuzzy matching and some kind of database that allows approximate match lookups. (e.g., Efficient map data structure supporting approximate lookup, How fast can we identifiy almost-duplicates in a list of strings?, How to compare/cluster millions of strings?) However, I suspect that in practice edit distance might not be enough to find all matches. Also, there is a risk that you might end up conflating two different papers (for instance, I have seen a series of papers with titles like "Catching the Bugblatter, Part I" and "Catching the Bugblatter, Part II" with the same authors).

Hopefully all of this is conveying that in practice I suspect the problem is messy and there is no single clean answer. Perhaps a pragmatic solution is to use some of the above techniques to find obvious matches, with the idea that this will take care of most cases of matches. For the remainder, just accept that you might store the article multiple times, but hopefully this won't be too common. Ultimately, storage space is extremely cheap, so storing the same article a few times probably isn't so bad.

---
Tags: python, big-data
---


# Question
Title: Are event and mode well defined terms in CS literature?
From my experience in programming small imperative scrips for personal usage with JavaScript,
I can conclude that an *event* is "A perceived change in the output of a system" (such as clicking a link from client side or refreshing a page from server side),
while a *mode* is a situation or "state of affairs" of a program (such as a "saved game" state we can later "load") and if a certain state has happened the program can behave in some way (such as terminating itself).

But if at all, are event and mode well defined terms in CS literature and if so, what is the difference between them?

# Answer
I'm not sure whether they have accepted meanings, but to the extent that they do, an "event" happens at an instantaneous point in time, as opposed to something ongoing. If I was reading something that used the word "mode", I probably wouldn't be sure what is meant by "mode" without looking at the context.

I'm not sure whether you should expect precise, widely-accepted definitions for terms that are used informally.
> 0 votes

---
Tags: terminology
---


# Question
Title: Finding most likely tree over a semilattice
If I am not mistaken, then a semilattice defines a finite set of trees, for example spanning trees.

Now assume that each semilattice edge is annotated with a transition probability. In addition, let's assume that the probability of a tree over the semilattice is the product of the probabilities of all the edges that the tree uses.

How to find the most likely spanning tree, that is the most likely hypothesis how the nodes came to be? I am unsure whether this amounts to finding a maximum spanning tree of the semilattice.

I guess this has applications in probabilistic graphical models...

# Answer
> 1 votes
The maximum spanning tree is about summing weights; maximizing the probability is about multiplying weights. To convert multiplication to sums, take the logarithm.

Hopefully that's enough for you to work out an algorithm for this task.

---
Tags: trees, spanning-trees, lattices, graphical-models
---