# Question
Title: What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues?
Lamport's distributed mutual exclusion algorithm (also described here) solves mutual exclusion problem for $N$ processes with $3(N-1)$ messages per request ("take and release lock" cycle).

It requires that for each pair of processes $P$ and $Q$ all messages send by $P$ to $Q$ are received and processed by $Q$ in the same order. E.g. if $P$ sends messages $m\_1$ and $m\_2$ in that order, $Q$ cannot receive $m\_2$ before receiving $m\_1$.

I would like to see how it breaks if I remove that First-In-First-Out condition and allow reordering. The only counterexample I was able to built uses two processes who want to acquire the shared resource:

1. $P$ starts with clock 10 and sends request $m\_1$ to $Q$
2. $Q$ starts with clock 1 and sends request $m\_2$ to $P$
3. $Q$ receives request $m\_1$ with timestamp 10 and sends acknowledge message $m\_3$ to $P$
4. $P$ receives message $m\_3$ before $m\_2$ and enters critical section. As far as $P$ is concerned, it's the only process wanting the resource
5. $P$ receives message $m\_2$ and responds to $Q$ with acknowledge
6. $Q$ enter critical section as $Q$'s request has timestamp 1 and $P$'s request has timestamp 10, so $Q$ has priority

However, that requires $P$ to respond to $Q$'s request $m\_2$ while in critical section. Otherwise, $Q$ will receive acknowledgment when $P$ is no longer in critical section and there will be no conflict.

Question being: how to construct a counterexample where processes do not respond to external messages while in critical section?

# Answer
Looks like this modification is correct. Proof is similar to proof of Lamport algorithm and follows.

Consider two processes $P\_i$ and $P\_k$ who entered critical sections at moments $e$ and $f$, correspondingly, requested them at moments $e'$ and $f'$, and exited at moments $e''$ and $f''$.

At moment $e$ process $P\_i$ have received a confirmation from $P\_k$. Suppose it was sent by $P\_k$ at moment $g \to e$.

*Case 1*: $g \< f'$. In that case, process $P\_k$ has both itself and $P\_i$ in queue, and $P\_k$'s ticket is greater than $P\_i$'s (because we use logical clock as tickets). So process $P\_k$ cannot enter the critical section until it receives a release from $P\_i$, and we have a correct mutual exclusion.

*Case 2*: $f' \< f \< f'' \< g$. In that case, $f'' \to g \to e$, and we have a correct mutual correct mutual exclusion.

*Case 3*: $f' \< f \< g \< f''$. That case is impossible as $P\_k$ have sent a confirmation while in critical section.

*Case 4*: $f' \< g \< f \< f''$. In that case, process $P\_k$ should've received a confirmation from process $P\_i$ by $f$. Suppose it was sent by $P\_i$ at moment $h$. If $h \> e$, then $h \> e''$ and we have a correct mutual exclusion ($e'' \to h \to f$). Otherwise, $h \< e$, so process $P\_i$ learns about $P\_k$'s wish before entering the critical section. Similarly, as $g \< f$, $P\_k$ learns about $P\_i$'s wish before entering the critical section. But only one of them has lower priority, hence, their critical sections happen in order.
> 2 votes

---
Tags: algorithms, distributed-systems, concurrency, mutual-exclusion
---


# Question
Title: Measuring the difficulty of SAT instances
Given an instance of SAT, I would like to be able to estimate how difficult it will be to solve the instance.

One way is to run existing solvers, but that kind of defeats the purpose of estimating difficulty. A second way might be looking a the ratio of clauses to variables, as is done for phase transitions in random-SAT, but I am sure better methods exist.

Given an instance of SAT, are there some fast heuristics to measure the difficulty? The only condition is that these heuristics be faster than actually running existing SAT solvers on the instance.

---

### Related question

Which SAT problems are easy? on cstheory.SE. This questions asks about tractable sets of instances. This is a similar question, but not exactly the same. I am really interested in a heuristic that given a single instance, makes some sort of semi-intelligent guess of if the instance will be a hard one to solve.

# Answer
In general, this is a very relevant and interesting research question. "One way is to run existing solvers..." and what would this even tell us exactly? We could see empirically that an instance seems hard for a specific solver or a specific algorithm/heuristic, but what does it really tell about the hardness of the instance?

One way that has been pursued is the identification of various structural properties of instances that lead to efficient algorithms. These properties are indeed prefered to be "easily" identifiable. An example is the topology of the underlying constraint graph, measured using various graph width parameters. For example it is known that an instance is solvable in polynomial time if the treewidth of the underlying constraint graph is bounded by a constant.

Another approach has focused on the role of *hidden structure* of instances. One example is the *backdoor set*, meaning the set of variables such that when they are instantiated, the remaining problem simplifies to a tractable class. For example, Williams et al., 2003 \[1\] show that even when taking into account the cost of searching for backdoor variables, one can still obtain an overall computational advantage by focusing on a backdoor set, provided the set is sufficiently small. Furthermore, Dilkina et al., 2007 \[2\] note that a solver called Satz-Rand is remarkably good at finding small strong backdoors on a range of experimental domains.

More recently, Ansotegui et al., 2008 \[3\] propose the use of the tree-like space complexity as a measure for DPLL-based solvers. They prove that also constant-bounded space implies the existence of a polynomial time decision algorithm with space being the degree of the polynomial (Theorem 6 in the paper). Moreover, they show the space is *smaller* than the size of cycle-cutsets. In fact, under certain assumptions, the space is also smaller than the size of backdoors.

They also formalize what I think you are after, that is:

> Find a measure $\psi$, and an algorithm that given a formula $\Gamma$ decides satisfiability in time $O(n^{\psi ( \Gamma )})$. The smaller the measure is, the better it characterizes the *hardness of a formula*.

---

\[1\] Williams, Ryan, Carla P. Gomes, and Bart Selman. "Backdoors to typical case complexity." International Joint Conference on Artificial Intelligence. Vol. 18, 2003.

\[2\] Dilkina, Bistra, Carla Gomes, and Ashish Sabharwal. "Tradeoffs in the Complexity of Backdoor Detection." Principles and Practice of Constraint Programming (CP 2007), pp. 256-270, 2007.

\[3\] Ansótegui, Carlos, Maria Luisa Bonet, Jordi Levy, and Felip Manya. "Measuring the Hardness of SAT Instances." In Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI’08), pp. 222-228, 2008.
> 26 votes

# Answer
Since you know about the phase transition, allow me to mention a few other simple checks that I am aware of (which are likely subsumed by the constraint graph analysis):

* Some early random SAT generators inadvertently created mostly easy formulas because they used "constant density", meaning a roughly equal proportion of all clause lengths. These were mostly easy because 2-clauses and units simplify the problem significantly, as one should expect, and really long clauses either don't add much branching or facilitate hyper-resolution even better. So, it seems better to stick with fixed-length clauses and vary other parameters.
* Similarly, a powerful simplification rule is Pure Literal Elimination. Obviously, a formula is really only as hard as the number of impure literals it has. Because Resolution creates new clauses numbering $|x|\*|\lnot x|$ (meaning, the product of occurrences of $x$ and its negation), the number of resolvents is maximized when there are an equal number of positive and negative literals for each variable. Hence, Balanced SAT generators.
* There is also a technique called "No Triangle SAT", which appears to be pretty fresh\[1\], which is a kind of hard-instance generator which forbids "triangles". A triangle is a set of clauses containing 3 variables $v\_1, v\_2, v\_3$ which occur pairwise in all combinations in some set of clauses (i.e., $\\{v\_1, v\_2, ...\\}, \\{v\_2, v\_3, ...\\}, \\{v\_1, v\_3, ...\\}$). Apparently, triangles tend to make a formula easier for known solvers.

\[1\] https://arxiv.org/pdf/1903.03592.pdf
> 2 votes

# Answer
On top of Juho's excellent answer, here's another approach:

Ercsey-Ravasz & Toroczkai, *Optimization hardness as transient chaos in an analog approach to constraint satisfaction*, Nature Physics volume 7, pages 966–970 (2011).

This approach is to rewrite the SAT problem into a dynamical system, where any attractor of the system is a solution to the SAT problem. The basins of attraction of the system are more fractal as the problem becomes harder, and so the "difficulty" of the SAT instance can be measured by examining how chaotic the transients are before the system converges.

In practice, this means starting a bunch of solvers from different initial positions and examining the rate at which solvers escape the chaotic transients before they arrive at an attractor.

It's not hard to come up with a dynamical system for which the "solutions" are solutions to a given SAT problem, but it's a little harder to make sure that the solutions are all attractors and not repellers. Their solution is to introduce energy variables (akin to Lagrange multipliers) to represent how badly a constraint is being violated, and try to get the system to minimise the energy of the system.

Interestingly, using their dynamical system, you can solve SAT problems in polynomial time on an analog computer, which in itself is a remarkable result. There is a catch; it may require exponentially large voltages to represent the energy variables, so unfortunately you can't realise this on physical hardware.
> 1 votes

---
Tags: complexity-theory, satisfiability, heuristics
---


title: How to reduce EQU to UNI?

text:
# Question
Title: How to reduce EQU to UNI?
Let $$\texttt{EQU}=\\{u\\#v \mid T(M\_u)=T(M\_v)\\} \\ \texttt{UNI}=\\{w \mid T(M\_w)= \Sigma^\*\\}$$

How can you prove $\texttt{EQU} \leq \texttt{UNI}$?

The idea I have so far is, to simulate the TM that decides whether a given $w = u\\#v$ is in $\texttt{EQU}$ or not. In case it is, our TM halts and we simply accept everything ($f(w) \in \texttt{UNI}$). But, as far as I know, there are two options for $w \notin \texttt{EQU}$ :

1. The simulation won't ever stop
2. The simulation stops but not with $q \in F$

The first case isn't a problem as I think. We won't ever accept because the TM never finishes with simulating. But the second case is a problem, as the TM accepts with $w \notin \texttt{EQU}$.

# Answer
This answer assumes that $T(M)$ is the set of inputs on which $M$ halts.

Given an instance $u\\#v$ of $\texttt{EQU}$, we construct a new Turing machine $w$ with the following input:

* A string $x$.
* An integer $t$.

The machine acts as follows.

1. Run $u$ on $x$ for $t$ steps. If $u$ halted, then run $v$ on $x$.
2. Run $v$ on $x$ for $t$ steps. If $v$ halted, then run $u$ on $x$.
3. Halt.

I claim that $w \in \texttt{UNI}$ iff $u\\#v \in \texttt{EQU}$. To see this, consider some input $x$. We distinguish four different cases:

1. Both $u$ and $v$ halt on $x$. In this case $w$ will halt on $x,t$ for all $t$ (since "run $v$ on $x$" and "run $u$ on $x$" will always terminate).
2. Both $u$ and $v$ don't halt on $x$. In this case the test in steps 1–2 will always fail, and so $w$ will always reach step 3 and halt on $x,t$, for any $t$.
3. $u$ halts on $x$ after $t$ steps, and $v$ doesn't halt on $x$. In this case $w$ won't halt on $x,t$, getting stuck at step 1.
4. $v$ halts on $x$ after $t$ steps, and $u$ doesn't halt on $x$. In this case $w$ won't halt on $x,t$, getting stuck at step 2.

---

How did I construct this machine? First of all, let us note that $\texttt{UNI}$ is $\Pi\_2$-complete. This means that we can reduce to it any language $L$ such that $$ x \in L \leftrightarrow \forall y \exists z \\, \Pi(x,y,z), $$ where $\Pi$ is any computable predicate. Next, using $H(u,x,t)$ for "$M\_u$ halts on $x$ within $t$ steps", we see that $$ u\\#v \in \texttt{EQU} \leftrightarrow \forall x (\exists s \\, H(u,x,s) \land H(v,x,s)) \lor (\forall t \\, \lnot H(u,x,t) \land \lnot H(v,x,t)). $$ Rearranging, this is the same as $$ u\\#v \in \texttt{EQU} \leftrightarrow \forall x \forall t \exists s \\, (H(u,x,s) \land H(v,x,s)) \lor (\lnot H(u,x,t) \land \lnot H(v,x,t)). $$ Therefore $\texttt{EQU}$ should reduce to $\texttt{UNI}$. Taking a look at the $\Pi\_2$-completeness proof, we reach the machine outlined above.

---

It is easy to see that $\texttt{UNI}$ reduces to $\texttt{EQU}$, by mapping $w$ to $w\\#h$, where $M\_h$ is a machine that always halts. We conclude that $\texttt{UNI}$ is also $\Pi\_2$-complete.
> 1 votes

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


# Question
Title: What are the sufficient conditions for weighted binary code to be self compliementary?
I was going through binary codes and found out that if the weighted binary code is self complimentary then it's weights addition will be equal to 9. Is the converse true? If not then what are the sufficient conditions for making a weighted binary code self complimentary. My research was in vain. Please help and clear my doubt.

For example: 3321 is self complimentary code. 3+3+2+1 = 9

# Answer
You haven't defined your terms, so let me quickly define them:

1. A *weighted binary code* $abcd$ is the mapping $C\colon \\{0,1\\}^4 \to \mathbb{N}$ given by $$C(xyzw) = ax + by + cz + dw.$$
2. A code $C$ is *legal* (my term) if $0,\ldots,9$ are all in the range of $C$.
3. A code $C$ is *self-complementing* if whenever $C(xyzw) \in \\{0,\ldots,9\\}$, we have $$ C(\bar{x}\bar{y}\bar{z}\bar{w}) = 9-C(xyzw), $$ where $\bar{x}$ is the negation of $x$.

Since $\bar{x} = 1-x$, we have $$ C(\bar{x}\bar{y}\bar{z}\bar{w}) = a(1-x)+b(1-y)+c(1-z)+d(1-w) = a+b+c+d - C(xyzw). $$ Therefore a legal code is self-complementing iff $a+b+c+d=9$.
> 1 votes

---
Tags: error-correcting-codes, binary
---


title: $PSPACE$ not equal $DSPACE(2^n) $

text:
# Question
Title: $PSPACE$ not equal $DSPACE(2^n) $
It seems pretty obvious that $PSPACE$ is not equal to $DSPACE(2^n) $. Can this be shown using the space hierarchy theorem? Is that the most simple and straight-forward way?

# Answer
> 2 votes
It is tempting to use the following argument: For every $k$, the space hierarchy theorem shows that there is some problem in $\mathrm{DSPACE}(2^n)$ which is not in $\mathrm{DSPACE}(n^k)$ (since $n^k = o(2^n)$), hence $\mathrm{PSPACE} \neq \mathrm{DSPACE}(2^n)$. Unfortunately, the same argument shows that $\mathrm{PSPACE} \neq \mathrm{PSPACE}$, since for every $k$ there is a problem in $\mathrm{DSPACE}(n^{k+1}) \subset \mathrm{PSPACE}$ which is not in $\mathrm{DSPACE}(n^k)$ (since $n^k = o(n^{k+1})$).

What went wrong? Hopefully this will be clear later on.

How do we fix this argument? Take a (space-constructible) function $f(n)$ such that

1. $f(n) = o(2^n)$.
2. For every $k$, $n^k = O(f(n))$.

For example, we could take $f(n) = 1.5^n$.

The space hierarchy theorem gives a language in $\mathrm{DSPACE}(2^n)$ which is not in $\mathrm{DSPACE}(f(n))$. This language is not in $\mathrm{DSPACE}(n^k)$ for any $k$, hence it is not in $\mathrm{PSPACE}$.

Notice that in contrast to the preceding argument, here the *same* language works for *every* $k$; there we got a *different* language for each $k$.

# Answer
> 2 votes
> Can this be shown using the space hierarchy theorem?

Yes. By the space hierarchy theorem, there is a language $L\in\mathrm{DSPACE}(2^n)$ that is not in $\mathrm{DSPACE}(f(n))$ for any $f=o(2^n)$. In particular, this language is not in $\mathrm{DSPACE}(n^k)$ for any $k$, so it is not in $\mathrm{PSPACE}$.

> Is that the most simple and straight-forward way?

It's hard to imagine anything simpler!

---
Tags: complexity-theory
---


# Question
Title: Proof that shortest path with negative cycles is NP hard
I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is shortest?)

How would I reduce the SAT problem into the shortest path problem in polynomial time?

# Answer
> 5 votes
Copied from my answer on cstheory.stackexchange.com:

---

Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.

This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.

Thus your problem is NP-Hard.

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


# Question
Title: Sampling in large graph using simple random walk
I'm studying sampling techniques in online social networks. The assumption is we don't have full access to the network(i.e, **we don’t know the size of the network**). However crawling is supported, i.e, starting with any arbitrary node we can access its neighbors. Hence we go for random walk(Markov Chain) based crawling techniques as it requires only neighborhood information for any node.

Let's assume we choose simple random walk(SRW) for crawling the network.

In SRW we start with an arbitrary seed node then choose one of the neighbors as new node. At the new node we choose one of its neighbors and this process continues.

Let G be our graph show in above figure, assume graph is large and **size of the graph is not known**. We go for SRW with node 'A' as initial node.

Since the size of the graph is not known how do we select initial distribution $X\_0$(at time 0), and initial transition probabilities $P\_0$(at time 0). After time 0 if I choose one of the neighbors(say B), how the transition probabilities $P\_1$(at time 1) and distribution $X\_1$(at time 1) are calculated.

# Answer
While the *algorithm* doesn't know the graph, when you are analyzing the performance of the algorithm on a graph, you do know the graph.

For a similar example, take the egg dropping puzzle. In this puzzle, the algorithm doesn't know the value of $T$, but when analyzing the algorithm, you are allowed to use the value of $T$; indeed, otherwise it's not clear how you'd ever end up with a running time depending on $T$.
> 2 votes

---
Tags: sampling, social-networks, random-walks
---


# Question
Title: Finding row wise sum of transpose of hv-convex binary matrix
I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n\*m).

```
e.g. I get {4,3,2,2,1} in the input. It's the row wise sum of the following matrix:

    1 1 1 1
    1 1 1 0
    1 1 0 0
    1 1 0 0
    1 0 0 0

```

To solve the problem, I have to find the row-wise sum of it's transpose.

```
i.e. I need to calculate {5,4,2,1}

1 1 1 1 1
1 1 1 1 0
1 1 0 0 0
1 0 0 0 0

```

Can it be achieved in less than O(n\*m)?

# Answer
A non-increasing sequence of integers is known as a *partition*. The operation you are describing is known as *conjugation*. Given a partition $\lambda\_1,\ldots,\lambda\_n$, you can compute its conjugate $\lambda'\_1,\ldots,\lambda'\_m$ as follows:

* Initialize a pointer $i$ at $n$.
* Set $\lambda'\_1 = i$.
* Advance $i$ backwards until $\lambda\_i \geq 2$.
* Set $\lambda'\_2 = i$.
* Advance $i$ backwards until $\lambda\_i \geq 3$.
* Set $\lambda'\_3 = i$.
* ...
* Stop once $i = 1$.

As an example, here is how you apply this algorithm on $4,3,2,2,1$. $$ \begin{align\*} &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ &&&& \uparrow \\ &&&& 5 \end{array} \\\hline &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ &&& \uparrow \\ &&& 4 \end{array} \\\hline &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ & \uparrow \\ & 2 \end{array} \\\hline &\begin{array}{ccccc} 4 & 3 & 2 & 2 & 1 \\ \uparrow \\ 1 \end{array} \end{align\*} $$ It might happen that at some point $i$ doesn't advance at all. This is what happens if we apply this algorithm on $5,4,2,1$: $$ \begin{align\*} &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ &&& \uparrow \\ &&& 4 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ && \uparrow \\ && 3 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ & \uparrow \\ & 2 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ & \uparrow \\ & 2 \end{array} \\\hline &\begin{array}{cccc} 5 & 4 & 2 & 1 \\ \uparrow \\ 1 \end{array} \end{align\*} $$
> 4 votes

# Answer
The row-wise sum of the transpose is just the column-wise sum of the original matrix. So, for inputs $a\_1 \cdots a\_n$ and outputs $b\_1 \cdots b\_m$, it looks something like this: $$ \begin{array}{c|c&c&c&lcr} & b\_1=4 & b\_2=2 & b\_3=1 \\ \hline a\_1=3 & 1 & 1 & 1 \\ a\_2=2 & 1 & 1 & 0 \\ a\_3=1 & 1 & 0 & 0 \\ a\_4=1 & 1 & 0 & 0 \end{array} $$

Each output is equal to the number of rows long enough to reach it. Therefore, a value $a\_k$ affects the first $a\_k$ outputs.

---

# Algorithm description

First, initialize a vector of length $m$ called $b$, setting all elements to $0$. Next, for each element $a\_i$ in $a$, increment $b\_{a\_i}$ by one. (this is the last element to be affected by $a\_i$.)

Next, we will iterate backward over $b$, adding the next element and storing the result back into $b$. This effectively sums all higher elements in the old $b$.

# Pseudocode:

```
conjugate(array a, int n, int m)
  b = new Array length m (all zeros)

  for i = 1 to n
    b[a[i]] += 1

  for i = m-1 downto 1
    b[i] += b[i+1]

  return b

```

# Ruby Implementation

```
def conjugate(a)
  b = Array.new(a[0], 0)
  a.each do |x|
    b[x-1] += 1
  end
  (a[0]-2).downto 0 do |i|
    b[i] += b[i+1]
  end
  b
end

```

Try it online!

# Efficiency

We have one loop over $a$ and one loop over $b$, giving $\Theta(n+m)$.
> 3 votes

---
Tags: graphs, combinatorics
---


# Question
Title: What are some practical problems which require the use of Kadane's algorithm?
I've worked through Kadane's and love its elegance. I am worried though, unless asked specifically about arrays and it's obvious that's what's for dinner, I won't know to use it.

What are some real-life problems and applications where this algorithm is key? How would one go about recognizing them in the wild?

# Answer
See the Wikipedia article on the maximum subarray problem for applications to genomic sequence analysis, computer vision, and data mining.
> 1 votes

---
Tags: algorithms, applied-theory
---


# Question
Title: Context free grammar for a palindrome of even length + cc
Suppose the language is $\\{AA^R: A \in \\{a,b\\}^\*\\}$.

I know that I can make a context free grammar for it:

$$S\to aSa \mid bSb\mid\epsilon$$

Now if the language was $\\{AA^Rcc: A \in \\{a,b\\}^\*\\}$, so the same thing but with $cc$ at the end. Would the following context free grammar work?

$$\begin{aligned} S&\to aS \mid bS\mid\epsilon\mid T\\ T&\to cc\\ \end{aligned}$$

I think it works cause you have the options to make the original string and its reverse, but unlike in the first example, the grammar doesn't fit how the output is suppose to be and so you kind of have to remember what the original string was to make the reverse and then append $cc$ at the end. But then I remember that automata doesn't have memory of previous states so what would be correct grammar?

# Answer
> 2 votes
### This CFG does not work

$$\begin{aligned} S&\to aS \mid bS\mid\epsilon\mid T\\ T&\to cc\\ \end{aligned}$$ It generates $acc$ by $S\Rightarrow aS\Rightarrow aT\Rightarrow acc$, which is not of form $AA^Rcc$. In fact, it generates the language $(a+b)^\*(\epsilon+cc)$.

---

You might have missed the basic mindset to write a context-free grammar (CFG).

### Every non-terminal in a CFG stands for a language.

Thinking in terms of languages instead of strings should be more helpful sometimes for constructing the CFG.

Since the language $S=\\{AA^Rcc: A \in \\{a,b\\}^\*\\}$ is the concatenation of the language of the palindromes of even length, $P=\\{AA^R: A \in \\{a,b\\}^\*\\}$ and the language of one word, $C=\\{cc\\}$, the corresponding substitution rule is $$ S\to PC$$ to which we add the substitution rules for $P$ and $C$ $$\begin{aligned} P&\to aPa\mid bPb\mid\epsilon\\ C&\to cc.\\ \end{aligned}$$ The collection of all substitution rules above is the CFG wanted. Note that each of the symbols $S, P, C$ is abused to denote a non-terminal as well as the languages it stands for, i.e, the context-free language generated if we treat it as the starting symbol.

### Exercise

Write a CFG for the language $\\{AA^RbcBB^R: A \in \\{a,b\\}^\*, B\in\\{c,d\\}^\*\\}$.

---
Tags: context-free
---


title: Calculate probabilty to escape the maze

text:
# Question
Title: Calculate probabilty to escape the maze
I am trying to solve the problem to calculate probability to escape the maze and stuck at one use case. Here is the problem statement

The Frog is in an two-dimensional maze represented as a table. The maze has the following characteristics:

1. Each cell can be free or can contain an obstacle, an exit, or a mine.
2. Any two cells in the table considered adjacent if they share a side.
3. The maze is surrounded by a solid wall made of obstacles.
4. Some pairs of free cells are connected by a bidirectional tunnel.

When the frog is in any cell, he can randomly and with equal probability choose to move into one of the adjacent cells that don't contain an obstacle in it. If this cell contains a mine, the mine explodes and the frog dies. If this cell contains an exit, then the frog escapes the maze.

When the frog lands on a cell with an entrance to a tunnel, he is immediately transported through the tunnel and is thrown into the cell at the other end of the tunnel. Thereafter, he won't fall again, and will now randomly move to one of the adjacent cells again. (He could possibly fall in the same tunnel later.)

It's possible for the frog to get stuck in the maze in the case when the cell in which he was thrown into from a tunnel is surrounded by obstacles on all sides.

So I get input as

The first line contains three space-separated integers n, m and k denoting the dimensions of the maze and the number of bidirectional tunnels.

The next n lines describe the maze. The i'th line contains a string of length m denoting the i'th row of the maze. The meaning of each character is as follows:

1. \# denotes an obstacle.
2. A denotes a free cell where the frog is initially in.
3. * denotes a cell with a mine.
4. % denotes a cell with an exit.
5. O denotes a free cell (which may contain an entrance to a tunnel).

The next k lines describe the tunnels. The i'th line contains four space-separated integers i1,j1, i2, j2. Here (i1,j1) and (i2, j2) denote the coordinates of both entrances of the tunnel. (i,j) denotes the row and column number, respectively.

So for 1st use case input is

```
3 6 1
###*OO
O#OA%O
###*OO
2 3 2 1

```

Answer for this is 0.25. Total possible path could be frog gets stuck (1,1) cell + can die two times (2 mines) + Exit. So probability is `1/4`

But for below use case am not able to deduce the correct probability.

```
7 7 2
O**%**O
OOOOOOO
OOO*OOO
**OA###
OOOO#OO
O*OO#O%
OOOO#OO
1 1 7 7
6 4 6 6

```

**Answer should be 0.13344359** **my answer is 0.2**

I wrote a DFS to calculate all the end state a frog could be. In this case 2 exit + 8 mines + 0 stuck.

```
prob = Double.valueOf(maze.exit.size())/Double.valueOf(maze.exit.size()+maze.mines.size()+maze.stuck.size());

private static void dfs(Vertices v, Maze m, Vertices[][] edgeTo) {
        m.setMark(v.x, v.y, true);

        if(!m.neighbours(v).isEmpty()) {
            for (Vertices w : m.neighbours(v)) {
                if (w!=null) {
                    edgeTo[w.x][w.y] = v;
                    if(!m.marked(w.x, w.y)) {
                        dfs(w, m, edgeTo);
                    }
                    if(w.state.equals("%")) {
                        m.addExit(w);
                    } else if(w.state.equals("*")) {
                        m.addMines(w);
                    }
                }
            }
        } else if(!v.state.equals("*") && !v.state.equals("%")) {
            m.addStuck(v);
        }
    }

```

**can someone help to explain the correct probability in this use case?**

# Answer
First of all, note that you should use pseudo-code in your question to make it readable by anyone.

You cannot treat this problem by just listing possible ends and give them equal probability. Consider this trivial case with no tunnel:

**%AO\***

the frog does not have a total 50 % to escape. On first move it has 50 % to go left to exit and 50 % to go right. But if it goes right it has 50 % to die on the mine and 50 % to come back on initial cell. Finally you build the series:

* to exit $\sum\_n \frac{1}{2^{2n+1}} = 2/3$
* to die $\sum\_n \frac{1}{2^{2n+2}} = 1/3$

Of course finding the series expression can be very complicated on hard mazes. So how to solve this problem ? You can for example use a dynamic programming solution.

The sub-problem is having the probabilities for the frog to be on any cell after the $k^{th}$ move, what are the probabilities after the $(k+1)^{th}$ move ? These probabilities also contain exit and death.

So let's take again the small example **%AO\***, indexing the cells 1 to 4 from left to right.

* at $k=0$, the frog is on cell 2 so $P(2) = 100 \\%$,
* at $k=1$, the frog moves left or right, so $P(exit) = 50\\%$, $P(3)=50\\%$,
* at $k=2$, $P(exit) = 50 \\%$, $P(2) = 25 \\%$, $P(dead)=25\\%$

ans so on, until $P(exit) + P(dead)$ is sufficiently close to 100 % for the precision you need.

Due to tunnels or even from start position, there may be some cells unable to reach a mine, an exit or any of them (as your first example). You should first investigate this, any cell that cannot reach an exit shoud be considered as a mine. And a cell that cannot reach a mine but can reach an exit should be considered as an exit. This will prevent any infinite loop and save some time.
> 1 votes

---
Tags: algorithms, graphs, probability-theory
---


# Question
Title: Given $L$ and $D$ find $X, \text { such that } X * 10^L + D \equiv 0 \mod M$
Given $L$ and $D$ find $X, \text { such that } X * 10^L + D \equiv 0 \mod M$. Integer $M$ is given and it is the same for all calculations however we need to solve for $X$ for more different numbers. One important thing that we know is that $\gcd(M, 10) = 1$.

I rewrited the equation in this type: $X * 10^L \equiv M - D \mod M$. If $M$ was prime number we could just multiply $M-D$ by $(10^L)^{M-2}$. However $M$ might be arbitrary integer. How can we use the fact that $\gcd(M, 10) = 1$

# Answer
Since $10$ is relatively prime to $M$, it has an inverse modulo $M$, which can be found efficiently using the extended GCD algorithm. So you can simply calculate $X = -10^{-L}D$ (all computations modulo $M$).
> 1 votes

---
Tags: modular-arithmetic
---


# Question
Title: Reduction from NP-complete problem to unknown complexity problem and vice-versa
Suppose I have two problems: $B$, which is NP-complete, and $A$, of unknown complexity.

Question:

* If I show that $B \le A$ I can state that $A$ is also NP-complete because the two required conditions are satisfied: (i) $A$ is in NP; (ii) I reduced a NP-complete problem to $A$.
* If I show that $A \le B$ I can say that $B$ is at least hard as $A$, so $A$ is at least NP-complete, but can be harder.

Are these statements correct?

# Answer
I shall assume "$\le$" indicates a poly-time, many-one (i.e., Karp) reduction. This seems to be the case since you are referring to NP-completeness.

> If I show that $B \le A$ I can state that A is also NP-complete because the two required conditions are satisfied: (i) A is in NP (ii) i reduced a NP -complete problem to A.

If $B \le A$, that is, $B$ is reducible to $A$, then $A$ is necessarily $\mathbf{NP}$-hard, that is, any problem in $C \in \mathbf{NP}$ is reducible to $A$ (i.e., $C \le A$). This is because any problem $C \in \mathbf{NP}$ is reducible to $B$ (due to the $\mathbf{NP}$-completeness of $B$) and we have $C \le B \le A$; using the transitivity of (this form of) reduction we obtain $C \le A$. However, *this does not at all imply* that $A \in \mathbf{NP}$—otherwise, any $\mathbf{NP}$-hard problem would be $\mathbf{NP}$-complete! To prove $A$ is $\mathbf{NP}$-complete, thus, you would also have to prove $A \in \mathbf{NP}$ separately.

> If I show that $A \le B$ I can say that $B$ is at least hard as $A$, so $A$ is at least NP-complete, but can be harder.

$A \le B$ means $A$ is reducible to $B$, which can be reformulated as $B$ being at least as hard as $A$, as you have stated. In no way does this imply that $A$ is $\mathbf{NP}$-complete. Granted, it could be the case, but, for all we know, $A$ could be in $\mathbf{P}$, a regular language, or even trivial (i.e., $\Sigma^\ast$ or $\varnothing$).
> 2 votes

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


# Question
Title: Confusion with analysis of hashing with chaining
I was attending a class on analysis of hash tables implemented using chaining, and the professor said that:

> In a hash table in which collisions are resolved by chaining, an search (successful or unsuccessful) takes average-case time θ(1 + α), under the assumption of simple uniform hashing.

and

> The worst-case time for searching is θ(n) plus the time to compute the hash function.

These are quoted from out textbook, ITA. Here α is the load factor, which is equal to n/m where n is the total number of elements to be inserted to the hash table and m is the size of the hash table (which is a constant for each implementation).

My confusion arises from the thinking that

> θ(1 + α) = θ(α) = θ(n/m) = θ(n)

So I claimed that θ(1 + α) = θ(n), ie the average case and worst case time complexities are the same and the professor disagrees with me.

She asked me to find out by myself why I am wrong. I did some brainstorming and the only deduction I can make is that either I am wrong in assuming that m is a constant or asymptotic notations can't be used to compare between worst-case and average-case running time in this case. Please help me find what is wrong here. Also I don't understand why θ(1 + α) is not written simply as θ(α) and also why the professor insists on the value of α being less than, equal to, or greater than 1

# Answer
The reason that we are using $\Theta(1+\alpha)$ rather than $\Theta(\alpha)$ is that $\alpha$ could be very small. Imagine for example that the hidden constant in both $\Theta$s is one, and that $\alpha=0.000001$. There is a large difference between $1.000001$ and $0.000001$.

Regarding your wrong deduction, note that the first paragraph mentions *average* case and the second *worst* case. It's true that the average case is at most the worst case, but not the other way around.
> 4 votes

# Answer
O(1+α) is only equal to O(α) when α becomes much greater than 1 and for hash tables that is usually not the case. For a chaining hash table it would typically be around 1 and for an open addressing hash table it would be less than or equal to 1. If α much greater than 1 we would be calling it a hash table any more but rather a bunch of lists that indeed will have an asymptotic complexity of O(n).
> 0 votes

---
Tags: complexity-theory, algorithm-analysis, asymptotics, hash-tables
---


# Question
Title: List of major Open Problems in Computational Complexity and their Likelihood?
I remember reading an article/paper (or perhaps a talk, most probably by Scott Arranson) where he lists the major open problems and their likelihood of being true or false in a table/graph. This is listed along with the 'surprise factor' of each result if its true/false.

I am unable to locate the article though. I wonder if someone remembers the article and can help. I am aware of a similar one by Ryan Williams but I am looking for the other one.

P.S. I know its a silly request. Apologies. But, still need it.

# Answer
> 4 votes
Perhaps you are looking for the diagram on slide 12 of this talk by Scott Aaronson. Scott has given the talk many times, and not all versions contain the slide. Note that except for P vs NP, it does not contain any open problems, but apart from that, it appears to match your description.

# Answer
> 5 votes
What you are searching for could be *Some Estimated Likelihoods For Computational Complexity* by R. Ryan Williams, 2018.

Here are "Some Estimated Likelihoods for Some Major Open Problems" in that paper. Note that "The numerical values of my 'estimated likelihoods' are (obviously) nothing too rigorous. What is more important is the relative measure between problems."

---
Tags: complexity-theory, reference-request
---


# Question
Title: Single-source shortest paths with even weight
I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even. In another words, we have to find the shortest way with the minimum even weight.

I'd like to have some ideas how we solve this.

Thanks.

# Answer
Forget the even-length requirement for a moment and consider how something like Dijkstra's algorithm works. As the algorithm progresses, you have essentially two types of vertex: the ones for which you've already figured out the shortest path, and the ones for which you only have an upper bound (i.e., the shortest path you've seen to that vertex so far).

Modify it so there are three types of vertex: ones for which you've figured out the shortest even-length path, ones for which you've figured out the shortest path but it was odd, and ones for which you only have an upper bound for the shortest path and shortest even path.
> 3 votes

# Answer
Another solution that doesn't require modifying the algorithm *(so you can do it with an off-the-shelf implementation)*:

Have two copies of the graph, one called `even` the other called `odd`. The idea is that when the total path-length *so far* is even/odd, you'll be in the `even`/`odd` graphs respectively. Then you only need to consider the start/end nodes on the `even` graph.

You can do this by removing the odd-length edges from both graphs, and replacing them with equivalent edges that criss-cross graphs. This works because adding an odd number swaps parity, while adding an even number keeps the same parity.
> 2 votes

---
Tags: algorithms, graphs, shortest-path, weighted-graphs
---


# Question
Title: Intersection of a recognizable language and a decidable language is decidable?
I'm having trouble with proving that "Intersection of a recognizable language anda decidable language is decidable.

I assume this is true although I have no idea how to proof it. Can somebody point me in the right direction?

# Answer
> 4 votes
It's false. Let $L\_1=\Sigma^\*$ be a decidable language and $L\_2=L\_{HALT}$ be the (recognizable) language of all halting TM-string pairs. Then $L\_1\cap L\_2=L\_2$, which is not decidable.

---
Tags: computability
---


# Question
Title: How to come up with a language that is recognizable but not co-recognizable?
Forming a language that is recognizable but not co-recognizable. I'm having trouble coming up with a language with these properties. A recognizable language is a language $A \subseteq \Sigma^\*$ iff $A = L(M)$ for some Turing machine $M$.

Co-recognizable is the exact same except the complement of $A$ has to be recognizable.

My question is how do I come up with a language that I know will be recognizable but not co-recognizable?

# Answer
Remember that there are three things a Turing machine can do, given an input. It can:

* Accept
* Reject
* Diverge (infinite-loop)

"Recognizable" means "we can accept on strings in our language, and reject-or-diverge on anything else". "Co-recognizable" means "we can reject-or-diverge on strings in our language, and accept on anything else". Or, equivalently, "we can accept-or-diverge on strings in our language, and reject on anything else".

So the key is, intuitively, to find a language so that a TM *always diverges on (some) strings not in the language*.

A classic example is the Halting Problem. (To be more specific, the set of encoded Turing machines that halt on empty input, for a given encoding.) You can recognize this language by simulating the machine, then accepting. But you can't recognize its opposite.

(Formally, you have to do a bit more work. You have to prove that the language is undecidable: that *no* Turing machine can always say "no" correctly, even if it can always say "yes" correctly. Usually this means reduction to the Halting Problem or Rice's Theorem.)
> 1 votes

---
Tags: turing-machines, church-turing-thesis
---


# Question
Title: Basic Question in networking - why max data size of ip datagram 65535 BYTES and not 65535 bits?
I recently started computer networks with some understanding of algorithms and discrete mathematics. I am completely new. Kindly elaborate following -

data size of ip datagram = 16bits. So with this $2^{16} -1 = 65536$ 16 bit patterns can be generated. My doubt:

1. Do we say each 16 bit pattern is 1 IP datagram or all those 65536 patterns as 1 IP Datagram?
2. If i consider all 65536 patterns as max data size, then max ip datagram size $= 65536$ patterns size$ = 65536\*16 $ bits $= 65536\*16/8$ bytes $= 65536\*2$ bytes

# Answer
16 bits is not the *size* of the IP datagram; it is the amount of bits required to *encode its length*. Hence, you can have datagrams of length up to 65536 octets (i.e., bytes), as described in RFC 760:

> Total Length: 16 bits

> Total Length is the length of the datagram, measured in octets, including internet header and data. This field allows the length of a datagram to be up to 65,535 octets.

Notice 65536 is not a prescribed length, that is, the length of the datagram is (or can be) *variable*.

---

Now, to answer your two questions:

> Do we say each 16 bit pattern is 1 IP datagram or all those 65536 patterns as 1 IP Datagram?

Each octet pattern of up to 16-bit length is a datagram. In informal parlance, a datagram is simply a packet which IP adds its header to. You could call the set of all possible patterns a "datagram space", though I doubt that's standard terminology. (You might care to ask that in a separate question.)

> If i consider all 65536 patterns as max data size, then max ip datagram size =65536 patterns size=65536∗16 bits =65536∗16/8 bytes =65536∗2 bytes

I'm not sure I see a question here. Though I suppose any one you had is answered by my remark about the datagram length above.
> 3 votes

---
Tags: computer-networks, communication-protocols, ip
---


title: Ternary processing instead of Binary

text:
# Question
Title: Ternary processing instead of Binary
Most of the computers available today are designed to work with binary system. It comes from the fact that information comes in two natural form, **true** or **false**.

We humans accept another form of information called "maybe" :)

I know there are ternary processing computers but not much information about them.

1. What is the **advantages** / **disadvantages** of designing and using ternary or higher levels of data signals in computers?
2. Is it feasible?
3. In which domain can it be better than classic binary systems?
4. Can we give computers the chance to make mistakes and expect to see performance improvements in most situations by this way? (I think performance gains can be observed if computers are not so strict about being absolutely correct)

**EDIT:** Are there difficulties differentiating between 3 levels of signal? Would it be too hard to keep data in memory since memory voltage is frequently released and loaded, (maybe hundreds of time a second?).

# Answer
> 8 votes
> Are there difficulties differentiating between 3 levels of signal?

That's more electronic than computer science (and the issue could be different with other technology). The 2 levels signals we use are generated by putting transistors in a saturation state(\*). They behave like switches and the whole technology is driven to optimize this behavior(+). Even without considering that historical skew, generating an intermediate level at a fixed value is more difficult than using saturation, will consume more power (a big part of the power is currently consumed in the transition between saturating state, you will need to stay in that mode where power leaks a lot), reduce the resistance to noise (can be reduced by increasing the supply voltage and thus the power consumption) leading to reduced fabrication yield.

(\*) Historically, there has been computer working with transistor in a non saturated state. There is a speed advantage to that. Power consumption (and needs for dissipation) killed the practice.

(+) Analog circuits are made with different processes which are deemed unsuitable for large digital circuits and even small one which don't need an analog part.

# Answer
> 6 votes
A ternary hardware system could about something else than $\\{\mbox{yes},\mbox{no},\mbox{maybe}\\}$ but using arbitrary $\\{0,1,2\\}$ or $\\{0,1,-1\\}$. The main inconvenient about such a thing is that the cost of reading a ternary digit is way bigger than for a bit for the same risk of error. (Bigger enough to be less efficient than using two bits to encode a ternary digit.) Therefore such systems would not provide any improvement *as is*. In particular I really doubt a ternary system would lead to a more compact representation.

However in the redundant binary representation, $\\{0,1,-1\\}$ is used to improve performances on operations on big integers, making them highly parallelizable because of a way less demanding carry mechanism (the most significant bit of the result does not depend on the least significant bits of the operands).

Side note: if you talk about the meaning of $\\{\mbox{yes},\mbox{no},\mbox{maybe}\\}$ as a logical thing, you might be interested in fuzzy logic. (You probably already have seen three-valued logic).

# Answer
> 5 votes
There is some information in the article "Ternary computer" on Wikipedia. To address some of your specific questions:

* Feasibility: Yes.
* Memory: Can be implemented via a Josephson junction.
* Advantages: Higher density of information per bit can lead to more compact data representations.

# Answer
> 3 votes
There is one usage of a ternary alphabet $\\{\mbox{yes}, \mbox{no}, \mbox{maybe}\\}$. In signal transferring you can use $\mbox{maybe}$ result of the transfer to increase the capacity of an information channel.

The channel where you have a probability $\alpha$ that $\mbox{yes}\rightarrow\mbox{no}$ or $\mbox{no}\rightarrow\mbox{yes}$ has much lower capacity per bit than a channel where the transitions are $\mbox{yes}\rightarrow\mbox{maybe}$ or $\mbox{no}\rightarrow\mbox{maybe}$. The capacities are $1-\mathcal O(\alpha)$ compared to much better $1-\mathcal O(\alpha^2)$.

# Answer
> 3 votes
Knuth considered this idea in V1 of TAoCP. He observed that we would need a new device to replace the flip-flop, and he proposed calling it the **flip-flap-flop**. Was he serious? Well, Knuth has quite a sense of humor.

But it looks like somebody has implemented the flip-flap-flop with 3 NOR gates, which is not that big a deal. So it doesn't require any new technology, but without new hardware it is also not any more compact than the flip-flop, requiring the same density of circuits on an information-theoretic basis.

Of course, there's always Muppet technology.

# Answer
> 1 votes
This article demonstrates the efficiency of various bases for numbering. Base 3 is more efficient in terms of the actual number of characters needed to express any given number on average. So a computer that uses a trinary system to represent integers will be more efficient on average than a binary computer, if it is used to express a wide enough range of number.

Interestingly, the most efficient number out of all of them is `e`.

# Answer
> 0 votes
In a web book about multi value switches, peter lablans states that N.value transistor switches create truth tables, which are mostly useful for scrambling and descrambling data.

Recently quantum dots have been integrated into amorphous zinc oxide gates (zinc being a non oxidizing metal?!) To make silicon ready 3/4 state switches for current CPUs, and its promoted as a quantum interface, not as an efficient logic process. https://lemmatalogic.com/multivaluedlogic/images/

He has a vb program here https://lemmatalogic.com/multivaluedlogic/#scr

\]

---
Tags: computer-architecture
---


# Question
Title: Graph ordering with smallest max vertex "discrepancy"
Consider an undirected graph $G=(V,E)$ and a bijective function $f:V \rightarrow \[|V|\]$ which orders the vertices by mapping them onto the first $|V|$ natural numbers.

Define the cost of an ordering of a graph to be:

$$\text{cost}(G,f) = \max\_{(u,v) \in E} f(u)-f(v)$$

(I refer to $f(u) - f(v)$ in the title as "discrepancy" to avoid confusion with terms such as length or distance)

Intuitively, if we were to construct $G$ by adding on one vertex at a time and adding the appropriate edges to the already-existing vertices, the cost is how far back in our list of vertices we'd have to go and add edges to.

Question: How difficult is the problem of minimizing this cost? Is there an efficient algorithm for finding an optimal ordering? Also is there a name for this cost that i'm not aware of?

Ideas:

A BFS ordering can do arbitrarily bad on this problem: Consider a complete binary tree -- the optimal cost is $O(\log N)$ but a BFS ordering can cost up to $O(N)$.

A DFS ordering can do arbitrarily bad on this problem: Consider a path graph modified such that each vertex is connected to an additional leaf vertex -- the optimal cost is $2$ but a DFS ordering can cost up to $O(N)$.

# Answer
Your problem is known as BANDWIDTH. Another way to describe it is: we are given a matrix, and we want to rearrange the rows and columns (in the same way!) so that the only non-zero entries lie across a narrow band around the diagonal.

BANDWIDTH is known to be NP-complete. Unger showed that it is NP-hard to approximate to within any constant factor. Feige gave an $\tilde{O}(\log^3 n)$-approximation algorithm which uses metric embeddings.

Among the many variants of BANDWIDTH, let me mention the MINIMAL LINEAR ARRANGEMENT problem (known by various other names), in which the goal is to minimize $\displaystyle\sum\_{(u,v) \in E} |f(u)-f(v)|$ rather than $\displaystyle\max\_{(u,v) \in E} |f(u)-f(v)|$.
> 4 votes

---
Tags: graphs, time-complexity
---


# Question
Title: Space complexity of breadth-first search
I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$ nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor.

Why isn't it $b^d$?

Why are $1+b+b^2+···+b^{d-1}$ (the previously searched depths) maintained in memory?

If it's a matter of completeness, then (a complete implementation of) DFS would suffer from the same problem.

# Answer
> 1 votes
That's not entirely correct Tobi. Breadth-First search requires to store in memory only those nodes awaiting for expansion. Thus, it only requires to store in memory $b^d$ nodes in the worst case, i.e., if the solution is found at the rightmost child at depth $d$. That is the number of nodes required to be stored in memory because when the solution is found at depth $d$, that is precisely the number of nodes awaiting for expansion.

Indeed! You could actually remove any node after expanding it. So far, you are correct when you are guessing that you could actually remove all nodes expanded in the previous depths whose sum gets so far as $b^0+b^1+b^2+b^3+...+b^{d-1}$. Now, here comes the question:

1. Why would you do it? Why would you actually remove those nodes? If you do not remove them, you could easily implement a *duplicate detection* mechanism: if a node $n$ is found at depth $d\_1$ it is stored in memory. If it is found again at depth $d\_2$, $d\_2\>d\_1$ then its expansion can be skipped because a shortest path to it was already found ---given that the edge costs are all the same.
2. Oh yeah! you might be thinking that this idea is not worthy as it requires to store in memory a rather large number of nodes: $b^0+b^1+b^2+...b^{d-1}$, isn't it? So that while *duplicate detection* seems desirable it might be too costly.

Note however that the sum of the terms of the geometric progression $b^0+b^1+b^2+...+b^{d-1}$ equals $\frac{b^d-1}{b-1}$ so that adding *duplicate detection* requires only a small fraction ($b-1$) of the nodes actually required to be stored in memory ($b^d$).

In other words, we say that the memory requirements of Breadth-First Search are *dominated* by the number of nodes awaiting to be expanded, $b^d$. Additional memory can be used as the total number of nodes in memory, $b^d+\frac{b^d-1}{b-1}=\frac{b^{d+1}-1}{b-1}$ (in case that *duplicate detection* is implemented), is much smaller than the number of nodes required to store the nodes in the subsequent level, $b^{d+1}$.

Test these numbers, even if $b=2$, note that with duplicate detection, the number of nodes in memory is $2^{d+1}-1$ which is smaller than $2^{d+1}$, the number of nodes required to store in memory for exploring an additional level **without** duplicate detection. The situation worsens significantly if you consider larger branching factors. For example, with $b=10$, the number of nodes required **with** duplicate detection is $\frac{10^{d+1}-1}{9}$, which is only 11% of the nodes required to be stored in memory for exploring the subsequent depth **without** duplicate detection, $10^{d+1}$ ...

Hope this helps,

---
Tags: complexity-theory, search-algorithms, search-trees, memory-management
---


title: Regularity of infinite concatenation

text:
# Question
Title: Regularity of infinite concatenation
It is well-known that an infinite union of regular languages is not necessarily regular, since *every* language can be written as a union of singletons. What about infinite concatenations?

Let $\\{ L\_z : z \in \mathbb{Z} \\}$ be a family of languages, cofinitely many of which contain $\epsilon$. We can define the infinite concatenation of the family as the collection of all words of the form $w\_{i\_1} \ldots w\_{i\_n}$, where $i\_1 \< \cdots \< i\_n$ and $w\_{i\_j} \in L\_{i\_j}$. (The definition makes sense if we replace $\mathbb{Z}$ with any linear order.)

> Is the infinite concatenation of a family of regular languages necessarily regular?

# Answer
> 2 votes
The answer is negative. Let $L\_n = \\{\epsilon, a^{3^n}\\}$ for $n \geq 0$, and let $L\_n = \\{\epsilon\\}$ for $n \< 0$. The infinite concatenation of the collection $\\{ L\_n : n \in \mathbb{Z} \\}$ is $$ L = \\{ a^m : \text{$m$ is the sum of distinct powers of $3$} \\}. $$ Since $L$ is unary, in order to show that $L$ is not regular, we need to show that the set $S = \\{ m : \text{$m$ is the sum of distinct powers of $3$} \\}$ is not eventually periodic. We can see this in many ways. For example, $S$ is infinite but has density $0$ in the limit.

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


# Question
Title: Construction of a Deterministic Tree Automaton (DTA)
Let $L \subseteq \Sigma^\*$ be a regular language. Let $\Sigma' = \Sigma\_0 \cup \Sigma\_2$ where $\Sigma\_0 =\Sigma$ and $\Sigma\_2=\\{\*\\}$.

We define $T\_L=\\{t \in t\_{\Sigma'} \mid \text{The leafs from t are from a word in $L$}\\}$ as a tree language.

The task is to construct a DTA for $T\_L$.

A DTA A over $\Sigma = \Sigma\_0 \cup \cdots \cup \Sigma\_m $ is a four tuple with $A= (Q,\Sigma, \delta, F)$ where Q is a finite state set, F final state set, and $\delta : \bigcup \_{i=0}^m(Q^i \times \Sigma\_i)\rightarrow Q$ and $Q^0 \times \Sigma\_0 = \Sigma\_0$.

My idea was to set $\Sigma \_0 \subseteq L \subseteq \Sigma^\*$. But how can the transition function check whether it is a word in L?

# Answer
> 0 votes
Your model is a bottom-up tree automaton. Let $P$ be the set of states of the finite state automaton for regular $L$. Now a state of the tree automaton at a vertex $v$ of the tree contains *all* $P \times P$ pairs $(p,q)$ such that there is a path from $p$ to $q$ on the string specified by the leaves under $v$. This can be deterministically evaluated in a bottom-up fashion.

More precisely, with every vertex $v$ we associate a binary relation $R(v)$ over $P$, thus $R(v) \subseteq P\times P$. Thus $(p,q)\in R(v)$ iff there is a path from $p$ to $q$ on the leaves under $v$.

For a leaf $v$ labelled $a\in \Sigma$ this means that $R(v) = \\{(p,q)\mid (p,a,q) \in \delta\\}$, where $\delta$ is the transition relation of the automaton for $L$.

If $u$ is a binary vertex (labelled by $\*$) with children $v,w$, then the relation $R(u)$ is the compostition of $R(v)$ and $R(w)$.

We accept at the root $r$ if $R(r)$ contains an accepting pair $(p,q)$ where $p$ is the initial state and $q$ is final.

---
Tags: regular-languages, finite-automata, trees, tree-automata
---


# Question
Title: What algorithm will tell us how to divide-up a round robin tournament into rounds?
We are designing a tournament for a game such as soccer (football) or chess. The tournament is "round robin." By "round robin," we mean that every team gets to play against each other team exactly once. For example, if you are playing, and there are 8 other teams, then you will play exactly 8 matches before the tournament is over.

A single "match" is played with 2 teams competing against each other. For example, (team 3 against team 9) is a single match. Formally, a match is a set of two integers, such as {3, 9}.

The tournament is divided into rounds. All teams who are scheduled to play during the current round play simultaneously. If team 2 is playing team 5 during round 10, then team 2 cannot simultaneously play against team 3 during the same round. In different notation, if {2, 5} ∈ R10 then {2, 3} ∉ R10. In general, no round is allowed to contain the same team more than once.

Formally, a round is a set of matches. For example, $R = \\{\\{1, 2\\}, \\{3, 5\\}, \\{4, 6\\}\\}$ is a round. A valid round $R$ is a round such that for every two distinct matches, M1 and M2, in $R$, $M1$$M2$ is the empty set. This captures the idea that no round is allowed to contain the same team more than once.

For some natural number, $n$, the tournament has:

* $2\*n$ teams
* $(2\*n-1)$ rounds
* $n$ matches per round.

The algorithm we seek, for any even number of teams, will output a a description of which matches to have in each round.

For example, for 6 teams, the algorithm output might be:

```
round 1: {1, 2}, {3, 5}, {4, 6}
round 2: {1, 3}, {2, 4}, {5, 6}
round 3: {1, 4}, {2, 5}, {3, 6}
round 4: {1, 5}, {2, 6}, {3, 4}
round 5: {1, 6}, {2, 3}, {4, 5}

```

Note that every team plays at most once per round, and that every team plays every opposing team exactly once before the tournament is over.

# Answer
You want the algorithm for constructing a Graeco-Latin square, or any of the algorithms described in https://en.wikipedia.org/wiki/Round-robin\_tournament#Scheduling\_algorithm
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Lower Bound for Time Complexity of Pairing Problem
Given an array X and array Y both of length n, the pairing algorithm will return the elements of the arrays matched so that the smallest element in X will be matched with the smallest element of Y, the second smallest in X matched with second smallest in Y and so on. i.e the algorithm will yield the pairs: $(x\_{1},y\_{1}),...,(x\_{i},y\_{i}),...,(x\_{n},y\_{n})$, $x\_{i}$ being the i'th smallest element in X.
I need to find the lower bound for the time complexity of the problem.

I think the lower bound is O(n) because when the two arrays are sorted we only need to match the elements with the same index in each array - so we'll need to go over n indices = O(n). But this just proves the existence of the possible time complexity of O(n) and doesn't prove it's the minimum.

Is O(n) the lower bound? And if so what is the proof?

# Answer
This answer uses the convention that the elements of $X$ are $x\_1,\ldots,x\_n$ (in their original, unsorted order), and similarly the elements of $Y$ are $y\_1,\ldots,y\_n$. This differs from your convention.

---

The complexity of this problem in the comparison model (as well as in related models, such as bounded degree algebraic decision trees) is $\Theta(n\log n)$.

For the upper bound, we can solve the problem by sorting both lists.

For the lower bound, if we fix the second array to be $y\_i = i$, then we are essentially sorting the first array $X$. Stated differently, there is a reduction from sorting to this problem, with the same value of $n$ and no extra comparisons. Since sorting takes $\Omega(n\log n)$ comparisons in the worst case, this problem also requires $\Omega(n\log n)$ comparisons.

---

So far we have only discussed worst-case complexity, and the same argument also works for average-case complexity. The *best-case* complexity is $\Theta(n)$. This means that we can find a correct algorithm that runs in time $O(n)$ on some input; and every correct algorithm requires $\Omega(n)$ comparisons on *every* input.

For the upper bound, consider the algorithm that first checks whether both $X$ and $Y$ are increasing ($2(n-1)$ comparisons). If so, it returns the mapping $(x\_i,y\_i)$. Otherwise, it transfers control to an arbitrary correct algorithm.

The lower bound follows from the same reduction from sorting, since sorting is known to require at least $n-1$ comparisons on *any* input. Indeed, the same argument used to prove this shows that any algorithm for the pairing problem requires $2(n-1)$ comparisons on *any* input.
> 1 votes

---
Tags: time-complexity, sorting, lower-bounds, selection-problem
---


# Question
Title: Computing the closest point inside an intersection of half-spaces
Is there an efficient way to compute, given a point, the closest point to it that's on the inside of an intersection of half-spaces?

For example, given the half-spaces `a` & `b`, the closest point to `p` that's "inside" the half-spaces is `x`. `+` denotes which side is "inside" the half-spaces `a` and `b`.

```
.p
       ^
       |
       |
       | x
   <---.--------------> b
       |       +
       |
       | +
       |
       v a

```

I'm particularly interested in an algorithm for half-spaces in 3D (planes)

My current line of thinking leads me to have to compute intersections of each half space, and then find the shortest point by picking from the shortest distance to each half-space and each intersection (line, point) that's within all the half-spaces. Is there a better way?

# Answer
This can be modeled as a convex program $$\begin{align} \text{min.} \qquad & ||x-p||\_2^2,\\ \text{s.t.} \qquad & Ax\leq b,\\ & x\in\mathbb{R}^3. \end{align}$$ and solved (in reasonable time) by standard solvers. Here's example code in julia

```
using Convex, SCS

# generate random problem data
m = 5;  n = 3
A = randn(m,n); b = randn(m,1); p=randn(3,1)

# define problem
x = Variable(n)
problem = minimize(sumsquares(x-p), [A*x<=b])

# solve
solve!(problem, SCSSolver())
println("Status $(problem.status) distance $(problem.optval)")

```
> 2 votes

---
Tags: algorithms
---


# Question
Title: solving the recurrence t(n)=t(n-2)+d*(n^2)/2 with iteration method
How can I solve $$T(n)=T(n-2)+\frac {d}{2}n^2$$ I couldnt find $d$ (dont know if I have to) and after 3 iterations I got to $k= \frac{n-1}{2}$ but had trouble to continue.

# Answer
> 3 votes
This answer assumes that $T(1) = \frac{d}{2}$

---

Your recurrence relation, in closed form, would be:

\begin{align} T(n) & = \frac{d}{2} n^2 + \frac{d}{2} (n-2)^2 + \frac{d}{2} (n-4)^2 + \dots + \frac{d}{2}\\ & = \sum\_{i=0}^\frac{n-1}{2} \frac{d}{2}(n-2i)^2\\ \end{align}

Which, with little effort, can be simplified further:

$$\dots = \frac{d}{2} \sum\_{i=0}^\frac{n-1}{2}n^2-4ni+4i^2 = \frac{dn^2}{4}(n-1) -2dn\sum\_{i=0}^\frac{n-1}{2}i +2d\sum\_{i=0}^\frac{n-1}{2}i^2$$

For further simplification, you can use the facts that:

$$\sum\_{i=1}^n i=\frac{n(n+1)}{2}$$

$$\sum\_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$$

But I'll leave that to you.

---
Tags: recurrence-relation
---


# Question
Title: Do height-balanced binary trees have logarithmic depth?
A family of binary trees is called balanced if for every tree $t$ in the family the height of $t$ is $O( \log n)$.

Given a family of trees such that for every tree $t$ in the family, for every node $v$ in $t$, the height difference between the right subtree of $v$ and the left subtree of $v$ is at most $c$, where $c$ is some constant.

I understand this claim is true. It is the general case for AVL trees. I just don't know how to prove it formally.

# Answer
> 4 votes
Let us denote by $N\_h$ the minimum number of leaves of a tree in your family of height $h$. Clearly $N\_0 = 1$, and $$ N\_h = N\_{h-1} + \min\_{0 \leq d \leq c} N\_{h-1-d}. $$ (Here $N\_h = 0$ if $h \< 0$.) You can prove inductively that $N\_h$ is monotone, and so for $h \geq c+1$, $$ N\_h = N\_{h-1} + N\_{h-1-c}. $$ This is a recurrence relation whose solution is $N\_h = \Theta(\alpha^h)$, where $\alpha$ is the maximal real root of $x^{c+1} - x^c - 1= 0$; for example, when $c = 1$, $x$ is the golden ratio.

Since the number of leaves in a tree of height $h$ is $\Omega(\alpha^h)$, it follows that a tree containing $n$ leaves has height $O(\log n)$.

# Answer
> 1 votes
Let $T\_h$ be any tree that satisfies your property and has height at least $h$. Let $|T\_h|$ be the number of its nodes.

For $0 \le h \le c$, $|T\_h| \ge 1$. For $h \> c \cdot i$, with $i \in \mathbb{N}^+$, you have: $$ |T\_h| \ge 1 + | T\_{c \cdot i} | + | T\_{ c \cdot (i-1)}| \ge 2 | T'\_{ c \cdot (i-1)}|, $$ where $T\_{c \cdot i}$, $T\_{ c \cdot (i-1)}$, and $T'\_{ c \cdot (i-1)}$ are trees of height at least $c \cdot i$, $ c \cdot (i-1)$, and $ c \cdot (i-1)$, respectively, that also satisfy your property.

Let $T$ be a tree of height $H$ from your family. From the above observations (choosing $h=H$) it follows that $|T| \ge 2^{\left\lfloor \frac{H}{c+1} \right\rfloor} \ge 2^{\frac{H}{c+1} - 1}$, or equivalently, $H \le (c+1)( 1+ \log |T|) = O(\log |T|)$.

# Answer
> 0 votes
Thanks everyone for the answers. Finally I decided to take the proof of AVL tree has a height of O (log n ) and implenent the recurrence with the constant c. Basically Avl is a special case of this claim so taking the proof of AVL using the same idea led me to the proof. Instead of N(h) = N (h-1) + N (h-2) + 1 I used N(h) = N ( h -1) + N ( h - 1 - c) + 1

---
Tags: data-structures, binary-trees
---


# Question
Title: What are examples of applications of the tree decomposition of a graph?
I am looking for *specific* applications of the tree decomposition (of a graph), because I want to motivate its existence. What are examples of problems that are more easily solvable using the junction tree of a graph (rather than tackling the problem directly on the graph)? Please, provide also the references to the papers or books that mention these specific applications.

# Answer
> 1 votes
An example of an application of the junction tree (or tree decomposition) of graph is described in the paper Junction Tree Variational Autoencoder for Molecular Graph Generation (2019), by Wengong Jin, Regina Barzilay and Tommi Jaakkola.

---
Tags: graphs, trees, applications
---


# Question
Title: Compute cache miss rate for the given code
**Problem Description:**

We consider a 128-byte data cache that is 2-way associative ($E=2$) and can hold 4 doubles in every cache line. A double is assumed to require 8 bytes.

For the below code we assume a cold cache. Further, we consider an array A of 32 doubles that are cache aligned (that is, $A\[0\]$ is loaded into the first slot of a cache line in the first set). All other variables are held in registers. The code is parameterized by positive integers $m$ and $n$ that satisfy $m\*n = 32$ (i.e., if you know one you know the other). Recall that the miss rate is defined as $\frac{\text{number of misses}}{\text{number of accesses}}.$

```
// Code:
float A[32], t = 0;
for(int i = 0; i < m; i++)
  for(int j = 0; j < n; j++)
      t += A[j*m + i];

```

**Problem:** Determine the miss rate for when $m=1,2$ and $16.$

**My Attempt:**

When $m=1$ we access the elements, $$A\[0\],A\[1\],A\[2\],\cdots,A\[31\]$$ and since each block in the cache can hold $2$ doubles, this means that for every miss we get one hit and so the miss rate is $1/2.$

When $m=2$ we access the elements, $$A\[0\],A\[2\],A\[4\],\cdots,A\[30\].$$ Here we first miss $A\[0\]$ but then we load the block with $(A\[0\],A\[1\]).$ However, this does not help since we need to access $A\[2\]$ and therefore we miss every time and thus the miss rate is $1.$

When $m=16$ we access the elements, $$A\[0\],A\[1\],A\[2\],\cdots,A\[31\].$$ And so like before this should have a miss rate of $1/2.$

However, the answers are: $$m=1, \text{miss rate} = 1/4$$ $$m=2, \text{miss rate} = 1/2$$ $$m=16, \text{miss rate} = 1/4.$$

I am not sure how to obtain these answers and so any help will be much appreciated.

# Answer
As the cache is 4 doubles, for m=1, after accessing A\[0\], there are in the cache A\[0\]...A\[3\]. So next access A\[1\] is a hit and it is the same for A\[2\] and A\[3\]. Only access A\[4\] will be a miss. Hence miss rate is 0.25

For m=2, After accessing A\[0\], the cache holds the same line. Next access is A\[2\] which is a hit, and A\[4\] is a miss and so on. So miss rate is 0.5. Note that total cache size is 8 doubles. So when accessing A\[8\], cache line 0 is cleared and when A\[1\] will be accessed on later iterations, it will be again a miss.

For m=16 and n=2, one needs to look closely at the access patterns. Also do not forget that the cache is associative with two lines.

iteration 1 i=0, j=0 -\> A\[0\] miss in line 0
iteration 2 i=0, j=1 16j+i -\> A\[16\] miss in line 1
iteration 3 i=1, j=0 16j+i -\> A\[1\] hit in line 0 (because cache is 2 ways associative)
iteration 4 i=1, j=1 16j+i -\> A\[17\] hit in line 1

and all access will be hits until iteration 8 (i=4, j=0). In that case, we access A\[4\] that isn't in any cache and we restart a new cycle. So we have 2 misses for 8 iteations and miss rate is 0.25
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Transitive Closure vs Reachability in Graphs
I am facing the most curious situation with \[my current information of\] transitive closure algorithms. Specifically, is what follows not an algorithm for finding the transitive closure of a graph `G(V, E)` and is the time complexity not `O(|V|+|E|)`:

> Use Kosaraju's to compute SCCs (strongly connected components) -- O(|V| + |E|)
>
> Create a DAG from the SCCs as (super)nodes -- O(|V| + |E|)
>
> In a single supernode, reachability of all nodes is the same and equal to the union of the nodes in the containing supernode plus the reachable supernodes in the DAG -- O(|V| + |E|) to compute reachability in the DAG and O(|V| * |V|) total to compute reachability sets for all nodes

These reachability sets *do* constitute the transitive closure of the graph wholly, right?
**But there aren't any `O(|V| + |E|)` transitive closure algorithms around.**
What am I missing?

# Answer
Your algorithm is known as Purdom's algorithm. There are two versions of transitive closure:

* Calculate the transitive closure as a relation. This cannot run in time $O(|V|+|E|)$, since the output could be bigger than that (consider a directed path, for example).
* Calculate enough information to be able to answer oracle queries to the transitive closure in $O(1)$. Even in this case, the algorithm doesn't seem to run in time $O(|V|+|E|)$. Hopefully the link would make it clear why.
> 2 votes

---
Tags: graphs
---


# Question
Title: What are elementary operations in time complexity definition?
Wikipedia gives us the following defintion of time complexity:

> "In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform."

Now what are these elementary operations ? Are they arithmetic operations or some simpler operations ?
Thanks in advance!

# Answer
The set of elementary operations and their cost constitute a *model of computation*. The most common model of computation used to analyze algorithms is the Random access machine. Briefly, memory is divided into words of size $O(\log n)$ bits, where $n$ is the size of the input to the algorithm. A program consists of a sequence of instructions. The exact set of instructions isn't really set in stone, but usually includes arithmetic instructions (addition, subtraction, multiplication, division with remainder), possibly bitwise instructions, memory dereferencing, control flow, and so on. In the *unit cost RAM*, the most common model, each instruction operations on a single word, and costs one unit of time.

Other relatively common models of computation include various models of Turing machine, the bit complexity model (in which words consist of a single bit), and logarithmic cost RAM.
> 4 votes

---
Tags: time-complexity
---


# Question
Title: Prove propositional formula is a tautology
I need to show this formula is a theorem of propositional calculus. I tried assuming antecedent and proving consequent but didn't work for this proof. Do I need to show it is equivalent to true? How should I start? It's not possible to use truth tables.

$(p \rightarrow q) \rightarrow (p \wedge r \rightarrow q \wedge r)$

Background:

In my class, there is no mention to it but I think this form of logic it's called Equational Logic. Probably, it's based on this book: A Logical Approach to Discrete Math by David Gries

EDIT: I was asked to provide more details on the type of proof needed. In my class, I am not allowed to use truth tables to prove this proposition. This is an example:

# Answer
> 1 votes
Here is what the formula states:

> If $p$ implies $q$, then $p$ and $r$ imply $q$ and $r$.

To prove this, you would like to argue as follows. Assume $p$ implies $q$, and suppose that both $p$ and $r$ hold. Since $p$ implies $q$, then $q$ holds. Hence both $q$ and $r$ hold.

How exactly this proof is expressed depends on your proof system.

# Answer
> 0 votes
This is a special case of the more general theorem

$((a \rightarrow b) \land (c \rightarrow d)) \rightarrow ((a \land c) \rightarrow (b \land d)$

You may find it easier to prove the general theorem first, then prove the special case by setting $a=p, \space b=q, \space c=d=r$.

---
Tags: logic
---


# Question
Title: Examples for Partial Combinatory Algebras
I am currently working on my Bachelor thesis about Turing Categories (see *Introduction to Turing Categories* \[\]). In this context I got some questions regarding Partial Combinatory Algebras (PCAs), which I want to get out here, as neither of my supervisors could help me.

1. In *Total Maps of Turing Categories* \[\] necessary and sufficient conditions for a category to appear as subcategory of total maps of some Turing category are given. As a corollary, the category of PTIME-functions, LOGSPACE-functions, LTIME-functions etc. can appear as total maps of some Turing category. Does this imply that these classes can be characterized by a specific PCA and (if so) how does it relate to Kleene's first model? In other words, are there complexity classes which can be represented by sub-PCAs of Kleene's first model?
2. Are there models of PCAs which are not a priori inspired by computability theory? The general setting of applicative system and computable function (see \[\] section 4) seems to be rather general such that it may be applicable in general categories. However all my attempts to find a PCA in categories like Top, K-Vec, R-Alg, R-Mod etc. have failed. I am well aware of Kleene's second model, Scott's graph model and the $\lambda$-calculus as they are stated in *Realizability - An Introduction to its Categorical Side* \[\]. I am just curious whether this notion of computability naturally arises anywhere else in ordinary mathematics...

I hope anybody can help me out. No matter what, thank you all for your time.

# Answer
Consider a subPCA $A$ of Kleene's first algebra. It contains $K$ and $S$. These are sufficient to implement every total computable function, so $A$ must contain at least these, and cannot be just some limited complexity class.

I do not quite understand why Kleene's second algebra and Scott's graph model aren't "topological". Kleene's second algebra is the universal 0-dimensional countably based Hausdorff space. Scott's graph model is the universal $T\_0$ countably based space. These characterizations have no trace of computability, but because the spaces are *universal* it is to be expected that they have a very rich structure, and so can be made into models of $\lambda$-calculus.
> 3 votes

---
Tags: complexity-theory, computability, reference-request, logic
---


# Question
Title: Why is the usual simulated annealing algorithm using a Boltzmann probability?
I've coded a personal version for the simulated annealing problem, and I was wondering why, (other than by analogy to the physics), the probability is $$ p = e^{-\dfrac{\Delta \text{length}}{T}}$$ (assuming we're applying to the TSP problem, so the parameter is here the length of the circuit).

Is there any way to explain why this law and not another? Is this one optimal?

# Answer
This formula can more insightfully be written as

$$ p = \frac{1}{e^{\dfrac{\Delta E}{T}}}$$

where, in the context of SA, $\Delta E$ is the difference between the "energy" (or quality) of two possible solutions and $T$ is the temperature (which is either a constant or a function of the input size).

So, the higher the energy difference $\Delta E$, the smaller the probability $p$. In the context of SA, if the cost of the current solution is greater than the cost of the new solution, then you replace the current solution with the new solution. However, if the cost of the current solution is smaller than the new solution, then you do not automatically discard the new solution. More concretely, with probability $p$, you accept the new worse solution. This the stochastic action taken by SA. So, the higher the diffence between the costs of the current and new solutions, the smaller the probability of accepting the new worse solution.

The Boltzman distribution only happens to capture this idea of accepting new worse solutions, provided that they are not extremely worse than the current solution. In theory, you can use other (similar) distributions.
> 1 votes

---
Tags: algorithms, optimization, heuristics, simulated-annealing
---


# Question
Title: CFG for all strings of a’s and b’s that contain a different number of a’s and b’s
I am trying to write CFG for all strings on {a,b} that contains different numbers of a’s and b’s? After two hours of brainstorming, I came up with this:

S→A|B
A→aE|aA|EA
B→bE|bB|EB
E→aEbE|bEaE|Λ

I tried running few strings on this, it worked, But then I run string **"abbab"** and it failed.
Kindly someone point out at my mistake or tell me the correct CFG for this as I don't know how to correct this.

# Answer
In fact, your grammar is correct and clean!

Here is how your grammar generates $abbab$.

$$S\Rightarrow B\Rightarrow EB\Rightarrow^\* abB \Rightarrow abbE\Rightarrow^\* abbab $$

**Exercise.** Show your grammar is correct.
> 2 votes

# Answer
Here is a (hopefully) more principled approach. Let us start with a grammar for the language of all strings containing the *same* number of $a$'s and $b$'s ("balanced"). We can identify such strings as walks in which $a$ gets translated to $\nearrow$ and $b$ gets translated to $\searrow$. We concatenate these arrows horizontally. For example, $aabbab$ is the walk $$ \begin{array}{cccccc} & \nearrow & \searrow \\ \nearrow & & & \searrow & \nearrow & \searrow \end{array} $$

A walk is balanced if it ends up in the Y axis. For every such walk, one of the following cases must hold:

* The walk is empty.
* The walk reaches the Y axis at some point in the middle.
* The walk doesn't reach the Y axis at any point in the middle.

A walk of the second type is a concatenation of two balanced walks, and conversely, the concatenation of two balanced walks is balanced. A walk of the third type is of the form $\nearrow W \searrow$ or $\searrow W \nearrow$, where $W$ is a balanced walk, and conversely, walks of these forms are balanced. This shows that the following grammar generates all balanced walks: $$ W \to \epsilon \mid WW \mid aWb \mid bWa $$

What about unbalanced walks? We will consider walks with more $\nearrow$s than $\searrow$s. There are at least two ways of approaching this problem:

1. For each such walk, we can consider the last time that the walk reaches the origin. That part of the walk is balanced, and then we must have $\nearrow$, followed either by another balanced walk, or by another walk with more $\nearrow$s than $\searrow$s; and conversely, any walk of these two types is "$\nearrow$-unbalanced".
2. For each such walk, we can remove $\nearrow$s until we get a balanced walk. Conversely, starting with a balanced walk, if we add at least one $\nearrow$ anywhere, we get an $\nearrow$-unbalanced walk.

A grammar capturing the first type of structure is $$ A \to WaW \mid WaA $$ A grammar capturing the second type of structure is a bit more complicated to state. Let us start with a grammar for *at least as many $a$ as $b$s*: $$ A \to E \mid EAEAE \mid EaEAEbE \mid EbEAEaE \\ E \to aE \mid \epsilon $$ Here $E$ means "optional $a$s". In order to convert it to a grammar of *more $a$ than $b$s* we need to add a new symbol $A'$ which enforces adding at least one $a$: $$ A' \to aE \mid aEAEAE \mid EA'EAE \mid EAaEAE \mid EAEA'E \mid EAEAaE \mid \cdots $$ (We let the reader complete the definition.)

Summarizing, if we choose option 1, then we get the following grammar: $$ S \to A \mid B \\ A \to WaW \mid WaA \\ B \to WbW \mid WbB \\ W \to \epsilon \mid WW \mid aWb \mid bWa $$
> 2 votes

---
Tags: automata, context-free, strings
---


# Question
Title: concatenation of context sensitive and context-free is context sensitive or not?
Assume that $L\_1$ is context sensitive language and $L\_2$ is context free language, is the language $L\_1 * L\_2$ context-sensitive or not?

I almost sure that is not, but can't prove it.

# Answer
> 4 votes
Suppose that $L$ is a context-sensitive language which is not context-free. Then $L\\{\epsilon\\}$ is not context-free (here $\epsilon$ is the empty word), while $L\emptyset$ is context-free.

# Answer
> 2 votes
**Claim.** The concatenation of two context-sensitive languages is context-sensitive.

Since a context-free language is a context-sensitive language, the concatenation of a context-sensitive languages and a context-free language is context-sensitive.

---

Here is a simple proof of the claim by illustration.

Suppose $L\_1$ is given by the following context-sensitive grammar
$\quad S\to abc\mid aAbc$
$\quad Ab\to bA$
$\quad Ac\to Bbcc$
$\quad bB\to Bb$
$\quad aB\to aa\mid aaA$

Suppose $L\_2$ is given by the following context-sensitive grammar
$\quad S\to aSbS\mid \epsilon$

Then the concatenation $L\_1L\_2$ is given by the following context-sensitive grammar.
$\quad S\to S\_1S\_2$
$\quad S\_1\to abc\mid aAbc$
$\quad Ab\to bA$
$\quad Ac\to Bbcc$
$\quad bB\to Bb$
$\quad aB\to aa\mid aaA$
$\quad S\_2\to aS\_2bS\_2\mid \epsilon$

---

Here is a simple formal proof.

Suppose the context-sensitive grammar for language $L\_1$ is $(N, \Sigma, P, S)$, where $N$ is a set of nonterminal symbols, $\Sigma$ is a set of terminal symbols, $P$ is a set of context-sensitive production rules, and $S$ is the start symbol. Similarly, $L\_2$ is generated by $(M, \Sigma, Q, T)$. Since renaming the nonterminal symbols in a grammar does not change the language generated, we can assume that $N$ and $M$ are disjoint. Then $L\_1L\_2$ is generated by grammar $(N\cup M, \Sigma, P\cup Q\cup\\{X\to ST\\}, X)$, where $X$, a nonterminal symbol not in $N$ and $M$ is the start symbol. It is obvious that the production rules in $P\cup Q\cup\\{X\to ST\\}$ are context-sensitive.

---

**Exercise 1.** The concatenation of two context-free languages $L\_1$ and $L\_2$ is context-free.

**Exercise 2.** The concatenation of two regular languages $L\_1$ and $L\_2$ is regular.

# Answer
> 1 votes
Yes, the concatenation $L\_1\*L\_2$ is context sensitive in the given case (proof below). However, I am not sure if this is your question, or whether you want to know if $L\_1\*L\_2$ is **only** context sensitive (and not context free in general), or context sensitive **and** even contex free. The latter does not hold, see the answer by Yuval Filmus

Proof:

When $L\_1$ is context sensitive, then there is an LBA $M\_1$ that accepts $L\_1$. When $L\_2$ is context free, it is in particular context sensitive and there is also an LBA $M\_2$ that accepts $L\_2$.

Now build a new LBA $M\_{1\*2}$ that merges $M\_1$ and $M\_2$ in the following way:

* Alphabet is the union of the individual alphabets,
* set of states is the disjoint union of the individual sets of states (rename if necessary),
* initial state is taken from $M\_1$,
* final state(s) are taken from $M\_2$,
* Let $s$ be the initial state of $M\_2$. For each final state $f$ of $M\_1$ and for each symbol $A$ in the alphabet, add a transistion $\delta(f,A) = (s,A,S)$. These transitions allow to "switch machines" from $M\_1$ to $M\_2$ whenever machine $M\_1$ would reach an accepting configuration.
* All other transitions are taken from $M\_1$ and $M\_2$.

It should be apparent that $M\_{1\*2}$ accepts $L\_1\*L\_2$. Since it is an LBA, $L\_1\*L\_2$ is context sensitive.

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


# Question
Title: sorting with noisy but persistent answers
Given a set of elements $A$ and a probability of noise $p\<0.5$. For any two elements $x,y\in A$ we can ask the oracle $O$ to know where $x$ stands w.r.t $y$ (0 means $x$ is smaller than $y$ and 1 means the other way).

The oracle answers correctly with probability $1-p$. The noise is random and independent but persistent in a sense that if the oracle answers incorrectly for one pair $(x,y)$ it will give the same answer if questioned on the same pair again.

Is there any known strategy to sort $A$ with high probability?

# Answer
For constant $p\>0$ there is no way to *exactly* sort $A$ with high probability. Think, e.g., of the first two elements: they will seem to be in the wrong order with probability $p$ and no other comparison provides any information on their order.

In fact, if an algorithm returns a permutation of $A$ that has maximum dislocation1 $D$ with high probability, then $D = \Omega(\log |A|)$.

The algorithm in the paper by Braverman and Mossel suggested by Yuval returns a permutation with maximum dislocation $O(\log |A|)$ and, in particular, returns the maximum-likelihood permutation. However, its running time can be quite large.

The following papers have improved the time complexity (in chronological order) for the problem of sorting with (asymptotically) optimal $O(\log |A|)$ maximum dislocation. Here the returned permutation does not need to be the maximum-likelihood one and $p$ needs to be smaller than some constant ($1/32$, $1/20$, or $1/16$):

---

1 The dislocation of an element in a permutation is the absolute difference between its position and its rank (position in the sorted sequence).
> 4 votes

# Answer
Your problem has been considered by Braverman and Mossel in their paper Noisy sorting without resampling. The paper has generated quite a lot of follow-up work, some of which might be more practical than the original algorithm suggested by Braverman and Mossel.
> 2 votes

---
Tags: algorithms, sorting
---


# Question
Title: Is Unification "an Implementation of Existential Quantification"?
I read a comment (I've forgotten the source), "Unification is an *implementation* of existential quantification." (Emphasis mine.)

If true, this point of view clears up many things.

For instance why omitting the "occurs check" in unification can lead to unsound inference: it would be the same as using the assumption of the existence of a thing in your proof(-term) of the existence of that thing.

It would also explain why the algorithms for unification in logic programming language engines I've looked at seem (to me) more arbitrary than other operators such as conjunction and disjunction.

But - is the statement true? Is it an over-simplification?

# Answer
It's possible you're paraphrasing me. I've certainly said things similar to that e.g. here.

A more precise statement would be that existential quantification in logic programming languages is (typically) handled by *introducing a unification variable*. To perform existential introduction, you need to have a term $t$. The rule looks like: $$\dfrac{\Gamma\vdash P\[t/x\]}{\Gamma\vdash\exists x.P}$$

One way to implement this is to just guess a term $t$ and then see if we can backchain $P(t)$. Of course, for a language like Prolog, there are an infinite number of possible terms, and you have no guidance on what term to guess. A different option is to have $t$ be a *meta*-variable that stands for a term and continue execution on the hope that we can constrain $t$ enough to know what to decide later. This is essentially what a unification variable is. Unification itself just constrains what possible terms that meta-variable can be. Then, instead of actually enumerating the (now constrained) terms, we usually return the (simplified) constraints themselves as a compact representation of the set of possible terms, assuming they aren't contradictory (i.e. that that set isn't empty).

The occurs-check is simply the enforcement of the fact that *usual* term languages don't have infinite terms. You can consider other term languages that can represent these terms leading to things like rational tree unification.

Unsurprisingly, the operation unification itself most directly implements is equality. If we did the "exhaustively enumerate terms" approach to handling existential quantification, all the places where we (implicitly) use "unification" could just be straightforward syntactic checks of ground terms. With meta-variables, they instead produce constraints. Of course, this suggests the natural and common generalization of allowing constraints other than syntactic equality, and this leads to constraint logic programming. One generic example of such a constraint is *dis*unification which states what a term (potentially containing meta-variables) *cannot* be. It is the negation of unification, $t\not\equiv s$ states that for all substitutions $\sigma$, $t\[\sigma\]\neq s\[\sigma\]$.
> 2 votes

---
Tags: unification, logic-programming
---


# Question
Title: In O(1) get the coordinate i,j of a diagonally ordered matrix
Say you have a matrix like this:

```
[][]int{
    {0, 2, 5, 9, 14},
    {1, 4, 8, 13, 18},
    {3, 7, 12, 17, 21},
    {6, 11, 16, 20, 23},
    {10, 15, 19, 22, 24},
}

```

As you can see, it is diagonally ordered

Question: In Order O(1) if I give you a number N, give me the position i,j.

---

For example, on a regular ordered matrix

```
[][]int{
  {0,1,2,3},
  {4,5,6,7},
  {8,9,10,11},
  {13,14,15,16}
}

```

The solution is

```
j := n % len(m)
i := n / len(m[0])

```

With that you get i,j.
Ex: N=9 -\> 2,1

But how to get them for diagonals?

# Answer
Thanks @Evil, I got this algorithm based on your response. It returns the coordinates when giving an input number.

Only tested for squared matrices. EDIT: works on non squared matrices too.

```
func translateDiagonal(n, lenY, lenX int) (int, int) {

    shifted := false

    if n > lenX*lenY/2 {
        n = lenX*lenY - n - 1
        shifted = true
    }

    k := int(math.Floor((-0.5 + math.Sqrt(0.25+2.0*float64(n)))))
    j := n - (k * (k + 1) / 2)
    i := k - j

    if shifted {
        i = lenY - i - 1
        j = lenX - j - 1
    }

    return i, j
}

func traverseDiagonal(m [][]int) {
    for k := 0; k < len(m)*len(m[0]); k++ {
        i, j := translateDiagonal(k, len(m), len(m[0]))
        fmt.Println(m[i][j])
    }
}

func main() {
    m := [][]int{
       {0, 2, 5, 9, 14},
       {1, 4, 8, 13, 18},
       {3, 7, 12, 17, 21},
       {6, 11, 16, 20, 23},
       {10, 15, 19, 22, 24},
    }

    traverseDiagonal(m)

}

```
> 0 votes

# Answer
These are triangular numbers, so:
$i = \lfloor(-0.5 + \sqrt{0.25 + 2 * n}\rfloor - 1\\ triangular = \frac{i * (i + 1)}{2}\\ j = n - triangular - 1$

Minus one comes from indexing from 1.
> 1 votes

# Answer
So the series for your very first column is $0, 1, 3, 6, 10, \dots$ which is A000217 also known as the triangular numbers. It has formula $k(k+1)/2$ for the $k$th triangular number.

We want to find the diagonal our number lies in, so we want to find the largest $k$ such that $k(k+1)/2 \leq n$. I'll leave that as an exercise to you.

Then once we found $k$ our number is the $l = n - k(k+1)/2$ element in the diagonal, counting from zero. So our number is simply at $(k-l, l)$.
> 0 votes

---
Tags: matrix
---


# Question
Title: Are Context Sensitive Languages Turing Complete?
Related questions:

1. Can regular languages be Turing complete?
2. Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
3. https://stackoverflow.com/questions/14589346/is-c-context-free-or-context-sensitive
4. https://softwareengineering.stackexchange.com/questions/132385/what-makes-a-language-turing-complete

# Answer
Context-sensitivity has nothing to do with the semantics of a language. A language could have an arbitrarily complicated grammar, and still not be able to do anything useful, perhaps because it has no looping construct.

To make the above possibly clearer, here's a simple example. We know that it is possible to list all Turing machines in some order. (The proof is not difficult and comes from Alan Turing himself). That means that we can associate every positive integer with some Turing machine, in such a way that every machine has a unique index.

Now, take the language $L\_1 = \\{a^i \mid i \> 0\\}$ (where $a^i$ means a string consisting precisely of $i$ $a$s). Since any string of $a$s is in $L\_1$, the language is equivalent to the regular expression $a^+$.

The semantics of a program in $L\_1$ is simple: it does whatever Turing machine number $i$ would do, where $i$ is the length of the program. That's clearly a Turing complete regular language.

Then we define $L\_2 = \\{a^ib^i\mid i\>0\\}$ and $L\_3 = \\{a^ib^ic^i\mid i\>0\\}$, with the same semantics: in each case, program $i$ executes Turing machine number $i$. So these languages are also Turing complete, but $L\_2$ is context-free and $L\_3$ is context-sensitive.

Now, let's redefine the semantics. We'll define three languages with exactly the same syntaxes, but instead of executing Turing machine $i$, they print out $i$ in binary and then halt. These three new languages are still regular, context-free and context-sensitive, respectively, since the syntaxes have not changes. But none of them is Turing complete.

Bottom line: What a language *means* and how it is expressed are completely different concepts.
> 4 votes

# Answer
Any context-sensitive language is decidable and can be recognised by a Turing machine in NLINSPACE. Recognising a string from an arbitrary deterministic context-sensitive *grammar* is PSPACE-complete.

Moreover, just as context-free languages are equivalent to NPDAs, context-sensitive languages are equivalent to linear-bounded automata. Every CSL can be recognised by an LBA, and the language recognised by any LBA is a CSL.

All of the above is fairly standard (since it's type-1 on the Chomsky hierarchy) and covered in any decent textbook on languages and automata.
> -1 votes

---
Tags: formal-languages, turing-machines, turing-completeness, context-sensitive
---


# Question
Title: Best known (state of science) time complexity of an array access problem
Consider an Array $A$ with $n$ values and the following operations:

1. get(i): Returns the value of $A\[i\]$
2. insert (x): Insert the element x into the any free place in A (not necessarily in $A\[x\]$ or the end of the array)
3. delete (x) delete the element $A\[x\]$

What is the best known (amortized) time complexity of all operations? Especially the delete-op seems like it needs at least $\Omega(log n)$

See also the papers in this post. However the **insert** operation is defined slightly different by me, does this have any effect?

# Answer
> 2 votes
Ok so I think you can build a structure that has $O(1)$ (amortized) complexity for all operations, and using $O(n)$ space for $n$ insertions.

The underlying array is a dynamic array (let's call it $T$) : it has amortized O(1) complexity for insertion at the end. In the array, you store tuples of values and booleans : the boolean will be set to false when you delete, true when you insert. You also keep a stack / queue / some dynamic data structure with O(1) push and pop to keep the indexes of empty places in the array that were previously filled (i.e. they are not at the end of the array), let's call it $S$.

get(i) : if the boolean at i is true, return the elemet at position $i$ in $T$ : $O(1)$, otherwise return an error : no element at that position.
Insert(x) : if $S$ is empty, insert the element at the end (setting the associated boolean to 1) : $O(1)$ amortized with dynamic array. If $S$ is not empty : pop a position from $S$ and insert the element at that position : $O(1)$ as well.
Delete(i) : set the boolean at $i$ to false, and add $i$ to $S$. $O(1)$ as well.

The only downside of that method is that the array is never reduced, and therefore has size $O$(number of insertions) and not $O$(number of element).

---
Tags: data-structures, amortized-analysis
---