# Question
Title: Permute rows of a matrix to minimize total number of inversions of its column vectors
Let $A$ be an $n \times k$ matrix of real numbers.

I'm looking for an exact algorithm to find a permutation of the rows of $A$, in such a way that the total number of inversions found in the resulting $k$ column vectors is minimal. That is, if $B$ is a row-wise permutation of $A$, I want to minimize:

$$ L(B) = \sum \_{j = 1} ^k \iota (B ^ j),$$

where $\iota(x)$ is the number of inversions in the array $x$, and $B^j$ denotes the $j$-th column of $B$.

I tried to do some basic research on the topic, but could not find anything particularly relevant. The $k=1$ special case amounts to simple array sorting, and I'm hoping one could generalize some array sorting algorithm to this more general case.

Any hint and/or reference would be very appreciated, thanks!

Side note: in the special application I have in mind, $n$ is small (around $100$), so that any solution with time complexity less than, say, $2^n$, could work for all practical purposes.)

# Answer
While I do not have an answer, I have given this some thought and would like to share my ideas.

I am making two simplifying assumptions but the general case shouldn't be much harder.

1. All numbers are distinct on each column.
2. $k$ is odd.

Now let $c\_{i,j}$ be the number of inversions caused by putting row $i$ above row $j$; that is, the number of columns $l$ for which $A\_{i,l} \> A\_{j,l}$. For the rest of the argument, we can ignore $A$ and work with the matrix $c$. Due to assumption 1, $c\_{i,j} + c\_{j,i} = k$ for all row pairs. Furthermore, due to assumption 2, $c\_{i,j} \neq c\_{j,i}$ and exactly one of the two will be smaller than $k/2$. When $c\_{i,j} \< k/2$, we say that row $i$ *dominates* row $j$.

Domination among rows can be cyclical as illustrated by the three rows below. Row 1 dominates row 2 (columns 1, 2 and 3 have smaller elements, thus $c\_{1,2} = 2$ and $c\_{2,1} = 3$), row 2 dominates row 3 and row 3 dominates row 1. Note that, for every pair of rows $i$ and $j$, either $i$ dominates $j$ or viceversa. You can view this as a tournament graph with $n$ nodes.

```
(1 1 2 3 3)
(2 2 3 1 2)
(3 3 1 2 1)

```

The task with these notations is to find a permutation of rows $\pi$ which minimizes

$$ \sum\_{i\<j} c\_{\pi(i), \pi(j)}$$

Let us consider what happens if we swap two consecutive elements, $\pi(i)$ and $\pi(i + 1)$. Those elements do not move relative to the other $n-2$, only relative to one another. The total cost changes by

$$ -c\_{\pi(i),\pi(i+1)} + c\_{\pi(i + 1),\pi(i)} = \\ -c\_{\pi(i),\pi(i+1)} + (k - c\_{\pi(i),\pi(i + 1)}) = \\ k - 2 \cdot c\_{\pi(i),\pi(i + 1)} $$

Since $\pi$ is optimal, it follows that the swap must increase the cost, hence

$$ c\_{\pi(i),\pi(i + 1)} \< k/2 $$

, in other words row $\pi(i)$ dominates row $\pi(i + 1)$. This holds for every consecutive pair of rows in the permutation. It follows that, if any of the $n$ rows dominates all the others, then no other rows may come before it in $\pi$. It must necessarily be placed first and we can reduce the problem by one row.

This is where I got stuck. If all the rows are part of a cycle in the tournament graph mentioned above, I do not know how to break the tie. Still, the following backtracking algorithm might perform well, depending on how adversarial your data is.

Assume we have filled $\pi(1...i-1)$. If there exists a row that dominates all the remaining rows, place it at position $i$ and recurse. Otherwise, from the remaining rows, iterate among those dominated by $\pi(i-1)$. Place each of them at position $i$ and recurse. Some heuristic might be useful here to prune the backtracking more quickly. For example, we could consider rows in increasing order of

$$\sum\_{j \in \mbox{ remaining rows }} c\_{i,j}$$

Keep a running cost of the permutation so far. If at any point it exceeds the minimum cost found so far, go back one level.
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: Can you help me find some examples of 3co-SAT for 4 variables?
I've been studying the examples of 3co-SAT recently.

It's easy to find an example of one variable.

$(x\_1\lor x\_1\lor x\_1)\land (\overline{x\_1}\lor \overline{x\_1}\lor \overline{x\_1})$

Examples of 2 variables are as follows.

$(x\_1\lor x\_2\lor x\_2)\land (x\_1\lor \overline{x\_2}\lor \overline{x\_2})\land (\overline{x\_1}\lor x\_2 \lor x\_2) \land (\overline{x\_1}\lor \overline{x\_2}\lor \overline{x\_2})$

Examples of 3 variables are as follows.

$(x\_1\lor x\_2\lor x\_3)\land (x\_1\lor x\_2\lor \overline{x\_3})\land (x\_1\lor \overline{x\_2} \lor x\_3) \land (x\_1\lor \overline{x\_2}\lor \overline{x\_3}) \\ \land (\overline{x\_1}\lor x\_2 \lor x\_3)\land (\overline{x\_1} \lor x\_2 \lor \overline{x\_3}) \land (\overline{x\_1} \lor \overline{x\_2} \lor x\_3) \land (\overline{x\_1} \lor \overline{x\_2} \lor \overline{x\_3})$

But I can't find examples of four variables. Can you help me find some examples of 3co-SAT for 4 variables?

# Answer
CNF is only used to describe problem formally, but it's kind of hard for human to understand it. Entailment is such tool that used to write "readable" formula. You can use propositional rules to give a contradiction.

Here is how i work it out:

First, given an unsatisfied clause using Entailment:

$A\wedge B\rightarrow C\wedge D, \neg(C\wedge D)\rightarrow (A\wedge B),\neg(C\wedge D)$

This breaks the Transpostion, it's certainly unsatifiable.

Secondly, rewrite it to CNF. For short, I use comma instead of a lot of $\wedge$s.

$$ (\neg A\vee \neg B) \vee (C\wedge D), (C\wedge D)\vee (A \wedge B),\neg C\vee \neg D $$

Use rules to simplify that, we get

$$ \neg A\vee \neg B\vee C,\neg A\vee \neg B\vee D, C\vee A,C\vee B, D\vee A, D\vee B, \neg C\vee \neg D $$

The variables in clause are less than 3. If you want a strict 3-CNF, you can simply repeat some literal in that clause.

May this help you.
> 0 votes

---
Tags: complexity-theory, np-complete, satisfiability, 3-sat, sat-solvers
---


# Question
Title: proof that every sentence obtainable by left-most derivations only when Greibach normal form
Could someone help me prove the following statement: “For any grammar in Greibach normal form, every sentence is obtainable by left-most derivations only.” I see that this is trivial, but I can't manage to start a formal proof of this statement.

What I thought is: Since every derivation in Greibach Normal Form has a form of A -\> aX or A -\> a with 'a' being a terminal and X being 0 or more variables, we can see that going from left to right we can get each terminal 'b' of the string by taking the corresponding production rule with B -\> bY. I think that whatever grammar it is, we can always say that every sentence is obtainable by left-most derivations and also by right-most derivations.

# Answer
> 2 votes
The fact that the grammar is in Greibach Normal Form does not contribute to the assertion being proved. For any context-free grammar $G$ with start symbol $S$, $\omega\in L(G)\iff S\Rightarrow\_{lm}^\*\omega$. It's not necessary to restrict the syntax of the productions of $G$ beyond the restriction imposed by the context-free restraint (which is that there is exactly a single non-terminal on the left-hand side of every production).

An essential observation about context-free grammars is that it doesn't matter which order you expand the non-terminals in a sentential form. (That's the origin of the description "context-free".) Regardless of which non-terminal you expand, you will end up with the same set of possible sentential forms and therefore the same set of sentences.

There are a number of ways to prove this simple statement, but I think the easiest is probably to use parse trees as an intermediate representation. A derivation is precisely a topological ordering of the non-leaf nodes in the parse tree. Unless the tree is linear, there are many such orderings, but since they all end with the same sentence, the tree is capturing an equivalence relationship less evident in the collection of derivations. With the parse tree in hand, it's easy to show that the leftmost derivation is the preorder left-to-right depth-first traverse of the tree, while the rightmost derivation is the preorder right-to-left depth-first traverse. Consequently, there is a unique left-most derivation corresponding to each parse tree (as well as a unique right-most derivation), which proves the original assertion.

Filling in the details in this proof outline is exercise 24 in section 5.1 of Peter Linz's *An Introduction to Formal Languages and Automata* (in the old edition I managed to find); it is not marked with a star so I guess the author considers it relatively easy to complete.

---
Tags: automata, context-free, normal-forms, derivation
---


title: Delaunay triangulation from an EMST

text:
# Question
Title: Delaunay triangulation from an EMST
Assume you know the Euclidean Minimum Spanning Tree of a set of $n$ 2D points (in general position).

Is there an efficient way (faster than $O(n \log n)$ operations) to obtain the Delaunay triangulation of these points ?

# Answer
> 1 votes
The Wikipedia article states, that:

> the Delaunay triangulation can be constructed from the Euclidean minimum spanning tree in the near-linear time bound $O(n\log ^{\*}n)$, where $\log ^{\*}$ denotes the Iterated logarithm.

This article refers to the paper, where you can find a randomized algorithm for the problem you're interested in.

---
Tags: computational-geometry, minimum-spanning-tree, triangulation
---


# Question
Title: Are there syntactic conditions on divergent $\lambda$-terms?
Probably the most famous example of a divergent term (ie, one which admits infinitely many $\beta$-reductions) in the $\lambda$-calculus is the Y combinator

$$ Y = \lambda f. (\lambda x. f(xx)) (\lambda x. f(xx)) $$

The kind of the "heart" of the recursion here is the inclusion of the subterm $xx$. I wondered if this is true in general; ie, if we have the theorem

$$ E \text{ is a divergent $\lambda$-term} \implies E \text{ contains a subterm of the form } AA $$

(Note: $A$ can be any term, not just names as in $A = x$).

The answer is *no*. The following term reduces to itself (and thus diverges), but does not contain a subterm of the form $AA$.

$$ \begin{align\*} &(\lambda ab.bab) (\lambda ab.aba) (\lambda ab.bab) \\ \rightarrow\_\beta& (\lambda b.b(\lambda ab.aba)b)(\lambda ab.bab) \\ \rightarrow\_\beta& (\lambda ab.bab) (\lambda ab.aba) (\lambda ab.bab) \end{align\*} $$

However, this term does contain the subterm $bab$, which although not of the form $AA$ is of the form $AYA$, which also looks suspicious.

Is there any such "syntactic" condition on divergent terms?

Here's a conjecture: if $E$ is a divergent $\lambda$-term, then $E$ contains a subterm $S$ of the form $S = F A\_1 A\_2 \cdots A\_n$ where at least one $A\_i$ contains $F$ as a subterm. That is, "for a term to be divergent, it must afford itself the possibility for a subterm $F$ to receive itself as an argument"

(The converse is false, as $(\lambda x.xx)(\lambda a.a)$ satisfies this via inclusion of $xx$ but does not diverge)

# Answer
This is essentially the criterion used by type systems to avoid divergence. Take, for instance, the simply typed lambda calculus. In order for $f\ x$ to be well typed, we must have:

$$f : T → U \\ x : T$$

In order for $f\ f$ to be well typed, it would have to be the case that:

$$T = T → U$$

But types are required to be inductively generated by $→$ and some base types, so there is no type that satisfies this equation. Similarly, in order for $f$ to receive itself as an argument at all, it would have to be the case that:

$$T = \cdots → T → \cdots$$

which is not allowed.

More elaborate type systems can allow some cases of self-application without enabling divergence. For instance, in the polymorphic lambda calculus, we can write:

$$λ(f : ∀T. T → T). f\_{∀T. T → T}\ f$$

In this case, it is safe because $f$ can only be the identity function. Or, even more precisely, intersection types allow cases of self-application like so:

$$λ(f : T \cap (T → U)). f f$$

and these sort of intersection types classify *exactly* the normalizing lambda terms. I suspect the intuition is that for any normalizing term involving self-application, only finitely many unfoldings of the $T = \cdots → T → \cdots$ equation are necessary, and can be expressed by a finite intersection, while the diverging terms genuinely require an infinite type that cannot be sufficiently approximated by any finite intersection.
> 1 votes

---
Tags: lambda-calculus
---


# Question
Title: A nearest neighbor data structure for meshes
I am trying to find a lightweight data structure to find the nearest neighbor mesh (a mesh being a collection of non-unique triangles) for a given point in R3 (3D Euclidean space). I have seen nearest neighbor problems for points and triangles, but never meshes as a whole collective.

So, in essence given a point P find the nearest mesh M to the given point P from a collection of meshes (some sort of query structure so this can be done over and over again), where the nearest neighbor mesh M is defined as the shortest Euclidean distance in R3 between the point P and the nearest point on a triangle in the mesh M. I was thinking maybe some sort of generalized voronoi diagram where each cell is associated to a list of meshes, but I start thinking about concavity of meshes and intersecting meshes and the point P inside of closed meshes and the point P inside of intersecting closed meshes and even the all the previous cases with open meshes then I am lost. Is there any such known structure for this? Any help would be appreciated! Thanks

# Answer
> 2 votes
It suffices to store all of the triangles from all of the meshes in a nearest-neighbor data structure for triangles. Then, given a point P, find the nearest triangle, check which mesh that triangle is a part of, and that will be the nearest mesh.

---
Tags: data-structures, computational-geometry, search-algorithms, nearest-neighbour
---


title: Big O notation simplification from sum

text:
# Question
Title: Big O notation simplification from sum
On calculating the convexity of an optimization problem, I am getting a term $O(\sqrt{n+m}(n)^3)$. Here both $m$ and $n$ are parameters. Is there any way I can simplify this term to write it as a product?
I know that if time complexity $T(n,m)=O(\sqrt{n+m}(n)^3)$, then $\exists C,M $ such that $\vert T(n,m) \vert \leq C\vert \sqrt{n+m}(n)^3 \vert $ when either $n,m \geq M$. I need the simplification for the interpretation of the algorithm. (Like, if time complexity is $O(n)$, then if $n$ is multiplied by 10, then the time complexity is also multiplied by 10. But it seems such an interpretation is not possible in the above case, as $m$ and $n$ are independent terms in summation).

# Answer
Presumably you are after a substitution like$$\sqrt{n+m}\\,n^3\le f(n)\\,g(m),$$ or equivalently

$$n+m\le p(n)\\,q(m).$$

If you freeze $m$, then $p(n)=\Omega(n)$ must hold (and similarly $q(m)=\Omega(m)$). So I see no better solution than

$$\sqrt{n+m}\\,n^3\le\sqrt{nm}\\,n^3= n^{7/2}m^{1/2}.$$
> 1 votes

# Answer
If you multiply $m$ by $10$, the magnitude of the term varies by a factor

$$\sqrt{\frac{n+10m}{n+m}}=\sqrt{\frac{\frac nm+10}{\frac nm+1}}.$$

That factor stays in range $\left(1,\sqrt{10}\right)$ and varies relatively little as a function of $\frac nm$.

If you multiply $n$ by $10$, the magnitude varies by $1000$ times a similar factor.

So it is not very wrong to explain the complexity as "roughly $n^{7/2}$".
> 1 votes

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


# Question
Title: Algorithm for merging arrays while keeping their order
My question is generalizable to arrays of any type but I'll use strings to keep it short.

We take a couple of strings as an input. Let's denote them ${S\_1,...S\_n}$. (Ex: "ABEF" and "CDE"). The output $U$ must fulfill the following conditions:

* The output must contain the entire "vocabulary" of all of the inputs and not more: $x\in U \Leftrightarrow \exists i : x\in S\_i$
* Each element in the output appears only once in the output.
* The elements in the output keep their relative ordering from their original strings. So if 'A' comes before 'B' in the string $S\_i$, then 'A' must come before 'B' in the output $U$.

The problem can have multiple solutions or no solutions. I'm fine with finding just one of them. Some examples might be:

| inputs | possible solutions |
| --- | --- |
| ABEF, CDE | ABCDEF, CDABEF, CABDEF... |
| ABEF, CDE, BC | ABCDEF (only solution) |
| ABEF, CDE, CB | CDABEF, CADBEF, ... |

I found this question with a similar algorithm. However, their algorithm allows repeated elements in their output.

Is there a name for this algorithm? What's the time complexity? Does anyone know an implementation in a Python library? Thanks!

Clarifications:

* the inputs do not have an ordering. The ordering is given by the inputs themselves. That's why "CDABEF" is a valid solution in the first example.
* If the problem does not have a solution, throw an exception.

# Answer
> 23 votes
You can easily solve your problem by creating a directed graph $G=(V,E)$ in which $V$ is the set of all characters that appear in some input string and $E$ contains the edge $(u,v)$ if character $u$ is immediately followed by character $v$ in some string.

This graph has $O(n)$ edges where $n$ is the total length of the input (i.e., the sum of the strings' lengths) and can be built in $O( \min\\{n+|\Sigma|, n \log n\\} )$ worst-case time, where $\Sigma$ is your alphabet (if the alphabet has constant size then this is just $O(n)$) or $O(n)$ expected time.

Then your problem admits a solution if and only if $G$ is a directed acyclic graph (DAG). This can be tested in $O(n)$ time. If $G$ is indeed a DAG, any topological ordering of the vertices in $G$ is a valid solution to your problem. A topological ordering of $G$ can be found in $O(n)$ time.

---
Tags: algorithms, time-complexity, sorting
---


title: Boolean Logic for Floats

text:
# Question
Title: Boolean Logic for Floats
I would like to know whether a theory exists which generalizes boolean logic to floats.

Specifically, assume that instead of booleans 1 and 0, I have True/False *tendencies*, such as 0.9, where 0.1. Here, 1.0 would mean completely true, and 0.0 completely false.

Boolean logic:

```
0 && 1 # == 0
0 || 1 # == 1

```

It should be possible to have an equivalent for floats:

```
1. && 0.9 # == 0.9, because 1. * 0.9 = 0.9
1. || 0.9 # == 1., because 1 + 0.9 - 1. * 0.9 = 1.

```

Is there a theory for this?

# Answer
> 3 votes
I recommend that you look up 'Fuzzy Logic'.

---
Tags: logic, combinatorics, arithmetic
---


# Question
Title: Turing Machines time complexity with regard to the NP and P problem
I'm studying Turing machines and I came across the following definitions:

> NP is the set of problems that can be solved in polynomial time by a non-deterministic Turing machine.

and

> Let t(n) be a function, where t(n) ≥ n. Then every t(n) time non-deterministic single-tape Turing machine has an equivalent 2^O(t(n)) time deterministic single-tape TM.

From what I understand, the second theorem is closely related to the P = NP problem.

My question is:

Why does it actually matter so much whether we can convert a non-deterministic TM running in polynomial time to a deterministic TM running in polynomial time? What are the 'advantages' of a deterministic TM over the non-deterministic one?

# Answer
> What are the 'advantages' of a deterministic TM over the non-deterministic one?

The advantage of the deterministic TM is that deterministic Turing Machines represent the type of computation we are capable of, whether by hand, calculator or computer. The non-deterministic Turing Machine includes a power our intuitive computation does not have – the power to branch out its computation indefinitely (often also conceptualized as "the ability to make lucky guesses").

At any point of its computation, a NTM can choose to perform two (or more) different actions at the same time. This results in more than one "parallel copies" of the same Turing Machine existing, at different states. These parallel copies of the machine can spawn further parallel copies in a tree-like multiverse. The execution of all of these parallel copies is halted whenever any of them accepts the input string, or all of them have rejected it.

As an example of how this can be applied to solve an actual problem, consider a NTM solving a SAT problem. A NTM can simply read the logical statement and assign *both* true and false values to each variable in a separate branch. Finally, every branch can simply read their version of the statement and accept if they ended up with a satisfied one, reject otherwise.

Sadly, not having access to NTM, we cannot solve problems as simply – our deterministic tools cannot spring forth infinite universe to try solving the instance in, and can at best emulate non-deterministic models one branch of the tree at a time. If we had access to an NTM, it would be a superior model, but such machines are unlikely to be possible in our world. Hence statements about deterministic Turing Machines are likely to be of much more practical interest than those about non-deterministic ones.
> 4 votes

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


title: Are Control Flow Graphs(CFG) planar?

text:
# Question
Title: Are Control Flow Graphs(CFG) planar?
I notice there are different definitions for CFG(basic block or statement), so let's consider following definition:

> Given a program, each statement is a node in CFG, and $(u,v)\in E\iff \text{v is successor of u ,or u is branch and u's target is v}$

Due to such definition, each node has atmost two out-edges. So we can't construct a $K\_{3,3}$ or $K\_{5}$ directly, and I have no idea how to move on. I've searched the web and found this, but I can't understand the examples. It looks like a different definition, for example, the last image seems to suggest that three `m(i)` are the same one, but in my opinion, they are executed one by one.

`Goto` is harmful to control flow, so I'm curious if we do not use `goto`, are CFGs always planar? If this is wrong, can we always write a programm whose CFG is planar without loss of function?

# Answer
> If this is wrong, can we always write a program whose CFG is planar without loss of function?

Yes, we can.

Suppose we have an arbitrary CFG $G$, which is a finite graph.

> It is known that any finite graph can be embedded into a three-dimensional space. - Wikipedia

Let's say for our CFG, we have a 3D embedding $E:G\mapsto\mathbb{R}^3$.

Of course, if we naively project such graph onto a plane $P$, it would not be planar in general.

However, two intuitions can help us see how we can always make a planar CFG functionally equivalent:

* With some techniques, it is possible to define our $E$ such that its projection $E\_P$ on $P$ is **nice**, such that the **only reason** $E\_P$ is not planar is that there are intersections between two edges (or should we say, the images of the edges). Such nicety excludes the following situations:
    + Two edges lie on the same line.
    + A node is passed through by an edge.
    + Three edges intersect at the same one point.
    + .etc
* There is a way to emulate an intersection of two edges using only planar structure.
    + Diagrammatically, for an intersection, we can make the following transformation $\tau$:

```
A  C         A'  D'
 \/    ==>    \ /
 /\    ==>     E
B  D          / \
             B'  C'

```

##### An example of $\tau$

Suppose in our diagram above, `A` goes to `D` and `B` goes to `C`. The following pseudo-code should work as the transformed version:

```
# A being replaced by
A': A; set is_from_A = true; goto E

# B being replaced by
B': B; set is_from_A = false; goto E

# E being
E: if is_from_A, goto D, else goto C

```

##### The sketch of proof

Theorem: for any program, there is a program whose CFG is planar that does the same stuff.

Proof.

* It is always possible to define a **nice** embedding for a CFG.
* The only possibility that the 2D projection of a **nice** embedding is not planar is that there are pairs of edges intersecting each other.
* We can create a program by exactly transforming the intersections with $\tau$. The resulting CFG is planar **and** does the same stuff as the original one.

QED.

A caveat is that this does not rule out the possibility that the resulting transformed planar CFG can be much more complex than the original version (having much more nodes and edges for example).
> 3 votes

# Answer
First: If we use your definition of a CFG, they still can be non-planar. Consider the following (silly) piece of code:

```
void D(){}
void E(){}
void F(){}

void A(x){
    if(x == 0) D();
    else if(x == 1) E();
    else F();
}
void B(x){
    if(x == 0) D();
    else if(x == 1) E();
    else F();
}
void C(x){
    if(x == 0) D();
    else if(x == 1) E();
    else F();
}

int main(){
    int x = input();
    if(x == 0) A();
    else if(x == 1) B();
    else C();
}

```

You will find that the CFG looks something like this:

Now notice that if you collapse the A0,A1 edge and the B0, B1 edge etc. you get $K\_{3,3}$ as a subgraph. And thus according to Wagner's Theorem the graph is not planar.

The article you reference uses essentially the same trick. But instead of if-statements they use virtual methods to make a three-way decision between types.
> 2 votes

---
Tags: graphs, planar-graphs
---


# Question
Title: Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?
So I'm doing an AI course that is talking about time complexities of different tree search algorithms. On this slide it talks about the time complexity of the algorithm, and I'm confused as to why we ignore the $d$ multipliers in the series for the Big-O time complexity of the algorithm

My initial thought is that the time complexity would be $db^d$ since the magnitude of d will affect the time complexity, but I clearly wasn't paying enough attention in first year when they went over Big-O notation. Any help would be greatly appreciated, thanks!

# Answer
If $b, d$ goes to infinity, as all other sum factors are asymptotically less than $b^d$ (except the last one!), the mentioned time complexity function will be in $\Theta(b^d)$. Hence, this algorithm is also in $O(db^d)$, but a tighter bound is $O(b^d)$.
> 0 votes

# Answer
Let x = $b^d$. The last term is x. The second to last is x * (2 / b). The third to last is $x * (3 / b^2)$, then $x * (4 / b^3)$ etc.

Let y = $x * (1 + 1 / b + 1 / b^2 + 1 / b^3 ...)$. That's a simple geometric series, easily to calculate. Now the sum is actually $y + y/b + y/b^2 + y/b^3 ...). Another simple geometric series, which gives you the exact result.
> 0 votes

# Answer
**Hint:**

$$s(d):=b^0+b^1+b^2+\cdots b^d=\frac{b^{d+1}-1}{b-1}$$

and by summation until $d+1$ and differentiation,

$$t(d):=0b^0+1b^1+2b^2+\cdots db^d=\frac{\partial}{\partial b}s(d+1)=\frac{d b^{d+1} - (1 + d) b^d +1}{(b-1)^2}.$$

The target expression is $(d+1)s(d)-t(d)$.
> 0 votes

# Answer
**Intuitively :** Number of nodes in last level is more than sum of all nodes in Previous level.

* At Level-$\color\red0$, we have $1$ node. It can be written as $b^\color\red0$
* At Level-$\color\red1$, we have $b$ nodes. Can be written as $b^\color\red1$
* At Level-$\color\red2$, there will be $b^\color\red2$ nodes.
*
*
* At Level-$\color\red{d-1}$, there will be $b^{\color\red{d-1}}$ nodes.
* At Level-$\color\red d$, we have $b^\color\red d$ nodes.

Now, sum of all nodes in previous level $$b^0+b^1+b^2+\ldots \ldots b^{d-1}$$It is a Geometric Progression with common ratio $b$ and first term $1$. Thus, using the summation formula, this sum will be

> $$\frac{b^d-1}{b-1}$$

This sum is less than $b^d$. Thus, number of nodes in last term **dominates**. Hence, $$\mathcal O (b^d)$$

---

**Mathematically :** Assume we go till depth $d$ (0-indexed).

* Then, we have to touch/process `Level-0` nodes $d+1$ times.
There is $1$ node at this level.
* We are processing `Level-1` nodes $d$ times.
There will be $b$ nodes at `Level-1` \[Very definition of $b$, the branching factor\]
* Then, we will process `Level-2` nodes $d-1$ times.
There will be $b^2$ nodes.

.
.
.

* At last, we will process `Level-d` nodes $1$ times.
There will be $b^d$ nodes in `Level-d`.

Thus, we have $$(d+1)b^0 + (d)b^1 + (d-1)b^2 + \ldots \ldots + (1)b^d$$

Now, this is **Arithmetico–geometric Progression (AGP)**.

> If AGP is of the form $$\alpha\beta+(\alpha+\delta)\beta\gamma+(\alpha+2\delta)\beta\gamma^2+\ldots\[\alpha+(n-1)\delta\]\beta\gamma^{n-1}$$then it's sum is given by $$\frac{\alpha\beta-(\alpha+n\delta)\beta\gamma^n}{1-\gamma}+\frac{\delta\beta\gamma(1-\gamma^n)}{(1-\gamma)^2}$$

Comparing standard formula with our series, we can have
$\alpha$ as

> $(d+1)$

$\beta$ as

> $1$

$\delta$ as

> $-1$

$\gamma$ as

> $b$

$n$ as

> $(d+1)$

Putting into the formula, and simplifying a bit, we will get $$\frac{(1-b)(d+1)+b(b^{d+1}-1)}{(1-b)^2}$$ which can be further simplified as $$\frac{2-2b-bd+b^{d+2}}{(1-b)^2}$$ *\[If any mistake in calculation, please comment\]*

Clearly $b^{d+2}$ is dominating.

Thus, it is $$\mathcal O (b^d)$$

---
> 0 votes

---
Tags: complexity-theory, time-complexity, search-trees, big-o-notation
---


# Question
Title: Why Lavarand (as opposed to other methods of generating random seeds)?
Cloudflare famously uses a wall of lava lamps (https://en.wikipedia.org/wiki/Lavarand) to seed random number generators. But if you're going into the real world to seed your rng, why lava lamps? Why not roll 1000 D20's (say dice with 20 different colored faces) and call it a day? Is it just to look cool, or does the distribution of states that lava lamps take have a unique (or rare) property?

# Answer
Cynical answer: Because lava lamps are pretty and the wall of lava lamps makes good marketing and it sounds impressive and conveys the impression that they are serious about security.

In practice, if all you care about is engineering, it suffices to seed a cryptographic strength pseudorandom number generator with a random seed. Most computers already contain perfectly reasonable ways to seed them, and most processors have built-in hardware support for generating random numbers that can be used to seed them. For instance, Intel has RDRAND, which reads from a hardware random number generator built into the processor. If you are using a processor that does not have this kind of support and you are paranoid, you can buy a hardware random number generator device.

Rolling dice requires human assistance, so is less preferable than the other alternatives.

You can read a lot more on Security.SE and Crypto.SE.

I think you'll find https://security.stackexchange.com/q/204870/971 and https://security.stackexchange.com/q/191296/971 highly relevant. See also https://security.stackexchange.com/q/42428/971, https://security.stackexchange.com/questions/tagged/random, https://crypto.stackexchange.com/questions/tagged/randomness, https://crypto.stackexchange.com/questions/tagged/entropy, https://security.stackexchange.com/questions/tagged/entropy.
> 1 votes

---
Tags: randomness, random-number-generator
---


# Question
Title: What is the difference between a Task-Specfic Programming (TSP) language and a Domain-Specific Language (DSL)?
As a software engineer, I am familiar with "domain-specific languages" (DSLs), such as PCRE and SQL, which aim to eschew complexity by only providing functionality specific to a given domain (e.g. string matching and database querying for PCRE and SQL, respectively).

However, in some CSE literature I've seen the term "task-specific programming languages" (TSP or "teaspoon" languages), e.g. Teaspoon Languages for Integrating Programming into Social Studies, Language Arts, and Mathematics Secondary Courses.

Are TSP languages different from DSLs? If so, how do they differ?

# Answer
> 1 votes
As the author of the article you linked writes in a different article \[**bold** emphasis mine\]:

> A task-specific programming language (TSPL) **is a domain-specific programming language** (in programming languages terms) **designed for a particular user task** (in human-computer interaction terms). Users of task-specific programming are **able to use the tool to complete useful tasks, without prior training**, in a short enough period that one can imagine fitting it into a normal class (e.g., around 10 minutes).

So, in other words, TSPLs *are* DSLs, more precisely, they are a special case of DSLs.

TSPLs are essentially at the intersection of DSLs and what is called *End-User Programming*, which means programming by people who are not programmers and do not even realize that what they are doing *is* programming.

The way I understand it, the difference between a TSPL and a DSL is that a DSL is designed to be specific to *one domain*, whereas a TSPL is designed to be specific to *one single task within one single domain*. A DSL is intended to be used during software development; even if it is not written by a software developer, it would still usually be written by a domain expert as part of a software development team or software development project. Said domain expert would also typically have access to software developers to help them out, or have received some limited software development training.

Whereas TSPLs are intended to be used by end users to solve some specific task that really has nothing to do with software development.

The paper you linked to puts these TSPLs into an even broader context: computer literacy. How can you teach computer literacy to people who would never sign up for a computer course and in an environment where you don't have time to explicitly teach computer literacy? The idea is to use TSPLs in contexts which have nothing to do with computers, but use them, in class, to solve a problem related to that class, thereby exposing students to computers and comput**ing** without them even realizing it.

There have been experiments which suggest that integrating computers *well* into, for example, teaching physics, can not only improve students' understand of physics, but also as a side-effect teach them computer science. An early example is Gerald Jay Sussman's (co-author of *Structure and Interpretation of Computer Programs* and originally a physicist) book *Structure and Interpretation of Classical Mechanics*, which teaches the entirety of classical physics without maths, instead using Scheme to explain the processes.

Alan Kay has also made some experiments having students drop objects from the roof of their schools, filming those objects, and using TSPLs for measuring distances travelled between video frames, and measure and graph the object's velocity and acceleration, thus enabling students to discover the laws of Newtonian Gravity all on their own. This is only possible with a TSPL that can be learned in a few minutes by a school kid. You couldn't do this with something like Python, OpenCV, and matplotlib.

Computer literacy / computer education is not the only use case for TSPLs, though, it is just what the paper you linked to focuses on. The big idea behind End-User Computing and TSPLs is to enable end-users (not programmers, not expert computer users) to solve specific tasks anywhere, anytime, using programming without having to learn programming, without having to think about programming, without even realizing that what they are doing *is* programming. The idea behind the paper you linked is to make use of TSPLs to "sneak" computer literacy education into totally unrelated courses and classes without taking away any precious teaching time (and in fact, actually *enhancing* the teaching).

---
Tags: education, domain-specific-languages
---


# Question
Title: Simulating nondeterministic RAM with nondeterminstic turing machine
Nondeterminstic RAM is like deterministic RAM with extra instruction “JMAYBE” which nondeterministically jump or continue when executed.

According to this paper: An $O(T \log T)$ reduction from RAM computations to satisfiability I guess that we can simulate nondeterministic RAM on nondeterministic TM , with only logarithmic overhead. But this paper also has an important refrence which i could not find “*J. Wiedermann, Deterministic and nondeterministic simmulation of RAM by the Turing machine, (IFIP 1983 Paris)*”. My question is , how i can show that:

> If a language $A$ is recognized by a nondeterministic RAM $P$ within time $T(n)$ and if $P$ has $l(n)$ logarithmic, then $A$ is recognized by some nondeterministic multitape Turing machine within time $ \log T(n) . T(n)$

The function $l(n)$ is associated with the machine, it denotes the time required to store the number $n$. here we assume $l(n) = \lceil \log |n| \rceil$.

This is my homework and i struggle with this question about one week (at first i learned about RAM model) , but i could not figure out how this simmulation is possible, and also i did not find any thing useful. All i know is , there is a naive simmulation which its overhead is quadratic.

# Answer
Here is your hint. Imagine that we augment $P$ to record a log of all the random-access reads and writes $P$ does to memory (i.e., for each read, record the address and the value that was read; for each write, record the address and the value that was written), in the order they were done. At the end of the computation, could you efficiently verify whether that log is self-consistent and correct? What would be the running time of an algorithm designed to verify the log?

It's your homework problem, so I won't share the complete solution until after the deadline, but if you ponder this thoughtfully, and then think about how you might apply it, it should help you with your homework problem.
> 1 votes

---
Tags: complexity-theory, time-complexity, computation-models
---


# Question
Title: Difference between inverted page table and a standard one?
I know that for standard page tables each process would have its own page table and for inverted the OS would have it.

But other than this what are the main differences between a standard page table and an inverted one?

# Answer
The purpose of this inverted page table is to reduce the amount of physical memory needed to track virtual-to-physical address translations. We accomplish this savings by creating a table that has one entry per page of physical memory, indexed by the pair \<process-id, page-number\>. Because they keep information about which virtual memory page is stored in each physical frame, inverted page tables reduce the amount of physical memory needed to store this information.

Each inverted page-table entry is a pair \<process-id, page-number\> where the process-id assumes the role of the address-space identifier. When a memory reference occurs, part of the virtual address, consisting of \<process-id, page-number\>, is presented to the memory subsystem. The inverted page table is then searched for a match. If a match is found—say, at entry i— then the physical address \<i, offset\> is generated. If no match is found, then an illegal address access has been attempted.

Although this scheme **decreases** the **amount of memory** needed to store each page table, it **increases** the amount of **time** needed to search the table when a page reference occurs. (because we might search the whole table to find a match).

Also with inverted page tables, only one mapping of a virtual address to the shared physical address may occur a any given time. A reference by another process sharing the memory will result in a page fault and will replace the mapping with a different virtual address.

---

More information : Operating System Concepts, 10th Edition | Abraham Silberschatz, Greg Gagne, Peter B. Galvin
> 1 votes

---
Tags: operating-systems, memory-management, paging
---


# Question
Title: in 2DPDA and 3DPDA:2 and 3 is the number of tapes or of stacks?
I'm struggling with the definitions of the push-down automata. In 2-DPDA and 3-DPDA, what do the numbers 2 and 3 stand for: for the number of stacks or of read-only tapes (and hence RO heads) ?

Finally, is there a language accepted by k-DPDA but not with (k-1)-DPDA for any k ?

It seems that the last question is unsolved (a conjecture by Ibarra-Harrison) as of 1968:

# Answer
$K{-}DPDA$ is equivalent to $2{-}DPDA$ for any $K \geq3. $That means for example $2{-}DPDA$ is capable of do the same work as $3{-}DPDA$ do, $2{-}DPDA$ is capable of do the same work as $4{-}DPDA$ do etc$.......... ... ... .. .. ..... .. .$

And $K{-}DPDA$ is equivalent to Turing Machine for any $K \geq2$$.$ $\\{a^nb^nc^n\\}$ is recognized by $2{-}DPDA$ but not by $1{-}DPDA$ or by $DPDA$ with $1{-}stack.$

---

**Theorem1:-** $\\{a^nb^nc^n\\}$ is recognized by $2{-}DPDA$.

**Proof:-** Suppose I have an two stacks $S\_1$ with stack bottom $Z\_0$ and $S\_2$ with stack bottom $Z\_1.$ Suppose consider the string $aabbcc$ is for $\\{a^nb^nc^n\\}.$

**Step1.** When $a$ will come push onto the stack $S\_1$.

**Step2.** When $b$ will come two things happen.

* push $b$ onto the stack $S\_2.$
* pop **one** $a$ from $S\_1$ against **one** $b$.

**Step3.** When $c$ will come, pop **one** $b$ from $S\_2$ against **one** $c.$

**Step4.** If you see finally two stacks $S\_1$ with stack bottom $Z\_0$ and $S\_2$ with stack bottom $Z\_1$ then strings are accepted otherwise rejected.

---

**Theorem2:-** $\\{a^nb^nc^nd^n\\}$ is recognized by $2{-}DPDA$.

**Proof:-** Suppose I have an two stacks $S\_1$ with stack bottom $Z\_0$ and $S\_2$ with stack bottom $Z\_1.$ Suppose consider the string $aabbccdd$ is for $\\{a^nb^nc^nd^n\\}.$

**Step1.** When $a$ will come push onto the stack $S\_1$.

**Step2.** When $b$ will come two things happen.

* push $b$ onto the stack $S\_2.$
* pop $a$ from $S\_1$.

**Step3.** When $c$ will come two things happen.

* push $c$ onto the stack $S\_1.$
* pop **one** $b$ from $S\_2$ against **one** $c$.

**Step4.** When $d$ will come, pop **one** $c$ from $S\_1$ against **one** $d.$

**Step5.** If you see finally two stacks $S\_1$ with stack bottom $Z\_0$ and $S\_2$ with stack bottom $Z\_1$ then strings are accepted otherwise rejected.

---

<sup>

**So we proved that $K{-}DPDA$ is equivalent to $2{-}DPDA$ for any $K \geq3.$**

**Note1:-** You can easily check $\\{a^nb^nc^nd^n\\}$ by $3{-}stack$ that is your homework.

N. B.- $K{-}DPDA$ means $K{-}stack$ or $K{-}counter$ with $DPDA.$

</sup>
> 0 votes

# Answer
Your image comes from M.Li and P.M.B. Vitányi: Kolmogorov Complexity and its Applications, Chapter 4 in Handbook of Theoretical Computer Science, vol. A, J. van Leeuwen Editor.

Both conjectures mentioned are of the form "(k+1)-head X automata are better than k-head X automata", so we can assume that k refers here to the numbers of heads on the (one-way) input tape of an X automaton. In the case of PDA that means there is only one pushdown stack available, but there are several heads that can read various portions of the input tape.

Note that even a finite state automaton can accept the non-context-free language $\\{a^n b^n c^n \mid n\ge 1 \\}$ if it has three heads that can move along the input tape. Each head moves to one of the letter segments, and synchronously they verify that the number of letters match.

The Harrison-Ibarra paper, Multi-Tape and Multi-Head Pushdown Automata. Inf. Control. 13(5): 433-470 (1968), is Open Archive, and can be accessed via the DOI: 10.1016/S0019-9958(68)90901-7

Here is the conjecture (page 462), with H for \`heads', which explicitly proposed languages in the difference between two successive levels of an head-hierarchy:

> Let $|\Sigma|\ge2$, and $c$ a symbol not in $\Sigma$. For each $n\ge \> 2$, define the following sets: $L\_2 = \\{ xcx \mid x \Sigma\*\\}$ $L\_{n+1} = \\{xcycx \mid y \in L\_n , x \in \Sigma^\*\\}$ (For example, $L\_3 = \\{ xcycycx \mid x, y \in \Sigma^\*\\}$ ). Then for each $n\ge 2$, $L\_n$ is $n$-HDPDA definable but not $(n - 1)$-HPDA definable.

The conjecture is proven by Marek Chrobak, Ming Li: k+1 Heads Are Better than k for PDAs. J. Comput. Syst. Sci. 37(2): 144-155 (1988) DOI:10.1016/0022-0000(88)90004-9

Here a quote from that paper (which matches your image):

> The following language was basically defined by Rosenberg \[R\] in order to show that $k + 1$ heads are better than $k$ heads for finite automata
> $L\_b = \\{ w\_1 \\#\dots \\# w\_b \\\\$ w\_b \\# \dots \\#w\_1 \mid w\_i\in \\{0,1\\}^\* \\}$
> \[...\] Amazingly, this language can also be used to serve our purpose although the proof technique is new.

The proof technique uses Kolmogorov complexity.
> 0 votes

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


title: safe edge theorem proof clarification

text:
# Question
Title: safe edge theorem proof clarification
I found the following proof for the theorem that states "A light edge that crosses a cut that respects A is safe for A":

See: https://www2.hawaii.edu/~janst/311\_f19/Notes/Topic-17.html where also all the necessary definitions are given.

What I do not understand in this proof is that we have here T that is a MST and then we say that T' is also a MST that contains the edge u-v and not x-y. But if the weight of u-v is less than that of x-y ("w(T) - w(x,y) + w(u,v) ≤ w(T)"), then T could have never been a MST (because it would have never chosen x-y over u-v)? Does someone see what goes wrong in my explanation?

# Answer
Although correct, that statement, "$w(T') = w(T) - w(x,y) + w(u,v) \le w(T)$" alone is indeed confusing, since it leaves the impression that $w(T')$ might be smaller than $w(T)$.

Well, the equal part of "$\le$" comes to rescue. It is possible that $w(T')=w(T)$.

Indeed, that must be the case, since we also have $w(T)\le w(T')$ by the definition of MST and $T$ being an MST.

There is nothing wrong to say "$w(T')\le w(T)$", just as we say "$3\le 3$".

---

Furthermore, we know that $w(x,y)=w(u,v)$. This is the fact that the edge in any MST that crosses a cut must be an edge of minimum weight that crosses that cut. (All minimum edges crossing the same cut have the same weight, of course.)
> 1 votes

---
Tags: algorithms, graphs, minimum-spanning-tree, spanning-trees
---


# Question
Title: Runtime complexity of permutation function
I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums.

```
    def permute(nums):
        res = []
        dfs(nums, [], res)
        return res

    def dfs(nums, curr, res):
        if not nums:
            res.append(curr)
            return
        for i in range(len(nums)):
            dfs(nums[:i]+nums[i+1:], curr+[nums[i]], res)

```

I think that the run time on an input of size $n$ is $T(n)=nT(n-1)+n$ because the function will make $n$ recursive calls on an input of size $n-1$ and it loops over $n$ terms. This gives $T(n)\in \mathcal O(n!)$ but some people say that it is $\mathcal O(n\cdot n!)$. Is the runtime of this $\mathcal O(n!)$ or $\mathcal O(n\cdot n!)$?

# Answer
> -1 votes
Consider this piece of code:

```
        for i in range(len(nums)):
            dfs(nums[:i]+nums[i+1:], curr+[nums[i]], res)

```

Note that `curr+[nums[i]]` creates a new list, and on the bottom level, each of the $n!$ new lists will have size $n$. Hence $\mathcal{O} (n! \cdot n)$ total complexity.

On the other side, note that the complexity `nums[:i]+nums[i+1:]` is also linear in terms of $n$, but it does not present a problem, since its length at the bottom levels is $\mathcal{O} (1)$.

---

To look at it another way, the output has a size of $n! \cdot n$, so, barring any clever tricks in storing the output, the whole algorithm can't take less than that to produce the whole output.

---

In terms of recurrence relation, it gets a bit tricky, as the deeper we go, the larger the second argument (`curr`) gets. So, perhaps we can write $T (n, \ell) = n \cdot T (n - 1, \ell + 1) + n \cdot (n + \ell)$, where $n$ is the length of `nums`, and $\ell$ is the length of `curr`. We are interested in $T (n, 0)$, and the base is $T (0, \ell) = \ell$.

---
Tags: time-complexity, runtime-analysis, recursion, backtracking, depth-first-search
---


# Question
Title: Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's
Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's.

So far, I have $(aa)^\*a((b+\varepsilon)(aa)^\*)^4$, but I don't think this covers all cases. For example, $abaabaaab$ should fit the criteria, but it wouldn't be in the language described by the above regular expression. Any help is appreciated!

# Answer
> 1 votes
Here is how to construct a regular expression for the set of strings over $\\{a,b\\}$ which contain an even number of $a$'s and at most one $b$.

Strings that contain no $b$ are of the form $a^n$, where $n$ is even. Such strings can be described using the regular expression $(aa)^\*$.

Strings that contain a single $b$ are of the form $a^n b a^m$, where $n+m$ is even. Thus either $n,m$ have the same parity. The case where both are even is described using $(aa)^\*b(aa)^\*$, and the case where both are odd is described using $a(aa)^\*ba(aa)^\*$.

In total, we obtain the regular expression $$ (aa)^\*(\epsilon + b(aa)^\*) + a(aa)^\*ba(aa)^\*. $$

# Answer
> -1 votes
It says the constraints are

1. Odd number of A's and
2. At most 4 B's let's start the expression

-\>string may start with both A & B

======\>(A+B)

-\>say the first letter of the string be A

======\>we need kernels should contain even A's to make it odd

```
   ========>of kind(_a_a_)
            ======>(AA)*;(BAA)*;(ABA)*;(AAB)*

```

-\>say if the expression has started with B

======\>we need to include odd number of A's into the second term

```
 ======>A*B*(say for singular B's)

```

-\> and to make whole recursion we will be taking whole (\*).

======\>((A*B*)+(AA)*+(BAA)*+(ABA)*+(AAB)*)\*

So, the final expression that would be accepting any string that would have odd number of A's and at most 4 B's is : (A+B).(A+B+AA+BAA+ABA+AAB)\*

(not simplified for understanding...)

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


# Question
Title: Is Turing machine a scientific theory in CS?
The English Wikipedia article about Turing machine opens with:

> A Turing machine is a mathematical model of computation that defines an abstract machine,\[1\]

As a Hebrew speaker, I read a similar explanation in Hebrew Wikipedia:

> מכונת טיורינג היא מודל חישובי מתמטי אשר באמצעותו ניתן לתאר באופן מופשט את פעולתו של מחשב (כולל מחשב מודרני).

## My problem

I understand this term as reflecting a scientific theory in CS or Math, but interestingly, none of the two opening sentences presented this concept as a *scientific theory* in either CS or Math.

By *scientific theory* I meant:

> An idea or set of ideas that can be falsified by principle (falsifiability as a condition for it to be real) and that one or more reinforcements can make it somewhat more plausible in reality.

But;

If it's a theory in Math, maybe my approach is wrong, because, as far as I understand, in Math the paradigm is different so something is either true or false (i.e, not true).

## My question

Is Turing machine a scientific theory in CS?

---

## Update

In comment section, Yuval Filmus said (minor paraphrase):

> Turing machines are a mathematical abstraction.
> They're neither a scientific theory nor a practical engineering idea;
> Actual computers are much better modeled using a different abstraction → **RAM machines**;
> The relevant scientific theory is the *Church-Turing thesis*.

This made me wonder "what is the difference between a *mathematical model* and a *mathematical abstraction* and does the former or the latter or both, can be based in a "scientific theory"?

This isn't the main question, but you are welcome to explain this in an answer as I think it's relevant.

# Answer
> 5 votes
No, as Yuval Filmus explained, a Turing machine is not a scientific theory.

Furthermore, something can be both a mathematical model and a mathematical abstraction; for example, if the model *is* an abstraction.

## Types of scientific theories

In the physical sciences, a scientific theory is a set of rules or models that makes testable predictions that could potentially be falsified. A Turing machine just isn't any of those.

In mathematics, the word "theory" may be used to describe a framework for reasoning where we have axioms, definitions, and inference rules for making deductions that follow from those axioms and definitions. A Turing machine isn't that, either.

## Personal opinion

I don't think it's a good use of time to devote a lot of energy to these kinds of questions. Instead, I would suggest that you learn the basic material in textbooks on Turing machines and computability and decidability, and don't worry too much about how to categorize or classify it or what words can be applied to it. From a computer science perspective, it's more useful to focus on the mathematics without trying to put it into a philosophical framework or trying to come up with definitions of these broad, vague concepts (abstraction, theory, model).

# Answer
> 2 votes
More precisely, a "theory" in mathematics (and by extension in other deductive branches of science) is a collection of axioms, definitions and propositions proved from the above, typically acompanied by a set of tools and techniques. So, newtonian mechanics, general relativity, group theory, thermodynamics, number theory, and a host of others are "theories". In experimental sciences (like physics), a "theory" is an explanation for a collection of somehow related phenomena, typically in the form of a deductive theory as above. That can be falsified (shown wrong, or be just an approximation).

Turing machines are one specific model of the idea of what "computation" is all about. There are theories around that concept (computability and complexity theories, the last one a central area of active research in theoretical CS and pivotal in practical algorithm development).

# Answer
> 0 votes
Firstly, I recommend you, not to visualize science and math as separate theories. Basically, to induce any kind of new scientific approach, there must be some mathematical model working underneath it.. as to mention math would be providing a background framework

Similarly, in the case of Turing machine or the concept of Automata theory they will be providing a background framework to visualize a computer's regular scenarios i.e., Turing machine is a mathematical model to describe a computer in theoretical sense or on paper scenarios. also Automata theory provides many kinds of mathematical models to assure on paper formations of all computational routines. as it just like we will be using the concept of integral calculus to analyze the irregular or non-newtonian objects or surfaces in physics.

Finally, yes, Turing machine is a kind'a mathematical model but being used as a part of computer science.Over the paradigms if you integrate the math with physical phenomena and logic it will become the physics.

# Answer
> 0 votes
**Short answer:** the Turing Machine is a fundamental concept in the Theory of Computability. Like the prime decomposition is a fundamental concept in the Theory of Numbers.

---
Tags: terminology
---


# Question
Title: Correctness of bft resulting in shortest path
I found the following proof concerning the correctness of a breadth-first traversal resulting in shortest path:

source: https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture6.pdf

The key is that if we assume that we have a shorter path, we get a contradicition. I however do not fully understand with what the consequence of having a shorter path contradicts. Could someone explain it to me?

# Answer
The contradiction is that we're assuming **the first time we've seen $w$** is through the node we're expanding, $v$. However, if there were a shorter path, then the second-to-last node in that path must be some other node, $v'$. Since the path is shorter, $dist\[v'\] \< dist\[v\]$. But if that's the case then $v'$ should've been expanded prior to $v$, and **we would've seen $w$** when that happened, contradicting our assumption.
> 1 votes

---
Tags: algorithms, shortest-path, correctness-proof, breadth-first-search, tree-traversal
---


# Question
Title: Prove there is an algorithm that needs at most n-1 comparisons to check if n-element array has all equal elements?
Question:

Prove that there exists an algorithm that can decide using at most n-1 comparisons whether a n-element array contains only equal numbers.

We use an algorithm that loops through all the elements in the array, comparing Ai with Ai+1 to check if both are equal, where 0 \<= i \< n. If there exists some i, such that Ai+1 != Ai, the algorithm returns false. Otherwise, for all i, Ai = Ai+1, hence the algorithm outputs true.

Construct a graph G on n nodes where nodes i and j are adjacent iff the algorithm compares Ai and Aj. Since the algorithm makes n-1 comparisons, there are n-1 edges with n nodes in G, ehnce the graph is connected. With a connected graph, the algorithm will always return the correct ouput as for any i, j indices of the array, Ai and Aj will be directly (or indirectly) compared with each other. Making more than n-1 comparisons simply adds more edges to G, and does not change the fact that the graph is already connected with only n-1 edges, hence the output of the algorithm will not change.

Therefore, there is an algorithm described above that needs at most n-1 comparisons to check if n-element array contains all equal elements.

This is my attempt at a proof, but I am sure that the part on the graph being already connected is wrong. Can someone help me correct my proof?

# Answer
How about considering proof by induction.

1. Given an array with 2 elements we make one comparison of those two elements, they are either the same or they aren't.
2. We assume that there exists an algorithm that that needs at most n-1 comparisons to check if n element array has all equal elements. So let's consider what happens with an n+1 element array. We can establish that the first n elements are identical (or not) by using at most n-1 comparisons and if they are identical we need one further comparison to check the n+1th element against any of the other n elements, thus we need at most n - 1 + 1 = n comparisons.
> 2 votes

# Answer
Let a sequence of $n$ elements. If all pairs of consecutive elements are equal, then by transitivity all elements are equal. By contradiction, if they are not all equal, then there is certainly a pair of consecutive elements that differ.

Hence

$$\bigwedge\_{i=0}^{n-1} (A\_i=A\_{i+1})$$ settles the query, in $n-1$ comparisons. This proves the *existence* claim.

On another hand, a binary relation (such as equality) can only reduce by one the number of equivalence classes. This proves *optimality* of $n-1$.
> 1 votes

---
Tags: algorithms, graphs, proof-techniques, correctness-proof
---


# Question
Title: Are deterministic Turing machines as powerful as probabilistic Turing machines?
I am wondering if it is known whether probabilistic Turing machines are more powerful than deterministic ones, in the sense that they can solve problems faster on average, or can solve problems that deterministic Turing machines cannot? That is, if a Turing machine can "flip coins", does this allow it to do things it could not have done before?

I ask because in fields like cryptography, you always assume the adversary is a probabilistic Turing machine (that is they can draw from a random source), so I am guessing that this assumption means it is known that probabilistic Turing machines are stronger? Or is this just conjecture, but we use probabilistic Turing machines anyway because deterministic Turing machines are just a special case?

# Answer
This is a famous open problem in computer science theory. In particular, it comes down to whether BPP = P. It is widely conjectured and suspected that BPP = P, or in other words that randomness does not significantly increase the power of computer algorithms. However, we have no proof of this conjecture. So, it remains possible that randomness allows some problems to be solved more efficiently (our best guess is, this is probably not the case, but we cannot completely rule it out).

In cryptography, there are several reasons we tend to use probabilistic algorithms rather than deterministic algorithms (e.g., probabilistic Turing machines rather than deterministic Turing machines):

1. Much of cryptography needs randomness to do anything. For instance, many techniques need to generate a random key, or generate a random value (nonce, IV, seed, salt, key, etc.). So, we need a probabilistic algorithm, so it has the ability to generate a random value, just to implement the cryptographic algorithm in the first place.
2. Empirically, in practice, it is easy to generate random numbers on real computers. So we might as well pick a theoretical formulation that matches the capabilities that real computers have.
3. In cryptography, we want to give the adversary every reasonable advantage. If we can prove security against all probabilistic polynomial-time algorithms, that is a more meaningful result than proving security against all deterministic polynomial-time algorithms (the former implies security against both, whereas the latter does not necessarily guarantee security against probabilistic algorithms). So, our definitions typically allow the adversary/attacker to use a probabilistic algorithm or probabilistic Turing machine, because this gives us a stronger, more meaningful notion of security.
> 2 votes

---
Tags: turing-machines
---


# Question
Title: What kind of data does L1, L2, L3 cache hold?
I understand that caches are the smallest and fastest memory that is integrated into the CPU. However, what I am confused about is the information that it holds. From what I know, the capabilities of cache are:

L1 cache - 64KB L2 cache - 256KB L3 cache - 4-12 MB Ram - 4-74 GB

For example: If I open up a page on the browser, what sort of data goes into the L1, L2, and L3 cache and maybe the RAM too. Does the L1 cache try to fill in as much reusable data as possible and if it's full then the remaining goes to the L2 cache and so on? Is the data that it holds like images or words ?

I can't seem to understand so any help would be much appreciated.

# Answer
> 2 votes
L1 cache: Every time you access any data, either it is in L1 cache already, or one cache line worth of data (often 32 or 64 byte) is read from the next level, and stored into L1 cache. If necessary, the data that was stored in that cache line is removed, and if it was modified, it is first written to the next level of data.

Same with L2 cache; if data is not in L1 cache, then either it is already in the L2 cache, or it is read from the next level in exactly the same way. Same with L3 cache. On processors where CPUs and GPUs access the same memory, there is often another cache level between CPU / GPU and memory. So what exactly is in the various caches changes all the time.

Sometimes the programmer knows that putting data into cache is not worth it. For example, if I need to process one GB of data sequentially, which is much more than any cache, it is pointless to store the data into any higher level caches, because it will never be reused. For this reason, some processors have instructions to read data but not putting it into L2 or L3 cache.

And some processors have "streaming" instructions: If you know that you are accessing sequential data, once you read data at location x, the processor guesses that you will read data at the following cache line after this, so it starts reading data from memory and putting it into the cache before it is used. Sometimes it isn't used at all.

# Answer
> 0 votes
The answer is that almost all the data that the CPU works on ends up in various levels of the cache. It's not like text goes into L4, and images go into L3, audio into L2 and video into L1.

The memory controller in the CPU will manage the data in the cache, moving it between levels according to various rules of thumb that the CPU designers have decided seem to work well.

---
Tags: computer-architecture
---


# Question
Title: What does interface and peripheral functions mean?
I know that interface means a point where any two things meet and interact, but I can't seem to wrap my head around the term when they use it in computers.

A chipset performs interface and peripheral functions for the processor. What does it mean?

What do you mean when you say the chipsets are the circuitry that provides **interfaces** for memory, expansion cards, and onboard peripherals?

The same goes for peripheral functions. I know peripheral devices are external devices used to connect to the CPU, but what is the function? Is it that the chips are responsible to transfer data from the peripheral devices via the bus to the processor?

# Answer
> 0 votes
I think you have the general idea right. I would add that

* Interfaces are more like APIs and cross-boundary objects that help interactions between two different worlds. So you can imagine a bus is an interface between the CPU and its peripherals, such as hard drives, GPUs, memory, etc. A chipset provides an interface between the CPU and these peripherals in a few ways. One way is that there is an instruction set for the CPU, so there is a very defined way of how devices can interact with the CPU. E.g. turn this bit on to tell the CPU something, or send a string of instructions tell the CPU something. The two worlds here are outside (general) and inside (CPU land).
* Peripherals are the external devices, and there are many of them. From a lower level perspective, you can talk about caches, like L1, L2 and how they interact with the processor, but if we consider those fast caches as part of the processor, then we can say the processor interacts with memory to store information, or the processor sends back results of instructions to the user, or the processor tells the GPU to display something to the monitor.
* At a higher level, if you consider your computer as a peripheral, then the mouse would be a peripheral that takes user hand input, a CD drive would be a peripheral that takes in disk data, and a microphone would take in voice input, and so on.

# Answer
> 0 votes
The CPU in a computer is a very general purpose device. The same CPU might be used in a gaming PC, or in a server, or in a spacecraft. So, when they design CPUs, they don't design them for a specific function; you won't find a CPU with a special electrical connection for connecting to the inertial guidance system of a spacecraft, or connections for a hard drive, or a mouse.

What the CPU has instead is a **bus**.

The bus (short for Omnibus, meaning "for all"), is a set of electrical data connections on the CPU which can be used to talk to other chips, which in turn talk to the peripherals of the computer (the mouse, the hard drive, the graphics card, etc.).

This set of other chips (the **chipset**) are the **interface** between the **CPU** and the **peripherals**. Arranging a computer this way means that different types of computers can be built for whatever function you require. A server, for example might have several chips on the bus for talking to hard drives, but no chips for handling graphics. A Home PC would have one chip for talking to a couple of hard drives, one chip for handling graphics, and another for USB, allowing things like mice to be connected.

---
Tags: computer-architecture
---


# Question
Title: Minimum absolute sum of 2 elements from 2 different lists
I am currently stuck on this problem, it is from a very highly competitive contest and so it is highly difficult as well. Below is the statement:

```
There are 2 lists of integers with the same length.
Pick an integer from each list and
calculate the absolute value of their sum.
Return the minimum value for the value.

Example: list1 = [1, 2]; list2 = [-2, 3] => result = 0

Explanation : take 2 and -2

```

Can anyone help?

Problem Source: 2008 Vietnamese National Student Competition ("Kì thi học sinh giỏi quốc gia"), question 1

I know that there is a brute force solution, but I got Time Limit Exceed (TLE), which means this MUST be done with less than $O(n^2)$ time complexity.

# Answer
**An $O(n\log n)$ solution:**

Sort the second list. For every element of the first, let $e$, find the two elements just smaller and just larger than $-e$, by dichotomic search. Then keep the smallest absolute sum. It is possible that one of the two elements does not exist.

E.g. $-7,-3,4, 6$ vs. $-2,-1,4,9$.

$\begin{align}-7&\to4\<7\<9&\to2\\\-3&\to-1\<3\<4&\to1\\4&\to.\<-4\<-2&\to2\\6&\to .\<-6\<-2&\to4\end{align}$
> 2 votes

# Answer
A solution that will often take not much more than n operations (but no guarantee):

1. In constant time find the range of both arrays, like -7 .. 6 and -2 .. 9 in the example.
2. Calculate the number of sums (16 in this case).
3. Make a guess for the smallest absolute difference say 2 in this case.
4. Create a hash table that lets you look up x div 2 (in this example) quickly, fill it with items from the second array.

Now look up the values from the first array. Say the first array had a value of -7, so you look up 2, 3 and 4 in the hash table. This would find values from 4 to 9, with an absolute value of the sum from 0 to 3. There’s a good chance to find the solution in linear time.
> -1 votes

---
Tags: algorithms, arrays
---


# Question
Title: Why there is no user interaction between uni-programming and multi-programming systems?
I was going through my Operating Systems book and in the disadvantages, they wrote that there is no user interaction between the user and computer in uni-programming and multi-programming systems and I asked why? to myself. There was no material or maybe I could not see or understand the idea that why there is no user interaction between the system and the user. I want to understand it properly.

# Answer
User interaction loosely can be thought of as responding to a user's request while the machine is performing some work. Uni-programmed systems(in the older days) as the name suggests can perform only one task at a time, as only one process could reside in main memory. To handle user inputs, you at least need to have an interrupt mechanism, and the ability to have more than one process in main memory.

Multiprogramming is a term used more often with modern operating systems, which have the ability to handle interrupts and holding more than one process in main memory. If you (hypothetically) take away the ability to handle interrupts, you are left with a batch of processes that would be executed with no user interaction.
> 0 votes

---
Tags: scheduling, cpu
---


# Question
Title: Array access is O(1) implies a fixed index size, which implies O(1) array traversal?
Arrays are generally presented as data structures with $\Theta(N)$ traversal and $\Theta(1)$ random element access. However, this seems inconsistent:

* if array access is really $\Theta(1)$, this means that the size of an element index is bounded by a constant (e.g., int64), since it can be processed in $\Theta(1)$. However, this implies that the array size is bounded by a constant (e.g., 264 elements), which makes traversal $\Theta(1)$.
* If traversal is $\Theta(N)$, then the size of the index has an information theoretic lower bound of $\Theta(\log N)$. Accessing an arbitrary $k$-th element requires processing the entire integer k, which has $\Omega(\log N)$ worst-case time-complexity (as $k$ can be arbitrary large).

In which model can both "standard complexities" defined for arrays, $\Theta(N)$ traversal and $\Theta(1)$ access simultaneously be true without the model being inconsistent?

# Answer
It's a good question. From a pragmatic perspective, we tend not to worry about it.

From a theoretical perspective, see the transdichotomous model. In particular, a standard assumption is that there is some integer $M$ that is large enough (i.e., larger than the input size; larger than the maximum size of memory needed), and then we assume that each word of memory can store $\lg M$ bits, and we assume that each memory access takes $O(1)$ time.

Notice how this solves your paradox. In particular, we'll have $N \le M$, so there is enough space in the array to store the entire array. Also, each array access really does take $O(1)$ time. The solution here is that $M$ grows with the size of the array, and is not a single fixed constant.

You can think of the transdichotomous model as assuming that we'll build a machine that is large enough to handle the data we're processing. Of course, the larger the data you have, the more bits you need to have in the address, so we need a wider bus to memory, so the cost grows -- but we just "ignore" this or assume it grows as needed.

There is a sense in which this model is cheating a little bit. While the time complexity of a memory fixed is $O(1)$ (fixed, independent of $N$ or $M$), the dollar cost of the computer does grow with $N$ or $M$: to handle a larger value of $M$, we need a larger data bus to memory, so the computer costs more. So there is a sense in which the transdichotomous model is cheating, and the cost of such a computer will go up as $\Theta(M \log M)$, not as $\Theta(M)$. In effect, the transdichotomous model is assuming we use increasing amounts of parallelism as the size of our data grows. You could argue that it is realistic, or that it is "sweeping under the rug" the cost of increasing the size of data buses, etc. I think both viewpoints have some validity.

This is analogous to how we think about Turing machines as a reasonable model for everyday computers. Of course, any one computer has a fixed amount of memory, so in principle we could say that it is a finite-state machine (with a gigantic but fixed number of possible states), so it can only accept a regular language, not all decidable languages. But that isn't a very useful viewpoint. A way out of that is to assume that when our computer runs out of storage, we go out and buy more hard drives, as many as are needed, to store the data we are working with, so its amount of memory is unlimited, and thus a Turing machine is a good model. A pragmatic answer is that Turing machines are closer to every computer than finite automata.
> 31 votes

# Answer
Big-O notation can be tricky because it hides details. Big-O describes a way to measure a function related to complexity. That function may be "number of memory accesses," which would explain the O(1) complexity. However, if you were on a machine supporting large heterogenous memory spaces, that may hide a complexity that you cared about. For example, on a NUMA supercomputer, with hypercube interconnects, we find that array access requires O(log n) *network* transactions, even though it's only O(1) memory accesses. This is because each memory access may requires some logarithmic number of steps to reach the node that has that memory.

It is up to the developer/theorist doing the work to determine whether any given metric is the "right" metric for the problem. And it can be easy to get them wrong.

In your specific case, I would assume that I have an oracle that can de reference a memory address to its value, and measure how many oracle accesses I need to do any given operation. I like using oracles like this because they're a big honkin' red flag. They encourage scrutiny. The question of "is this measuring what I want to measure" comes naturally from their use. And, in many circumstances, we find that this model is acceptable for most architectures. In particular, if you have more than 18 exabytes of memory (at which point the 64-bit addressing model falls apart), you should question this assumption. Under that number, its a *reasonable* model, especially when we recognize how much of it is handled in parallel by the hardware and electromagnetic physics.

Remember that Big-O is an asymptotic complexity number, measuring behavior as your values approach infinity. You will never actually operate on machines with infinite memory space, nor infinite processing time. In the practical world, we use it as a *surrogate* for measuring the actual complexity as actual complexity can be nefariously difficult to compute.

I recommend anyone who has gotten the basics of Big-O and wonders about the dark corners of its assumptions to look at matrix multiplication. There's a rather obvious $\Theta(n^3)$ algorithm that's pretty easy to get to, but there are faster ones. Strassen's algorithm reaches $O(n^{\log\_2 7}) \approx O(n^{2.807})$. There are even faster algorithms, in theory. However we start to find that the Big-O notation lies for our smaller finite problems. The time constants on the faster algorithms are hard to stomach, so it is rare to find anything faster than Strassen's is value-added.

But, for *many many* algorithms, Big-O does a good job of describing things. For lots of things, its very obvious that a $O(n^2)$ algorithm is notably slower than a $O(n \log n)$ algorithm for reasonably sized $n$. Often no more than a thousand is needed. We rarely push the limits of the size of our integers, except perhaps once per generation.

But, when you get to the big numbers, it is indeed worth revisiting the notation, and asking whether it is really measuring what you seek.
> 5 votes

# Answer
The cost of array access would be for example $c\_1$ if the array size is less than $2^{64}$, $c\_2$ if the array size is less than $2^{128}$, $c\_3$ if the array size is less than $2^{256}$ and so on. Since $2^{128}$ exceeds the total size of all hard drives on earth, and $2^{256}$ vastly exceeds the number of bits that can be physically stored in the universe, we are justified to ignore that array access doesn't take constant time.

We are *not* justified to ignore that accessing all elements in an array of $2^{64}$ items takes an awful lot longer than accessing all elements in an array of ten items. There is a large gap between computer science being abstract and not caring about implementation details, and having only results that are basically useless.
> 2 votes

---
Tags: complexity-theory, terminology, arrays, computation-models
---


# Question
Title: Is the root function computationally equivalent to function application?
If a function type is representable by exponentiation, does it follow that function application is represented by the right inverse, roots? It would seem that roots consume a function's input to return the output, and logarithms consume a function's output to return the input.

\begin{equation} \sqrt\[a\] {b^a} = b \end{equation} \begin{equation} \log\_{b} {b^a} = a \end{equation}

I don't know of any mathematical notation that lets one flip the notation to represent application nicely, so I'll abuse some notation briefly to layout out some identities in a way that feels computationally intuitive to me.

* Exponent: (`<-` or `->`)
* Root (right inverse): (`<-o` or `o->`)
* Logarithm (left inverse): (`o<-` or `->o`)

Given this notation, function application seems to resemble:

`(A -> B) <-o A = B` (when `f: A -> B`, and `a: A`, then `f(A): B`)

Logarithms look like the following, perhaps representing ideas like looking up the index for an array element:

`(A -> B) ->o B = B`

Is this baseless conjecture, or is there research to support this?

# Answer
This is the definition of root and logarithms.

And the usual notation for the inverse of a function $f$ is $f^{-1}$, which satisfies $f^{-1}(f(x))=x$ and $f(f^{-1}(y))=y$

$\log\_a(x)=f^{-1}(x)$ where $f(x)=a^x$

$\sqrt x=f^{-1}(x)$ where $f(x)=x^a$.

Function composition, which is denoted by $h=f\circ g$, creates a new function $h$ which computes to be $h(x)=f(g(x))$. So the inverses, can also be defines as $f\circ f^{-1}=f^{-1}\circ f=Id$ where $Id$ is the identity function which gets an input $x$ and returns it unchanged.
> 0 votes

---
Tags: type-theory, mathematical-foundations, curry-howard
---


# Question
Title: Formal language rewrite rules: strange notation
I'm reading "Program=Proof" by Samuel Mimram, and they use a notation for defining a formal language that I'm not familiar with.

Here is how **"Program=Proof"** defines a **formal language of Propositional Logic**:

>

Here is how **"Program=Proof"** defines a **formal language of λ-calculus**:

>

**On the other hand, I'm more used to formal languages defined in the following way** (this example is from Wikipedia):

>

---

Do I understand it right that this rule:

> A, B ::= X | A ⇒ B | A ∧ B | ⊤ | A ∨ B | ⊥ | ¬A

can be rewritten to a more traditional:

> S → X | S ⇒ S | S ∧ S | ⊤ | S ∨ S | ⊥ | ¬S

And this rule:

> t, u ::= x | t u | λx.t

can be rewritten to a more traditional:

> S → x | S S | λx.S

without any loss of information?

# Answer
Yes, I think that's basically the intent. I guess the book is trying to write grammars without grammatical symbols. For me, it's abuse of notation, but that's pretty common.

Because there is no formal notation for grammatical symbols, the grammar doesn't really express the fact that $A$ and $B$ are *formulas*, $X$ is a *propositional variable*, and $\\{⇒, ∧, ⊤, ∨, ⊥, ¬\\}$ are syntactic tokens. That needs to be expressed in the narrative (or left to the readers' intuitions), but that's probably a quibble since the meaning is more or less evident.

A similar quibble could be raised about the author's handling of operator associativity. But I don't think that this is a text about parsing theory; it's more about programs as formal semantic structures. It's equally possible to read the "grammars" as type declarations for expression components, also a reading which requires a certain generosity but nonetheless offers some insights.
> 2 votes

---
Tags: formal-languages, formal-grammars, logic, lambda-calculus
---


# Question
Title: How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?
I want to prove that $\mathcal M =\\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\\}$ is not a CFL.

Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$.

When I separate to cases, looking at the homogeneous case, by choosing either $w\_0$ or $w\_2$ I can't disprove the lemma, because the number of $c$ is always less/equal then the maximum and greater/equal then the minimum.

Any help?

# Answer
> 1 votes
#### Idea

The pumping lemma for context-free languages is not useful since M is "pumpable" with pumping length $p=2$. Instead, we will select a word in $\mathcal M$ that has less number of $a$'s and almost equal number of $b$'s and $c$'s, using Ogden's lemma to force its "pumpable part" to include at least one $a$.

#### Pump $s=a^pb^{3p+1}c^{3p}\in\mathcal M$

Suppose $\mathcal M$ is context-free and $p\ge1$ be the pumping constant for $\mathcal M$ in Ogden's lemma.

Mark all $p$ $a$'s in $s$. By Ogden's lemma, $s=uvwxy$, where $u,v,w,x,y$ are strings such that:

1. $\\#\_a(vx)\ge1$.
2. $uv^nwx^ny\in\mathcal M$ for all $n\ge0$.

In $s$, all $a$'s in $s$ are at the left and $v$ is to the left of $x$. So we know either $v$ is empty or $\\#\_a(v)\ge1$, thanks to condition 1.

There are two cases.

* $v$ or $x$ contains different symbols.
Then $uv^2wx^2y\notin \mathcal M$, since it contains symbols in the wrong order.
* Otherwise, neither $v$ nor $x$ contains different symbols.
In particular, $v$ is empty or contains $a$ only.
    + Suppose $x$ is nonempty and contains $c$ only.
    Consider $s'=uv^3wx^3y$.

    - $\\#\_a(s')\le \\#\_a(u^3v^3w^3x^3y^3)= 3\\#\_a(s)=3p$
        - $\\#\_b(s')=\\#\_b(s) = 3p + 1$
        - $\\#\_c(s')=\\#\_c(s) + 2\\#\_c(vx) \ge 3p + 2\gt \max(3p, 3p+1)$

    So, $s'\notin \mathcal M$
    + Otherwise, $x$ does not contain $c$.
    Consider $s''=uv^{3p+1}wx^{3p+1}y$.

    - $\\#\_a(s'')\ge\\#\_a(v^{3p+1}x^{3p+1})\ge 3p+1$
        - $\\#\_b(s'')\ge\\#\_b(s) = 3p + 1$
        - $\\#\_c(s'')=\\#\_c(s) = 3p\lt \min(3p+1, 3p+1)$

    So, $s''\notin \mathcal M$

So, in all cases, $uv^nwx^ny\not\in M$ for some $n$. This contradicts Ogden's lemma.

Hence, $\mathcal M$ is not context-free.

#### Exercises

1. Check that $\mathcal M$ satisfies the pumping lemma for context-free languages with pumping length $p=2$.

2. Show that $\mathcal J =\\{a^ib^jc^k \mid \min(i,k)\le j\le\max(i,k)\\}$ is not context-free.

# Answer
> 0 votes
**This is incorrect -- it does not take into account that $|vwx|$ can have more than $p$ characters. I will try to salvage it in the coming days.**

Ogden's lemma seems to work better here. Suppose $L$ is context-free and let $p$ be the lower limit. Choose $s = a^{p}b^{p+2}c^{p+1}$ and mark all the $a$'s (the first $p$ symbols of $s$). Then by Ogden's lemma we should be able to write $s = uvwxy$ such that:

1. $vx$ has at least one marked position: this means that $v$ contains at least one $a$.
2. $vwx$ has at most $p$ marked positions: this is trivially true because $s$ has exactly $p$ marked positions.
3. $uv^nwx^ny \in L$ for all $n \geq 0$.

Due to our choice of $s$ and markings, $vwx$ will consist of at least one $a$ and possibly some $b$'s. Hence, $uv^3wx^3y$ will have

* at least $p+2$ symbols $a$;
* at least $p+2$ symbols $b$;
* exactly $p+1$ symbols $c$ (same as $s$).

Therefore, condition (3) above fails, so $L$ cannot be context-free.

# Answer
> 0 votes
I want to give you some intuition why your language isn't CFL. We know that every CFL there exist atleast one PDA. If PDA doesn't exist that means languages definitely not CFL. So I give you intuitive proof with respect to PDA design, whether the design of PDA is possible or not:

$L\_1 = \\{ a^i b^j c^k | k ≥ min(i,j) \\}$

Here number of $c$ is greater than minimum of number of $a$ and number of $b.$ So, we can say that if number of $c$ is greater than number of $a$ or if number of $c$ is greater than number of $b$, we accept. i.e.,

$L\_1 = \\{ a^ib^jc^k | k ≥ i$ or $k ≥ j\\}$

The OR condition here means even though we need to do two checks, we can accept in either case and hence using non-determinism we just need a PDA to accept $L\_1$ (we non-deterministically check if $k \geq j$ and if $k \geq i$). So, $L\_1$ is a CFL but not DCFL.

$L\_2 = \\{ a^i b^j c^k | k \leq max(i,j) \\}$

This can be rewritten as $L\_2= \\{ a^ib^jc^k | k \leq i$ or $k \leq j \\}$

So, similarly $L\_2$ is also CFL but not DCFL.

By the above two languages $L\_1,L\_2$ you can prove that your language $\\{a^ib^jc^k ~|~k\le\max(i,j) ~and~ k\ge\min(i,j)\\}=\\{a^ib^jc^k ~|(~k\leq i ~Or~ k \leq j) ~and~ (k \geq i ~Or~ k \geq j\\}$

isn't CFL because here is needed two comparison,making it CSL.

<sup> If $L\_2 = \\{ a^i b^j c^k | k \geq max(i,j) \\}$ then alone $L\_2 = \\{ a^ib^jc^k | k ≥ i$ AND $k ≥ j\\}$ is CSL. </sup>

---
Tags: formal-languages, context-free, formal-grammars, pushdown-automata, pumping-lemma
---