# Question
Title: Empirical Risk and True Risk - Generalization Error Proof
I showed that, over an uncountable domain,learner A and a distribution P, such that for every sample size m and all samples S from $P^m$ $$ : L\_S(A(S)) − L\_P (A(S))| = 1 $$ Now I wanna prove for countable domains. Lets assume X = N. I wanna prove that, for sample size m, and every $\epsilon\> 0$, there exists a learner A and a distribution P over X, such that for all samples S from $P^m$ we have $$ |L\_S(A(S)) − L\_P (A(S))| ≥ 1 − \epsilon $$

Not sure how to go about it. Any help is appreciated.

# Answer
This answer (as, I presume, the question) uses the notation of the book *Understanding Machine Learning: From Theory to Algorithms* by Shai Shalev-Shwartz and Shai Ben-David.

Suppose our domain set is $\mathbb N$ and we are interested in binary classification. We want to show that there exists a distribution $P$ on $\mathbb N$ and a learning algorithm $A$ such that the difference between the *empirical error* $L\_S(A(S))$ of the hypothesis $A(S)$ produced by $A$ given the finite sample set $S$ and the *true error* $L\_P(A(S))$ is large, i.e. the hypothesis $A(S)$ performs well on the training data but does not generalize.

So to prove the statement, let $m \geq 0$ and $\varepsilon \> 0$ and consider a binary classification scenario over the domain set $\mathbb N$.

We define a learner $A$ as follows: Given a set $S \subset \mathbb N \times \\{0, 1\\}$ of $m$ samples, $A$ outputs the hypothesis $$ h\_S(x) = \begin{cases} y, & \text{if } (x, y) \in S \\ 0, & \text{otherwise}. \end{cases} $$ Clearly, the empirical error of the hypothesis produced by $A$ will be $0$ for any training set $S$ as we defined the output of $A$ specifically to be correct for all samples in $S$.

It remains to construct a probability distribution over $\mathbb N$ such that the true error of the hypothesis $A(S)$ is at least $1 - \varepsilon$ for any choice of $S$. Recall that the true error of a hypothesis $h$ w.r.t. a distribution $P$ is defined as $$L\_P(h) = \Pr\_{(x, y) \sim P}\[h(x) \neq y\].$$

We now fix the labels in our distribution to always be 1 to ensure that $A(S)$ errs on all inputs not contained in the sample set $S$. Hence the task now reduces to assigning probabilities to each $n \in \mathbb N$ such that the combined probability of any $m$ points forming such a sample set is bounded by $\varepsilon$. To achieve this, consider the distribution $P \colon \mathbb N \to \[0, 1\]$ with $$ P(n) = \begin{cases} \varepsilon / m, & \text{if } n \leq m - 1 \\ \varepsilon / (m \cdot 2^{n - m + 1}), & \text{otherwise}. \end{cases} $$ If we consider any sample set $S \subset \mathbb N$ of size $m$, we find that $$ \Pr\_{x \sim P}\[x \in S\] = \sum\_{n \in S} P(n) \leq \sum\_{n \in S} \frac{\varepsilon}{m} = \varepsilon.$$ Hence, using the learner $A$ on a sample set $S$ of size $m$ drawn using the distribution $P$ yields a hypothesis $h\_S$ with $$ \begin{align} L\_P(A(S)) &= \Pr\_{x \sim P}\[h\_S(x) \neq 1\] \\ &= \Pr\_{x \sim P}\[x \notin S\] \\ &= 1 - \Pr\_{x \sim P}\[x \in S\] \\ &\geq 1 - \varepsilon. \end{align} $$ To finish everything off, recall that we defined $A$ such that $L\_S(A(S) = 0$, yielding $$|L\_S(A(S) - L\_P(A(S))| \geq 1 - \varepsilon.$$
> 2 votes

---
Tags: machine-learning, computation-models, learning-theory
---


# Question
Title: minimum number of states in cross product of two minimum DFAs
If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of states in cross product DFA = num of states in FA1 x Num of states in FA2). How to think on this?

# Answer
You probably know that if $\cal A$ and $\cal B$ are DFA, then their product recognizes the language $L({\cal A}) \cap L({\cal B})$. Now if ${\cal A} = {\cal B}$, then $L({\cal A}) \cap L({\cal B}) = L({\cal A})$. Thus if $\cal A$ is a minimal DFA with at least two states, ${\cal A} \times {\cal A}$ is never minimal.
> 2 votes

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


# Question
Title: Computing morphic word produced by uniform morphism
Let $\Sigma = \\{a,b,c\\}$, and consider the function $f\colon \Sigma \to \Sigma^\*$ given by $f(a) = abc$, $f(b) = bac$, and $f(c) = cba$. We can extend $f$ to $\Sigma^\*$ in the obvious way. Since $f(a)$ starts with $a$, it can be shown inductively that $f^{(n-1)}(a)$ is a prefix of $f^{(n)}(a)$ for every $n$, where $f^{(n)}(a)$ is the result of applying $f$ on $a$ for $n$ times: \begin{align} &f^{(0)}(a) = a \\ &f^{(1)}(a) = abc \\ &f^{(2)}(a) = abcbaccba \end{align} and so on. Hence the sequence $f^{(n)}(a)$ converges to an infinite limit word $f^{(\infty)}(a)$.

> How do I compute the $i$'th symbol of $f^{(\infty)}(a)$?

# Answer
> 0 votes
Denote $f^{(\infty)}(a)$ by $w$. Thus $f(w) = w$. Let $w\_0,w\_1,w\_2,\ldots \in \\{a,b,c\\}$ be the individual symbols of $w$. The crucial observation is that if $n = 3m + r$ for $r \in \\{0,1,2\\}$ then $$ w\_n = f(w\_m)\_r. $$ Indeed, since $w = f(w)$, we have $$ w\_0 w\_1 w\_2 w\_3 w\_4 w\_5 w\_6 w\_7 w\_8 \ldots = f(w\_0 w\_1 w\_2 \ldots) = f(w\_0) f(w\_1) f(w\_2) \ldots, $$ from which this formula can be recovered.

This gives a very simple recursive formula for computing $w\_n$: $$ w\_n = f(w\_{\lfloor n/3 \rfloor})\_{n \bmod 3}, $$ with base case $w\_0 = a$.

A similar approach works for every morphic word produced by a uniform morphism (one in which $|f(\sigma)|$ is the same for all $\sigma \in \Sigma$).

---
Tags: word-combinatorics
---


# Question
Title: Is “A -> aAA” convertible to regular grammar?
I have a simple grammar as below and wonder if it is convertible to regular grammar?

If yes, what is the conversion sequence? If no, how can we prove it?

```
S -> A
A -> aAA | b | c

```

In which S is the start symbol; A is non-terminal; a b c are terminals.

Any help or suggestion is appreciated.

# Answer
> 2 votes
You can prove inductively that any word $w$ generated by your grammar satisfies $$\\#\_b(w) + \\#\_c(w) = \\#\_a(w) + 1.$$ Also, you can prove inductively that for every $n$, your grammar generates a word having $a^n$ as a prefix.

You can now use the pumping lemma to show that the language generated by your grammar isn't regular.

Variant: intersect the language generated by your grammar with $a^\*b^\*$ to get an explicit language which is not regular.

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


title: IDE and EIDE data transfer speed

text:
# Question
Title: IDE and EIDE data transfer speed
Why are data transfer speeds faster with EIDE than IDE? Wouldn't it be slower with the additional conversion of logical block addressing? What did they change to make it faster?

# Answer
**tl;dr**: 25 times the clock frequency and two transfers per clock cycle equals 50 times the data rate.

First of all, let's forget about the terms *IDE* and *EIDE*. They were never specified in any standard or reference, and they were used in widely different manners by different people.

Some people use the term *IDE* (Integrated Drive Electronics) for *any* interface where the drive controller is integrated into the drive hardware, i.e. they use the term *IDE* to refer to any ATA, SATA, SCSI, SAS, IEEE1394, USB, or Thunderbolt drive. Some use it to refer to ATA-1 and the proprietary predecessors *only*, some use to refer to all ATA versions. Some people use the term *EIDE* to *exclusively* refer to ATA-2, some use it to refer to ATA-2 and ATA-3, some to any standard starting with ATA-2, excluding SATA, and some to any standard starting with ATA-2 *including* SATA.

So, let's stick to just official ATA versions, and let's call the proprietary versions before ATA-1 *pre-ATA*.

(Almost) every new ATA version has introduced new transfer modes, starting with the very simple PIO 0 transfer mode of pre-ATA. Each transfer mode has its own maximum transfer rate and cycle time.

Looking at Wikipedia, those were:

* **pre-ATA**:
    + *PIO 0* \[3.3 MBs | 660 ns\]
* **ATA-1**: adds
    + *PIO 1* \[5.1 MBs | 383 ns\]
    + *PIO 2* \[8.3 MBs | 240 ns\]
    + *Single-word DMA 0* \[2.1 MBs | 960 ns\]
    + *Single-word DMA 1* \[4.2 MBs | 480 ns\]
    + *Single-word DMA 2* \[8.3 MBs | 240 ns\]
    + *Multi-word DMA 0* \[4.2 MBs | 480 ns\]
* **ATA-2**: adds
    + *PIO 3* \[11.1 MBs | 180 ns\]
    + *PIO 4* \[16.7 MBs | 120 ns\]
    + *Multi-word DMA 1* \[13.3 MBs | 150 ns\]
    + *Multi-word DMA 2* \[16.7 MBs | 120 ns\]
* **ATA-3**: drops all *Single-word DMA* modes
* **ATA/ATAPI-4**: adds
    + *Ultra-DMA 0* \[16.7 MBs | 240 ns ÷ 2\]
    + *Ultra-DMA 1* \[25.0 MBs | 160 ns ÷ 2\]
    + *Ultra-DMA 2* \[33.3 MBs | 120 ns ÷ 2\]
* **ATA/ATAPI-5**: adds
    + *Ultra-DMA 3* \[44.4 MBs | 90 ns ÷ 2\]
    + *Ultra-DMA 4* \[66.7 MBs | 60 ns ÷ 2\]
* **ATA/ATAPI-6**: adds
    + *Ultra DMA 5* \[100 MBs | 40 ns ÷ 2\]
* **ATA/ATAPI-7**: adds
    + *Ultra DMA 6* \[133 MBs | 30 ns ÷ 2\]

Note that the Ultra DMA 4, 5, and 6 transfer modes required 80-wire ribbon cables instead of the older 40-wire ribbon cables. The 80-wire ribbon cables still had 40 connectors with the same pinout and semantics as the older cables, every other wire was a ground wire that was intended to provide physical separation as well as reduce capacitative coupling between the signal wires.

Also note that the Ultra DMA modes have two transfers per clock cycle, hence Ultra DMA 0 has the same maximum transfer rate as PIO 4 at half the clock speed.

Also, later versions introduced *independent device timing*, which allowed the host adapter to talk to each of the two devices on the bus with a different timing, whereas before that, it had to use the timing of the slower of the two devices.

Other than improvements to the transfer mode, there were also improvements to the command set that improved performance especially with multiple drives per bus. Originally, commands were completely serialized. The host adapter was only allowed to send a new command once the previous command was finished. ATA/ATAPI-4 introduced *overlapped commands* and *queued commands* as optional extensions to the *ATA Command Set (ACS)*.

*Overlapped commands* allow the host adapter to send overlapping commands to both Device 0 and Device 1 on the bus, i.e. it allows the host adapter to *parallelize* communication with the two devices. *Queued commands* allow the host adapter to place multiple commands in a queue on the device, thus allowing the device to schedule the commands in a way that makes most sense for the device.

E.g. imagine, there is a `WRITE` command to write `A` into block `23`, another `WRITE` command to write `B` into block `23` and a `READ` command for block `23`, the drive could just throw away the first `WRITE` command, have the `READ` command immediately return `B` without even moving the read head, and only execute the second `WRITE` command.

However, neither overlapped nor queued commands were actually widely implemented because they caused a large load on the host CPU due to the way they were designed for backwards-compatibility with the ISA bus (from which the original pre-ATA bus was derived in 1986 and even the very latest version of Ultra DMA 6 in 2005 still had to be compatible with). Placing this large load on the host CPU meant that in most cases, while raw drive performance might have slightly increased depending on workload, the *overall* system performance didn't improve.

So, performance improvements were mostly made by improving the transfer mode, mainly by increasing the clock frequency (from 1.67 MHz in pre-ATA all the way up to 41.67 MHz in Ultra DMA 7), and later making two transfers per clock cycle (Ultra DMA). The command set added (optional) features for performance improvements as well, but those features were widely ignored.

Using DMA transfer as opposed to Polling I/O also helped, especially reducing load on the host CPU.
> 3 votes

---
Tags: memory-hardware
---


title: CYK - finding the closest word accepted

text:
# Question
Title: CYK - finding the closest word accepted
Let's say I have a context-free grammar G and a string S. The normal CYK algorithm outputs that s can not be build using G. How would I find the closest String S' that can be build using G?

# Answer
> 2 votes
Your problem has been solved by Myers, Approximately Matching Context-Free Languages. A more recent algorithm, together with many relevant pointers, is Rajasekaran and Nicolae, An error correcting parser for context free grammars that takes less than cubic time.

---
Tags: context-free, parsers, normal-forms
---


# Question
Title: Expressivity of neural networks, how much information can be stored
I want to know whether a given neural network (with a finite number of nodes) is able to store all injective maps f: D -\> C, where D has cardinality k and C has cardinality N (so the number of maps is N! over (N-k)! ). For example is a network with 1000 nodes able to store 60 injective maps from {1,2,3} to {1,2,3,4,5}?

(By storing information I mean something like: when classifying information the network can access and use the information)

In particular I was curious if the above question can be translated to a question about the VC-dimension of a neural network. Can a question about storing injective maps in a neural network be translated to a question about the VC-dimension of a neural network?

EDIT: I’m interested in something like the following result

There are 60 functions, note that we can represent this with 6 bits The codomain consists of 5 elements, which can be encoded by 3 bits (since 5 \< 2^3) We need to map 3 elements of the domain to an element of the co-domain, so we need 3 times 3 bits for each function So to encode 60 functions we need 60 * 3 * 3 bits

In general we need (N! / (N-k)! ) * k * log\_2(N) bits Note that (N-k+1)^k \< N! / (N-k)! \< N^k and even (N-k)^k \< (N! / (N-k)! ) * k * log\_2(N) \< N^k

One weight in a neural network is 32 bits If we have X weights, then we have X\*32 bits

So if X\*32 is smaller than log\_2(N-k) * k, then it’s not possible to express all the functions in the network \[I’m actually more interested in negative results like the one I gave, sorry if that’s confusing. Positive results are welcome as well.\]

# Answer
> 1 votes
You're probably not going to get a theoretical answer, because analyzing exactly what set of functions can be computed by a particular neural network is messy. Or, at least, you probably won't get a tight analysis. There are theorems showing that neural networks are universal approximators, meaning that given sufficient capacity it is possible to express every function, but this doesn't tell you the minimize size needed to express every function; it just tells you that there exists a size that is large enough.

However, if you're willing to accept empirical evidence rather than theorems and proofs, research has demonstrated empirically that if you choose a deep neural network architecture with sufficient capacity and you train for long enough, neural nets can memorize the training set and achieve 100% accuracy on the training set, at least for a randomly chosen function $f$ \[1\]. This may not tell you exactly what size neural network you need to ensure that it can express all such functions, and it's not a proof or a guarantee.

The VC dimension is beautiful theory but it's not clear it has a great deal of relevance to modern use of neural networks in practice.

\[1\] Understanding deep learning requires rethinking generalization. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals. arXiv:1611.03530

---
Tags: complexity-theory, machine-learning, neural-networks, space-complexity, kolmogorov-complexity
---


title: Iterate unique sets of integers

text:
# Question
Title: Iterate unique sets of integers
I'm trying to figure out of if there's a way to generate all unique sets of integers of length K, where each member has an upper bound of N, and a lower bound of M, without tracking which sets have already been generated, where the order doesn't matter.

To be clear: I'm not looking for ways to filter duplicates from a pre-computed set of sets.

I'm asking if there is an algorithmic approach to generate the unique combinations of values, without producing duplicate combinations/repetitions along the way that must be tested for and removed.

For example, I wrote this counter, which will generate all sets of length K with members bounded at N, but with duplicates.

JavaScript:

```
function count(k, n, m = 0) {
    // Create counting columns
    let cols = Array(k).fill(m);
    let rows = [];

    while (true) {
        rows.push(cols.slice(0));

        for (let j = 0; j < k; ++j) {
            ++cols[j];

            if (cols[j] <= n) {
                break;
            } else if (j === k - 1) {
                return rows;
            }

            // If no overflow, reset column and increment the next on next loop
            cols[j] = m;
        }
    }
}

```

Output:

```
> let k=3, n=5, m=1

> count(k, n, m).join('\n');

"1,1,1
2,1,1
3,1,1
1,2,1
2,2,1
3,2,1
1,3,1
2,3,1
3,3,1
1,1,2
2,1,2
3,1,2
1,2,2
2,2,2
3,2,2
1,3,2
2,3,2
3,3,2
1,1,3
2,1,3
3,1,3
1,2,3
2,2,3
3,2,3
1,3,3
2,3,3
3,3,3"

```

But, as you can see, that produces 1,2,3 as well as 3,2,1.

An example case: if I'm searching for sums of cubes that equal a cube, I don't need to test `2^3 + 16^3 + 12^3 = 18^3` if I've already checked that `2^3 + 12^3 + 16^3 = 18^3`.

So I wouldn't want to generate an equivalent set again after having already tested an alternate order of the same terms.

Many thanks.

# Answer
> 2 votes
There is a trick to achieve this. Basically you always keep the subset you are currently considering sorted.

```
subset = [];
function forSubsets(n,k,m=1){
  if(subset.length == k) console.log(subset);
  else{
    for(var i = m; i <= n; i++){
      subset.push(i);
      forSubsets(n,k,i);
      subset.pop();
    }
  }
}

```

As you can see on each recursion one element is added to the subset, which is equal or bigger than all previous elements (since the loop starts from m where m is the previously added element). The order for `forSubsets(3,2)` would be \[1,1\]; \[1,2\]; \[1,3\]; \[2,2\]; \[2,3\]; \[3,3\]; Of course you have to adapt the implementation to your programming language, but I hope the recursive idea is understandable. `yield` syntax could also be used to implement this concept in a readable manner (e.g. Python). StackOverflow should be a better place for implementation details. By changing the bounds in the for-loop the you could also draw the subsets from $0,...,n-1$ instead of $1,...,n$.

Just for the sake of completeness: Here is the code for generating subsets without duplicate elements (but no duplicate subsets):

```
subset = [];
function forSubsets(n,k,m=0){
  if(subset.length == k) console.log(subset);
  else{
    for(var i = m+1; i <= n-k+1+subset.length; i++){
      subset.push(i);
      forSubsets(n,k,i);
      subset.pop();
    }
  }
}

```

---
Tags: algorithms, counting, iteration
---


# Question
Title: How to build a graph of people where node connections are determined by name and age?
I was given the following question (please don't mind the programming language semantics, it's a language-agnostic question):

Given a list of `Person`s, and two arbitrary `Person`s out of that list, we need to find the minimum *nth-degree* relationship between them.

Here are the definitions of `Person` and a "relationship":

* A `Person` is defined as having 2 properties: `Name` and `Age`:

```
class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
}

```
* A relationship between two `Person`s is defined as follows:

1. Two `Person`s are considered to be in a *1st-degree* relationship if they have *either* the same name or the same age.
    2. Two `Person`s are considered to be in a *nth-degree* relationship if they have n people of 1st-degree connecting them.

Example input:

Given the following list of `Person`s:

```
persons = [{ Name = "John", Age = 60 }, { Name = "John", Age = 50 }, { Name = "Ted", Age = 50 }]

```

Then:

1. The two `John`s have a **1st degree** relationship (because they have the same name).
2. The second `John` and `Ted` have a **1st degree** relationship (because they have the same age).
3. Hence, the first `John` and `Ted` have a **2nd degree** relationship (because the second `John` connects them).

Now, I understand that it's a simple Dijkstra's algorithm question, but what I don't know is **how should we build the graph of `Person`s**?

I'm looking for an algorithm, but preferably code, that can build the graph in a time complexity which is better than $O(|V|^2)$.
If you think this question can be solved without building a graph (e.g., using BFS as mentioned in the comments), please let me know how can this be done, but I still want to know how to build the graph.

# Answer
> 4 votes
I assume you want to build the graph of all people, with edges between each pair of people at degree 1. Once you have this graph, it is straightforward to calculate the distance ("degree") between any two people using standard algorithms.

It's easy to build that graph in adjacency list format; or to store it implicitly and generate the adjacency lists on demand.

Store a hash table that maps from name to a list of all people with that name; and another hash table that maps from age to a list of all people with that age. Now, given one person, you can use the hash tables to quickly find all other people who have a first-degree relationship with that person, i.e., who are adjacent in the graph. This lets you build an adjacency list representation of the graph in $O(|V|+|E|)$ time, i.e., linear time rather than quadratic time.

Then, once you have this graph, you can compute distances using BFS in this graph. Note that you can construct the graph on-the-fly as you execute the BFS algorithm; you don't need to build the entire graph in advance.

---

Footnote: I'm treating hash table lookups as $O(1)$ time. This is a reasonable modelling assumption for practical work. For theoretical work, you can ensure that lookups take $O(1)$ expected time if you use an appropriate hash function, which is nearly as good for most practical purposes.

# Answer
> 1 votes
Since your only parameters are name and age, you can make two lists, sort them, and then construct a graph using adjacency list:

$n \gets$ size of the set $\mathbf{persons}$;
$V \gets \\{\ \\}$; // set of vertices
$\mathit{adj} \gets \[\ \]$; // adjacency list
**for** $i = 1 \to n$ **do**

$\mathbf{persons}\[i\].\mathit{id} \gets i$;
$\mathit{adj}\[i\] \gets \[\ \]$; //adjacency list of vertex $v\_i$

**endfor**

$A \gets$ $\mathbf{persons}$ sorted by $\mathit{name}$;
$B \gets$ $\mathbf{persons}$ sorted by $\mathit{age}$;

**for** $i = 2 \to n$ **do**

**if** $A\_i.\mathit{name} == A\_{i-1}.\mathit{name}$ **then**
$Q \gets \\{(i-1)\\}$;
$j \gets i$;
**while** $A\_j.\mathit{name} == A\_{i-1}.\mathit{name}$ **do**
$Q \gets Q \cup \\{j\\}$;
$j \gets j+1$;
**endwhile**
add\_clique($Q$); // this function runs in $|Q|$ and adds edges between all pairs in $Q$
$i \gets j$;
**endif**

**endfor**

**for** $i = 2 \to n$ **do**

**if** $B\_i.\mathit{age} == B\_{i-1}.\mathit{age}$ **then**
$Q \gets \\{(i-1)\\}$;
$j \gets i$;
**while** $B\_j.\mathit{name} == B\_{i-1}.\mathit{name}$ **do**
$Q \gets Q \cup \\{j\\}$;
$j \gets j+1$;
**endwhile**
add\_clique($Q$);
$i \gets j$;
**endif**

**endfor**

The above operations take $O(n \log n)$ time to sort, and $O(n)$ time to create an adjacency list, which is less than $O(n^2)$ unless the number of edges are $O(n^2)$.

# Answer
> 0 votes
If there are no other constraints, it's easy to represent the graph using an adjacency matrix. You can construct a matrix where an entry `A[3,2]` will represent the relationship between `persons[3]` and `persons[2]`. So if you want to represent the edge between two "John"s, your entry `A[0,1]` would be equal to `1`. You can iterate through each of the elements of `persons` and fill the matrix this way. Note that this makes adding a vertex $O(|V|^2)$.

# Answer
> 0 votes
This will be more of a programming/coding companion to D.W.'s answer than a self-contained answer to *how should we build the graph of `Person`s?*

You seem to have narrow concept of *graph* and *building a/the graph* that I don't seem to share.

I see *nodes*: Persons and *edges*: equality of one of a specified set of properties of `Person` \- that's my *graph*, even before I think of *representation*.

Different algorithms on graphs need different operations supported - examples:

* predicate *adjacent*: given two nodes, are they?
this can be answered for two nodes in the presentation presented in the question
* iterating ("outgoing", if directed) *edges of a node*
as edges in this problem don't carry information, this is equivalent to *iterating directly connected node* \- I'd skip modelling edges and support the latter.
*How* depends on implementation/run-time environment. Alienated by C#, I have to consult docs.microsoft.com to find `System.Collections.Generic.IEnumerable<Person>` should fit the bill.
If I assigned to every `Person` a separate collection of its namesakes and peers, that is bound to require $\Theta(n^2)$ space - not following this train of thought.
I can build collections of namesakes and collections of peers as I add `Person`s to the graph (which is what I take D.W. to suggest). To get suitable enumerators *without explicitly specifying additional parameters*, a C# `Person`/`Node` should be a class *nested* in `Graph`. The `IEnumerable<Person>` implementation would `yield return` each namesake and each peer, skipping the object which was used to invoke it.

---
Tags: graphs
---


# Question
Title: How expensive is it to verify that a gate is universal?
I know that a NAND gate is considered universal because we can use it to implement an AND, OR, and NOT gate.

Given an arbitrary gate, or set of gates, how many operations would it take to verify if these gates are universal (by brute force), and does there exist a more efficient way to do this? How expensive is this in general?

With the example of the NAND gate we can construct a NOT, AND, and OR, pretty easily, but is there a systematic way to do this?

More specifically, assume we are given $n$ two input, one output gates, where the gates are specified as a truth table.

Is there a way to also generalize this to, given $n$ gates, in which all the gates take $m$ inputs and 1 output, how expensive would this be?

# Answer
> 5 votes
The problem is actually much more tractable than the other answers suggest. Specifically, for your first problem

> assume we are given two input, one output gates, where the gates are specified as a truth table.

I give an $O(n)$ solution. The problem is more difficult in the generalization to where each gate has $m$ inputs, where the solution below will be $O(n \cdot m \cdot 2^m)$. But this is in principle kind of unavoidable, because it actually takes $n \cdot 2^m$ just to write out all the truth tables. In other words, if you don't spend this amount of time, you won't even be able to test all possible inputs to your existing gates, so it makes sense you wouldn't be able to determine universality. It's possible the additional $O(m)$ factor can be avoided, though it's not very significant compared to the $2^m$.

I will give a solution that:

1. Either proves universality *or* disproves universality, in a finite amount of time; and
2. Works for any number of gates.

The solution actually falls out of a very beautiful and lesser-known theorem of universal algebra due to Emil Post in 1941. Your problem is, given a set of gates, to determine if they are Functionally Complete. In what follows, we assume that constants are not allowed; but if you prefer to allow the constants $1$ and $0$, then just add constant gates (with 0 inputs) that output $1$ and $0$, respectively.

**Theorem (Post, 1941). A set of gates is NOT functionally complete if and only if one of the following five conditions is satisfied:**

* All of the gates are *monotone*. This means that if any of the inputs change from false to true, the output will only change from false to true and never from true to false (if it changes at all). For example, AND and OR are monotone; NAND, NOR, and NOT are not.
* All of the gates are *affine*. This means that the output depends in a "linear" way on the input; it means that the gate is really just an XOR of some of the input variables. NOT is also affine.
* All of the gates are *self-dual.* This means that switching false and true in all inputs always switches false and true in the output. For example, NOT is self-dual as is the MAJORITY gate, but AND, XOR, and OR aren't. Note also that if you allow constant inputs (1 and 0), then these are not self-dual and so this criterion is not satisfied.
* All of the gates are *truth-preserving.* This means that if all inputs are true, the output is true. For example, the constant 1 is truth-preserving, as is AND, but 0 is not.
* All of the gates are *false-preserving.* This means if all inputs are false, the output is false.

---

We can use this theorem to derive the following $O(n \cdot m \cdot 2^m)$ decision procedure for deciding whether $n$ gates, with $m$ inputs each, are expressively complete.

* First run through all the gates, and check if they are truth-preserving or false-preserving. This can be done in $O(1)$ per gate because we only have to check two inputs (all false, and all true). If all gates are truth-preserving or all are false-preserving, return false.
* Next run through all gates and check if they are self-dual. This takes $O(2^m)$ per gate because we need to check, for each input, how it compares to the negated input where true and false are switched. If all gates are self-dual, return false.
* Next we run through all gates and check if they are monotone. This requires checking for each of the $2^m$ possible inputs, what happens if any of the $m$ input wires switch from false to true, so it takes $m \cdot 2^m$. If all gates are monotone, return false.
* Finally, we run through all gates to check if they are affine. Iterate through each of the $m$ input wires. For each wire, then try all possibilities for all the other $(m-1)$ wires, with that wire both true and false. If the gate is affine, you should see that irrespective of the other wires, either this wire always has no effect on the output, or it always flips the output. If neither of these behaviors is observed for some input wire then the gate is not affine. If all gates are found to be affine, return false.

Otherwise, once all of these checks pass (there's at least one non-truth-preserving gate, at least one non-false-preserving gate, at least one non-monotone gate, at least one non-self-dual gate, and at least one non-affine gate), then return True.

Note: If you are allowing constant inputs 1 and 0, then modify the algorithm by removing the "self-dual", "truth-preserving", and "false-preserving" checks. So, all you have to do is check if all your gates are monotone and if all your gates are affine.

---

Finally, here are a couple of examples to illustrate the way the theorem works. First, for the NAND gate: NAND is special because it is not false-preserving, not truth-preserving, not monotone, not self-dual, and not affine. As a result, it alone is functionally complete. Another common example of a functionally complete set of gates is NOT and AND. In this case: NOT is not truth-preserving, false-preserving, and monotone, covering those three requirements; and AND is not self-dual or affine, covering the other two requirements. But if either AND or NOT is dropped, then not all five requirements are satisfied.

# Answer
> 0 votes
A gate with m input bits has $2^m$ possible inputs. Each possible input has 2 possible output values, so there are $2^{2^m}$ possible such gates. m = 2 -\> 16 gates, m = 3 -\> 256 gates, m = 4 -\> 65,536 gates, m= 5 -\> about 4 billion gates, m = 6 -\> about 18 billion billion gates.

You can easily write a program that does an exhaustive search to check if all the gates can be produced. That will run very quickly with m \<= 4, will take a *lot* of patience for m = 5, and doesn’t have a chance in hell with m = 6.

However, if you do this, then in practice there is a good chance that either you find a NAND gate quickly, or that you quickly run out of further gates.

---
Tags: logic
---


title: How to delete an element from a B-tree

text:
# Question
Title: How to delete an element from a B-tree
There is a lot of information online on this specific topic, but I still don't quite understand how to delete elements from a B-tree.

For example, given the following tree, how would we delete 26 and 63?

Is there a general approach?

# Answer
B-tree deletion tends to be explained very badly in most textbooks, because the algorithm has one particular case which is complicated.

When inserting a leaf element in a B-tree, if a node becomes over-full, you split it. This has the effect of inserting a node into to its parent. If that node then becomes over-full, continue recursively.

When deleting a leaf element in a B-tree, if the node becomes under-full, you conceptually merge it with one of its neighbours *and* the common parent element. This "merge" (or "rotation") operation is the key to understanding B-tree deletion.

Let's take deleting 26 as our example. This leaves us with a node containing just 25, which is under-full.

Suppose you merged the node with its right neighbour and its common parent. This would leave you with a node containing the elements 26, 34, 45, 27, with the element 34 removed from the parent. This is exactly the same situation you would be in if you had a leaf node which contained three elements and added a fourth, leaving the node over-full. So just do what you would do if this were an insertion.

It's a similar story if you delete an interior element. Suppose you deleted the element 34. Then all you do is merge the two child nodes that it affects, giving you a node with the elements 25, 26, 45, and 47. This is exactly the situation you'd be in if you had a node with three elements and inserted a fourth.

In practice, you don't actually "merge", but you "rotate" elements between child nodes and the new common parent entry. "Merging" only happens if there is no way to "rotate" without one of the new nodes remaining under-full.

Assuming the usual B-tree variant, a node can store between $t-1$ and $2t-1$ entries, where $t$ is the minimum ply of the tree. If you need to merge, it's because an entry was deleted, either from one of the nodes being merged or its common parent. Either way, you have $2t-2$ entries that you have to deal with. The solution is to just make it one node, which has the effect of deleting a node from the parent node. You can now simply delete recursively.

Some care needs to be taken with the root node, because deleting from the root node may result in the height of the tree changing.

**ADDENDUM**

Do not read this until you fully understand the textbook algorithms, at least in theory, because I'm going to go off-textbook now and make a few comments about how real-world B-trees aren't the same as what you see in your textbook.

Real B-tree implementations are often designed for concurrency, which complicates both insertion and deletion even more; just because you hold an exclusive lock on a node, that doesn't mean you hold an exclusive lock on its parent. Unlike insertion, however, deleting an entry can, at worst, make a node under-full, and B-tree lookup operations still work on under-full nodes. So real implementations may just record that a node's parent needs rebalancing, and complete the rebalance later, perhaps with a concurrent task. (By the way, you can do a similar trick with insertion.)

Further on that point, because high concurrency means avoiding interior node deletion if you can, real B-tree implementations often try very hard to avoid it using aggressive rotation. So, for example, given a choice of two siblings with which to merge an under-full node, *always* choose the larger one. Even consider distributing the entries between three siblings at a time if that applies.

Real B-tree implementations are also often designed for ACID-safe database transactions. Implementing transaction-safety is beyond the scope of this discussion, but fully supporting two-phase commit and rollback affects how algorithms on B-trees are implemented.

Even though the size criterion is more strict, deletion from B+-trees can be less complex the interior nodes do not hold full entries. This is especially true when transactions are needed. Again, beyond the scope of this discussion, but this is one of many reasons why B+-trees are much more common in the wild than B-trees.

Finally, and most importantly, many real B-tree implementations have to deal with keys that aren't of a constant size, such as strings. This means that the upper and lower bounds of a real B-tree node are measured in bytes, not entries. This has implications, for example, when choosing which key should be the new common parent of a merged node. Real implementations try to choose the *physically* smallest one that also keeps the *physical* sizes of the new child nodes roughly equal.
> 2 votes

# Answer
All of the keys you want to delete in this particular example belong to the case when we are deleting keys from a leaf node, without need to rebalance a tree after deletion.

Algorithm for deleting a key from a leaf node consists of three steps:

**1)** Search for the value to delete.

**2)** If the value is in a leaf node, simply delete it from the node, because there are no subtrees to worry about.

**3)** If underflow happens (i.e., if we break one of the defining rules/properties of a B-tree - every non-root node has to have at least **(M-1)/2** keys), rebalance the tree.

Also, if you are interested in implementation of rebalancing algorithm, beyond the scope of the given example, I suggest these sources:

https://www.youtube.com/watch?v=vqIxJaNrPI4

https://webdocs.cs.ualberta.ca/~holte/T26/del-b-tree.html
> 0 votes

---
Tags: data-structures, b-tree
---


# Question
Title: Time Complexity proof for Segment Tree implementation of the ranged sum problem
I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here.

However I'm not able to prove that the querying time is indeed $\mathcal{O}(\log n)$. This link (and many others) say that we can prove that at each level, the maximum number of nodes processed is $4$ and so $\mathcal{O}(4 \log n) = \mathcal{O}(\log n)$.

But how do we prove this, perhaps by contradiction?

And if so, if we were to use segment trees for ranged sum of higher dimensional arrays, how would the proof be extended?

For example, I can think of finding a sub matrix sum by dividing the original matrix into 4 quadrants (similar to halving intervals in linear arrays) building a quadrant segment tree but the proof eludes me.

# Answer
The claim is that there are at most $2$ nodes which are expanded at each level. We will prove this by contradiction.

Consider the segment tree given below.

Let's say that there are $3$ nodes that are expanded in this tree. This means that the range is from the left most colored node to the right most colored node. But notice that if the range extends to the right most node, then the full range of the middle node is covered. Thus, this node will immediately return the value and won't be expanded. Thus, we prove that at each level, we expand at most $ 2 $ nodes and since there are $ \log{n} $ levels, the nodes that are expanded are $ \boxed{2 \cdot \log{n} = \Theta\left( {\log{n}} \right)} $
> 11 votes

# Answer
At each level (L) of tree there would be at max 2 nodes which could have partial overlap. (If unable to prove - why ?, please mention)

So, at level (L+1) we have to explore at max 4 nodes. and total height/levels in the tree is O(log(N)) (where N is number of nodes). Hence time complexity is O(4\*Log(N)) ~ O(Log(N)).

PS: Please refer my answer on - Segment tree time complexity analysis
> -1 votes

---
Tags: data-structures, runtime-analysis, search-trees, intervals
---


# Question
Title: Generate a uniform random numbers in $O(1)$
Suppose you have access to a random number generator $G()$ that generates uniform random numbers in $\\{0,\cdots,n-1\\}$. (Here, $n$ is given and cannot be changed.) How do we generate a uniform random number in $\\{0,\cdots,m-1\\}$ for $m\leq n$? We require that we can only call $G()$ $O(1)$ times in expectation.

My effort: Suppose $n=km+r$, where $k$ and $r$ are integers. Call $G()$. If $G()\leq km$, return $G()\mod m$; otherwise, call $G()$ again.

But in expectation, this will call $G()$ $O(\frac{n}{n-r})$ times, and $r$ can be $1,\cdots,m-1$.

# Answer
Since $r \< m \leq n$, necessarily $k \geq 1$ and so $n - r = km \geq m \> r$. In particular, $r \< n/2$ and so $n-r \> n/2$. In total, we conclude that $n/(n-r) \< 2$.
> 3 votes

---
Tags: randomized-algorithms
---


# Question
Title: Longest Repeated (Scattered) Subsequence in a String
**Informal Problem Statement:**

Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right yields the same result as reading only the blue letters.

In the example we could colour them like this: $A\color{blue}{C}\color{red}{CAB}B\color{blue}{AB}$

Therefore, we say $CAB$ is a repeated subsequence of $ACCABBAB$. It is also a longest repeated subsequence (which is easy to check).

Can we compute longest repeated subsequences efficiently?

**Formal Question:**

Is it NP-hard to decide for a string and some $k$, whether a repeated subsequence of length $k$ exists in the string?

* If so: Which problem can be reduced to this problem?
* If not: What is an efficient algorithm? (obviously, this algorithm can then be used to compute a longest repeated subsequence)

**Bonus Question:**

Will their always be a repeated subsequence of length $n/2 - o(n)$ if the size of the alphabet is bounded by a constant?

(This is known to be true for binary alphabets.)

Edit 2: The negative answer to the Bonus Question is already known for alphabets of size at least $5$. In fact for alphabets of size $Σ$, there are strings with longest repeated subsequences of a length of merely $O(n · Σ^{-1/2})$. Random strings suffice to show this. The result already existed, but I overlooked it.

Edit: **Note:**

Some people mean "substring" when they say "subsequence". I don't. This is not the problem of finding a substrings twice.

# Answer
> 5 votes
The special case of $k = n/2$ is the same problem as this CST.SE question How hard is unshuffling a string? asks.

Buss and Soltys proved NP-completeness of this problem \[1\] by reducing 3-Partition problem to this problem.

* \[1\]: Buss, Sam, and Michael Soltys. "Unshuffling a square is NP-hard." Journal of Computer and System Sciences 80.4 (2014): 766-776.

# Answer
> -3 votes
This can be solved in ~~polynomial time~~ by constructing a graph $G$ where each node represents a point $(i,j)$ in some repeated subsequence of $S$ such that $S\[i\]=S\[j\]$. Edge between nodes $u$ and $v$ means that $u$ can be continued by $v$ to form a repeated subsequence of length 2.

**1.** Find the nodes. This can be done in $O(n^2)$ time by building a sorted list of indices for each character $c$, and then enumerating the unique pairs. There are no more than $m=n^2$ nodes.

**2.** Find the edges. It takes $O(1)$ time to check if node $u$ can be continued by node $v$, so by considering all pairs $(u,v)$ this step takes $O(m^2)$ time.

**3.** Note that the longest path in $G$ may not be a valid repeated subsequence. Consider paths $ab$ and $bc$. If there exists an edge $ac$ then $abc$ is a valid repeated subsequence of length 3. Therefore it takes $O(m^4)$ time to find all repeated subsequences of length 3. In the general case it takes linear time to check whether two valid paths of length $n$ can be combined into a valid path of length $n+1$.

**4.** Iterate step 3 until no longer paths can be found.

---
Tags: algorithms, complexity-theory, np-complete, strings, subsequences
---


# Question
Title: What is the property of a PL that extracting a subroutine should not change the meaning?
What is the name of the property of a Programming Language that says that extracting a subprogram into a subroutine and using that subroutine instead of the subprogram should not change the meaning of the program?

I could swear that this exists and that it has a well-known name, but I can't for the life of me remember it. My efforts to search for the name have been thwarted by being swamped with results for the Liskov Substitution Principle or Referential Transparency.

What I am looking for is the property that I should be able to replace

```
printf("Hello");

```

with

```
void hello() {
    printf("Hello");
}

hello();

```

without changing the meaning of the program.

I think it is named after the person who coined it, but I am not sure. Something like *XYZ Equivalence* or *XYZ Principle* where *XYZ* is the name of a well-known Computer Scientist. I want to say *Strachey*, but I couldn't find a mention of anything similar in *Fundamental Concepts in Programming Languages*.

# Answer
> 2 votes
I believe you are looking for Morris style Contextual Equivalence. Which says that the meaning of a term (in your case a subroutine) should not change in any context.

If, $⟦ \cdot ⟧ : term \to \mathcal{D}$, is the meaning function then $$\forall C. ⟦C\[t\]⟧ = ⟦ C ⟧ \circ ⟦ t ⟧ $$ Where $C\[\cdot\]$ is a context with a hole in it.

# Answer
> 1 votes
Purely by accident, I found the answer to my question as well as the fact that my question is wrong.

What I was thinking of was *Tennent's Correspondence Principle*, which I read about in the context of Java Lambdas and today re-discovered in the context of `do`-expressions for ECMAScript.

```
foo

```

should be equivalent to

```
(fn { foo })()

```

for any expression `foo`, i.e. that I can wrap an expression in a closure without changing the meaning of the expression.

Except it turns out that this is *not* the Principle of Correspondence, it was misquoted by Neal Gafter and seems to have taken on a life of its own after that.

This is actually the *Principle of Qualification*.

The actual *Principle of Correspondence* talks about variable definitions and function parameters and says that for every mechanism of parameters, there should be an equivalent mechanism of definitions and vice-versa. The example he gives is the following Pascal block:

```
var i : integer;
begin
  i := -j;
  write(i)
end

```

which is equivalent to the following procedure and vice versa:

```
procedure p(i : integer);
  begin
    write(i)
  end;

begin
  p(-j)
end

```

And he points out that there is no mechanism for variable definitions that is equivalent to `var` parameters (i.e. pass-by-reference) in Pascal, meaning that Pascal does not obey the Principle of Correspondence.

References:

---
Tags: programming-languages, language-design
---


# Question
Title: Why Linear bounded automata requires Nondeterministic Turing machine ? Why not Deterministic Turing machine?
Going through the topic of LBA, i.e., Linear bounded automata. I found that LBA requires the NTM with some constraints on tape. I found the same information from different sources. But I did not get why all the sources mentioned that it needs a NTM. I am not getting why I need a NTM for LBA? We also know that any NTM can be converted to DTM. Therefore, I can take a DTM and put those tape constraints for building a LBA. I think that with a tape constraints DTM would be converted to LBA! Please make me correct and kindly tell me why I need an NTM for an LBA?

# Answer
The conversion from nondeterministic Turing machine to deterministic Turing machines doesn't conserve space. The best known construction, known as Savitch's theorem, converts a nondeterministic Turing machine using space $s(n)$ to a deterministic one using space $O(s(n)^2)$, and this is suspected to be tight in general; see for example this question on cstheory.

Linear-bounded automata correspond to a class of grammars, context-sensitive grammars, in the following strong sense: a language can be described by a context-sensitive grammar iff it is accepted by some linear-bounded automaton. We only know how to prove this result if the linear-bounded automata are allowed to be nondeterministic. Indeed, assuming that $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$ (a conjecture which is much weaker than the tightness of Savitch's theorem), there exists a context-sensitive language which cannot be decided by a deterministic linear-bounded automaton.
> 2 votes

# Answer
From Savitch's theorem:

A nondeterministic L(n)-tape bounded Turing machine can be simulated by a deterministic $\[L(n)\]^2$-tape bounded Turing machine, provided $L(n) \geq \log\_2 n$.

Thus, in particular, every context-sensitive language can be recognized within deterministic storage $n^2$, where $n$ is the length of the input.

The context-sensitive languages are precisely those sets accepted by nondeterministic Turing machines within storage $L(n) = n$. Then Every context-sensitive language is accepted by some deterministic Turing machine within storage $n^2$.

**Conclusion:** So, this is all about a matter of storage, that is why we use NTM in the LBA as it requires less storage over DTM. As an interesting aside, there remains an open problem to do with LBAs in the realm of complexity theory: does a deterministic LBA have the same power as a normal non-deterministic LBA or, equivalently, does NSPACE(n) = DSPACE(n)?

***N.B:*** Please make me correct if I misunderstand the concepts. If it is satisfactory then you may please give me an upvote.

Ref:

1. Savitch, Walter J. "Relationships between nondeterministic and deterministic tape complexities." Journal of computer and system sciences 4.2 (1970): 177-192.
2. https://www.cs.auckland.ac.nz/~nies/Students/Bax380project2010.pdf
> 0 votes

---
Tags: turing-machines, automata, context-sensitive, linear-bounded-automata
---


title: Schwartz-Zippel lemma question

text:
# Question
Title: Schwartz-Zippel lemma question
Schwartz-Zippel lemma is as follows. Let $f(x\_1,\ldots,x\_n)$ be a polynomial of total degree at most $d$ over a field $\mathbb{F}$ and assume that $f$ is not identically zero. Pick uniformally at random elements $r\_1,\ldots,r\_n$ from the field $\mathbb{F}$ then probability that

$$f(r\_1,\ldots,r\_n) = 0 \le \frac{d}{|\mathbb{F}|}$$

Let us assume that $f$ is multiplinear which means each of the monomial in the polynomial $f$ is of same degree. My question is as follows. Is the following bound (given below) tight or we can come up with a better bound?

$$f(r\_1,\ldots,r\_n) = 0 \le \frac{d}{|\mathbb{F}|}$$

# Answer
If $f = \prod\_{i=1}^d x\_i$ is a single monomial then $$ \Pr\[f=0\] = 1 - \left(1 - \frac{1}{|\mathbb{F}|}\right)^d \geq \frac{d}{|\mathbb{F}|} - \frac{d^2}{2|\mathbb{F}|^2}. $$ (The second bound is Bonferroni's inequality.)

This shows that Schwartz–Zippel is essentially tight when $d$ is small compared to $\mathbb{F}$.

The bound $1-(1-1/|\mathbb{F}|)^d$ is tight for multilinear polynomials, see this answer on math.se.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Does CSL contain an empty string or not? Is empty string accepted by LBA or not?
I am confused and got contradictory statements from various sources. It is mentioned in Page no 292, Chapter 11 A Hierarchy of Formal Languages & LBA, Peter Linz -An Introduction To Finite Automata, 5th Edition that "A language L is said to be CSL if there exists context-sensitive grammar G such that $L = L(G)$ or $L = L(G) \cup \\{\varepsilon\\}$." So the Language contains empty string & grammar as per Peter Linz.

In another version, I found that the production $S\to\varepsilon$ is also allowed in CSL, provided that 'S' does not appear on the right-hand side of any productions. However, several other sources like this youtube lecture (https://www.youtube.com/watch?v=i3c\_2c2KFpY) explain that CSL does not contain a null string. Here in this given link (https://gyires.inf.unideb.hu/GyBITT/14/ch06s04.html) it is written that LBA accepts null string generated from a CSL.

In the book, "Theory of Computer Science: Automata, Languages and Computation" by Mishra K.L.P , third edition, Publisher-PhI, on page 299, subsection 9.8.1 that "The set of strings accepted by nondeterministic LBA is the set of strings generated by CSG, excluding null strings".

This is too much for making a complete confusion. Example:

L=$\\{a^nb^nc^n| n\geq 0 \\}$, whether this is CSL or Not? This language contains empty string too!

Please help me to get the right knowledge.

# Answer
> 2 votes
Welcome to CS.SE! I only know of the latter definition, i.e. the one allowing $S \to \varepsilon$ but disallowing $S$ in the right sides of productions. Ultimately this is done to have a *nice* definition in the sense that the class of context-sensitive languages forms a proper superset of the class of context-free languages. Definitions excluding the empty string to be in context-sensitive languages are a little bit less nice, in that sense.

As you found out, definitions may vary between sources and are often chosen in order to state some property or result in a particularly nice manner. This is common in mathematics and another example would be the question of including 0 in the natural numbers $\mathbb N$ or not. The thing is that usually these little changes do not really matter in the end; they do not fundamentally change the mathematical nature of the thing defined, and this is also the case with the small differences between the definitions for context-sensitive languages you encountered.

---
Tags: turing-machines, automata, linear-bounded-automata
---


# Question
Title: What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)
I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as

$(0+0001)((1111)^\*+(00)^\*)$

1. What is the length of the longest string that cannot be pumped?
2. What is the length of the shortest string that can be pumped, I think this will come naturally when we find the $p$ (the pumping length).

The pumping length of a regular language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be split as $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) $xy^iz \in L$ for every $i \geq 0$.

As per the answer https://cs.stackexchange.com/a/83727/33673, can we chose $y$ (the middle term in $xy^iz$ to be $1111$ in this case?

# Answer
> 3 votes
1. It will be convenient to distribute the concatenation to get the equivalent RE $$0(1111)^\ast + 0(00)^\ast + 0001(1111)^\ast + 0001(00)^\ast.$$ Now note that any such string can be writen as $s = s\_i(s\_r)^\ast$ where $s\_i$ denotes the initial part (i.e. $0$ or $0001$) and $s\_r$ denotes the repeated part (i.e. $1111$ or $00$). We see that $s$ can be pumped if and only if $s\_r$ is non-empty and hence, the longest non-pumpable string is $0001$ and the answer is $4$. Indeed any string of length $5$ or more must have a repeatable part as defined above.
2. The two shortest strings in the language are $0$ and $000$. We see that $0$ clearly cannot be pumped (as $\varepsilon$ is not in the language) but $000$ can be pumped by repeating the last two zeroes arbitrarily often (and importantly we can also delete them to get $0$). Hence the answer is $3$.

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


# Question
Title: Create a Turing-machine that decides $A=\{0^{3^n} | n\ge 0\}$
I need to find a Turing machine that decides $A=\\{0^{3^n} | n\ge 0\\}$.

I tried doing the same as Sipser does on page 172 in his back, where he creates a Turing machines that decides $A=\\{0^{2^n} | n\ge 0\\}$, by iterating over the input, and crossing (by writing $x$) on every other $0$.

I wanted to cross every third $0$, but I failed getting to any possible machine. Either I create a machine that does not accept $000$, or a machine that accepts $00000$ or $000000$.

I found a solution that for each iteration cross off $2/3$ of the $0$ over the tape, meaning after each iteration we remain with third of the $0$. But is it possible to get to a solution as I wanted? where on each iteration we cross off third, and remain with $2/3$?

# Answer
> 1 votes
Okay I can't draw and the only tools for visualizing Turing machines aren't the most practical so I'll give you a list of states and how they behave. Note that `next` refers to the next state and that if `next` and `write` aren't assigned the machine doesn't move to another state / doesn't write something.

A brief verbal description since the machine is somewhat big (9 states). There are states for count 0/ count 1 and count 2. Which count zeros...; Now when the machine reaches a third zero it is replaced with X and we are back to "count 0". Every of those three states has a "back" state responsible for moving back to start if we encounter an "empty". Notice that if we do not encounter a zero on our way back we are done and have to report accept or reject. If however we encounter a zero on our way back "count i back" switches to state "count i not finished" which if it encounters a "empty" (while moving left) will switch back to "count i" ($i \in \\{0,1,2\\}$.

```
"count 0" (initial state)
    read 0: {move: right, next: "count 1"}
    read X: {move: right}
    read empty: {move: left, next: "count 0 back"}
"count 1"
    read 0: {move:  right, next: "count 2"}
    read X: {move: right}
    read empty: {move: left, next: "count 1 back"}
"count 2":
    read 0: {move: right, write: X, next: "count 0"}
    read X: {move: right}
    read empty: {move: left, next: "count 2 back"}
"count 0 back"
    read X: {move: left}
    read 0: {move: left, next: "count 0 not finished"}
    read empty: reject
"count 1 back"
    read X: {move: left}
    read 0: {move: left, next: "count 1 not finished"}
    read empty: accept
"count 2 back"
    read X: {move: left}
    read 0: {move: left, next: "count 2 not finished"}
    read empty: reject
"count 0 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 0"}
"count 1 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 1"}
"count 2 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 2"}

```

Hope you get the idea!

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


# Question
Title: A voting scheme where votes are scriptable
I am looking for literature on mathematical models of (political) voting schemes. Concretely, I am interested in models that allow votes of the following form:

> "I am voting for $X$, but only if $\>40\\%$ of my peers vote for them, too. Otherwise, I'd like to vote for $Y$ instead."

In that sense, I'd like to consider votes to be scripts over some language. I got this idea from Bitcoin where money isn't actually sent to specific accounts, but rather scripts are given that determine who may redeem that money.

---

## A naive model

To give you a more precise idea, I have come up with the following (naive) model of **scriptable votes**:

Let $C$ be a set of *candidates*, e.g. $C = \\{\text{rep},\text{dem}\\}$ for republicans and democrates. An *election outcome* $O \in \mathrm{ProbDists}(C)$ is a probability distribution on $C$. For finite $C$, this is known as a normalized histogram. A *vote* $v$ is a mathematical function $v\colon \mathrm{ProbDists}(C) \to C$, which – given a *putative outcome* – decides which candidate to vote for.

In most elections around the world, all votes are constant functions: e.g. if you mark your cross for republicans, in the above model you would cast the constant function $v \equiv \mathrm{rep}$. And if you marked democrates, you would cast $v' \equiv \mathrm{dem}$ instead.

Importantly, our model also supports votes as in the quote above: $$v^\text{example}(O = \\{p\_\mathrm{rep}, p\_\mathrm{dem}\\})=\begin{cases} \mathrm{rep} & \text{if } p\_\mathrm{rep} \> 0.4\\ \mathrm{dem} & \text{else} \end{cases}$$ where the notation $O = \\{p\_\mathrm{rep}, p\_\mathrm{dem}\\}$ is syntactic sugar for extracting the probabilities assigned to $\mathrm{rep}$ and $\mathrm{dem}$, respectively. Here, you see that $v^\text{example}$ is a script over the usual mathematical language. But given some votes how do we determine the (final) outcome?

Let $V = v\_1,\ldots,v\_N$ be the multiset of cast votes. An ***admissible outcome*** of an *election* $(C, V)$ is an election outcome $O \in \mathrm{ProbDists}(C)$ such that the multiset $\\{v\_1(O),\ldots,v\_N(O)\\}$, interpreted as a normalized histogram on $C$, equals $O$. We can see this as some kind of fixpoint.

**Examples.** Let $C$ and $v := v^\text{example}$ as above.

* For the election $(C, \\{v\\})$, i.e. with $v$ being the only vote, we have two admissible outcomes: $O\_1 = \\{p\_\mathrm{rep} \mapsto 1, p\_\mathrm{dem} \mapsto 0\\}$ and $O\_2 = \\{p\_\mathrm{rep} \mapsto 0, p\_\mathrm{dem} \mapsto 1\\}$. For $(C, \\{v, v\\})$, we have the same two outcomes. The same holds true for three, four, and arbitrarily many copies of $v$.
* Consider a new kind of vote $w(O) \equiv \mathrm{dem}$ that always votes for democrates. The election $(C, \\{v,w\\})$ has two admissable outcomes: $O\_1 = \\{p\_\mathrm{rep} \mapsto 0.5, p\_\mathrm{dem} \mapsto 0.5\\}$ and $O\_2 = \\{p\_\mathrm{rep} \mapsto 0, p\_\mathrm{dem} \mapsto 1\\}$. In the latter case, the vote $v$ "noticed" that they will never be surrounded by a like-minded peer group of size $\> 40\\%$ and hence switched its candidate it voted for.

---

## Research Questions

Concerning scriptable votes, some broad questions I'd be interested in are:

* Does every election have at least one admissible outcome? If not, can we relax the conditions on admissible outcomes to just choose the best ones?
* How much influence do individual votes have? Is the function that maps $(C, V)$ to a set of admissible outcomes continuous in some sense?
* Are mathematical functions for votes really the best model? While *if conditions* like $p\_\mathrm{rep} \> 0.4$ sound reasonable (and interesting), should we perhaps disallow conditioning on equalities such as $p\_\mathrm{rep} = 0.4578$? Perhaps votes should be scripts over a tailored domain-specific language. How do their properties such as being total (exceptions?) or deterministic (probabilistic?) affect the questions above?

# Answer
> 3 votes
# Broad context

First off, the field in which this sort of research would be carried out is called **computational social choice (theory)**. Searching for papers or books in that field will give you exactly what you ask for: *literature on mathematical models of (political) voting schemes*, and related topics like resource allocation and judgement aggregation. As for a reference, I'd recommend the *Handbook of Computational Social Choice*. As a sidenote, if you want to ask questions about these things, the tag `social-choice-theory` on math.stackexchange.com might be a good idea.

# Your voting rule

Now, as for your specific idea, there are some unclear parts. You consider probabilities, but are unclear on what exactly those probabilities mean. You imply that they're based on the proportion of votes any candidate gets, but the voters don't simply vote for a candidate. I'd recommend trying to really formalize your idea and see if it has some interesting properties. I'm not aware of any serious research effort in this sort of direction.

One thing to consider is the reason for such a system. That is, why would a voter want to vote for X only with a certain level of support, and Y otherwise? Is it 1.) because they prefer X but are scared that a vote for a minor candidate might be a waste, or is it 2.) because the level of support somehow changes the desirability of the candidate? In the case of 1.), the voter really just supports X, and has Y as their second favorite candidate. A solution might not involve a complicated ballot, as you propose, but perhaps just a good voting rule that fits in the existing mathematical frameworks. In the case of 2.), where a voter's true preferences might rely on other's preferences, making such a complicated ballot might indeed be a good idea.

Importantly, you must consider that *every* voter can submit such a ballot, and therefore changes in outcome might beget changes in preference which beget changes in outcome and so on and so forth. It might not be possible to make any decent voting rule within this system that is guaranteed to converge to some outcome. You'll even have to be careful that the outcome is not just well-defined, but computable.

Regardless of all this, we might already be able to answer one of your research questions. Unless I misunderstand things, there is not always an admissable outcome. Consider a single voter who votes X only if X has less than half of the votes, and Y otherwise. Now, if X would win, they would prefer Y, and vice versa. I don't have any direct ideas on how to relax admissibility to guarantee one exists.

---
Tags: reference-request, modelling, voting
---


# Question
Title: Measuring the difficulty of a sequence-to-sequence problem using automata theory
Automata theory measures the difficulty of language recognition problems by using an automaton that can accept or reject for the given string.

However, I want to measure the difficulty of a sequence-to-sequence (seq2seq) problem.

For instance, what is the difficulty of the following seq2seq problem associated with counting as follows:

$\Sigma = \\{a, b, 1, 2, 3, T \\}$ where $T$ is a terminal symbol.

$A = \\{xT \\}\_{x \in \\{a1, a2, a3, b1, b2, b3\\}^\*}$

$B = \\{sT \\}\_{s \in \\{a, b\\}^\*}$

A seq2seq function $f:A \to B: w\_1d\_1 \cdots w\_nd\_n T \mapsto \underbrace{w\_1 \cdots w\_1}\_{d\_1} \cdots \underbrace{w\_n \cdots w\_n}\_{d\_n}T$ where $w\_i \in \\{a, b\\}$ and $d\_i \in \\{1, 2, 3\\}$.

To go further, is there any way to convert a seq2seq problem into a language recognition problem?

Moore machine or Mealy machine equipped with an output function deals with similar problem where the length of the output is equal or less than that of the input.

# Answer
Finite-state transducers capture a class of seq2seq problems that correspond to the notion of regular languages, which could be thought of as the "easiest" problems in automata theory. Your example function $f$ can be implemented by a finite-state transducer.
> 1 votes

---
Tags: automata
---


title: Linear Grammar in less than cubic time

text:
# Question
Title: Linear Grammar in less than cubic time
I have a linear grammar $G$ and a string $s$. $G$ is is not limited to right or left linear only but rather has a mix of rules of both types.

Is there an algorithm to determine whether $s \in L(G)$ in less than cubic time?

Converting to CNF and applying the CKY algorithm takes cubic time, and I am wondering if there is a more efficient algorithm.

# Answer
> 2 votes
Yes, you can. As Dmitry explains, CYK parsing can be used to parse a linear grammar in $O(n^2)$ time, where $n$ is the length of the input word.

CYK parsing is a dynamic programming algorithm that sets $P\[l,s,R\]$ to be true if $a\_{s .. s+l-1}$ can be generated from the non-terminal $R$, where $a\_{1..n}$ is the input word.

Note that there is a recurrence relation that can be used to compute $P\[l,s,R\]$ from values of the form $P\[l',s',R'\]$ with $l'\<l$, in $O(1)$ time. In particular, if we have the rule $R \to b\_1\cdots b\_k Q c\_1 \cdots c\_m$, then we should set $P\[l,s,R\]$ to true if $a\_{s .. s+k} = b\_{1 .. k}$ and $P\[l-k-m,s+k,Q\]$ is true and $a\_{s+l-m .. s+l-1} = c\_{1 .. m}$. Do this for each rule with $R$ on the left-hand side. If none of them sets $P\[l,s,R\]$ to true, set $P\[l,s,R\]$ to false. This takes $O(1)$ time (treating the size of the grammar as a constant).

We repeat this for each of the entries $P\[l,s,R\]$. There are $O(n^2)$ such entries (treating the size of the grammar as a constant), and each entry takes $O(1)$ time to compute, so the entire algorithm runs in $O(n^2)$ time.

---
Tags: formal-grammars, dynamic-programming, parsers
---


# Question
Title: Are different assignments allowed for the implication graph proof of 2-SAT being in P?
One proof for $2-SAT$ being in $P$ uses the implication graph, *i.e.* one creates 2 vertices per variable $a$, one for each possible literal ($a$ and $\neg a$). One then adds 2 arcs per clause $(a \lor b)$, one from $\neg a$ to $b$ and one from $\neg b$ to $a$, respectively representing the implications $\neg a \implies b$ and $\neg b \implies a$. Finally, (assuming a solution exists) one sorts the connected components in topological order and traverses these in reverse order. Now for the important part :
**For every literal $a$ encountered, set variable $a = true$, and for every literal $\neg a$ encountered, set variable $a = false$.**
Don't change variables already set. The resulting assignment is a solution.

My question is : Do other assignments work as well, as long as the underlying implications stay $true$ ? For example :
**For every literal $a$ encountered, set variable $a = false$, and for every literal $\neg a$ encountered, set variable $a = true$.**
since $false \implies false$, or even some combination :
**For every literal $a$ encountered, if it points to some literal that equals $false$, set $a = false$, otherwise set it to either $false$ or $true$. For every literal $\neg a$ encountered, if it points to some literal that equals $false$, set $a = true$, otherwise set it to either $false$ or $true$.**
since $true \implies true$, $false \implies true$, and $false \implies false$?

# Answer
(Example below)
Following anything other than :
**For every literal $a$ encountered, set variable $a = true$, and for every literal $\neg a$ encountered, set variable $a = false$.**
might set to $true$ a literal higher up in the DAG of strongly connected components (which you're traversing in reverse topological order), which can cause a chain reaction downwards obtaining a $true \implies false$, which is not allowed.

An example is the following : $(a \lor b) \land (a \lor \neg b)$
Indeed, traversing the created implication graph in reverse topological order makes you start at literal $a$, which you need to set to $true$, as setting it to $false$ would set literal $\neg a$ to $true$ higher up in the DAG, creating said contradiction of $true \implies false$ somewhere in between. Also, one can trivially see why $a$ needs to be set to $true$ in the example.
> 0 votes

# Answer
You have to understand that $a \implies b$ cannot be interpreted as $\neg a \implies \neg b$. Only the contraposition $b \implies a$ is true, but this one is already in the implication graph by construction.

Thus, with your algorithm, you will make abrirtrary assignments. This will probably leads to an impossibility even if the problem does have a solution. Of course, on trivial examples, one can see that this algorithm may produce a solution.

Also note that $a \implies b \implies c$ means there is elsewhere in the graph $\neg c \implies \neg b \implies \neg a$. So when you decide to assign false in order to $a, b, c$, you are reading the graph and the strongly connected components reversly.
> 1 votes

---
Tags: proof-techniques, check-my-answer, 2-sat
---


# Question
Title: Implementing Deterministic Turing Machine
If i want to implement a Deterministic Turing Machine from a Non-deterministic Turing machine is **always** suggested to use the Breadth-first algorithm ? If yes, why ?

# Answer
> 1 votes
The reason for that is, if you use Depth-First Search (DFS), there exists the probability of the search going through a path that is infinite in length (loop) and you will never get an answer. If you use BFS it's more likely that you will find a path on to an accept state, if a path to one exists.

For example imagine that you have a tree with 100 children on left from the root and the right child of the root you only have 3. If you use DFS you will traverse the 100-deep left branch and later go right, and now instead having 100 branches just imagine you have infinite number of branches.

# Answer
> 1 votes
Think first that 'will my program halt?'. If you are sure that yes, your TM will definitely HALT then go for any searching algorithm, no problems at all. But, if are not sure about the HALTING issue, then? A TM is an idealized computer because the amounts of time and tape memory that it is allowed to use are unbounded. When it falls in ‘loops’ it may run for many years or even centuries after centuries although it will not produce any output. To avoid this looping problem we adapt BFS searching policy while developing a TM.

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


# Question
Title: How to we prove if a right linear language is ambiguous?
Considering the following language as an example:

$$\begin{align} S &\rightarrow aS \mid bA \\ A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\ B &\rightarrow aB \mid \varepsilon \\ D &\rightarrow aD \mid \varepsilon \end{align}$$

This has ambiguous transitions on the string $ba$, but how do we prove in general that a right linear language is ambiguous. Is there an algorithm for this?

# Answer
For simplicity, let me assume that the only allowed rules are of the form $A \to aB$ and $A \to \epsilon$. Denote the set of nonterminals by $V$, where $S \in V$ is the starting symbol.

Construct a new right linear grammar with nonterminals $V \times V \times \\{0,1\\}$. The new grammar will simulate two different production sequences for each word, keeping track whether the two actually differ. The starting symbol is $(S,S,0)$, and the rules are:

* For every pair of original rules $A \to aB$ and $C \to aD$ we add the rule $(A,C,1) \to a(B,D,1)$. (Possibly some of $A,B,C,D$ are equal.)
* For every pair of original rules $A \to aB$ and $A \to aC$ such that $B \neq C$ we add the rule $(A,A,0) \to a(B,C,1)$. (Possibly $A=B$ or $A=C$.)
* For every pair of original rules $A \to \epsilon$ and $B \to \epsilon$ we add the rule $(A,B,1) \to \epsilon$. (Possibly $A=B$.)

A word $w$ has two different derivations in the original grammar iff it can be generated by the new one.

For example, in your sample grammar the word $ba$ has two different derivations, $S \to bA \to baB \to ba$ and $S \to bA \to baD \to ba$, and this is reflected in the following derivation in the new grammar: $$ (S,S,0) \to b(A,A,0) \to ba(B,D,1) \to ba. $$
> 3 votes

# Answer
A right linear grammar with rules of the form $A\to aB$ and $A\to\varepsilon$ is a finite state automaton in disguise.

Such a linear grammar is ambiguous iff the following holds:

There is a pair of productions $A\to aB$ and $A\to aC$ ($B\neq C$) such that $A$ is reachable from $S$, and the languages derivable from $B$ and $C$ have a string in common.

How do we check whether pairs $B,C$ generate a common string? This can be done by a recursive marking algorithm. We start by marking pairs $(B,C)$ such that $B\to \varepsilon$ and $C\to \varepsilon$ (including $B=C$). Now repeatedly mark pairs $(X,Y)$ for which there are productions $X\to a B$ and $Y\to aC$ with $(B,C)$ marked.
> 2 votes

---
Tags: automata, regular-languages, finite-automata, linear-bounded-automata
---


title: optimal testing strategy

text:
# Question
Title: optimal testing strategy
Here I have a problem in understanding the `optimal testing strategy`.

In a scenario, You have been given two laptop batteries and a testing device. The testing device will make the battery connected to it (one battery can be connected at a time) deliver `x mA`, where `x` is an integer. The testing device is constructed in such a way that the battery will always explode if there’s any risk of explosion at that current.

Now we want a program that receives inputs. Input consists of multiple lines, one line per case (at most 200 test cases). Each line contains a single positive integer n between 1 and 4711 inclusive, giving the current at which the battery is known to explode. Input is terminated by a line containing 0, which should not produce any output.

And produce Output, where for each case, print one line containing the worst-case number of tests to perform when using an optimal testing strategy.

```
|-----------------|------------------|
|  Sample Input   |  Sample Output   |
|--------- -------|------------------|
    1                0
    2                1
    10               4
    23               7
    0

```

This was a programming contest question marked as an easy question. but I do not get the definition of the optimal testing strategy. What can be the boundaries? Generally what this question means?

# Answer
> 4 votes
in my opinion, The designer of this question just wanted to make a famous algorithm problem a bit complicated but made it totally nonsense.

This is the famous two egg problem where

> You are given two eggs and access to a 100-story building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

# Answer
> -1 votes
The question is badly posed, either because the person posing the question isn't very good at writing English, or because you copied or paraphrased it badly. As asked, we have no idea what "an optimal strategy" is or what it is supposed to be. The crux of the problem is in "giving the current at which the battery is known to explode" instead of "giving a current at which the battery is known to explode". And of course "will always explode if there’s any risk of explosion at that current" is more than problematic.

In the "two egg problem" the optimal strategy is obviously one that minimises the number of stairs that I need to climb, which is likely to invalidate most answers that you find.

In case of the battery, I'd investigate how long it takes until the battery explodes, how much money the tester is paid per hour, and what the cost of an exploding battery is, and determine the optimum strategy from this information.

---
Tags: software-testing, testing
---


# Question
Title: Why is the inverted index called so and not simply index?
In my notes is represented like this:

From wikipedia:

> In computer science, an inverted index (also referred to as a postings file or inverted file) is a database index storing a mapping from content, such as words or numbers, to its locations in a table, or in a document or a set of documents.

**Where is the inversion** with respect to a normal index (like the one found at the end of books)?

> Index: (in a book or set of books) an alphabetical list of names, subjects, etc. with reference to the pages on which they are mentioned.

**Am I missing something?** Like a nuance of the meaning of the name due to the fact that english is not my main language.

# Answer
> 17 votes
Here is an array:

* A\[0\] = Alice
* A\[1\] = Bob
* A\[2\] = Charlie

Here 0,1,2 are indices.

Now suppose that we want to know which index contains a given word. Then we use a dictionary:

* D\[Alice\] = 0
* D\[Bob\] = 1
* D\[Charlie\] = 2

This is an inverted index (according to your Wikipedia quote).

---

The word index has different meaning in different contexts:

* Technical books often have an index of terms at the end.
* The Catholic church held an index of forbidden books.
* In economics, there are financial indices.
* In computer science, an index is usually an integer used to index into an array.

# Answer
> 9 votes
The reason why we use the term "inverted index" is that the term "index" came to computer science first. In fact, it has several common meanings in computer science, but in this case it refers to the more general concept of an efficient lookup data structure for a database.

What we call an "inverted index" is, strictly speaking, an inverted *file* used as a database index. "Inverted file" is the data structure, and "index" is the use to which it is put. A B-tree data structure, similarly, can be put to more uses than just database indexing, but it makes sense to talk of a "B-tree index".

The index in a book is not the only kind of text index. *Strong's Concordance*, which is considered an important ancestor of modern full-text search, is a *permuted* index (specifically, a variant known today as a KWIC index).

The inverted file is not the only data structure that can be used for text/string indexing. Suffix arrays and Burrows-Wheeler indexes are commonly used for strings that don't need linguistic analysis such as indexing DNA or RNA sequences. Some of these index variants have efficient partial match queries.

The signature file (a probabilistic index structure, essentially Bloom filters for text search) was briefly popular, but it turned out to be nowhere near as generally useful as its competitors.

# Answer
> 3 votes
# It's Relative

The distinction is between "keys" and "values". However, what counts as a "key" vs. a "value" *depends on the maintainer*. Consider a phone book. Most people would keep a phone book around because they know the name of someone they wish to call, but don't know their phone number. Thus, the book is arranged with *names* as the key, and *phone numbers* as the value. On the other hand, it is also useful to see a phone number which is calling you, and know the name associated with it. We generally call this service "Caller ID". Since this mapping from *phone number* to *name* inverts the most common search, one might call the database which contains this information an "inverted index" from values to keys. Even so, it's merely a matter of perspective. The phone company may very well maintain the information in a database with the number as the primary key and the subscriber as a non-key field, which would therefore cause the Caller ID function to depend on an "index", while the phone book would be considered an "inverted index".

# Google

Since the URI is, by definition, the canonical way to identify a web page, it is natural to use the URI as the key when building a collection of web pages (relational theory tells us that the primary key should be unique for each tuple, although that is not really true for URIs, since they have relative addressing and aliases). Unfortunately, this is only useful for answering queries like: "Which URLs contain the word 'cat'?" Most users are not interested in such queries. Most users are more interested in searching not by the *keys* of this index, but rather by the *values*: "Which *pages* contain the word 'cat'?"

Now, we know that URIs are *logically* the *keys* to a web search index, because you can't follow *content words* from one page to another. You can only follow URIs. Further, if your crawler ends up at the same page from multiple pathways, you don't want to store the page multiple times as distinct entities. You want to ensure that each page is stored at most once. This is also a good reason to use the URI as the index. However, in order to support the *content search* function, it is useful to create a mapping from content words to URIs. Since the page content is considered the *values* of the index, this *value* to *key* mapping is therefore called an "inverted index".

If, for some reason, it were more natural to index web pages internally by their content, then that would be considered the "forward index", and the URI to page mapping would become the "inverted index". But web pages resist this categorization because the content is not necessarily stable over time, while the primary key of a tuple should remain immutable (and effectively, HTTP attempts to enforce this by providing redirects when the URI for a page logically changes). Thus, URI to page content is strongly preferred as the "forward mapping".

# Books

If you want to know what page a particular word appears on in a book, you may have to search the whole book to find the answer. Thus, the "index" in a book maps from keywords to pages. But if you want to know what words appear on a particular page in a book, you just need to turn to that page and you will find the answer after reading at most one page. Random access to a particular page in a book is fast and efficient (relatively speaking), which is why books generally don't come with a mapping from page numbers to keywords (wouldn't that be an unusual book?!). However, one *could* make the argument that the *page number* is the most natural "index" for the content in a book. I would base this argument on the fact that indexed access is usually the naturally fastest access method for a database. Note that word-based access without an index is essentially *sequential* (assuming the book is not specially ordered, like a dictionary). From this perspective, one could quite reasonably argue that the "index" in a book is really an "inverted index", in very close analogy to the Google scenario. We simply define the *page number* as the "URI" for page content within a book, and you have a kind of isomorphism between book pages and web pages (complete with the fact that textbooks will sometimes refer to other pages within the book by page number or chapter).

# Memory

If we examine computer memory, we see that the CPU only allows us to access its contents by *address*. Therefore, the memory address is the "key" to the datastore that we call "working memory". If you had the query: "Tell me the locations which contain the value 0x12345678", you would be frustrated by the fact there are no machine instructions which perform this function (although, CISC architectures like x86 come close with instructions like REPNZ SCAS).

When a memory is specifically designed for the inverse value to key search, we call it a "content-addressable memory". This can be implemented in hardware or software (but most commonly in software, via associative maps of all kinds). Again, the fact that searching for a value by address is easy, while searching for an address by value is hard biases the definition of "key" and "value" for the case of general memory in a very natural way. Good luck finding someone who calls a MOVE instruction an "inverted index" because they think of memory contents as keys and addresses as values.

# Conclusion

While an "index" does not necessarily require a unique set of keys, this is almost universally preferred. And, since the majority of mappings in the world are not bijective, it is often the case that the "values" for an index are far from unique. These facts orient the "natural" definition of an "index": a mapping from a set of unique keys to non-unique values. Then, the inverse mapping is naturally an "inverted index".

A quick rule of thumb to tell whether you are looking at an index or an inverted index to ask: "How many results do I get for this key?" If the answer is: "Zero or one", then you are probably querying an index. If the answer is: "Zero to many", then you are probably looking at an "inverted index". And so, contrary to convention, you should think of the table at the end of many books as an *inverted index*, rather than an "index". ;)

---
Tags: data-structures
---


# Question
Title: string concatenation vs language concatenation
What exactly is the difference between $$ C = \\{a^\*\\}\\{b\\}\\{a^\*\\}\\{b\\}\\{a^\*\\}\\{b\\} $$ and $$ D = \\{a^nba^nba^nb | n \geq 0 \\} $$

It is known that D is non-regular and C is regular, but I am not sure why.

# Answer
> 0 votes
The exact difference is that the expression for D uses -the same n- for all the 'a' substrings. The expression for C *does not* impose that restriction on its strings, i.e each of the 'a' substrings of a string in C *may or may not* be of different lengths.

# Answer
> 0 votes
C is a regular expression over $\Sigma\\{a,b\\}$. We can design a finite automaton that can accept the language which can be generated from C. On the other hand, the language D is not regular. Using pumping lemma for regular language it can be proved that D is not regular. Hope this will help you. If you need more explanation then please feel free to ask.

---
Tags: formal-languages, regular-languages, finite-automata, strings, theory
---


# Question
Title: Better word to describe JavaScript "algorithm"?
For my undergraduate senior project, a professor asked me and my partner to design an algorithm to determine true resolution in the browser, unaffected by zooming, multiple screens, viewport size, etc. (tl;dr our implementation was okay, it usually did the job correctly.)

It's super pedantic, but I've been thinking about the terminology of calling it an "algorithm". It really doesn't seem like an algorithm, because it's very dependent on JavaScript and the state of the browser at a given time. Particularly, our script has a lot of if-statements to determine what what variables and data to work with depending on the browser and configuration. I certainly don't think I could write it out in a language-agnostic pseudocode.

Is there a better word to describe what we wrote? Does it count as an "algorithm" per say? If I had to think of alternate words, they'd be:

* implementation (but of what, just our general idea/design?)
* script/program

Are there better words that are more general than simply script or program?

# Answer
You can certainly describe the inner workings of your project as an algorithm. It takes an input (whatever information it obtains from the browser) and produces an output, as a result of some scheme of calculations. Perhaps it needs to read inputs during the course of its calculations (depending on the first inputs, it might make different queries of the browser), so it might be some sort of interactive or adaptive algorithm.
> 6 votes

# Answer
In my opinion anything that is language specific would not be considered an algorithm but a solution. So in your case you came up with a javascript solution to solve your problem. I think you answered your own question when you said you could not write the pseudocode. If your solution can not be written in psuedocode then i would not classify it as an algorithm.
> 2 votes

# Answer
"...the most common misconception that an algorithm and a pseudocode is one of the same things. No, they are not! Let us take a look at definitions first:

*Algorithm* : Systematic logical approach which is a well-defined, step-by-step procedure that allows a computer to solve a problem. (Can be what's in the code-side Notes explaining the performance steps of a function, in the case of good Notes.)

*Pseudocode* : It is a simpler version of a programming code in plain English which uses short phrases to write code for a program before it is implemented in a specific programming language.

*Program* : It is exact code written for problem following all the rules of the programming language." (https://www.geeksforgeeks.org/difference-between-algorithm-pseudocode-and-program/?ref=lbp)

Your professor highlighted the endeavor of algorithm to correctly and fully assess a # of applicable and inapplicable inputs and thus arrive at an accurate and full solution to the specifically suggested solvable problem. Your program \[sufficient language usage\] derives from its algorithm \[procedural logic of arrangement thereof\] to provide an adequate and honest answer to the question of underlying browser resolution. Emphasis on logic of methodology may be taken for granted in programs... you had to eliminate dependencies to attain accurate information regarding any given browser, regardless of values set among different properties offered within features of the browser.

Your *pseudocode* transforms the task-list of your *algorithm-based* procedure (logical multi-steps, exhaustive/conclusive operations, "only-every" aspect and behavior that must factor into the solution posited by a program to offer true solution) into *more codiFIED* instructions, as are better understood by the eventual machine code understanding of a running computer. However, "pseudocode is not an actual programming language... Many time algorithms are presented using pseudocode since they can be read and understood by programmers who are familiar with different programming languages. Pseudocode allows you to include several *control structures* such as While, If-then-else, Repeat-until, for and case, which is present in many high-level languages..." Pseudocode remains a high-level understood meld of syntax and symbols to *structurally signify* the *roles* of programming articulation in the final draft... If the program wasn't accurate in some browser cases, and not for the code of the program throwing errors or negating designed tasks, were some browser aspects not considered within the design itself of your algorithm (i.e. approach to solution?)
> 1 votes

---
Tags: algorithms, terminology
---


# Question
Title: How to use DFA/NFA to prove the language {$0^n 1^$ | x ∈ Σ*, n ≥ 1} is regular?
I'm trying to prove the language L = {$0^n 1^$ | x ∈ Σ\*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA. I'm thinking to have n+1 states in a NFA, with the start state as the accepting state. The NFA reada $0$s to go from q$0$ to q$n+1$, then reading $1$s or $0$s to stay in the q$n+1$, then reading the same number of $1$s to go back to the q$0$. Is this a valid way to prove L is regular?

# Answer
Your language consists of all words starting with $0$ and ending with $1$.
> 3 votes

# Answer
Your solution depends on $n$. In this case the $n$ in the formulation of the language is not a constant, but a variable ranging over the positive integers $n\ge 1$. So we need strings of the form $0^n x 1^n$ for any $n\ge 1$, and any $x\in\Sigma^\*$.

In general that would not be possible with a FSA, it cannot count and compare the numbers of $0$'s and $1$'s, but this is a trick question. See the answer by Yuval.
> 2 votes

# Answer
Your language is regular and can be rewritten as $$ L = {0\Sigma^\*1} $$ (start with 0 end with 1)
> 1 votes

---
Tags: automata, finite-automata, pushdown-automata, discrete-mathematics, computational-linguistics
---


# Question
Title: How to tell if a grammar is LALR(1) formally?
There is an “informal” definition of $\operatorname{LR}(k)$ (can be recognised by a parser that looks at $k$ symbols ahead) and a “formal” one (as a property of the set of rightmost derivations possible for the grammar). Is there a similar formal criterion of a grammar being $\operatorname{LALR}(k)$ or specifically $\operatorname{LALR}(1)$?

For context, I am interested in looking into grammar transformations that preserve the property of being $\operatorname{LALR}(1)$ (for example, does eliminating right recursion in an $\operatorname{LALR}(1)$ grammar result in a grammar that is still $\operatorname{LALR}(1)$?)

# Answer
The answer to your first question is: Not that we know of.

A grammar is $\hbox{LALR}(k)$ if and only if its $\hbox{LALR}(k)$ automaton is deterministic. The only way that we know of checking that a grammar is $\hbox{LALR}(k)$ is to build the automaton, or something that essentially amounts to building the automaton.

The good news is that the key complication is empty derivations. So, for example, if a $\hbox{LL}(1)$ grammar has no nonterminals that have *only* empty derivations (i.e. if every nonterminal has at least one non-empty derivation), it is $\hbox{LALR}(1)$.

See Beatty, *On The Relationship Between LL(1) And LR(1) Grammars* for further results. You may find something in there that's useful to you.
> 1 votes

# Answer
Eliminating right-recursion can create parsing conflicts in an LALR(k) grammar.

Here's a very simple example with $k=1$.

$$\begin{align}S&\to L R\\ L&\to \epsilon\\ L&\to L a b\\ R&\to \epsilon\\ R&\to a c R\\ \end{align}$$

That grammar is LALR(1). If you change R to left recursive:

$$\begin{align}S&\to L R\\ L&\to \epsilon\\ L&\to L a b\\ R&\to \epsilon\\ R&\to R a c\\ \end{align}$$ then it becomes LALR(2). (It's easy to produce grammars where the discrepancy is higher.)
> 1 votes

---
Tags: formal-languages, formal-grammars, reference-request
---


# Question
Title: Applying the Pumping Lemma to aspecific string
Given the language $ A = \\{w \in \\{a,b\\}^{\*} | w = w^{R}\\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$.

From my understanding of the Pumping Lemma, to show it would hold, I need to decompose $ s $ into $ s = xyz $ such that (1) $ xy^{i}z \in A, i \geq 0 $, (2) $ y \neq \epsilon $, and (3) $ |xy| \leq p $.

For cases where $ p \geq 2 $, the decomposition makes sense to me and appears to be quite trivial. For example, when $ p = 2 $, then $ s = aaaa $, and can be decomposed into $xyz$ where $x = a, y = a, z = aa $, which satisfies the conditions above above. Induction could be used to show this holds for larger values of $ p $.

However, I am struggling on the case where $ p = 1 $. Here, $ s = aa $, and it seems like there are not enough symbols to decompose into $ xyz $. My best guess would be to choose $ x = a, y = a, z = \epsilon $, but for some reason this doesn't feel legal -- can you ad-hoc assign pieces of $ xyz $ to be $ \epsilon $? Also, I believe this decomposition would fail to satisfy condition (3) above. Can you offer some guidance on understanding what is happening in the case where $ p = 1 $?

Thanks for your time!

# Answer
> 0 votes
The empty string is a legitimate string, just like the empty set is a legitimate set. We say that a word $w \in \Sigma^\*$ can be *pumped* with respect to parameter $p \geq 1$ and a language $L$ if there exists a decomposition $w = xyz$, where $x,y,z \in \Sigma^\*$ satisfy the following three requirements:

* $|xy| \leq p$.
* $y \neq \epsilon$.
* $xy^iz \in L$ for all $i \geq 0$.

A mathematical definition hides nothing. A word can be pumped if it satisfies the definition as stated. No more, no less.

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


# Question
Title: Arrange in increasing order of asymptotic complexity
I have the following functions that I need to rank in increasing order of Big-O complexity:

$$(\log n)^3, 10\sqrt n, n\log n, n\sqrt n, n^4 + n^3, (2.1)^n \cdot n^2, 3^n, 2^n \cdot n^3, n! + n, n^n. $$

My current ranking is as follows:

$$(\log n)^3 \< 10\sqrt n \< n\log n \< n\sqrt n \< n^4 + n^3 \< (2.1)^n \cdot n^2 \< 2^n \cdot n^3 \< 3^n \< n! + n \< n^n. $$

Is my ranking of the functions in increasing order of complexity correct?

# Answer
> 13 votes
You have mistake in $(2.1)^n \cdot n^2\<2^n \cdot n^3$, because it is equivalent $\left(\frac{2.1}{2}\right)^n\<n$

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