# Question
Title: Given n sorted arrays with size k select one element from every array such that the sum of the elements is minimum and the sum of their indices is k+1
So if $k = 3$ and $n = 2$ and we select the element $a\_1\[3\]$ of the first array then we have to select $a\_2\[1\]$ from the second array. If we select the element $a\_1\[2\]$ then also $a\_2\[2\]$ must be selected etc.

I can think of a DP algorithm to solve that which takes $O(nk)$ time (I don't think that I need to describe it, it's fairly easy to think). But I don't know if binary search can be used to find the answer more efficiently.

This may sound like a weird problem but it's part of a DP algorithm I'm trying to figure out and so the complexity will be multiplied with $kn$ so it would be great if I found a solution with $O(k)$ complexity.

# Answer
A conditional lower bound based on max-plus convolution can be shown: Fix $n = 3$. If a $\mathcal{O}(k^{2 - \epsilon})$ algorithm to this problem (with fixed $n$) exists, then MAXCONV could be solved in $\mathcal{O}(n^{2 - \epsilon})$. Max-plus convolution is a reasonable hardness assumption, as it is a much-studied problem for which no $\mathcal{O}(n^{2 - \epsilon})$-algorithm is known.

For this we'll use the result that MAXCONV can be solved in $\mathcal{O}(n^{2 - \epsilon})$ iff MAXCONV UPPERBOUND can be solved in $\mathcal{O}(n^{2 - \epsilon})$ (reference: "On Problems Equivalent to (min,+)-Convolution", ICALP 2017)

To show this, first note that we may drop the requirement that the arrays are sorted. To show this, take arbitrary values $b\_{i}\[j\]$, set $V = 2 \max\_{i, j} |b\_{i}\[j\]|$, and set $a\_{i}\[j\] = b\_{i}\[j\] + Vj$. Now $a\_{i}\[j+1\] - a\_{i}\[j\] = b\_{i}\[j+1\] - b\_{i}\[j\] + V \geq 0 \geq 0$, and the answer for $a$s is exactly $(k+1)V$ more than the answer for $b$s.

In a MAXCONV UPPERBOUND instance $(a\[i\])\_{i = 0}^{n-1}, (b\[i\])\_{i = 0}^{n-1}, (c\[i\])\_{i = 0}^{n-1}$ we are asked if for all $k$ we have $\max\_{i+j = k} a\[i\] + b\[j\] \leq c\[k\]$. To reduce it to our problem, set $a\_{1}\[j+1\] = a\[j\]$, $a\_{2}\[j+1\] = b\[j\]$ and $a\_{3}\[j\] = -c\[n-j\]$. Further set $a\_{1}\[n+1\] = a\_{2}\[n+1\] = a\_{3}\[n+1\] = -\infty$. Now the answer is positive if and only if at least one of the upper bounds doesn't hold: if the answer is positive, then $a\_{1}\[x\] + a\_{2}\[y\] + a\_{3}\[z\] \> 0$ for some $x + y + z = n+2$, hence $a\[x-1\] + b\[y-1\] \> c\[(x-1)+(y-1)\]$ and the upper bound for $k = x+y-2$ doesn't hold. Similarly if $a\[i\] + b\[j\] \> c\[i+j\]$, we have $a\_{1}\[i+1\] + a\_{2}\[j+1\] + a\_{3}\[n+2 - (i+1) - (j+1)\] = a\[i\] + b\[j\] - c\[i+j\] \> 0$.
> 2 votes

---
Tags: sorting, dynamic-programming
---


# Question
Title: Picross solving: matching checked cells to their clues
I am writing a picross solver, and I am going with the "human logic" solving, which attempts to reproduce the reasoning a human might have when confronted to such a puzzle, in an iterative manner.
Having solved a lot of those by hand, I found the human logic to be very algorithmic-ish given how the same kind of reasoning takes place in most situations (which is also what motivated me in writing a solver).
However, I am encountering problems when trying to formalize some of that logic.

# What is picross

Also called nonograms, they are puzzles consisting of an empty grid with clues on the top and left borders:
The clues indicate the length of groups of consecutive cells that need to be checked, and groups must be separated by at least one empty (unchecked) cell. Clues are ordered.
For example, clues `7 2` in the first row indicate that the following must take place somewhere in that row:

* 7 consecutive cells must be checked
* at least one cell must be left empty after that 7-long sequence
* another 2 consecutive cells must be checked after the empty cell(s)

Here is what the solved grid looks like:

In order to help in the process of solving, it is also possible to cross cells to indicate that they cannot be checked, as in they **must** remain empty for sure.

# Trivial solving

The easiest part of the solving is filling the empty grid with what you can deduce from the clues alone in each row and column. In that regard, some clues are nice, and some clues are not so nice.
For example, given that the previous grid is 10 cells wide, and that clues `7 2` fit in exactly 10 cells (7 checks + 1 space + 2 checks), there is only one possible solution for the first row.
However, by looking at the second row and its clue `6`, you will only be able to find that only cells at columns 5 and 6 can be checked with certainty:

```
|■|■|■|■|■|■| | | | |     1. Check the 6 leftmost cells
          ↓
| | | | |■|■|■|■|■|■|     2. Slide the group all the way to the right
          ↓
| | | | |■|■| | | | |     3. Keep cells that are *always* checked during the sliding

```

You can generalize this reasoning to a group of several clues by calculating the minimum space in which they fit, computing the difference with the actual available space and checking cells at only certain indices depending on those two numbers.
As mentioned, this is the easy part, because it only depend on the clues. It assumes the row or column is empty and thus it doesn't take its state into account.

# Further (iterative) solving

From that point onwards, several other pieces of reasoning can be performed in a loop on each row and column, and that will be sufficient to solve the entire grid *in most cases*. This paper, from section 2.2.2 (p. 16), identifies all such techniques. There is one problem however: these reasonings take into account the current state of a row or column, they build upon it. What that means is that in order for most of those to be carried out, they need to know which group of checked cells may correspond to which clue.

For example, considering the following row (10-wide with clues `3 4`):

```
3 4║ | | | | |■| | |■| ║

```

an algorithm identifying which cell may belong to which clue would tell me the following:
*both cells 6 and 9 belong to clue `4`*
**Reason:** if cell 6 belonged to clue `3`, a group satisfying clue `4` would not fit in the row (at least while being properly separated by an empty cell, as required). Cell 9 cannot belong to clue `3` for the same reason, as well as because cell 6 is located before and was found to exclusively belong to clue `4`, which is *after* clue `3`.

For the following row:

```
3 4║ | | |■|■| |■| | | ║

```

the algorithm would tell me:
*cells 4 and 5 belong to clue `3`, and cell 7 belongs to clue `4`*
**Reason:** if cells 4 and 5 belonged to clue `4`, a group satisfying clue `3` would not fit in the row. In the same way, there would not be enough space to satisfy clue `4` if cell 7 belonged to clue `3`.

Finally, for the following row:

```
3 4║ | | | |■| |■| | | ║

```

the algorithm would tell me: *cell 5 belongs to either clue `3` or clue `4`, but cell 7 belongs to clue `4` for sure*
**Reason:**

* if cell 5 belongs to clue `3`, there is still enough space for both a group of three ending at cell 5 and a group of four beginning at cell 7. Cell 5 may belong to clue `3`.
* if cell 5 belongs to clue `4`, there is still enough space for both a group of three starting at cell 1 and a group of four starting at cell 5. Cell 5 may belong to clue `4`.
* if cell 7 belongs to clue `4`, there is plenty of space for both groups required by clues. Cell 7 may belong to clue `4`.
* if cell 7, however, belonged to clue `3`, there would not be enough space for a group satisfying clue `4` afterwards. Cell 7 may **not** belong to clue `3`.

And this is exactly that algorithm which I'm having trouble writing down.
It also turns out I was able to come up with a solution while writing this question. See my (rather long) self-answer below.

# Answer
> 2 votes
**Long answer warning!!!**

So here is the approach I've taken to come up with this algorithm:

* We are trying to pair checked cells with potential clues they may belong to, so iterating on both of those would be a good start.
* Given a cell at **index** `i` and a clue at **index** `n`, cell `i` may only belong to clue `n` *iff*:
    + there is enough space before cell `i` for groups which satisfy all clues at index \< `n`; and
    + there is enough space after cell `i` for groups which satisfy all clues at index \> `n`
    + **Note:** a group of checked cells satisfying clue `n` will *always* fit without overlapping with the spaces needed by other clues. Otherwise, it means the clues are ill-formed, which is out of the question here.

---

* **Problem:** this doesn't take into account the fact that a cell may be part of a group of checked consecutive cells. In such a case, with just the above, it is possible that checked cell `i` is detected as belonging to clue `n`, but checked cell `i+1` is detected as *not* belonging to clue `n`, which doesn't make sense. Consider the following row:
`2 3║ | | | | |■|■| | | ║`
Here, cell 6 will be detected as possibly belonging to both clues `2` and `3`, but cell 7 will be detected as belonging exclusively to clue `3`. It is obvious that such a case doesn't make sense, and the answer is that both cells cannot belong to clue `2`, only to clue `3`.
    + **Solution:** let "group `i`" be the group of checked consecutive cells that cell `i` is part of. Cell `i` may belong to clue `n` *iff* the left and right boundaries of group `i` do not overlap with the spaces needed by other clues, as computed above.

---

* **Problem:** this fails to take into account crossed cells (telling this cell *cannot* be checked), which could "break up" the space available for a group statisfying clue `n`, potentially making cell `i` an invalid match for clue `n`. Consider the following row:
`4 3║ | | |■|×|■| | | | ║`
Here, both checked cells will be detected as belonging to clue `4`. Indeed, if there weren't a cross inbetween them, those two cells could form a group of 4 and there would still be enough space left for a group of 3 afterwards. However, there *is* a crossed cell between them, telling us this is not possible.
    + **Solution:** find the position of the closest crosses both left and right of cell `i` (if any). Cell `i` belongs to clue `n` *iff*, given a group of checked cells which satisfies clue `n` and includes cell `i`:
        - that group can fit between the two bounding crossed cells that were found (if any); and
        - that group can still not overlap the spaces needed by other clues, as computed above.
    + **Note:** the last condition above is now a required check because, as seen above, a crossed cell may restrict the possible positions for the entire group, which as a result could inevitably overlap with the spaces needed by other clues, thus making cell `i` an invalid match for clue `n`. Continuing the example given above: cell 6 cannot belong to clue `4`, as it would need to form a group of 4 that would overlap with the space needed by a group of 3 placed afterwards (as required by clue `3`).

---

* **Problem:** this fails to detect the presence of some discriminative checked cells. Consider the following row:
`3 3║ | |■| |■|■| | | | ║`
With just the above, the output will be that all three checked cells may belong to both clues. While the "*may*" part of the statement makes it not wrong, it would be naive to come to such a conclusion. It is obviously apparent that if the empty space in cell 4 was checked, there would be a group of 4, which by the clues of the row is invalid. Therefore it can be crossed, and cell 3 belongs to the first clue, while cells 5 and 6 belong to the second clue.
    + **Solution:** This requirement is out of scope for the algorithm currently being designed. In order for this specific requirement to be fulfilled, we basically insert an imaginary cross in cell 4 and ask the algorithm to behave as if it was there. However, if we inferred its presence, then it is not imaginary anymore, it must be there! This is part of **solving** the grid, **adding** information to the row, *not* extracting already existing information. See section 2.2.5 (p. 17) of the linked paper, "*Joining and splitting*".
    So this is basically a non-issue, but I thought I'd include it here as it was part of my thought process at some point, and it also constitutes a valid point to raise.

---

* **A free improvement:** the algorithm we've got so far does an okay job. It assumes that any checked cell can belong to any clue, and performs a series of simple checks on each cell and each clue to validate whether this can actually hold true. If a checked cell is marked as belonging to several clues, we can't tell which of these clues the cell actually belongs to.
However, if one cell is marked as belonging to one clue, then we can be sure that it belongs exclusively to that clue. This means the following: any other cell which might have been detected as belonging to the same clue and which is "out of range" for a group stemming from the original cell can be seen as a false positive and removed from the belonging entries accordingly.
Consider the following result, where a figure above a cell means that cell was marked as potentially belonging to the clue that corresponds to the figure:
`---║ 1 ║`
`---║ 2 2 ║`
`1 2║ | |■| | | | | |■| ║`
Because cell 9 belongs exclusively to clue `2`, and because cell 3 is out of range for a group of 2 stemming from cell 9, cell 3 cannot be part of clue `2`: it is a false positive. We get the following result after removing it:
`---║ 1 2 ║`
`1 2║ | |■| | | | | |■| ║`

---

Combining all of the above together, we get the following algorithm:
*(using 0-indexing for cells, as opposed to 1-indexing used throughout the question and this answer)*
*(using `#` to indicate comments)*

```
Input:
- a row (array of cells of length rowWidth)
- corresponding clues (array of integers of length cluesLength)

Initialize belongEntries, a 2D array of dimensions (rowWidth, cluesLength), to false.

For each checked cell (index i) in the row:
    leftCross ← index of the first crossed cell left of cell i, or -1
    rightCross ← index of the first crossed cell right of cell i, or rowWidth

    For each clue (index n):
        spaceLeft ← minimum space required for all clues before clue n
        If spaceLeft > 0:                   # If there are clues before clue n
            spaceLeft ← spaceLeft + 1       # Account for an extra space

        spaceRight ← minimum space required for all clues after clue n
        If spaceRight > 0:                  # If there are clues after clue n
            spaceRight ← spaceRight + 1     # Account for an extra space

        # maxLeft and maxRight are the maximum coordinates group i can span over (inclusive)
        maxLeft ← spaceLeft
        maxRight ← rowWidth - spaceRight - 1   # -1 to account for 0-indexing

        # Restrict both max coordinates to the coordinate of a potentially closer crossed cell
        # Add or remove 1 from the cross coordinate to get the coordinate of the cell *next* to it
        maxLeft ← max(maxLeft, leftCross + 1)
        maxRight ← min(maxRight, rightCross - 1)

        # Check that cell i is within allowed coordinates for clue n
        If maxLeft <= i <= maxRight:
            boundLeft ← index of the left boundary of group i
            boundRight ← index of the right boundary of group i

            clueVal ← (value of clue n)
            groupLength ← (boundRight - boundLeft) + 1

            # Not mentioned above, but don't forget to check that group i is not larger than the clue we're trying to match it to
            If groupLength <= clueVal:

                # Check that the boundaries of group i do not overlap with other     clue spaces
                If maxLeft <= boundLeft <= boundRight <= maxRight:

                    # Check that a group satisfying clue n would fit between max coordinates
                    If (maxRight - maxLeft) + 1 >= clueVal:
                        belongEntries[i, n] ← true

# Detect and eliminate false positives
# Using a lot of shortcuts here not to expand on irrelevant array indexing gymnastics

exclusiveCells ← list of indices of cells which belong to only one clue
For each indice i in exclusiveCells:
    clueIndex ← index of the only clue associated with cell i
    clueVal ← value of the only clue associated with cell i
    otherCells ← list of indices of cells which also belong to clue clueIndex

    # In case i is part of a group
    boundLeft ← index of the left boundary of group i
    boundRight ← index of the right boundary of group i
    groupSize ← (boundRight - boundLeft) + 1

    # Max additional distance the group can cover to reach an outer cell
    extent ← clueVal - groupSize

    # For each cell sharing the same clue with cell i
    For each indice j in otherCells:
        # Ignore if cells i and j are part of the same group
        If not (boundLeft <= j <= boundRight):
            # We're going to compute a distance to cell j,
            # but that distance calculation should start at different points
            # depending on whether cell j is left or right of group i
            If j < i:
                startCell ← boundLeft
            Else: # if j > i
                startCell ← boundRight

            distance ← abs(startCell - j)

            # If a spanning group would overextend its available space, remove cell j from the entries for that clue
            If distance > extent:
                belongEntries[j, clueIndex] ← false

```

---

Results for a 20-long row (clues marked above cells are indicated by their 0-index in the list of clues):
`---------║ 3 3 ║`
`---------║ 0 1 1 1 2 2 4 4 ║`
`1 3 4 2 1║ |■| |×| |■|■|■| |×│■| | |■| | |■| |■| ║`

After removal of false positives (1st pass):
`---------║ 3 ║`
`---------║ 0 1 1 1 2 2 3 4 ║`
`1 3 4 2 1║ |■| |×| |■|■|■| |×│■| | |■| | |■| |■| ║`

After removal of false positives (2nd pass):
`---------║ 0 1 1 1 2 2 3 4 ║`
`1 3 4 2 1║ |■| |×| |■|■|■| |×│■| | |■| | |■| |■| ║`

To account for cases like this one, in which several passes of elimination are needed, we can simply loop over the elimination part of the algorithm until no more changes are brought:

```
oldBelongEntries ← Same array as belongEntries, initialized to false everywhere

While belongEntries != oldBelongEntries:
    oldBelongEntries ← belongEntries

    # Detect and eliminate false positives
    ...

```

**Nice !**

---
Tags: algorithms
---


# Question
Title: DCFL with prefix property have LR(0) grammar?
There are two important theorems about LR(k) grammars and DCFL. Mentioned here.

1. A language has an LR(1) grammar iff it is DCFL.
2. A language has an LR(0) grammar iff it is DCFL and has prefix property.

I have counter example for 2nd theorem, plz see if it is valid counterexample. (Ofcourse its not valid and I am wrong, But what wrong I am doing here ?)

DCFL without prefix property: $\\{b(ab)^n \mid n\geq0\\}$

2nd theorem says it should not have $LR(0)$ grammar, but here it is-

$ S \rightarrow Sab \\S \rightarrow b$

PS: This is my first question here, sorry if I violated any protocol.

# Answer
Your grammar is $\mathrm{LR}(0)$ by adding a $\mathrm{\\$}$ symbol to the alphabet and a starting deduction rule $S'\rightarrow S\\$$ when constructing the $\mathrm{LR}(0)$ automaton (and it is a standard construction).

Omitting syntactical purposes, every DCFL $\mathrm{L}$ can be parsed by an $\mathrm{LR}(0)$ grammar for $\mathrm{L}\\$$. What makes $\mathrm{LR}(k)$ ($k\>0$) more practical is that it may include more syntactical information which is very important in compiler design. Otherwise, all these techniques would never be used in practice. In that case, $\mathrm{LL}(k)$ with local manipulation for expressions would be used instead, even with prohibitive cost of time and space.
> 3 votes

# Answer
As an conceptual understanding we can think of it as the grammars which satisfies prefix property can be reduced without even using look ahead as those can be accepted by DPDA which accepts through empty stack, but if language is not satisfying the prefix property we will have to check whether the look ahead is $ or any character, if its $ then we can reduce it otherwise we will have to scan input further. DPDA(empty stack acceptance) is less powerful than DPDA(final state acceptance), thats why LR(0) is less powerful than LR(1) Hope this helps.
> 0 votes

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


title: Text detection in computer vision

text:
# Question
Title: Text detection in computer vision
I'm curious about the way text recognition works in machine learning(or more generally, the question of object vs not object) in computer vision.

How are systems trained when the not-object data set is so much greater in quantity and apparently lacks structure?

One approach is having the algorithm first searches for a text box and once it finds one applies character recognition. Thus the initial classification comes down to "text" or "not text". "Not text" doesn't have any particular structure though and in fact almost everything is "not text"...so how is this dealt with?

What would the "not text" training set be? Random images? Clearly you need negative examples.

# Answer
> 1 votes
Many research projects use something called "hard negative mining": instead of training on all of the positive instances (e.g., "text" or "object") and all of the negative instance (e.g., "not text" or "not object"), they train on all of the positive instances and a carefully chosen subset of the negative instances. In particular, they omit many of the 'obvious' negative instances and try to bias towards choosing negative instances that are more difficult to handle correctly. It's not clear to me whether this is truly necessary or beneficial with modern machine learning methods, but it is something you could try, if you don't want to use all of the negative instances.

Yes, to create negative instances, you would normally sample random patches of the image (at a random location), subject to the restriction that they not have too much overlap with the actual text/objects.

For learning more about how to recognize object vs objectness, read about "objectness" detection or saliency detection. For learning more about detecting text, you might be interested in the stroke width transform and the segmentation step in OCR.

---
Tags: machine-learning, neural-networks, computer-vision
---


# Question
Title: Prime checking and factorization with just bit cheking
I've read about some methods of prime factorization like here and here. However, I'm wondering: what can we do in prime factorization with just some bit manipulation and without other variables/constants?

In base 10, we can get some hints about the factors of an integer just be checking the digits:

* digit's place is even --\> int is even
* digit's place is 0 of 5 --\> int is divisible by 5
* sum\_of\_digit % 3 = int % 3
* sum\_of\_digit % 9 = int % 9

Given an integer `num` as a bit array, how can we check for `num`'s primality and guess or extract its prime factors just by looking at its bits like we do with digits in base 10?

```
   There are 5 0's --> (num % (2^5)) = 0
            / \
           /   \
           |   |
1010101110100000
      | |      ^
      | |      | last bit is 0 --> num is even
      | |
       v
may be these 3 bits can give some information?

```

What's allowed:

* bit-manipulations which take 1 argument are allow. This includes functions like `not` but not `xor`.
* `if`s and loops are allowed but bits in `num` will be used for the flag. (no using `if num > 2`)
* `num` is the only variable/constant allowed to be declared. We can `not(num)` (flip every bits in `num`) but not `num - 2` (`2` is another var/const).
* Operating on bits only in `num` like summing all the bits (`bit_sum(20) = bit_sum(b1010) = 2` because there are 2 `1`s)

Bonus if the operation can quickly be done by hand like the given examples for base 10.

# Answer
Given any specific candidate divisor $d$, it is easy to check whether $d$ is a divisor of the number (the standard modular reduction algorithm is a generalization of those tricks you mentioned). This can be done for all $d$. However, it doesn't help with efficient factorization, because there are exponentially many candidate divisors, so trying each one, one-by-one, is far too inefficient.

In other words, this approach to factorization is not likely to be useful, no matter how many tricks you accumulate.
> 3 votes

---
Tags: primes, factoring, bit-manipulation
---


# Question
Title: How does the forget layer of an LSTM work?
Can someone explain the mathematical intuition behind the forget layer of an LSTM?

So as far as I understand it, the cell state is essentially long term memory embedding (correct me if I'm wrong), but I'm also assuming it's a matrix. Then the forget vector is calculated by concatenating the previous hidden state and the current input and adding the bias to it, then putting that through a sigmoid function that outputs a vector then that gets multiplied by the cell state matrix.

How does a concatenation of the hidden state of the previous input and the current input with the bias help with what to forget?

Why is the previous hidden state, current input and the bias put into a sigmoid function? Is there some special characteristic of a sigmoid that creates a vector of important embeddings?

I'd really like to understand the theory behind calculating the cell states and hidden states. Most people just tell me to treat it like a black box, but I think that, in order to have a successful application of LSTMs to a problem, I need to know what's going on under the hood. If anyone has any resources that are good for learning the theory behind why cell state and hidden state calculation extract key features in short and long term memory I'd love to read it.

# Answer
> 1 votes
Think of it like this: The cell state $h\_t$ is a vector. The forget vector $f\_t$ is used to choose which parts of the cell state to "forget". We update the hidden state with something like $c\_t = f\_t \circ c\_{t-1}$ (it's actually more complicated, but let's start with that, to gain intuition). Suppose $f\_t$ were a vector of 0's and 1's. In the coordinates where $f\_t$ is 1, the value of $c\_{t-1}$ would be copied over to $c\_t$ (it's not forgotten). In the coordinates where $f\_t$ is 1, $c\_t$ is reset to zero and the value of $c\_{t-1}$ is ignored (it's forgotten). So, the forget vector can be used to control in which positions we forget values from the previous cell state vector.

Now what remains is to figure out a way to choose a forget vector $f\_t$. In general we might want to choose which positions to forget based on both the current input $x\_t$ and the previous hidden state $h\_{t-1}$. So, we should compute $f\_t$ as some function of $x\_t$ and $h\_{t-1}$. Many choices of how to represent that function might be possible, but a LSTM chooses a specific function for this. In a LSTM, this is done by a single-layer fully-connected neural network. A single-layer fully-connected neural network concatenates all of the inputs, then multiplies them by a matrix, adds a bias, and feeds the result to an activation layer (in this case, sigmoid activation). So that's why the formula for $f\_t$ looks the way it does: that formula is capturing what a single-layer fully-connected neural network does.

---
Tags: neural-networks, mathematical-foundations, mathematical-analysis
---


# Question
Title: What is the LTL expression for "there is a value of y whose next value is 8"?
Basically i have a program which increases a variable by 1 in each iteration and resets it to 0 as soon as y becomes 8 (i.e. mod 8).

It is a quite simple example but it still bugs me out because i cannot clarify if my LTL-formula is correct for the property "there is a value of y whose next value is 8". For this i came up with the:

$$FX(y \doteq 8)$$

which means "somewhere in the future the **next** value of y is 8".

Is it the correct LTL formula for my question (even though it is of course invalid for my application)?

# Answer
The important thing that is missing from your question is how you model your program, and specifically, what are the atomic propositions you allow.

If your atomic propositions are "y=0",...,"y=8", and your transition system is modeled accordingly, then the formula $FX y=8$ means the eventually, the next position would have "y=8". Note that this is equivalent to the formula $XF y=8$, which basically says that y=8 sometime after the first position.

However, you phrased your requirement as "there is a value of y whose next value is 8", and it's not clear what this means. What is the "next value of y"? LTL does not recognize y as an entity, only the propositions mentioned above. So you cannot really talk about values of variables in LTL, without first adding all possible values as propositions.
> 3 votes

---
Tags: linear-temporal-logic
---


# Question
Title: Are there any problems that reduce to the halting problem?
I'm reading through sipser and there is a lot of computability problems that the halting problem reduces to, i.e. if $A\_{TM} = \\{\langle M,w\rangle : M$ accepts input $w\\}$ then $A\_{TM} \leq P$ where P is some other language, but is there an example of another language that reduces to $A\_{TM}$ (i.e if we could decide $A\_{TM}$ then we could decide that problem)

# Answer
Trivially every *computable* problem is reducible to $A\_{TM}$. On the other extreme, there are plenty of problems which are $A\_{TM}$ "in disguise," which is to say that they are Turing-equivalent to $A\_{TM}$ \- for example, it's a standard exercise to show that $$\\{\langle M\rangle: M\mbox{ halts on input $0$}\\}$$ is Turing-equivalent to $A\_{TM}$.

A more interesting situation arises when we ask about *strict* reducibility:

> Is there a problem $X$ such that $(i)$ $X$ is not computable, $(ii)$ $X$ reduces to $A\_{TM}$, but $(iii)$ $A\_{TM}$ does not reduce to $X$?

The answer to this question was shown to be **yes** by Kleene and Post, although interestingly no *natural* examples are known (and indeed it's generally believed that none exist). This led to a natural follow-up question ("Post's problem"):

> Is there a **computably enumerable** $X$ with the above properties?

This turned out to be much harder to solve, and wound up taking more than a decade; Friedberg and Muchnik independently introduced the **priority argument** to show that the answer is **yes**.

Today priority arguments - indeed, ones vastly more complicated than the original Friedberg/Muchnik theorem - are one of the main techniques in computability theory. They originally went by excitingly violent names: *finite injury* (Friedberg/Muchnik falls into this category), *infinite injury* (introduced by Sacks), and *monstrous injury* (introduced by Lachlan). While the first two terms are still in use, the third is not, and we categorize priority arguments more complicated than "basic infinite injury" according to the complexity of an associated set (the "true path"); in particular monstrous injury arguments are now called **0'''-arguments**.
> 3 votes

# Answer
All decidable problems can be reduced to the halting problem, since you can build a machine that solves the problem in bounded time and place (even if the bound was super exponential) and accepts if the output is yes else it goes into a loop.

A more interesting example is **the post correspondence problem**. It is a well-known undecidable problem. The proof is basically a reduction from the Halting problem. Here I present a reduction in the other direction, namely from the post correspondence problem to the halting problem.

First let us define the problem. Given two sets of words $A := \\{a\_1, \dots a\_n\\}$ and $B := \\{b\_1, \dots, b\_m\\}$ over an alphabet of size at least two. Is there a sequence $i\_1, \dots i\_l$ and $j\_1, \dots j\_{l'}$ such that the strings resulting from concatenating $a\_{i\_1}a\_{i\_2}\dots a\_{i\_l}$ is equal to the sting $b\_{j\_1}\dots b\_{j\_{l'}}$.

For a reduction to the halting problem, given an instance $I$ of the post correspondence problem, we build a touring machine $M$, such that the instance is a yes-instance if and only if the machine halts by the empty input (The machine totally ignores the input band).

For each positive integer $k$, the machine simulates all strings that result from concatenations of at most $k$ strings in $a$ and all strings that result from concatenations of at most $k$ strings in $b$ and check if any resulting string from the first set is equal to any resulting string from the second set.

If the machine halts at some value of $k$, this means there is a string of at most $k$ strings from $a$ that can be written as a concatenation of at most $k$ strings from $b$ and hence the given instance is a yes instance.

On the other hand, if the given instance is a yes-instance, for $k = max\\{l, l'\\}$, the machine halts in the $k$-th iteration.
> 1 votes

# Answer
Before Fermat's Last Theorem was proved, it could easily be reduced to the halting problem: You can easily write a program that will halt if and only if there are 1 ≤ a ≤ b ≤ c, and n ≥ 3, such that $a^n + b^n = c^n$. A proof that the program halts or not would have proved that FLT is wrong or right. And a solution to the halting problem (a program that can decide whether an arbitrary other program halts or not) would have been able to prove or disprove FLT.
> 0 votes

---
Tags: computability, reductions, halting-problem
---


# Question
Title: What goes into proving two complicated programs are equivalent?
Say I wanted to prove that two programs were equivalent (either *rigorously* if possible, or *informally* if not). More specifically, say I have something relatively complex such as an HTTP server implemented in C, and one implemented in Node.js/JavaScript. What can I do in terms of saying "these two are effectively the same"? What are my options? What is possible? What is not possible?

*It's been a little while since I've looked into proving program equivalence (I'm currently linked to this, but I can't read it yet haha, and it looks like it's focusing on extremely simple programs like equality checks or basic loops, whereas I'm asking about a robust HTTP server).*

Essentially (I'm imagining) I want to say "these two programs in JS and C do the same thing". That "*do the same thing*" is obviously vague, but at the same time it means something specific. Any observable outcome on either system is generally the same, *give or take*. So it's like a proof, but without being a *perfect* proof. It's like it's a partial proof or something.

I would like to be able to say of my programs "these two implementations are equivalent for all intents and purposes". I would probably start by providing measurable guarantees or observations about performance and input/output behavior, and then write some tests, and ... I don't quite remember, somehow make statements about the system. Or should I just be thinking that "a functioning HTTP server in either language is an **AXIOM**". That would simplify it :) Just assume it does the same thing as one another. But that's sidestepping it feels like.

Wondering what are my options here? How far can I take this in theory? I am not concerned with how long this would take to implement or define, if it takes years, fine. I just would like to know what is possible in terms of making the statement "these two programs in C and JS are equivalent" more rigorous and nailed down. What techniques/theories/research-directions could I look into to make it possible?

Right now I am just *assuming* they are equal implicitly, allowing my code to call either the C function or the JS function knowing that the ~overall effect~ is the same (nebulous, I know, don't know how to pin it down). I would like to apply some math or model checking or program simulation or something to this so that I can make it more solid, if possible :)

At the other end of the spectrum is proving that `3 > 2` is equivalent in both C and JS. What am I even supposed to do in this simple case? Making that slightly more complex on it's way to a full HTTP server, copying a string in C is very different than in JavaScript, but it's a relatively simple thing. Where do I even begin to prove those "operations" equivalent between the two languages? Or if not "prove", then just "state" that they are equivalent, with some backup evidence or something, I dunno.

Here is not much, but this diagram is what I'm basically trying to do:

At a broader level, the problem seems to be similar to this.... Say I want to get a medallion. I can either go the store and buy one, or I can 3D print one. Both "algorithms" (going to the store, or 3D printing) are way different from each other, but they are effectively the same. There would be no straightforward way to step-wise prove these are equivalent *operationally* (from what my imagination provides), but visibly the end result is the same. How would you (even here) state this with rigor?

# Answer
> 2 votes
Formal analysis today is usually done on module or unit level. Unfortunately I'm not aware of a common metric which allows to predict if a formal analysis will be possible. Only structurally very simple codes can be formally analysed even with LOC's or cyclomatic complexities of up to a million.

In your case here the code of any of the two programs is clearly too complex for a full formal analysis:

* Model-checking will not work.
* A complete (bi-) simulation will not work either.

So the best practical solution I know is **model-based testing**. While it is not a proof still formal methods can be used. It ultimately eliminates the disaster of writing and maintaining manually written test cases.

P.S.:

A short list of steps which can be done in this case:

* An abstract model of the two programs is created. This is a third implementation which will omit all unimportant details. The abstraction has the advantage that this model is simple enough again to be formally analysed. The model can be implemented in any language you like if the model analyser will analyse the byte code.
* The abstract model can be traversed and e.g. a condition coverage is reached in a test suite. This step is done using a model-based-testing tool.
* Finally these test cases are tested on the two programs and it is checked if the abstract model can simulate the two program implementations.
* This simulation relation is of course not a proof of the equivalence.
* The abstraction is a very clean specification what was taken into account in our tests and what was omitted.
* Two model-based testing tools which can be recommended: Microsoft Spec Explorer, Conformiq Designer

# Answer
> 4 votes
One could write an entire book surveying techniques of proving program equivalence. This answer is just as a very short starting point:

Theoretically, if you think about your programs as Turing Machines, then all hope is lost -- proving that two TMs have the same language (i.e., they are *semantically* equivalent) is undecidable (in fact, it's not in RE$\cup$ coRE).

Still theoretically, if you think about your programs as finite state machines, by including the states of the memory as part of the machine, then program equivalence for DFAs is very simple (solvable in NL), and for NFAs it's PSPACE complete. The problem with this approach is that the state space would be huge (e.g., if you have only 100 bits of memory, your state space has at least $2^{100}$ states), so this is unreasonable.

Now that we've cleared the theoretical bounds, there is an immense body of work addressing these topics, including ways to define operational semantics.

Basically, this is the field of Formal Verification, and just some keywords that can get you started:

* Model checking
* Bisimulation
* Abstraction - Refinement
* Theorem Provers (e.g., Coq)

Note that in practice, many companies are formally verifying their code. For hardware, this is common practice, and is an important stage in development. For software, the huge complexity means that only small bits of code are getting proved formally, never entire programs (not yet, at least).

---
Tags: reference-request, proof-techniques, model-checking, research
---


# Question
Title: Number of ways n can be written as sum of at least two positive integers
I found a solution in Python for this problem, but do not understand it. The problem is how many ways an integer n can be written as the sum of at least two positive integers. For example, take n = 5. The number 5 can be written as

```
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

```

Here's a solution for given $n$.

```
# zero-based array (first index is 0)
ways = [1, 0, ..., 0] (n zeroes)

for i in 1, ..., n-1:
    for j in i, ..., n:
        ways[j] = ways[j] + ways[j-i]

print ways[n]

```

This solution is elegant and efficient, but unfortunately, I do not understand the logic. Can someone please explain the logic of this solution to the problem? Is there a way to make this algorithm easy to understand?

# Answer
Let us denote the array *ways* after $t$ iterations of the outer loop by $w\_t$. The recurrence implemented by the code is $$ w\_0(n) = \begin{cases} 1 & \text{if } n = 0, \\ 0 & \text{if } n \> 0. \end{cases} \\ w\_t(n) = \begin{cases} w\_{t-1}(n) & \text{if } n \< t, \\ w\_{t-1}(n) + w\_t(n-t) & \text{if } n \geq t. \end{cases} $$ You can prove by induction that $w\_t(n)$ is the number of representations of $n$ as a sum of natural numbers between $1$ and $t$ (without regard to order). (This is also the number of representations of $n$ as a sum of at most $t$ natural numbers.)

The code returns $w\_{n-1}(n)$, which is the number of representations of $n$ as an arbitrary sum of natural numbers, other than the representation $n$.

As an aside, if you allow the trivial representation then you get the partition function. Using Rademacher's asymptotic formula, the partition function can be computed in time $\tilde O(\sqrt{n})$, much faster than your $\Theta(n^2)$ algorithm.
> 2 votes

---
Tags: algorithms, number-theory, integer-partitions
---


# Question
Title: Is it possible to prove Tarski's Undefinability theorem from Turing's Halting Problem?
In the Wikipedia page for Turing's Halting problem, they mention that you can prove Gödel's First Incompleteness theorem from it. This is the relevant quote:

> Assume that we have a sound (and hence consistent) and complete axiomatization of all true first-order logic statements about natural numbers. Then we can build an algorithm that enumerates all these statements. This means that there is an algorithm N(n) that, given a natural number n, computes a true first-order logic statement about natural numbers, and that for all true statements, there is at least one n such that N(n) yields that statement. Now suppose we want to decide if the algorithm with representation a halts on input i. We know that this statement can be expressed with a first-order logic statement, say H(a, i). Since the axiomatization is complete it follows that either there is an n such that N(n) = H(a, i) or there is an n' such that N(n') = ¬ H(a, i). So if we iterate over all n until we either find H(a, i) or its negation, we will always halt, and furthermore, the answer it gives us will be true (by soundness). This means that this gives us an algorithm to decide the halting problem. Since we know that there cannot be such an algorithm, it follows that the assumption that there is a consistent and complete axiomatization of all true first-order logic statements about natural numbers must be false.

After reading this proof, I wondered if a very similar proof by contradiction could also prove Tarski's Undefinability theorem?

I was thinking of something along the following lines:

Imagine that a truth predicate isTrue($\ulcorner s \urcorner$) for any arbitrary logic sentence s were computable. In that case, this predicate would also be able to compute the truth status for any arbitrary H(a,i). Therefore, we would be able to compute isTrue($\ulcorner H(a,i) \urcorner$) for any possible H(a,i). Consequently, such isTrue($\ulcorner s \urcorner$) predicate would solve Turing's Halting problem, while we already know that it is fundamentally unsolvable. Therefore, such truth predicate is not computable.

Is there a flaw or a problem with this proof strategy?

The fact that the Wikipedia page mentions this proof strategy for Gödel's First Incompleteness but not for Tarski's Undefinability got me wondering. Maybe it does not work for Tarski after all? What's the catch?

# Answer
> 3 votes
As cody observed, the problem with that strategy is that *definable relations need not be computable*. For example, the Halting Problem is definable in $(\mathbb{N}; +,\times)$ (see Kleene's $T$-predicate).

That said, a *relativized* form of the incomputability of the Halting Problem, applied to iterates of the Turing jump, does do the job:

* First, we show that for each $n$ and each $\Sigma\_n$ formula $\varphi$ the set $\\{x: \varphi(x)\\}$ is computable from ${\bf 0^{(n)}}$, uniformly in $n$ and $\varphi$.
* Next, we show that for each $n$ the set ${\bf 0^{(n)}}$ is itself definable by some $\Sigma\_n$ formula $\psi\_n$. This is an application of Kleene's $T$-predicate.
* Now we're good to go. Suppose we had a $\Sigma\_n$ formula $\varphi$ defining the set of (Godel numbers of) true sentences in the language of arithmetic. Then ${\bf 0^{(n)}}$ could compute ${\bf 0^{(n+1)}}$ as follows: given $k$, we ask ${\bf 0^{(n)}}$ whether $\varphi(\underline{\ulcorner\psi\_{n+1}(\underline{k})\urcorner})$ holds. *(Here "$\underline{i}$" denotes the numeral corresponding to the number $i$, and "$\ulcorner\theta\urcorner$" is the Godel number of $\theta$.)*
* But that gives ${\bf 0^{(n+1)}}=({\bf 0^{(n)}})'\le\_T{\bf 0^{(n)}}$, a contradiction by the relativized unsolvability of the Halting Problem.

---
Tags: logic
---


# Question
Title: Prove that the class of CFG languages that are closed under reversal is undecidable
## Note

The wording of the title may be a bit vague, but I'm not asking if CFLs are closed under reversal. Please see below.

## Problem Description

Given a word $w$, define $w^{r}$ to be its reversal.

Let $L=\\{ G \vert G \text{ is a } CFG \text{ and for every } w \in L(G), w^{r} \in L(G) \\}$

Prove that $L$ is undecidable.

## My Attempt

I am aware that I should reduce a known-to-be-undecidable language to L, but by looking at the four undecidable languages here (Equivalence, Disjointness, Containment, Universality), I still failed to determine which language I can use. Please guide me a direction, thank you.

# Answer
> 4 votes
Let $G\_1,G\_2$ be two context-free grammars. We can construct a context-free grammar $G$ such that $$ L(G) = \\#L(G\_1) \cup L(G\_2)^r\\#, $$ where $\\#$ is a new symbol. The language $L(G)$ is closed under reverse iff $L(G\_1) = L(G\_2)$.

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


# Question
Title: O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?
I came up with this O(V+E) algorithm for calculating the chromatic number X(g) of a graph g represented by an adjacency list:

1. Initialize an array of integers "colors" with V elements being 1
2. Using two for loops go through each vertex and their adjacent nodes and for each of the adjacent node g\[i\]\[j\] where j is adjacent to i, if j is not visited yet increment colors\[g\[i\]\[j\]\] by 1.
3. After doing this the maximum integer in the array "colors" is the chromatic number of the graph g(if the algorithm works).

Here is my C++ code:

```
#include <bits/stdc++.h>
using namespace std;

struct graph {
    vector<vector<int>> adjL;
    vector<int> colours;
    vector<bool> vis;
};

int chrNUM(graph& G) {
    int num = 1;
    for(int i = 1; i < G.adjL.size(); i ++) {
        for(int j = 0; j < G.adjL[i].size(); j ++) {
            if(!G.vis[G.adjL[i][j]]) {
                G.colours[G.adjL[i][j]] ++;
                num = max(num, G.colours[G.adjL[i][j]]);
            }
        }
        G.vis[i] = true;
    }
    return num;
}

void initGET(graph& G, int N, int M) {
    cin >> N >> M;
    G.adjL.assign(N + 1, vector<int>(0));
    G.colours.assign(N + 1, 1);
    G.vis.assign(N + 1, false);
    for(int i = 0; i < M; i ++) {
        int u,v;
        cin >> u >> v;
        G.adjL[u].push_back(v);
        G.adjL[v].push_back(u);
    }
}

int main() {
    graph g;
    int n;  //number of vertices
    int m;  //number of edges
    initGET(g, n, m);
    cout << chrNUM(g);
}

```

I am wondering if there is a flaw? Maybe it works for certain graphs only? Maybe it gives X(g) for smaller graphs but a value higher than X(g) for larger graphs? I found it worked correctly for all the graphs I have tried (up to 20 vertices). I know this is an NP complete problem but I want some counterexamples for my algorithm if possible or an explanation as to why the method won't work. I have also got a recursive (DFS) solution which is a bit different but mostly similar to this. Any ideas?

Thanks in advance!

# Answer
Your algorithm is known as greedy coloring. Wikipedia gives an example of a bipartite graph, the crown graph, where the greedy coloring can produce a coloring using $n/2$ colors (for the worst ordering). For random $G(n,1/2)$ graphs, the greedy coloring typically produces a coloring using double the optimal number of colors.
> 10 votes

---
Tags: algorithms, complexity-theory, graphs, np, graph-traversal
---


# Question
Title: Is concatenation of regular language with any other language regular?
I came across following problem:

> True or false? If $L$ is a regular and $M$ is not a regular language then $L.M$ is necessarily not regular.

The answer given was:

> Consider $L$ to be $\emptyset$ and $M$ be $\\{a^nb^n | n\leq 0\\}$
> $L.M=\emptyset$, which is regular. Hence the statement is false.

I guess the solution incorrectly tries to generalize the case of those two specific languages to all other languages. For example, if $M$ is DCFL, then I believe $L.M$ wont be regular. Am I correct with this?

# Answer
As you show, if $L = \emptyset$ then $LM$ is regular for *any* language $M$. Conversely, for languages over $\\{0,1\\}$ (or any non-unary alphabet), there is a language $M$ such that if $L \neq \emptyset$ then $LM$ is not regular: $$ M = \\{10^p : p \text{ prime}\\}. $$ Indeed, suppose that $w \in L$. Then $$ w^{-1}(LM \cap w10^\*) = M. $$ Since all of the operations preserve regularity, we conclude that $LM$ is not regular.

Over a unary alphabet, the picture is a bit different. Let $$ M = \\{ 0^{n!} : n \geq 0 \\}. $$ If $L \neq \emptyset$ is finite then $LM$ is not eventually periodic, and so not regular. If $L$ is infinite and not regular, then $L\\{\epsilon\\}$ is not regular. If $L$ is infinite and regular, then it is eventually periodic. For every language $M$, $LM$ is also eventually periodic (with the same period), and so regular.
> 2 votes

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


title: Finding a winner in a "long list"

text:
# Question
Title: Finding a winner in a "long list"
This is from betting domain which has something that is called a long list: a list of a "home team win/draw/away team win" markets for 13 games. A punter can select any combination of the possible outcomes which are encoded in a following way:

```
1 - home team wins
2 - draw
4 - away team wins
3 - home team wins or draw
5 - home team wins or away team wins
6 - draw or away team wins
7 - home team wins or draw or away team wins

```

Meaning a `[3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7]` represents a selection where punter put following bets:

* "home team wins or draw" in a first game
* "home team wins" in games 2-12
* "home team wins or draw or away team wins" in 13th game

After games are finished there will be another 13 elements list representing winning outcomes, for example: `[4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]` means that in a first game away team won and in all other games home team won.

The question is if I'm missing any properties within those numbers that will make finding a winning bets easier than comparing each number one by one? Like in our case case checking if there are bets that has `4`,`5`, `6` or `7` for the first game and `1`, `3`, `5` or `7` for rest of them.

# Answer
> 3 votes
The bitwise and of the bet and result is nonzero if and only if the bet is winning. Further, the bitwise and has exactly one bit set if the bet wins.

To see this, note that the encoding of a bet has bit $1$ set iff it wins if the home team wins, bit $2$ set iff it wins if the game is a draw, and bit $4$ set iff it wins if the away team wins.

For example, if our bet is 6 - draw or away team wins, its binary encoding is 110. Then if the away team wins, the result is encoded as 100 and the bitwise and is 100. If the home team wins, the result is encoded as 001 and the bitwise and is 000.

In the word-ram model this can even help us calculate the result asymptotically faster: if the encodings of the bets and results are stored consecutively in binary with 3 bits per number, then counting the number of bits in the bitwise and of these two sequences gives the number of won bets in $\mathcal{O}(\frac{n}{w})$ with $w$ bits per word. Similarly all winning bets could be found in $\mathcal{O}(\frac{n}{w} + r)$ where $r$ is the number of winning bets. Of course this assumes the representation of the data is convenient for us, if it isn't, we need $\mathcal{O}(n)$ work to change its representation.

For example, the bets \[3, 6, 1\] and results \[4, 2, 1\] would be represented as 110011100 and 001010100 respectively, the bitwise and of which is 000010100. This indeed has two set bits corresponding to the two winning bets.

---
Tags: algorithms, number-theory
---


# Question
Title: is the empty language L = ∅ a subset of every languages?
I need to show false the following claim

> Every language L which is a subset of $A\_{TM}$ ($L \subseteq A\_{TM}$) is undecidable.

For this, I wish to use the empty language L = ∅ (I know is decidable).

Is it correct that the empty language L = ∅ is a subset of every languages (and also of $A\_{TM}$)?

# Answer
Yes. Remember that $A\subseteq B$ just means "every element of $A$ is also an element of $B$." In case $A=\emptyset$, this is trivially true *("vacuously true")* regardless of what $B$ is.

It may also help to think in terms of counterexamples: $A\subseteq B$ is the "default" situation, and is only false if there is a *counterexample*: some $x\in A$ with $x\not\in B$. Since there are no $x\in \emptyset$ in the first place, there are never any counterexamples to $\emptyset\subseteq B$ (again, regardless of what $B$ is).

---

It's worth mentioning that there are less trivial solutions to this problem as well. For example, fix some $a\in A\_{TM}$. The **padding lemma** then builds us a computable infinite set $A\subseteq A\_{TM}$ of "equivalent versions" of $a$ (not everything "equivalent to" $a$ shows up in $A$, but infinitely many things do).

And even more is true - $A\_{TM}$ is *computably enumerable*, and we have the following general fact:

> Every infinite computably enumerable set has an infinite computable subset.

This is a good exercise. *HINT: think about the fact that any computably enumerable set which we can enumerate "in order" is computable.*
> 1 votes

---
Tags: undecidability, halting-problem
---


# Question
Title: if A is decidable then B is decidable too
Assume that a language A is reducible to language B. The claim is true?

if A is decidable then B is decidable too.

The correct answer is:

> This claim is wrong. If A is e.g. the empty language (which is clearly decidable) and B is $A\_{TM}$, then surely ∅ is reducible to $A\_{TM}$, but $A\_{TM}$ is undecidable. The claim is true the other way round: If B is decidable then A is decidable too.

I have problem to understand two points:

1. **A is e.g. the empty language (which is clearly decidable)**

Why empty language is ("clearly") decidable and $L\_∅$ is not?, where, $$L\_\emptyset = \\{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\\}.$$

1. \**A is reducible to $A\_{TM}$ \**

I have difficulties to image a reduction from $∅$ to $A\_{TM}$, where $A\_{TM} = \\{\<M,w\> | \ M \ is \ a \ TM \ and \ M \ accepts \ w\\}$

# Answer
1. By definition, a language $L$ is decidable if there exists a TM $M\mid L = L(M)$ deciding it. Consider a TM that rejects on all inputs (for example, one where $q\_o = q\_{\text{rej}}$). The language of this TM is $\emptyset$, so $L=\emptyset$ is decidable.
2. With reductions, in general if $A\leq B$ ($A$ reduces to $B$), then $B$ is at least as hard as $A$ with respect to decidability. An undecidable language $A\_{TM}$, regardless of what it actually is, is harder to decide than the decidable language $\emptyset$ by definition. The specifics of the reduction don't matter; the only information we needed was given in the problem statement (that $A$ is reducible to $B$).
> 1 votes

# Answer
Elucidium addresses most of your question; let me address the remaining point, which is why $\emptyset$ and $L\_\emptyset$ behave differently.

The point is that they're simply very different sets in the first place. For example, $\emptyset$ has no elements - that's its definition - while $L\_\emptyset$ is infinite (there are lots of Turing machines which don't do anything). Just because something is *related to* $\emptyset$ doesn't mean it *behaves like* $\emptyset$.
> 1 votes

---
Tags: turing-machines, undecidability, halting-problem
---


# Question
Title: Edmonds-Karp Algorithm with both directed and undirected edges?
How would this work and be implemented?

If you have directed edges pointing away from the source to a bunch of other verticies, and directed edges pointing from those vertices to a sink, but have those vertices in the middle linked by undirected edges, how would flow work and be maximized?

# Answer
> 2 votes
Replace each undirected edge $(u,v)$ by two directed edges, one in each direction: $u\to v$ and $v\to u$. That gives you a graph with only directed edges. Then the max-flow on that graph is the same as the max-flow on your original graph.

---
Tags: algorithms, graphs, network-flow, minimum-cuts
---


# Question
Title: Find a threshold such that one function is always bigger than the other
Given the recursively defined function $c$: $$c(m,n)=\begin{cases}0&\text{for }m=0\\ n^2+n+1&\text{for }m = 1\text{ and }n\ge 0\\ c(m-1, 1)&\text{for }m\>1\text{ and }n=0\\ c(m-1,c(m,n-1))&\text{for }m\>1\text{ and }n\>0\\ \end{cases}$$

and the function $d$:

$$d(n) = \underbrace{2^{2^{.^{.^{.^{.^{2}}}}}}}\_{\text{$n+2$ }}$$

The inputs $m$ and $n$ are both natural numbers. I'm asked to find an $x$, such that for all numbers $y \ge x$, $c(y,y) \> d(y)$.

I rewrote the two functions using Python in order to calculate some values:

```
 c(m, n):
    if m == 0:
        return 0
    else if m == 1 and n >= 0:
        return n**2+n+1              # return n^2+n+1
    else if m > 1 and n == 0:
        return c(m-1, 1)
    else if m > 1 and n > 0:
        return c(m-1, c(m, n-1))

```

```
 d(n):
    exp_num = n-1
    result = 2
    while exp_num != -1:
        result = 2**result           # result = 2^result
        exp_num = exp_num - 1
    final_result = 2**result         # final_result = 2^result
    return final_result

```

Some inputs and outputs:

`c(1, 1) = 3`

`c(2, 2) = 183`

`d(1) = 16`

`d(2) = 65536`

`d(3) = 20035299... 19156736`, a number with 19729 digits.

I believe the threshold is $3$, as `c(3, 3)` doesn't seem to be realistically computable considering there are over 19K digit in (4, 2). Unfortunately I have no idea how to prove this. Any help would be much appreciated.

# Answer
As you suspected, the threshold is indeed 3.

Here is one approach to prove that for all numbers $y \ge 3$, $c(y,y) \> d(y)$.

Step 0, show that $c(\cdot, \cdot)$ is strictly increasing with respect to each variable when the second variable is not 0.
Step 1, show that $c(1,n) \gt n^2$ for all $n\ge0$.
Step 2, show that $c(2,n) \gt 2^n$ for all $n\ge0$.
Step 3, show that $c(3,n)\gt d(n)$ for all $n\ge0$.
Step 4, show that $c(y,y) \gt d(y)\text{ if }y\ge3$.

---

**Exercise.** Show that $c(3,y) \> \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}\_{2y+2 \text{ copies of }2}$ for all $y\ge0$.
> 2 votes

---
Tags: recursion, proof-assistants
---


# Question
Title: Why does the effectiveness of my reinforcement based neural network recede after a while?
I have a reinforcement based neural network training on the OpenAI gym CartPole-v1 environment. For the structure and training algorithm, assume it is the same as the one in this article.

Typically, it averages becoming more effective, eventually perfectly solving the environment (500/500 reward for several hundred games in a row) but then starts to regress. Typically somewhere in the range of 100~150/500 total reward. This seems to happen regardless of learning rate, but I haven't tested with very low learning rates (less than 0.01) because of the amount of time it takes to train.

Can anyone tell me why this happens? I can't seem to find any literature on it, but perhaps I just don't know the name.

# Answer
It's been a couple of years since I asked this question, and my knowledge has advanced quite a bit in that time, so I figured I'd answer this as best I can.

This is, as far as I know, still an open research problem. Policy-gradient agents diverging after converging for a while is a known problem, and there are a variety of hypotheses around it. KL-divergence constraining techniques (PPO, TRPO) seem to help stabilize a bit, so it's likely something to do with KL-divergence.
> 0 votes

# Answer
There seems to be some kind of overfitting happening.It happens when noise and fluctuation in data is learned as concept by your Neural Network Model.

https://en.wikipedia.org/wiki/Overfitting
> 0 votes

---
Tags: machine-learning, neural-networks, reinforcement-learning
---


# Question
Title: How do I solve the part (a), of the following question?
The problem I'm facing is how do I know whether the mapping is "1-way set associative", "2-way set associative", "4- way set associative", etc.

Please help!

# Answer
> 0 votes
It's 32 way set associative mapping. How?

Each cache line has one block and it is given that one block has 8 words. It is already given it is a set associative mapping with set size as 256 words or 256/8 = 32 blocks (or 32 cache lines. As, each cache line holds one block). Hence it is 32 way set-associative mapping.

---
Tags: computer-architecture
---


# Question
Title: Understanding DIQKD protocol, a few questions
I'm refering to this paper here ***"Fully Device-Independent Quantum Key Distribution"*** (Umesh Vazirani and Thomas Vidick) and unfortunately there are many things I don't understand.

1) Page 3: by the word round, what do the authors actually mean? Is it right to say it's basically how many times Alice and Bob use their own devices?

2) Page 3, Testing section: this equality `aᵢ ⊕ bᵢ = xᵢ ∧ yᵢ` I was told it describes the requirement of the CHSH game. Alice input can be anything belonging to the set `{0,1,2}` while Bob's input can only be an element of the following set`{0,1}`. Their output can be `0` or `1`, respectively. The paper says ***"They compute the fraction of inputs in B that satisfy the CHSH condition aᵢ ⊕ bᵢ = xᵢ ∧ yᵢ..***". My understanding is: if ⊕ is exclusive OR and ∧ is logical AND then the following makes sense: `aᵢ=1 bᵢ=0` `1 ⊕ 0 = 1 ∧ 1` Is that correct? If I'm right what does the following expression mean? ***"If this fraction is smaller than cos2 π=8 − η they abort the protocol***"

---

***Cross-posted on quantumcomputing.SE***

# Answer
> 3 votes
All of these are defined in page 2 of that paper.

1) A **round** is a single interaction with the device: Alice gives it an input, Bob gives is an input, and the device outputs a bit to Alice and a bit to Bob.

2) While Alice's **input** is from the set $\\{0,1,2\\}$, the output she gets from the device, $a\_i$, is a single bit. Then, the equation $a\_i \oplus b\_i = x\_i \wedge y\_i$ is on bits (the case of $x\_i=2$ is treated separately). This equation is indeed the CHSH condition. If the bits where classical, the expected CHSH term is bounded by $2$, while if the system is quantum, values of up to $2\sqrt2$ are possible. By measuring the amount of times the equation holds you can estimate the value of the expected CHSH term, and if it is large enough, this implies the generation of "true" randomness.

There is a longer and more detailed version of that paper in https://arxiv.org/abs/1210.1810

---
Tags: quantum-computing
---


# Question
Title: Is arithmetic coding restricted to powers of $2$ in denominator equivalent to Huffman coding?
With restriction to $\frac{k}{2^n}$ as line segment ends, does arithmetic coding degrade to Huffman coding? As far as I can tell, each symbol will be encoded with an integer amount of bits, which is the same as Huffman coding. However, I'm not sure how to prove that arithmetic coding with this restriction is optimal for integer code lengths.

# Answer
You can't prove it because it's not true.

Arithmetic coding "degrades" to Huffman coding if all of the probabilities are of the form $2^{-k}$. Or, to put it another way, when the Kraft-McMillan inequality is an equality.
> 1 votes

# Answer
The simplest case: Two symbols A and B, one coming up with a probability 1/4 and one with probability 3/4.

Of course you have to explain now what exactly you mean with your restriction - I know arithmetic coding, but "line segments" seems to be a term coming from a particular implementation. (My view of arithmetic coding is that in theory every finite sequence of symbols is turned into a real number r in the interval \[0, 1), and we record the binary representation of the number r. And in practice, you modify this slightly to avoid a need for infinite precision. And nowhere does "line segments" come up).
> 0 votes

---
Tags: information-theory, data-compression, coding-theory, huffman-coding
---


# Question
Title: Why is recursive programming problematic for branch predictors
Consider for example the following recursive program:

```
function fibonacci(int n) {
    if (n < 2) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

```

The question is now, why recursive programs are problematic for branch predictors? I think that this is due to the fact that the branch-instruction inside these programs follows a very hard to predict pattern. When considering for example `fibonacci(4)`, it holds that

`fibonacci(4) = fibonacci(2) + fibonacci(3)`

`fibonacci(4) = fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(2)`

`fibonacci(4) = fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1)`.

Thus the following function calls will be performed in this order: `fibonacci(2), fibonacci(3), fibonacci(0), fibonacci(1), fibonacci(1), fibonacci(2), fibonacci(1), fibonacci(0)`. This results in following sequence of Taken / Not Taken for the if-statement: `NT NT T T T NT T T`, which is quite irregular.

My question is now, if my answer and reasoning is correct?

# Answer
> 4 votes
It would seem that recursion isn't the problem at all, but a pattern of branches that is hard to predict. For example, if you calculate n! using recursions (if n = 0 -\> return 1 else return n * factorial (n-1)) that should play very nicely with branch prediction. For example 25! will start with 25 taken branches, followed by one branch not taken.

If you calculated fib (n) by simulating the recursion using a stack, you would have mostly a loop, with the exact same branches inside the loop, and as far as branch prediction is concerned, it would be just as good / bad with no recursion anywhere in sight.

PS. This was about predicting whether a branch is taken or not taken. Newer processors use other branch-related predictions: Predicting the target of a branch (for example for virtual functions, where a branch will lead to one of possibly many implementations of a virtual functions), and prediction of the target of a "return" instruction, where the processor predicts that a "return" instruction most likely branches to the instruction after the previous "call subroutine" instruction.

# Answer
> 2 votes
Along with the problem of unpredictable T/NT patterns (as explained by the other posts), there is a problem with the return addresses.

The prediction of the return address is done by using the RAS (return address stack), which is a circular buffer containing the last called addresses. When a return instruction is used, the last address of the RAS is used and the RAS pointer is decreased.

The problem with recursion is that the size of the RAS is limited (such as 64 addresses). If you use Fibonacci with a big N, we have more than 64 function calls and the older addresses in RAS are overwritten. Since the return address is hard to calculate, we can not use the prediction and speculative execution for these overwritten addresses, resulting in a lot of thrown away executions in the pipeline.

---
Tags: computer-architecture, recursion, cpu
---


title: Is Reed Solomon also a Fountain code?

text:
# Question
Title: Is Reed Solomon also a Fountain code?
Once you encode your message as a polynomial you can effectively generate and stream an endless number of points on that polynomial of which only a finite subset would be required to recover the polynomial.

Why isn't Reed Solomon also a Fountain code? I have never seen it listed as such and I looked.

# Answer
> 4 votes
It's difficult to call Reed-Solomon a fountain code. This is due to two reasons.

The first reason is rather technical.
Let's assume you use a systematic code. After sending the message itself (the systematic part), the "fountain" is the remaining redundancy symbols = evaluation of the polynomial in other points. In order to be decoded correctly, you must attach to each symbol the index it belongs to, i.e., the point it is evaluated in. You cannot permute the symbols order and still decode correctly, hence the index is crucial.
So RS by itself doesn't fit the decoding properties of fountain codes, where any order of received symbols is OK. However, this is merely a technicality since you can always send the symbol along with its index (this is also done in fountain codes).

The second reason is more meaningful and inherent.
In a (systematic) $\[n,k\]$ block codes (e.g., Reed-Solomon), there are exactly $n-k$ redundancy symbols. That's it. You don't have a "fountain" of "infinite" number of redundancy symbols you can send. You only have $n-k$, and once the decoder receives enough of them it will be able to decode. Using RS notations, you can evaluate the polynomial only in points in the finite field $\mathbb{F}$, and there is a finite (and relatively small) amount of them.

So the "fountain" in block-codes reduces to only be re-sending the $n-k$ redundancy symbols again and again, and requiring the decoder to collect (almost) all of them. This is not as good as the properties fountain codes are providing.

# Answer
> 0 votes
I don't know the answer, but it seems that usual fountain codes have O(N) algos, while fastest RS algos are O(N\*log(N)) and non-incremental, and incremental ones are O(N^2).

---
Tags: error-correcting-codes
---


# Question
Title: Is finding a solution of a satisfiability problem harder than deciding satisfiability?
Is the problem of determining whether or not a given Boolean expression is satisfiable computationally distinct from actually finding a solution to the expression?

In other words, is there another way of finding that a given expression is satisfiable without explicitly determining the 'right settings' for the Boolean variables? Or do all possible proofs reduce in polynomial time to the 'right settings'?

Forgive my ignorance, I am only an engineering student. Wikipedia seems to imply that the act of *just* finding SAT or UNSAT is NP-complete.

# Answer
> 21 votes
As mentioned in a comment, any method of determining satisfiability of a Boolean formula can be easily converted into a method for finding the satisfying variable assignment. This is because Boolean satisfiability problems are downward self-reducible.

From Wikipedia:

## Self-reducibility

The SAT problem is self-reducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment. First, the question is asked on the given formula $Φ$. If the answer is "no", the formula is unsatisfiable. Otherwise, the question is asked on the partly instantiated formula $Φ$$\\{x\_1=TRUE\\}$, i.e. $Φ$ with the first variable $x\_1$ replaced by $TRUE$, and simplified accordingly. If the answer is "yes", then $x\_1=TRUE$, otherwise $x\_1=FALSE$. Values of other variables can be found subsequently in the same way. In total, $n+1$ runs of the algorithm are required, where $n$ is the number of distinct variables in $Φ$.

# Answer
> -5 votes
The correct answer is that the determining if a solution exists and determining a solution are computationally distinct. Not all methods for determining if a solution exists can produce a solution. There exists a solution to the Hamiltonian Path problem that can determine if a path exists but cannot produce any such path. That said the question is made moot by arxiv.org/abs/cs/0205064.

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


# Question
Title: Measuring Complexity of Boolean Satisfiability Problem
How exactly is the complexity of a SAT solver measured? My main concern is that, for $N$ variables, you can have, e.g., an OR of $O(2^N)$ AND terms, which would take at least $O(2^N)$ time to process. If the formula can contain duplicate sub-expressions, e.g., $(A \land B) \lor (A \land B)$, then the formula's maximum size is unbounded. In this case, wouldn't the complexity be better measured in terms of how complex the formula is, rather than how many variables it takes?

# Answer
> 7 votes
The *boolean satisfiability problem* (SAT) involves finding a satisfying truth assignment for a set of clauses $C$ over the boolean variables $V=\\{v\_1, v\_2, ..., v\_n\\}$ so that each clause in $C$ contains at least one true literal. Since $V$ contains $n$ variables and each of these variables can only have $2$ different values (i.e., true or false), the total number of possibilities to be tested is $2^n$. We don't know how to solve SAT in polynomial time (since SAT is NP-complete); therefore, all solvers take exponential time in the worst case. Fortunately, however, there exist several ways to prune the search space.

> Wouldn't the complexity be better measured in terms of how complex the formula is?

The importance of the SAT problem lies in that every decision problem in NP can be reduced to SAT for **CNF** formulas. Other restricted versions of SAT exist (such as 3-SAT, Horn-SAT, and XOR-SAT); these restricted versions can be either in P or NP depending on the restriction (see Schaefer's dichotomy theorem). Regardless of this, note that problems in NP (such as SAT) are characterized by solutions (in the case of SAT, truth assignments) that can be verified in polynomial time.

# Answer
> 4 votes
I think you have a misconception. SAT *by definition* accepts formulas in CNF form, and only in CNF form. Moreover, in practice, SAT solvers all use CNF form.

(You might find some tools that have a front-end/preprocessor that will convert a formula in some other format into CNF form then feed it to a SAT solver.)

The complexity of a SAT solver *isn't* measured. We know that in the worst case they can take exponential time, so we don't worry about trying to characterize their asymptotic running time via theory. Instead, think of SAT solvers as a heuristic: in the worst case they could take an extremely long time, but on real-world formula seen in practice, they often run much faster than that.

# Answer
> -3 votes
There are problems for which there is no reduction to SAT that is of P complexity. Those problems may or may not be solved by computations that can be performed in O(2^n) or less time and space. SAT is always worst case O(2^n) or less by definition.

SAT has a P complexity solution. See arxiv.org/abs/cs/0205064.

---
Tags: time-complexity, satisfiability, boolean-algebra
---


# Question
Title: Complexity class for polynomial algorithm for 3SAT, but with exponentially large values?
I have a hypothetical question: suppose there exists an algorithm that solves an NP-Complete problem polynomial time, but requires the computation of values that grow exponentially big (or small).

For example, suppose POLY-3SAT solves 3-SAT in N^17, however to do so it must compute/evaluate the value of a number C whose value grows as N^1000 (or 1/N^1000).

What would this imply? Does computing/evaluating an exponentially large value automatically place the algorithm in EXP-SPACE (or some other complexity class)? It seems like this would be a different complexity class than just ordinary P.

# Answer
Complexity classes are classes of problems, not classes of algorithms. For example, the existence of Dijkstra's algorithm means that the problem of computing shortest paths in graphs is in **P**, but it doesn't make sense to say that "Dijkstra's algorithm is in **P**".

Exponentially large values can be stored in binary in a polynomial numebr of bits, and we can compute on such numbers using a polynomial number of operations. This notwithstanding, it seems that you're trying to get a polnomial-time algorithm that somehow dows exponentially much work, which is an oxymoron.
> 5 votes

# Answer
It would imply that P = NP. The part about "values that grow exponentially big" is irrelevant; the same remark is true of any algorithm that solves a NP-complete problem in polynomial time.

A number whose value is as large as $N^{1000}$ is not a problem. It takes $1000 \lg N$ bits to represent such a number. You can add two such numbers in $O(\lg N)$ time, and multiply them in $O((\lg N)^2)$ time, which is polynomial in the input size.

Make sure you understand the difference between the size of the input and the input itself -- i.e., the difference between the value of a number and the number of bits needed to represent that number. I suggest you take a look at Relationship between an integer N and the number of bits n required to represent the integer, Complexity of multiplication, Time complexity of addition, Why addition algorithm is not pseudo- polynomial?, How can we assume that basic operations on numbers take constant time?.
> 3 votes

# Answer
If there exists an algorithm that solves NP-complete in P time and space then the values computed cannot grow exponentially. A problem in which the values computed grew exponentially would not be an NP-complete problem, as it could not be reduced to SAT by any P complexity algorithm.

The answers that the problem and not the algorithm are defining of complexity are incorrect. The problem has no inherent complexity. We say a problem is of X complexity based on the best known algorithm that can solve all possible instances of it. SAT defines the set of problems for which the best publicly known means to solve all possible instance was exponential in the number of variables (bits in the case of Boolean expressions).

However, given the time frame mentioned in arxiv.org/abs/cs/0205064 there existed a solution not publicly known to the specific problem before it the problem was publicly known and determined to not have a known P complexity solution.
> -2 votes

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


# Question
Title: Thirty-one game. Prediction of the winner
I have a problem with creating an algorithm to predict a winner of thirty-one game.

Players from a deck of cards, take the Ace, 2, 3, 4, 5, and 6 of each suit. These 24 cards are laid out face up on a table. The players alternate turning over cards and the sum of the turned over cards is computed as play progresses. Each Ace counts as one. The only limit is the sum value of stacked cards: it cannot exceed 31. The player who cannot make a move loses.

My task is to determine the winner in the game based on stack of cards put aside. We assume that both players play perfectly.

For example:

`356656` means gameplay: player A puts down 3, player B puts down 5, player A puts down 6, player B puts down 6, player A puts down 5, finally player B puts down 6 and wins because player A cannot make any move.

```
356656 -> winner B
35665 -> winner B
3566 -> winner A
111126666 -> winner A
552525 -> winner A
2 -> winner A

```

# Answer
> 1 votes
This kind of question can be answered using a simple recursive procedure.

A *state* of the game consists of:

* a sequence $a\_1,\ldots,a\_n$ describing how many cards of each value in $1,\ldots,n$ remain (in your case, $n = 6$).
* the number of "points" remaining $p$.

Your initial state is $\vec{a}=(4,4,4,4,4,4)$ and $p = 31$.

For each state $(\vec{a},p)$, there is a sequence of possible moves, which in this case is $$ N(\vec{a},p) = \\{ (a\_1,\ldots,a\_{i-1},a\_i-1,a\_{i+1},\ldots,a\_n),p-i : i \in \[n\], a\_i \geq 1, i \leq p \\}. $$ Let us say that a position is *winning* if the first player wins when starting from it. A position is winning iff there is a next position which is losing, and so the winning predicate $W(\vec{a},p)$ satisfies the recurrence $$ W(\vec{a},p) = \bigvee\_{\vec{b},q \in N(\vec{a},p)} \lnot W(\vec{b},q). $$ When $N(\vec{a},p) = \emptyset$, the disjunction is empty, and so $W(\vec{a},p)$ is false.

In your case, you can easily calculate $W((4,4,4,4,4,4),31)$ to be true. The winning moves are $1,2,5$.

Here is `sage` code that calculates this:

```
@CachedFunction
def game(cards, target):
    return [i for i in range(len(cards)) if target >= i and cards[i] >= 1\
    and len(game(cards[:i] + (cards[i]-1,) + cards[i+1:], target-i)) == 0]

```

This code also allows cards with value zero. You can run it like so:

```
sage: game((0,4,4,4,4,4,4),31)
[1, 2, 5]

```

It outputs the set of winning moves (if any).

---
Tags: algorithms, game-theory
---


# Question
Title: Why multiple rotations might be needed after deletion in an AVL tree if after insertion there can be at most one needed?
I understand that after deletion you have to retrace to update ancestors and after insertion you do the similar however at most one rotation will be performed.

The question is why is there the difference in number of potential rotations for these two operations.

To me it seems like these operations should be the reverse of each other but this difference in their properties suggests they're not. Why?

# Answer
Adding one element to a set, versus deleting one element from a set, are indeed rather symmetric operations. You are right.

However, in the case where the sets are represented by a tree, the two operations turn out to be asymmetric. When adding an item one branch may be too long, and one well-chosen rotation will rebalance. When deleting an item one branch may be too short, and the local rotation needed to rebalance will change the height of the current tree, so we may be forced to repeat rotating at other spots.

So it seems that "too long" and "too short" are not symmetric for tree rotations.

There are various other set representations that are not symmetric with adding and deleting.

We can keep sets as unordered arrays. Adding is easy, just put a new item at the end. Deleting is slightly harder. Assuming we have actually found the item, it is removed in the array, and then the last item is moved to the open spot.

We can also keep sets as hash-tables, with open adressing. Then adding has a standard solution, but deleting is hard, as doing it in the naive way may make other items untraceable (when we have a method other than linear probing).
> 1 votes

---
Tags: trees, avl-trees
---


title: Is a^mb^n where m=n^2 a CFL?

text:
# Question
Title: Is a^mb^n where m=n^2 a CFL?
Is $a^mb^n$ where $m=n^2$ a CFL?

---

I have a doubt regrading this problem. Say if we pop $n$ number of $a's$ from the stack for each $b$ then it is a CFL (to be exact DCFL) right?

On the other hand I have this doubt, do we know the number of $b's$ we are provided with, if not how can we pop $n$ number of $a's$ for each $b$? So this case doesn't make it a CFL right?

Which of these 2 cases are applicable? Are we always aware of the number of $b's$ we have? Then shouldn't it be a *regular language*?

# Answer
> 3 votes
This is not a context-free language, as an immediate consequence of Parikh's theorem.

In terms of pushdown automata, there is no way for a PDA to keep track of the number of $b$'s in the string in a way it can access *repeatedly* while reading (or popping) the $a$ part of the string. This is an essential feature of context-free languages; it is the same reason why languages such as $\\{a^n b^n c^n d^n | n \> 0\\}$ are not context-free.

For more examples, check out our reference question on proving languages are not context-free.

# Answer
> 3 votes
Here is an alternative argument. Let $h$ be the homomorphism given by $h(a) = \epsilon$, $h(b) = b$. Then $$ h(L) = \\{ b^{n^2} : n \geq 0 \\}. $$ If $L$ were context-free, then $h(L)$ would be unary context-free, and so regular. But $h(L)$ is not eventually periodic.

You can also show that $h(L)$ is not context-free using the pumping lemma. The pumping lemma gives us a constant $p$ such that $b^{p^2}$ can be partitioned into $uxyzw$, where $|xyz| \leq p$, $|xz| \neq 0$, and $ux^iyz^iw \in h(L)$ for all $i \geq 0$. Let $|xz| = q$. Then $ux^2yz^2w = b^{p^2+q}$, but $p^2 \< p^2+q \leq p^2 + p \< p^2+2p+1 = (p+1)^2$, and so $b^{p^2+q} \notin h(L)$.

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


title: Cellular Automata Using Small Boards

text:
# Question
Title: Cellular Automata Using Small Boards
I'm working on making patterns for a digital lava lamp (essentially, making interesting patterns using a 4x10 grid), and I've been looking into cellular automata. I tried implementing some variations on Langton's Ant but it tends to loop in very boring ways. Does anyone have any suggestions for interesting automata on small boards?

The lamp I'm working on can be played with here.

Any suggestions on a more appropriate place to post this question are welcome.

EDIT: By interesting, I mean patterns that work well on small boards. For example, Langton's Ant was not interesting because it always tended to find some static state over such a small board.

# Answer
> 1 votes
"interesting" is very subjective.

You could try Brian's Brain or Brian's Seeds, both of which I find interesting.
http://en.wikipedia.org/wiki/Seeds\_%28cellular\_automaton%29

While they are designed for an infinite plane, you could wrap your 4x10 grid at the top and bottom presenting a theoretical sphere instead of a plane.

As a interesting thought, you could start with Langton's ant and then add a swarm to the ant, then chose a random element of the swarm to take over control for the next X iterations.

# Answer
> 1 votes
The smallest "interesting" cellular automaton I know of is an ant that counts in binary. It's the same as Langton's Ant, except where Langton's Ant turns to the right on a black (or lit) square, this one doesn't turn and just continues forward. (On a white/unlit square, it still turns to the left like Langton's does.)

(Its rule is **RN** in the "multi-color ant" naming scheme, or **120010** in the "multi-state ant" or general "turmite" naming scheme.)

It counts in single pixels, but is symmetrical around both axes, so it will use 2x10 pixels to count in 5 bits (from 0 to 31).

---
Tags: automata, cellular-automata
---


title: Copy operation in under 9 states?

text:
# Question
Title: Copy operation in under 9 states?
There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following graphic the machine is denoted by a yellow line. It is immediately to the right of a series of three 1’s followed by many 0’s.

The machine is tasked to make a copy of the 1’s. When finished, the copy must be separated from the original by a single cell containing a 0. The final resting place for the machine is immediately to the right of the original 1’s. The following graphic shows the cells after the machine has fulfilled its copy task.

At each step the machine must decide whether to move left one cell or right one cell, and whether to write 0 or 1 to the cell that it is currently positioned at. The machine cannot see what is in the neighboring cells. It can only see the value in the current cell. The machine makes its decision based purely in the current cell’s value and on the decisions it made previously.

I was able to program the machine to perform the copy operation using nine states (S0 – S8).

QUESTION: Is there a way for the machine to perform the copy operation in less than nine states?

The above graphics show just one example, in which three 1’s are copied. Of course, the machine must be able to perform the copy operation on any number of 1’s.

The diagram below shows the nine states that I needed. But first, here is an explanation of a notation used in the diagram:

Here is the strategy I used: As described above, the 1’s must be copied. How to know which 1’s have been copied and which remain to be copied? Answer: Shift the leftmost 1 to the left one cell and then copy it. Repeat for the next leftmost 1. And so on. There will be a series of shifted 1’s that have been copied and a series of unshifted 1’s that remain to be shifted and copied. Once there are no more unshifted 1’s, the machine is done. State 0 is the final state. State 1 is the starting state.

# Answer
> 0 votes
Input: 0^a 1^b 0^c with a + c \>= b + 1

Output: 0^z 1^b 0 1^b with b + z + 1 = a + c

Strategy:

1. Move 1^b to the back of the tape
2. Copy 1^b immediately to the left
3. Clean up

States:

* q0: scan left until you see 1; if beginning of tape, continue with state q3. Otherwise, change 1 to 0 and continue to q1
* q1: scan right until blank or 1; then, move left and continue with state q2
* q2: change 0 to 1, go left, and continue with q0
* q3: scan right until you find 1; if you do, change 1 to 2, move left and continue with step q4; otherwise continue with state q6
* q4: scan left until you find 0; then, move right and continue with state q5
* q5: scan left until you find 0; when you do, change it to 2, move right, and continue with state q3
* q6: scan left until you find a blank, changing all 2s to 1s along the way. then, halt-accept.

If you count halt-accept as its own state, this has 8 states, so it's at least one better than the one you gave (if this one works). Here's how I'd see it processing your example:

```
   0000001110: q0
-> 0000001101: q0, q1, q2, q0
-> 0000001011: q0, q1, q2, q0
-> 0000000111: q0, q1, q2, q0
-> 0000020211: q0, q3, q4, q5, q3
-> 0000220221: q3, q4, q5, q3
-> 0002220222: q3, q4, q5, q3
-> 0001110111: q3, q6, halt-accept

```

---
Tags: finite-automata, turing-machines
---


# Question
Title: Union of a language in P and a language in NP\P
TRUE or FALSE Statement:

> Assume that $P \neq NP$. Then, for all languages $L\_1$ and $L\_2$, if $L\_1$ is in P and $L\_2$ is in NP but not in P then $L\_1 \cup L\_2$ is in NP but not in P.

I have a doubt about the point: *$L\_1 \cup L\_2$ is in NP but not in P*.

I know P is a subset of NP, then $L\_1 \cup L\_2$ is in NP (because $P \subseteq NP$), but the sentence "is in NP but not in P" it puzzles me.

# Answer
From an Hint (by Yuval Filmus), the statement is FALSE because if $L\_1=Σ^∗$ then $L\_1 \cup L\_2=Σ^∗$. I know $Σ^∗$ is in P (i.e., a TM which accepts all strings), and the statement is FALSE.
> 1 votes

---
Tags: complexity-theory, np
---


# Question
Title: Can a 2-way set associative mapping have just one set?
Though unintuitive, can a 2-way set associative mapping have only one set. For e.g., Cache size 8 bytes, block size 4 bytes and main memory size as 16 bytes. Here the number of cache lines are 2 and given 2 way set associative the set count is only 1. Can I map the 4 blocks (0,1,2 and 3) in the main memory to a 2-way set associative mapping?

If I can, what would be the set index? Since the set size is 1 = 20. is set index always 0. \[in CPU OS simulator, it is not throwing any error when I try to set the cache and block size and mapping as 2-way\]

# Answer
> 0 votes
Set index will be 0 or no set index. Set associative mapping has set identification algorithm the same as direct mapping which is j mod m, where j is the main memory line and m is the total set count. Here in this case, main memory has 4 main memory lines ( 0, 1, 2 and 3 with each having 4 bytes). Now set count is 1, hence 0 mod 1, 2 mod 1, 3 mod 1 and 4 mod 1 are all 0 which means all blocks will get mapped to Set 0 and within the set 0, the mapping is fully associative. The behaviour and mapping is more like fully associative mapping. hence for a set-associative mapping, a 2-way set associative mapping with 2 cache lines or a 4-way set associative mapping with 4 cache lines etc., behaves like fully associative and set index width is 0. Generalizing, a K-way set associative mapping with K cache lines only will behave like a fully associative mapping.

---
Tags: cache
---


# Question
Title: Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?
I understand the difference in the parsing tables of the above 4 parsers. I understand that CLR\>LALR\>SLR\>LR(0) in terms of power.

Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?. I think goto should vary as reduce moves vary? Also, if a grammar is accepted by CLR(1) parser, for which parser it would have highest and lowest no. of reduce moves or would it be the same? Please explain

# Answer
> 2 votes
Every reduce action corresponds to a production; the action "undoes" the production by replacing its right-hand side with the non-terminal which produced it.

That can only happen in one way; the parsing automaton does not invent or suppress non-terminals. So it doesn't matter which algorithm was used to create the automaton; the actions will be the same.

The automata may have different numbers of states, so the state sequence may differ. But not the actions performed on state transitions.

To put it another way:

If a grammar has an \*LR automaton, the grammar is unambiguous, which by definition means that there is only one rightmost derivation. A rightmost derivation, written backwards from sentence to start symbol, can be represented as a series of shifts and reduces. Any LR grammar which recognises a sentence in this grammar must produce the same rightmost derivation, so it must perform the sane sequence of shifts and reduces.

# Answer
> 0 votes
They can all be derived from the LR(0) table - in fact directly so, if using the right kind of analysis. But the result may involve state-splitting. The same LR(0) state may appear in 2 or more LR(k) contexts, making necessary a split into nearly duplicate copies. Each copy differs in terms of which further restrictions it imposes; the restrictions borne of which lookaheads are present.

The Wikipedia article on SLR parsing describes the situation a little better https://en.wikipedia.org/wiki/Simple\_LR\_parser. Both SLR(1) and LALR(1) work off the same tables. Neither table splits any states from the LR(0) parsing table (a point made clear in the LALR Wikipedia article https://en.wikipedia.org/wiki/LALR\_parser), but may impose look-ahead restrictions on reduce actions.

The historically standard method for LR(k) for k \> 0 (especially for k \> 1!) uses the same number of lookaheads for every state - even when it's not necessary to do so. So, many more splittings may occur as a result. https://en.wikipedia.org/wiki/Canonical\_LR\_parser

A minimal LR parser for LR(k), in effect, will keep k at the smallest possible value that resolves conflicts for a given state. So, it can be LR(0) 90% of the time and maybe LR(1) or LR(2) or higher for a few bothersome states. It's LR(ω) with variable k ∈ {0,1,2,3,...} = ω.

The ability to talk about this more cogently is greatly impeded by the fact that the LR formalism, itself, is not fully self-contained in an important sense. The parsing tables only describe part of what the parser does. The all-important "roll-back" actions do not explicitly appear anywhere in the table (though they can be derived from what's in the table) and they are not represented directly by the parser itself but only indirectly by either a separate narrative description or separate procedural/algorithmic description. In YACC, that "separate" account is traditionally the "skeleton" use to create the cookie-cutter code that appears in YACC code output.

It is possible to bring it all together within a fully unified, algebraic, framework using a newly-published algebraic framework for context-free expressions; and I'm strongly tempted to describe it in detail here; but this would make the reply an order of magnitude larger. Within this setting it is easier to describe what the different methods are doing.

If there's enough interest I may post the fuller account in a followup; but will hang onto it, in the meanwhile for now.

---
Tags: context-free, compilers, parsers, lr-k
---