# Question
Title: Converting S->aTbS|epsilon T->aTb|epsilon to chomsky normal form
The grammar have the following producitons,

\begin{align} S&\rightarrow aTbS \mid\epsilon\\ T&\rightarrow aTb\mid\epsilon \end{align}

Already turned this homework in, but I need to convert this grammar to chomsky normal form. Our teacher didn't go over this very well and all the documentation doesn't make sense to me and they almost all over the same example. Can someone please help? I only understand the first step which is making a new start state go to $S$. I have a vague understanding that I have to remove the null terminations next.

# Answer
Our grammar $G$ has following two production where $S$ is start symbol.

$S\rightarrow aTbS \vert\epsilon$

$T\rightarrow aTb|\epsilon$

Now to convert it to chomsky normal form (CNF) we have to perform following steps:

1. If there is some production having $S$ in it's right side($S\rightarrow aTbS$ in this example) then add new start symbol $S\_0$ and production rule $S\_0 \rightarrow S$ to $G$.
2. Then remove null production from $G$: So, after removing null production $G$ will have following productions:

$S\_0 \rightarrow S$

$S \rightarrow aTbS|abS|aTb|ab$

$T \rightarrow aTb|ab$
3. Now we have to remove unit production from $G$. But there are none of them.
4. Then if there is production containing both terminal and nonterminals on RHS then introduce new non-terminal for the terminal appearing there and replace occurence of terminal in that RHS by this non-terminal. example will make this clear.

we, have this $S \rightarrow aTbS$ production. So we add production $A \rightarrow a$ and $B\rightarrow b$ to G. and then rewrite production $S \rightarrow aTbS$ as $S \rightarrow ATBS$

Doing same for all production we will have production set of $G$ as follow:

$S\_0 \rightarrow S$

$S \rightarrow ATBS|ABS|ATB|AB$

$T \rightarrow ATB|AB$

$A \rightarrow a$

$B \rightarrow b$
5. Now we handle the case where RHS of production contains more than 2 non-terminals. What we do is simple. We just keep first non-terminal as it is and introduce new nonterminal for remaining part. Again example will make this clear.

We have this $S \rightarrow ATBS$ production. So we introduce new non-terminal $C$ and add production $C\rightarrow TBS$. Then modify original production as $S\rightarrow AC$.

Note here that now we have to do this process for newly introduced production also. i.e $C\rightarrow TBS$ will be converted to $C\rightarrow TD$ for instance and we have to add $D \rightarrow BS$

Now after this step $G$ will contain following productions:

$S\_0 \rightarrow S$

$S \rightarrow AC|AD|AE|AB$

$C \rightarrow TD$

$D \rightarrow BS$

$E \rightarrow TB$

$T \rightarrow AE|AB$

$A \rightarrow a$

$B \rightarrow b$

So now grammar is in CNF. But one thing is still remaining. Original grammar produces empty string but this grammar does not. For that add production $S\_0 \rightarrow \epsilon$ to $G$.
> 2 votes

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


# Question
Title: Efficiently compute the sum of edge weights product of all possible path in a DAG
I thought of using Depth First Search (DFS) to find all possible paths in O(|V|+|E|). However, computing the product of all the edge weights for a path is O(2^N). Is there any way to compute this more efficiently?

# Answer
You can actually solve this in $O(|V|+|E|)$ time. Since it is a DAG, we can apply dynamic programming.

Let $p = u\_1u\_2\dots u\_k$ be a path and $cost(p) = w(u\_1,u\_2)\times w(u\_2,u\_3)\times\dots \times w(u\_{k-1}, u\_k)$ be the edge weight product of the path. One important observation is that $cost(u\_0p\_1) = w(u\_0,u\_1)\times cost(p\_1)$.

Now, for each node $u$, let $dp(u)$ be the sum of edge weight products of all paths **originating from $u$**.

Let the children of $u$ be $v\_1,v\_2,\dots,v\_m$. We can compute $dp(u)$ using the relation

$$dp(u)=\sum\_{i=0}^m w(u,v\_i) \times dp(v\_i)$$

A Topological sorting can find the order of nodes to compute. Then, the final answer is the sum of all $dp$

$$\sum\_{u\in V} dp(u)$$
> 3 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: Searching for the biggest area inside 2D matrix
I have an algorithmic problem where I need to find the biggest area of a certain type of pixels inside a 2D matrix with following conditions:

1. Each pixel needs to be connected either diagonally or adjacently.
2. The area is considered coherent only if it is surrounded by the other type of pixel( x-es on the edge are not)

A pixel is considered an object with 3 fields:

```
int x,y;          //Cordinates of a pixel
String type;      //Type of a pixel
boolean visited;  //Was the pixel visited

```

The input file is something like this:

```
oooooooooo
oXXooXXXoo
oooXoooooo
xooooXXXXo
xxooXooooo
xxxooooooo

```

The output in this example should be an int of value 5.

Is someone able to tell me if the BFS algorithm is a viable solution or should I try a different approach?

# Answer
A BFS combined with floodfill should be enough.

Basically, you do the following:

1. Iterate until you find the first X
2. Run a BFS on it and change all pixels to `visisted = True`. Also keep track if you happen to reach the boundary or fulfill any other criterion s.t. it is disqualified
3. If it is not disqualified, save its size as the current max-size
4. Iterate further until you find the next unvisited pixel and redo steps 2-4. Keep track of the largest size found.
5. If you need the original array, change back the visisted state of each pixel in a final iteration.

Overall runtime: Linear, because you change each element at most twice (once to visisted and once back), and also consider only a constant number of neighbors for each element (8).
> 1 votes

---
Tags: algorithms, maximum-subarray
---


# Question
Title: Hitting Set Problem with non-minimal Greedy Algorithm
The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S\_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ such that $|\mathcal{H} \cap S\_i| \geq 1$ for all $1 \leq i \leq n$.

We may ask for the minimal cardinality of $\mathcal{H}$, that is, what is the least number of elements needed to "Hit" every $S\_i$?

Further, we may use a greedy algorithm to ensure we find a hitting set. In this greedy algorithm, we set $\mathcal{H} = \emptyset$, and while we still have sets $S\_i$ that have not been hit, we add to $\mathcal{H}$ an element whom appears in the most $S\_i$ that have not been hit, breaking ties arbitrarily if there are any.

My question is: What is an example of a Universe set $\mathfrak{U}$ and subsets $S\_i$, where $1 \leq i \leq n$ for some $n \in \mathbb{N}$, such that the greedy algorithm above does not find a minimal Hitting Set $\mathcal{H} \subset \mathfrak{U}$?

For a longer (and probably clearer) description, and more info on the Hitting Set problem, see http://theory.stanford.edu/~virgi/cs267/lecture5.pdf, or Prove that Hitting Set is NP-Complete.

# Answer
> 3 votes
The greedy algorithm always finds a minimal set (inclusion-wise). However, it does not necessarily find a minimum one.

So what does minimal and minimum mean, you might ask. Minimal set in a family of sets (say the set of all hitting sets), is a set that is not a superset of any other set in the family. That means, a minimal hitting set is a hitting set where if you exclude any element from it becomes a non-hitting set. On the other hand, a minimum hitting set is a hitting set of the smallest size. Even though a minimum hitting set might not be unique, all minimum hitting sets are minimal but minimal hitting sets do not have to be minimum.

An example, where the greedy algorithm does not yield a minimum hitting set is

$$U = \\{1, 2, 3, 4, 5\\}\\ \mathcal{F} = \\{ \\{1, 2, 3\\}, \\{1, 3, 4\\}, \\{1, 4, 5\\}, \\{1, 2, 5\\}, \\{2, 3\\}, \\{4, 5\\} \\},$$ where $U$ is the universe and $\mathcal{F}$ is the family of sets to be hit. A minimum solution is hence $\\{2, 4\\}$. Any solution including $1$ is not minimum, since the set must hit $\\{2, 3\\}$ and $\\{4, 5\\}$ using at least one element of each resulting in a solution of size at least 3. However, the greedy algorithm includes $1$ in the first step and hence can not yield a minimum solution.

---
Tags: graphs, np-hard, sets, greedy-algorithms, set-cover
---


title: Chinese room test vs Turing Test

text:
# Question
Title: Chinese room test vs Turing Test
So, I took up a new course (AI) in my uni and came across these two test $TURING$ $TEST$ and $CHINESE$ $ROOM$ $TEST$. But I am not able to understand is the Chinese room test really accurate? Does it really dis-approve the TURING test?

# Answer
> 4 votes
The Turing test and Searle's Chinese Room argument represent two alternative definitions of intelligence.

The Turing test is based on the assumption that intelligence is difficult to formally define but can be easily recognised by behavior. So if a computer program behaves and interacts in a way that is practically indistinguishable from the behavior of human being (who we assume is "intelligent") then, based on this assumption, we should say that the computer program is also intelligent. In the Turing test, the particular behavior that is tested is holding a conversation in natural language.

Searle's Chinese Room argument is a challenge to the validity of the Turing test. It posits a complex system that behaves as if it were intelligent (in this case, holding a conversation in Chinese), but in which each component of the system follows an algorithm, and so no part of the system can be said to "understand" Chinese. The Chinese Room argument is based on the assumption that the system as a whole cannot be said to be intelligent unless some of its individual components are intelligent - it is essentially a reductionist argument.

In summary, the Chinese Room argument says that its is possible for a system to simulate intelligence without actually being intelligent. Whereas the Turing test is says that if a system can simulate intelligence then it actually is intelligent.

We can illustrate the difference between the two points of view with an analogy as follows. The Turing test would say that an aeroplane flies because it travels through the air from one place to another - it exhibits "flying" behavior. The Chinese room argument would say that an aeroplane only simulates flight because it does not flap its wings.

---
Tags: artificial-intelligence
---


# Question
Title: What are the characteristics of a typeless programming language?
Assume that we have an imaginary programming language that allows you to assign a Literal to a variable, but does not allow you to set the the data type of the variable, for example

```
Allocate4Bytes   an_int_variable        123456;
Allocate2Bytes   a_short_int_variable   123;
Allocate4Bytes   a_float_variable       2.1;

```

And this programming language also provides different operators to work with different data types, for example:

* The `+` operator is used to add an int to a short int.
* The `#+` operator is used to add a float to an int.
* the `=` operator is used to assign an int to an int.
* the `#=` operator is used to assign a short int to a short int.
* etc.

So it is the job of the programmer to keep track of the data type of each variable and use the appropriate operator on it.

Is this programming language considered to be a typeless programming language, or can we say that this programming language have data types (even though it does not have operator overloading and type safety, etc.)?

# Answer
It depends on what happens if the programmer tries to do something like add two things with the wrong operator. If it causes a compile-time error, the language is probably statically typed. If it throws a runtime error complaining that the two have the wrong type, the language is probably dynamically typed. If it doesn't throw an error and just tries to add those two things (possibly resulting in gibberish), it might be untyped.

To put it another way, it depends how those operations are implemented. If they are implemented to keep track of the type of the variables and check that those types match what is expected, it is typed. If it doesn't keep track of types, then it is untyped or weakly typed.

See https://en.wikipedia.org/wiki/Type\_system and https://www.sitepoint.com/typing-versus-dynamic-typing/.
> 7 votes

# Answer
A typeless computer language is one that imposes no type-like rules on values. A value may be treated as an integer, float, string, pointer etc by simply using it as if it were, usually by passing it as an argument to an operator.

BCPL was typeless in that it had a machine word of a predetermined size as its only data type, and that word could be used as an integer, pointer, character etc at will. It made writing compilers easier, and using them harder!

Parts of this philosophy made their way into its successor B, and thence into the C language that finally succeeded it. You can still write typeless code in C, if you don't mind adding a few casts and ignoring a few warnings.
> 2 votes

---
Tags: programming-languages
---


# Question
Title: Do algorithms always have a return value?
I learned that algorithms written in programming languages always return some value, not necessarily an input value.

But, if the return type of the main function is *void*, then does the algorithm return any value?

# Answer
> 1 votes
Actually, you have asked three different questions: 1) \[Does algorithm always have a return value?\[sic\]"

The algorithm by default is not a function/method (or to say program), but it could be. Sticking to the stringent definition of the algorithm. An algorithm is a set of instruction for accomplishing a task. Every piece of code could be called an algorithm e.g. 1) defining a variable or 2) writing a logic for a loop is also an algorithm. So, addressing to your original question "Does algorithm always have a return value?" answer is 'NO'. In similar situations like 1), and 2) an algorithm does not return a value.

2) "I learned that the algorithm written in programming langauge always have a return value, not necessarily an input value.\[sic\]"

If you wish to convert/write your pseudo code to a specific program in some programming language e.g. C/C++. Then every program should consist of at least one function. Programming languages like C/C++/JAVA/C# etc., provides default function call Main() in which you can call user defined function(s) (or main itself).

So, reaching the end of a function other than main is equivalent to return;. reaching the end of the main function is equivalent to return 0;. reaching the end of any other value-returning function is undefined behavior, but only if the result of the function is used in an expression.

In certain languages like C/C++ there are features which allows function to defined as 'no-return' function.

> ```
> #include <stdlib.h>
> #include <stdio.h>
> #include <stdnoreturn.h>
>
> noreturn void stop_now(int i)
> {
>     if (i > 0) exit(i);
> }
> int main(void)
> {
>      puts("Preparing to stop...");
>      stop_now(2);
>      puts("This code is never executed.");
> }
>
> ```

The 'noreturn' keyword appears in a function declaration and specifies that the function does not return by executing the return statement or by reaching the end of the function body. This type of adventure could be costly and can cause undefined behaviour to your C/C++ program.

P.S. When function/method have return type as 'void' they do not return any value, or anything. Control simply returns. It is also important to learn that void doesn't mean nothing. void is a type to represent nothing. That is a subtle difference : the representation is still required, even though it represents nothing.

3) "But it we use the main function with void return value, does that algorithm have a return value?\[sic\]"

P.S. If you define return type of main function as 'void' then it does not have any return value. You can actually omite 'return' keyword or simply type 'return' with no expression (or even 0).

# Answer
> 1 votes
An algorithm is not the same as it's implementation in some language.

Most languages have some sort of `null`-type. Java and C++, for instance, have a `void` type, and Python has a `none` type. Returning `void` or `none` is returning something, because both `void` and `none` are a part of the language, so yes, even a program which returns `null` has returned *something*.

To answer your other question, an algorithm always outputs something because by definition it must solve some class of problems in finite space and time.

Further reading.

# Answer
> 0 votes
An algorithm always outputs something because by definition it must solve some class of problems in finite space and time.

---
Tags: algorithms
---


title: What is a GPU year?

text:
# Question
Title: What is a GPU year?
I am reading papers in machine learning and they say things like, "This computation took $x$ number of GPU years".

What is a GPU year? How long is that?

# Answer
> 30 votes
That means, one year of computation time on a single GPU (or half a year on two GPUs, or a quarter of a year on four GPUs, etc.).

If you are thinking of using this term in your own writing, I encourage you to also specify what type of GPU you are using. One-GPU year on a Tesla V100 GPU is a *lot* more computation than one-GPU year on a K520 GPU. The notion of "GPU-year" is close to meaningless if you don't specify what type of GPU was used.

# Answer
> 2 votes
The paper in question, as pointed out in the comments, contains the following footnote:

> Reproducing these experiments requires approximately 6.85 GPU years (NVIDIA P100)

Note the mention of the exact GPU type that this statement is referring to in parentheses. This is vital information. As with most execution time measurements for software, you really only understand how fast it is, if you know what hardware it was measured on.

What that statement means is that a single machine with one of those NVIDIA P100 GPUs installed would need 6.85 years to reproduce the mentioned experiment. The time unit is completely meaningless unless you know which GPU it is referring to. A different GPU might need to spend a significantly different amount of time for the same task.

For example, a GPU twice as powerful as the P100 should be able to complete the same task in roughly half the time. In particular, an array of two P100 GPUs should be able to do so.

Note though that GPU work is not automatically parallelizable. If the underlying algorithm can not be parallelized arbitrarily, adding more GPUs will likely not decrease the time proportionally. If your algorithm does not behave like this, using GPU hours as a unit might be misleading. Prefer using wall clock time for measurements in such cases to avoid confusion.

---
Tags: computer-architecture, operating-systems, cpu
---


# Question
Title: For arbitrary RR(1) grammar $G$, is there an equivalent LL(1) grammar $G'$?
Failed to find similar term, here I coin the noun **RR**(Right-to-left, Rightmost derivation) as an opposite concept of LL.

The question is inspired by an interesting example grammar $G$: $$S \rightarrow S S + | a$$ It's obviously an RR(1) language. After some time to explore, I find an equivalent LL(1) grammar: $$ \begin{array}{l} S \rightarrow a A \\ A \rightarrow S + | \epsilon \end{array}$$

So, there seems a road to more generalized conclusion. Consider arbitrary RR(1) grammar, is there an equivalent LL(1) grammar $G'$, where *equivalent* means $L(G) = L(G')$?

# Answer
> 1 votes
No. A language $\mathcal{L}$ is $RR(k)$ exactly if its reverse $\mathcal{L}^R$ is $LL(k)$. So if a $RR(k)$ grammar $G$ could be transformed into an $LL(k)$ grammar $G'$, that would mean that both $L(G^R)$ and $L(G') = L(G)$ are $LL(k)$.

But $LL(k)$ is not closed under reversal; there are $LL(k)$ languages whose reverse is no $LL(k)$. The classic demonstration that the set of $LL(1)$ languages is a proper subset of the set of $LR(1)$ languages also serves for this question.

The language $\\{a^ib^j\mid 0 \le i\le j\\}$ is $LL(1)$:

$$\begin{align} S &\to A B\\ A &\to \epsilon \\ A &\to a A b\\ B &\to \epsilon \\ B &\to b B \end{align}$$

However, its reverse $\\{b^ja^i\mid 0 \le i \le j\\}$ is not $LL(k)$ for any $k$, although the reverse is clearly $RR(1)$, since a n $RR(1)$ grammar for the reverse language can be constructed by simply reversing every production in the original grammar:

$$\begin{align} S &\to B A\\ A &\to \epsilon \\ A &\to b A a\\ B &\to \epsilon \\ B &\to B b \end{align}$$

(As it happens, the above grammar is LR(1). The language is an abstraction of the "dangling else" syntax.)

---
Tags: formal-languages
---


# Question
Title: Diffie-Hellman and its disadvantage with large primes
I was reading our university slide on the Diffie-Hellman where it is mentioned that one of the disadvantages of D-H is that **For large prime, $p-1$ is an even number so, $\mathbb{Z}^\*\_p$ will have a subgroup of order 2**

What does this statement mean?

# Answer
Let $p$ be a prime number and denote by $\mathbb{Z}\_p$ the ring of integers modulo $p$. The set $\mathbb{Z}\_p^\*$ typically denotes the units of $\mathbb{Z}\_p$. This set is defined as $$\mathbb{Z}\_p^\* = \\{n \in \mathbb{Z}\_p : \exists m \in \mathbb{Z}\_p, nm = 1\\},$$ where arithmetic is done modulo $p$. An important fact about $\mathbb{Z}\_p$ is that it is a field. This means that we can simplify the above to $\mathbb{Z}\_p^\* = \\{1, 2, \ldots, p-1\\}$. This set forms a group under multiplication, and it is a standard fact that this is a cyclic group, i.e., it is isomorphic to $\mathbb{Z}\_{p-1}$ where the group operation is addition. In symbols, $(\mathbb{Z}\_p^\*,\times) \cong (\mathbb{Z}\_{p-1},+)$.

Since $p-1$ is even, consider the two-element subset of $\mathbb{Z}\_{p-1}$ given by $\left\\{0,\frac{p-1}{2}\right\\}$. As $\frac{p-1}{2} + \frac{p-1}{2} = p-1 = 0$ in $\mathbb{Z}\_{p-1}$, this set forms a subgroup of $\mathbb{Z}\_{p-1}$. The *order* of a subgroup is its cardinality as a set, so this is a subgroup of order two.

Via the isomorphism between $(\mathbb{Z}\_{p-1},+)$ and $(\mathbb{Z}\_p^\*,\times)$, this corresponds to a subgroup of $\mathbb{Z}^\*\_p$ of order two.
> 2 votes

---
Tags: computer-networks, cryptography
---


title: Cryptography: Play Fair cipher

text:
# Question
Title: Cryptography: Play Fair cipher
In our university, we were taught that since all 26 letters cant be placed together in a $5\*5$ square matrix we must put $i/j$ together like this represented in the below diagram. Here our key is $monarchy$, now what would have happened if the key contained $j$ in itself? say if the key would have been $jargon$ then how do we accommodate the one extra letter which should have been left?

# Answer
When using the convention that *i* and *j* are in the same square then they are for all intents and purposes regarded as the exact same letter, both in the key and in the plaintext. In the ciphertext, whenever it is required to write 'i/j' you can choose which one to write, while introducing no ambiguity for the decoder (in order to make the ciphertext 'look more random' it is probably best to flip a coin).

In particular, the Playfair tableau with key 'jargon' is the same as the tableau with key 'iargon': both have 'i/j' in the upper left-hand corner. HOWEVER, if you use an online solver tool it may be (the first site I checked had this implem bug) that *j* is not parsed, and the tableau is built as if the key were 'argon'; this is a (common?) implem bug though.

Note also that there other conventions than placing *i* and *j* in the same square.
> 2 votes

---
Tags: cryptography
---


# Question
Title: Necessary conditions for proving If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))
I am learning about algorithmic complexities and I read that if f(n) and g(n) are asymptotically positive functions and if $f(n) =O(g(n))$ then the relationship $log(f(n)) = O(log(g(n)))$ holds.

I would like to know what are the **necessary and sufficient conditions** for this relation to hold?

# Answer
It's obviously wrong. As an example take f(n) = 2, g(n) = $1 + e^{-n}$.

log f(n) = 1, log g(n) ≈ $e^{-n} / \log e$.
> 1 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, runtime-analysis
---


# Question
Title: If current time in milliseconds is considered good enough random seed for a pseudorandom number generator, why not just use that time directly?
I was reading about pseudorandom number generators and how they need a seed and how that seed is usually current system time in milliseconds. One of the most common algorithms is the linear congruential generator, which is an algorithm that based on some fixed constants and this seed through some mathematical computations gives the final pseudorandom output.

But what are the disadvantages of using this time directly as a pseudorandom number?

# Answer
> 4 votes
The key property that we want from (non-cryptographic) pseudorandom numbers is that they "look" independent. In particular, say you have some algorithm that requires a PRNG to perform well and you give it a current time function as a PRNG. Then, if the algorithm repeatedly queries what is supposed to be a PRNG, it will actually see that it gets the same value many times in a row until, until it eventually increments by one. These values are very, very far from random and can be detrimental to algorithmic performance.

# Answer
> 3 votes
It's not random. It increases by 1 every milliseconds. In computer terms, it stays unchanged for a loooooong time (millions of clock cycles).

But current system time in milliseconds is most definitely not good enough anyway. If an attacker knows that you seeded a random number generator some time today, there are only 86 million possible seed values. Easily brute forced; totally insecure.

---
Tags: cryptography, randomness, pseudo-random-generators, real-time
---


# Question
Title: checking '<' for two binary numbers in a cnf-formula
I want to check whether a arbitrary binary number is less or equal to another binary number in a cnf-formula. I can already construct a formula, which is not in cnf:

Lets say n and m are two-digit binary numbers:

$n = n\_2 + n\_1$

$m = m\_2 + m\_1,$

where $n\_i, m\_i \in \\{0,1\\}$ for $i \in \\{1,2\\}$. Then the boolean formula, which will evaluate to true if $n \< m$, would be:

$(\neg n\_2 \land m\_2) \lor (((\neg n\_2 \land \neg m\_2) \lor (n\_2 \land m\_2)) \land \neg n\_1 \land m\_1)$

As described, this formula should only evaluate to true if $n \< m$. I know that every boolean formula can be transformed into a cnf formula, but it seems impractical, if i have higher digit binaries.

So is there a way to construct a cnf formula, which does the same?

# Answer
> 3 votes
Yuval describes the general approach.

Let the binary representation of the two numbers be $n\_1,\dots,n\_k$ and $m\_1,\dots,m\_k$, where $n\_1$ is the most significant bit. Introduce fresh new boolean variables $t\_1,\dots,t\_k$. The intention is that these will indicate the common prefix of $n,m$.

In particular, add the following clauses:

* $t\_{i+1} \implies t\_i$ -- this ensures that $t\_1,\dots,t\_k$ has the form $1,\dots,1,0,\dots,0$.
* $t\_i \implies (n\_i=m\_i)$ -- this ensures that $t\_1,\dots,t\_k$ captures the common prefix of $n,m$
* $(t\_{i-1} \land \neg t\_i) \implies (n\_i=0 \land m\_i=1)$ -- this ensures that at the first position where $n,m$ differ, $n\_i \< m\_i$. (For the case $i=1$, treat $t\_{i-1}$ as True.)
* $\neg t\_k$ -- this ensures $n \ne m$

Each of these can be converted to a conjunction of CNF clauses. For instance, the first corresponds to the CNF clause $\neg t\_{i+1} \lor t\_i$. The second corresponds to $(\neg t\_i \lor \neg n\_i \lor m\_i) \land (\neg t\_i \lor n\_i \lor \neg m\_i)$. The third corresponds to $(\neg t\_{i+1} \lor t\_i \lor \neg n\_i) \land (\neg t\_{i+1} \lor t\_i \lor m\_i)$.

Now your formula is the conjunction of all of these CNF clauses. You obtain a formula with about $5k$ clauses. This formula will be satisfiable iff $n\<m$.

# Answer
> 0 votes
> I want to check whether a arbitrary binary number is less or equal to another binary number in a cnf-formula.

This exercise is very interesting to become familiar with Boolean formulas in *CNF*. In the question you did not specify whether the two numbers must have the same length or different lengths but for simplicity we will focus on the case $|n|=|m|$. When we are done, you will notice that the cases $|n|\<|m|$ and $|m|\<|n|$ are "trivial" variation of the former, which is more interesting. Let's see some properties that the formula you requested has, first of all a bit of *combinatorics*; we will build up the truth table of your formula $\phi$ for $1$, $2$ and $3$-*bit* numbers.

$1$-*bit* truth table $\begin{bmatrix} 0\_{(mn00)} & 0\_{(mn01)} \\ \color{red}{\text{1}}\_{(mn10)} & 0\_{(mn11)} \\ \end{bmatrix}$

---

$2$-*bit* truth table $\begin{bmatrix} 0\_{(00|00)} & 0\_{(00|01)} & 0\_{(00|10)} & 0\_{(00|11)}\\ \color{red}{\text{1}}\_{(01|00)} & 0\_{(01|01)} & 0\_{(01|10)} & 0\_{(01|11)}\\ \color{red}{\text{1}}\_{(10|00)} & \color{red}{\text{1}}\_{(10|01)} & 0\_{(10|10)} & 0\_{(10|11)}\\ \color{red}{\text{1}}\_{(11|00)} & \color{red}{\text{1}}\_{(11|01)} & \color{red}{\text{1}}\_{(11|10)} & 0\_{(11|11)}\\ \end{bmatrix}$

---

$3$-*bit* truth table

## $\begin{bmatrix} 0\_{(000|000)} & 0\_{(000|001)} & 0\_{(000|010)} & 0\_{(000|011)}& 0\_{(000|100)} & 0\_{(000|101)} & 0\_{(000|110)} & 0\_{(000|111)} \\ \color{red}{\text{1}}\_{(001|000)} & 0\_{(001|001)} & 0\_{(001|010)} & 0\_{(001|011)} & 0\_{(001|100)} & 0\_{(001|101)} & 0\_{(001|110)} & 0\_{(001|111)}\\ \color{red}{\text{1}}\_{(010|000)} & \color{red}{\text{1}}\_{(010|001)} & 0\_{(010|010)} & 0\_{(010|011)} & 0\_{(010|100)} & 0\_{(010|101)} & 0\_{(010|110)} & 0\_{(010|111)}\\ \color{red}{\text{1}}\_{(011|000)} & \color{red}{\text{1}}\_{(011|001)} & \color{red}{\text{1}}\_{(011|010)} & 0\_{(011|011)} & 0\_{(011|100)} & 0\_{(011|101)} & 0\_{(011|110)} & 0\_{(011|111)}\\ \color{red}{\text{1}}\_{(100|000)} & \color{red}{\text{1}}\_{(100|001)} & \color{red}{\text{1}}\_{(100|010)} & \color{red}{\text{1}}\_{(100|011)} & 0\_{(100|100)} & 0\_{(100|101)} & 0\_{(100|110)} & 0\_{(100|111)}\\ \color{red}{\text{1}}\_{(101|000)} & \color{red}{\text{1}}\_{(101|001)} & \color{red}{\text{1}}\_{(101|010)} & \color{red}{\text{1}}\_{(101|011)} & \color{red}{\text{1}}\_{(101|100)} & 0\_{(101|101)} & 0\_{(101|110)} & 0\_{(101|111)}\\ \color{red}{\text{1}}\_{(110|000)} & \color{red}{\text{1}}\_{(110|001)} & \color{red}{\text{1}}\_{(110|010)} & \color{red}{\text{1}}\_{(110|011)} & \color{red}{\text{1}}\_{(110|100)} & \color{red}{\text{1}}\_{(110|101)} & 0\_{(110|110)} & 0\_{(110|111)}\\ \color{red}{\text{1}}\_{(111|000)} & \color{red}{\text{1}}\_{(111|001)} & \color{red}{\text{1}}\_{(111|010)} & \color{red}{\text{1}}\_{(111|011)} & \color{red}{\text{1}}\_{(111|100)} & \color{red}{\text{1}}\_{(111|101)} & \color{red}{\text{1}}\_{(111|110)} & 0\_{(111|111)}\\ \end{bmatrix}$

In the previous tables I have highlighted in red the cases in which $\phi = 1$ ($n\<m$). An interesting thing about this function is the fact that the more $n$ and $m$ increase in the number of bits, the closer the number of valid results by random assignements approximates to $\frac{1}{2}$, this is a convergent series:

$Pr(\phi =1)$ (with $|n|$=$|m|$=$1$ *bit*): $0,25$

$Pr(\phi =1)$ (with $|n|$=$|m|$=$2$ *bits*): $0,375$

$Pr(\phi =1)$ (with $|n|$=$|m|$=$3$ *bits*): $0,4375$

$Pr(\phi =1)$ (with $|n|$=$|m|$=$5$ *bits*): $0,484375$

$Pr(\phi =1)$ (with $|n|$=$|m|$=$6$ *bits*): $0,4921$

$Pr(\phi =1)$ (with $|n|$=$|m|$=$14$ *bits*): $0,499969$

$Pr(\phi =1)$ (with $|n|$=$|m|$=$20$ *bits*): $0,4999995$

The diagonal of the truth matrix is always composed entirely by $0$s, below that we find the values that validate the formula, above those that invalidate it. If $|n|\>|m|$ there is an increase in $0$s, if instead $|m|\>|n|$ there is an increase in $1$s.

Obviously, the longer the length of $n$ and $m$, the longer the length of the formula. It is impossible to have a boolean formula that does what you ask but that is of fixed size. Let's see how the *CNF* looks for the simplest case (the first truth table), $|n|=|m|=1$*bit* :

$\phi$ = ($\neg n$ $\lor$ $\neg n$) $\land$ ($m$ $\lor$ $m$)

$\phi$ is validated if and only if $n$ \< $m$ when $n$ and $m$ are $1$ *bit* long.

I hope that what is written above can help you by giving you more tools to "visualize" and build the formula according to your needs.

---
Tags: data-structures, logic, satisfiability, binary
---


# Question
Title: Significance of quantifier ordering in quantified boolean formulas (kQBF vs. QBF)
I am studying solvers of quantified boolean formulas (QBF) as a generalization of SAT solving. The standard DIMACS format of SAT specification is extended to QDIMACS, which adds "a ..." and "e ..." lines denoting which variables are to be existentially quantified and which variables are to be universally quantified.

For instance, a simple QDIMACS input such as:

```
p cnf 2 3
a 1 0
e 2 0
1 2 0
-1 0
-2 0

```

...would be correspond to the formula $\forall x \exists y \ (x \lor y) \land \neg x \land \neg y$ where $x$ and $y$ range over $\\{T, F\\}$. SAT is an instance of QBF where all the variables are existential.

The above is an example of 2QBF, where we have two layers of quantifiers. A more complex QDIMACS problem with alternating quantifiers might be:

```
p cnf 2316 15282
e 1 17 2 18 3 19 4 ... 0
a 1598 1599 1600 1601 1602 1603 0
e 65 81 66 82 67 83 68 ... 0
a 1610 1611 1612 1613 1614 1615 0
e 193 209 194 210 195 211 196 ... 0
a 1616 1617 1618 1619 1620 1621 0
-2 -18 0
-3 -19 0
-4 -20 0
-5 -21 0
-6 -22 0
-7 -23 0
...

```

Anyways, on to my question. I don't understand why 2QBF != QBF. It seems to me for any formula $F$ and variables $x$, $y$ ranging over the booleans that $\forall x \exists y \ F$ is equivalent to $\exists y \forall x \ F$.

To demonstrate my thinking, I will consider the Shannon expansion of the universal quantifier.

\begin{align} \forall x \exists y \ F \iff& (\exists y \ F\[x \to T\]) \land (\exists y \ F\[x \to F\]) \\\\ \exists y \forall x \ F \iff& \exists y \ (F\[x \to T\] \land F\[x \to F\]) \end{align}

---

1. Suppose $\exists y \ (F\[x \to T\] \land F\[x \to F\])$ is satisfiable. Then the same assignment would extend to both $\exists y \ F\[x \to T\]$ and $\exists y \ F\[x \to F\]$.
2. Suppose $\exists y \ (F\[x \to T\] \land F\[x \to F\])$ is unsatisfiable. Then at least one of $\exists y \ F\[x \to T\]$ or $\exists y \ F\[x \to F\]$ is also unsatisfiable.

Thus $\forall x \exists y \ F \iff \forall y \exists x \ F$.

---

A similar question has been asked before here, but there appears to be ambiguity over the domain of the quantifiers. They should range only over true or false and not over other mathematical objects or propositional variables. This is in correspondence to the standard interpretation of the SAT problem.

For instance, $\forall x \exists y \ x \leftrightarrow y$ would not be true since setting $y$ to $x$ is not valid.

Is my interpretation of QBF correct? Is there a counterexample I'm missing?

# Answer
Let me first give a concrete example of a formula $F(x,y)$ such that $\forall x \exists y. F(x,y)$ is true, but $\exists x \forall y. F(x,y)$ is false. I'll then address the expansion of the universal quantifier in your question.

Take $F(x,y)$ to be a formula expressing the equality $x \oplus y = 1$, where $\oplus$ denotes exclusive-or. We can explicitly write $F$ as $$F(x,y) = (x \land \neg y) \lor (\neg x \land y).$$

To see that $\forall x \exists y. F(x,y)$ is true, let $x$ be given and take $y = \neg x$. Then $x \oplus y = x \oplus \neg x = 1$.

To see that $\exists x \forall y. F(x,y)$ is false, first take $x = 1$. Then for $y = 1$, we have that $F(x,y)$ is false, i.e., $F(1,1)$ is false. By the same reasoning, $F(0,0)$ is false, so there is no $x$ such that $\forall y. F(x,y)$ is true. Hence $\exists x \forall y. F(x,y)$ is false.

---

Your mistake is in the following argument.

> Suppose $\exists y\ (F\[x \to T\] \land F\[x \to F\])$ is unsatisfiable. Then at least one of $\exists y\ F\[x \to T\]$ or $\exists y\ F\[x \to F\]$ is also unsatisfiable.

The point is that $\exists y\ F\[x \to T\]$ and $\exists y\ F\[x \to F\]$ may both be satisfiable, but the choice of $y$ which satisfies them may be different. In order to satisfy $\exists y\ (F\[x \to T\] \land F\[x \to F\])$, you must find a single value of $y$ that satisfies both $F\[x \to T\]$ and $F\[x \to F\]$ simultaneously. This may not be possible, even if it is easy to satisfy one of $F\[x \to T\]$ and $F\[x \to F\]$ individually.

It may be helpful to expand your argument using the example I gave to see exactly where it breaks down.
> 2 votes

---
Tags: satisfiability, boolean-algebra, propositional-logic
---


# Question
Title: Can you create a deterministic PDA for non-palindomes?
Using non-determinism to create a PDA to recognize non-palindromes is easy.

My first instinct was to say yes, but it would be extremely complicated. After thinking about it, I don't think you could.

# Answer
The language of palindromes isn't DCFL, see for example this question, which proves this for the closely related language of even length palindromes. Since DCFL are closed under complementation, it follows that your language is not DCFL.
> 2 votes

---
Tags: pushdown-automata
---


# Question
Title: How can I show that a language is Turing-recognizable and decidable?
I was wondering how I can show that the language $\\{a^n b^n c^n \mid n \geq 0 \\}$ is Turing-recognizable. Also, if it is Turing-decidable?

# Answer
A language is Turing decidable if you can write a C program (replace C with your favorite programming language) that outputs YES if the input belongs to the language and outputs NO otherwise. It is Turing recognizable if in the latter case the C program simply never halts.
> 1 votes

---
Tags: turing-machines, semi-decidability
---


title: How can I show h(n) = O( √ n)?

text:
# Question
Title: How can I show h(n) = O( √ n)?
Is there any way to make recursion tree that satisfies the height $h(n) = h(n−\sqrt{n}) + 1$ to show $h(n) = O(\sqrt{n})$?

# Answer
Hint: Suppose that $n = 2^{2^k}$. Hence:

$$h(n) = h(2^{2^k} - 2^{2^{k-1}}) + 1 = h((2^{2^k} - 2^{2^{k-1}}) - \sqrt{2^{2^k} - 2^{2^{k-1}}}) + 1 + 1 = h(2^{2^k} - 2^{2^{k-1}} - 2^{2^{k-2}}\times \sqrt{2^{2^{k-1}}-1}) + 1 + 1$$

From the expansion, the order of $2^{2^{k-1}} = \sqrt{n}$ times is the length of the tree.
> 1 votes

# Answer
Consider the following sequence: $a\_0 = n$, $a\_{t+1} = a\_t - \sqrt{a\_t}$. You are interested in the minimum $t$ for which $a\_t$ falls behind some arbitrary constant $C \> 0$ (this corresponds to the base case of your recursion).

Here is the basic idea. As long as $a\_i \geq n/4$, the sequence is decreasing at a rate of at least $\sqrt{n}/2$. Therefore after at most $(n-n/4)/(\sqrt{n}/2) = \alpha \sqrt{n}$ steps (where $\alpha = 3/2$), you dip below $n/4$. After at most $\alpha \sqrt{n/4}$ steps, you dip below $n/4^2$. And so on. It takes at most $\alpha \sqrt{n/4^r}$ to dip below $n/4^{r+1}$. The total number of steps to reach $C$ is thus at most $$ \alpha\sum\_{r=0}^\infty \sqrt{n/4^r} = \alpha\sqrt{n} \sum\_{r=0}^\infty 2^{-r} = 2\alpha\sqrt{n}. $$ With more effort, you should be able to determine the constant in front of $\sqrt{n}$.

Note also the trivial $\sqrt{n} - O(1)$ lower bound, which follows from the fact that the sequence decreases by at most $\sqrt{n}$ each step.
> 1 votes

---
Tags: recursion
---


# Question
Title: How is $\text{PCP}[O(\log n),O(1)]$ NOT P?
As a prover, we just try to convince the verifier that it's correct, no matter whether it is or not. So we can just analyze every possible route.

For $\text{PCP}\[O(\log n),O(1)\]$, won't there just be polynomial many possible routes, and checking all just cost polynomial time?

> In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover is all-powerful and possesses unlimited computational resources, but cannot be trusted, while the verifier has bounded computation power. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.

# Answer
> 3 votes
A language $L$ is in $\mathsf{PCP}(r(n),q(n))$ if there is a randomized polytime algorithm $V(x,y)$ which acts as follows:

* The algorithm is given $r(n)$ random bits.
* Given these random bits, it chooses (deterministically) $q(n)$ locations in $y$.
* It reads $y$ at these locations, and based on that, decides whether to accept or reject.

Furthermore, $V$ satisfies the following two conditions:

* If $x \in L$ then there exists $y$ such that $\Pr\[V(x,y) \text{ accepts}\] = 1$.
* If $x \notin L$ then for any $y$, $\Pr\[V(x,y) \text{ accepts}\] \leq 1/2$.

Let $n = |x|$. Since $V$ uses only $r(n)$ random bits and reads at most $q(n)$ bits of $y$, at most $2^{r(n)} q(n)$ bits of $y$ can potentially be read. when $r(n) = O(\log n)$ and $q(n) = O(1)$, this means that at most polynomially many bits are read from $y$, and so we can assume that $y$ has polynomial length.

Every language in $\mathsf{PCP}(O(\log n), O(1))$ is in $\mathsf{NP}$. Indeed, given $y$, we can compute $\Pr\[V(x,y)\text{ accepts}\]$ in polynomial time (since there are only polynomially many choices for the random bits). However, the language is not obviously in $\mathsf{P}$, since there are exponentially many choices for $y$.

---
Tags: complexity-theory, p-vs-np
---


# Question
Title: Can someone explain the logic diagram for the Boolean expression NOT A OR B AND C
An IB question requests: Construct the logic diagram for the Boolean expression NOT A OR B AND C.

The answer

looks to me like not A or (B and C), whereas what I expected only gets partial credit. Can someone explain?

# Answer
The question is assuming that the operators precedence goes $NOT \rightarrow AND \rightarrow OR$, which is pretty standard for boolean logic.

Hence the proper parathensization would be $\text{((NOT A) OR (B AND C))}$, which correspods to the correct diagram, whereas the partial credits corresponds to $\text{(((NOT A) OR B) AND C)}$, which would just be a left to right evaluation of the operators.
> 3 votes

---
Tags: logic
---


title: What are Surnames' dataset usages?

text:
# Question
Title: What are Surnames' dataset usages?
I have found a dataset which involves surnames dispersion around the world that sorted by population which I use it for a name recommender system.

Its readme page caught my attention because it has mentioned that suitable for cybersecurity and ML fields. Unfortunately on I'm a newbie person in these fields, and I can not understand how it is proper in other topics such as the mentioned topics.

On the other word, I would like to know how sort of names is usable on other topics?

# Answer
The *readme* file lists the following uses for the dataset:

*1*. *Cyber Security*

*2*. *Machine Learning*

*3*. *Recommender System*

I believe that you already know point *3* since you specified that you want to use the dataset to build a *recommender system*.

About Point *2*: You can use the information in the dataset to train a machine learning algorithm. The former could, for example, learn to recognize the relationships between surnames and nationality, therefore, after the training, you could pass one or more surnames as an input to the algorithm and it could return the country.

About Point *3*: Here the subject becomes wider: such a database can have great potential in the field of security. For example it could be used to perform password penetration tests, towards servers, using the list as a dictionary. For this same reason, however, it could also be useful to any attackers with malicious intent. Another example: imagine you have gained access to a confidential database that stores all user passwords and usernames. However, these data are hashed. You could submit all dataset records to the same hash function and compare them with database hashes to see if you find matches.
> 1 votes

---
Tags: machine-learning, security
---


# Question
Title: Proving the decidability of whether a CFG generates a particular string or not
Let $G$ be a context-free grammar and $w$ be a string of length $|w| = n$.

Consider the language $A\_{CFG}$ = { \<$G$, $w$\> | $G$ is CFG that generates $w$ }, where \<$G$, $w$\> is a string encoding of $G$ and $w$.

Now we have to show that $A\_{CFG}$ is decidable, or in other words, there exists an algorithm that determines whether $w$ is generated by $G$ or not.

Now, the proof given in my book converts $G$ into an equivalent CFG $G'$ in Chomsky Normal Form and one-by-one checks all derivations in $G'$ that take $2n - 1$ steps, since a grammar in CNF takes exactly $2n - 1$ steps to generate a string of length $n$.

Now, I have an alternate algorithm in mind. I want you guys to tell me if there is something wrong with it or not because this one seems to be much simpler than the one given in my book.

So, since every CFG has a pushdown automaton which recognizes the same language, we convert the CFG into an equivalent PDA. Now we simulate the PDA on our Turing machine on the string $w$. This process must end in a finite number of steps since our string is finite in length.

Is this an alternate algorithm that illustrates the decidability of $A\_{CFG}$ or is there something wrong with it?

# Answer
> 4 votes
If you give a word $w$ not in the language, then the TM is not guaranteed to halt as an NPDA isn't always guaranteed to terminate in finite steps for a finite word.

So, you can produce a counter example in which your construction doesn't work. Take an NPDA which doesn't terminate for a given word (exists, of course) and run your algorithm on that word. Since that word is not in the language your TM won't ever produce any output as simulation will never end. You were supposed to output a "NO" here.

On the other hand, the CNF algorithm works because it guarantees execution in finite steps for every word, whether it belongs to the language or not.

# Answer
> 2 votes
Pushdown automata are nondeterministic. Therefore you need to simulate all possible execution paths. The problem is that since PDAs support $\epsilon$-moves, there could potentially be infinitely many execution paths, and it's not clear whether there's an a priori bound on an accepting computation.

Using CFGs in Chomsky normal form circumvents all these difficulties.

---
Tags: formal-languages, turing-machines, context-free, undecidability, pushdown-automata
---


# Question
Title: How to show all false outputs in a circuit?
I have 3 input variables and the output for all 8 possible combinations is 0 (false). When making a circuit, how would I show this using gates or no gates at all? Thanks!

# Answer
Hint: $A \land \lnot A$ is always False, no matter whether $A$ is True or False.
> 0 votes

# Answer
First you can write down the truth table of your circuit, in this case it will be entirely composed of $0$s. Then you will build up a Boolean expression in the form you prefer (if you have no limitations) which reproduces the behavior (relation input/output) observed in the truth table.

Note that every *operator* of your *boolean expression* correspond to a logic gate:

$\land$ = *AND*

$\lor$ = *OR*

$\neg$ = *NOT*

$\oplus$ = *XOR*
> 0 votes

---
Tags: logic, discrete-mathematics, circuits
---


# Question
Title: Finding the number of distinct strings in regular expression
Given the regular expression $(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )$, how many distinct strings are in the language? How do you determine this from looking at the regular expression? Do I have to generate a table of all possible combinations or is there a more straightforward way?

# Answer
In your example, think of the result as having filled four slots: _ _ _ \_, each of which can take one or three substrings, namely 0, 1, or the empty string. Ignoring the empty strings, it's clear that there are sixteen possible results: 0000, 0001, 0010, ... , 1111.

With the empty strings, though, since we could make 10 by $(\epsilon)(\epsilon)(1)(0)$, or by $(\epsilon)(1)(\epsilon)(0)$, or four other arrangements. What now? Well, if we realize that the six possibilities we just had all correspond to the string 10, we've got it: we'll have all strings over $\\{0,1\\}$ of length zero, one, two, three, and four, namely

$\epsilon$ (1 of them)

$0, 1$ (2 of these)

$00, 01, 10, 11$ (4)

$000, 001, 010, \dots, 111$ (8)

$0000, 0001, 0010, \dots 1111$ (16)

For a total of $1+2+4+8+16=31 = 2^5-1$. This is a particularly nice example; in general it'll be far more complicated, like, say the the expression $(1 + 01)1(1(0+\epsilon) + (101(10+101)))$. Sad to say, there's no simple rule governing all cases.

By the way, welcome to the site!
> 7 votes

# Answer
Your regular expression can also be written as $(0+1+\epsilon)^4$. It is not hard to check that it captures all strings over $\\{0,1\\}$ of length at most 4. You can count these in various ways.

As an exercise, try to answer the question for $(0+1+\epsilon)^n$.

More generally, counting the number of strings in a regular expression can be difficult. Indeed, suppose that you are given a CNF $C\_1 \land \cdots \land C\_m$ over the $n$ variables $x\_1,\ldots,x\_n$. For each $i \in \[m\]$, you can write a regular expression $r\_i$ of length $O(n)$ for the set of all truth assignments which falsify $C\_i$. For example, if $C\_i = x\_1 \lor x\_2 \lor x\_3$ then the regular expression is $000(0+1)^{n-3}$. Let $r = r\_1 + \cdots + r\_m$, whose length is $O(mn)$. The number of strings in $L\[r\]$ is $2^n$ iff the CNF is unsatisfiable.
> 0 votes

---
Tags: regular-languages, finite-automata, regular-expressions, parsers, lexical-analysis
---


# Question
Title: Difference between Parallel and Concurrent programming?
When looking at concurrent programming, two terms are commonly used i.e. concurrent and parallel.

And some programming languages specifically claim support for parallel programming, such as Java.

Does this means parallel and concurrent programming are actually different?

# Answer
> 26 votes
> Distinguish parallelism (using extra computational units to do more work per unit time) from concurrency (managing access to shared resources). Teach parallelism ﬁrst because it is easier and helps establish a non- sequential mindset.

From " A Sophomoric∗ Introduction to Shared-Memory Parallelism and Concurrency" by Dan Grossman (version of November 16, 2013)

# Answer
> 22 votes
Conurrency and parallelism differ in the problems they solve and cause, but they are not independent.

### Concurrency

Executing two tasks *concurrently* means that individual steps of both tasks are executed in an interleaved fashion. If you disregard parallelism, you can assume that only one statement is executed at any point in time, but you have (a priori) no guarantee which task gets to execute the next step.

This is useful in some regards:

* Clearer programming of independent tasks in one program.
* Allows to deal with IO while computing (e.g. in GUI).
* Allows for execution of more than one program at a time (concurrency on OS level).

Some of the main challenges are:

* Maintain data consistency.
* Avoid deadlocks and livelocks.
* Determine precise semantics of concurrent processes.
* Determine static properties that ensure correctness.

### Parallelism

Executing two tasks *in parallel* means that statements are executed *at the same time*. This is mainly useful for:

* Improve system throughput by executing programs in parallel (e.g. on multi core systems).
* Improve runtime of individual programs by utilising multiple CPUs at once.
* Utilise IO on many machines (e.g. distributed databases).

Key challenges include:

* Partition problems that allow and develop algorithms that can employ parallelism.
* Minimise dependencies and communication among the computation units.
* All the problems brought by concurrency: at least from the point of view of memory, parallel programs look like concurrent ones due to serialisation of memory accesses.
* Deal with sub-optimal hardware support.

See also this question for distinguishing parallel and distributed computing.

# Answer
> 21 votes
In addition to Nish's answer, let me recommend Simon Marlow's book on Parallel and Concurrent Programming in Haskell or his shorter tutorial. They answer your first question from Haskell's perspective, so they could be better suited for theoretically inclined readers (Haskell is a purely functional, lazy programming language that is much closer to Mathematics than other languages).

Quoting from there:

> In many fields, the words parallel and concurrent are synonyms; not so in programming, where they are used to describe fundamentally different concepts.
>
> A parallel program is one that uses a multiplicity of computational hardware (e.g. multiple processor cores) in order to perform computation more quickly. Different parts of the computation are delegated to different processors that execute at the same time (in parallel), so that results may be delivered earlier than if the computation had been performed sequentially.
>
> In contrast, concurrency is a program-structuring technique in which there are multiple threads of control. Notionally the threads of control execute "at the same time"; that is, the user sees their effects interleaved. Whether they actually execute at the same time or not is an implementation detail; a concurrent program can execute on a single processor through interleaved execution, or on multiple physical processors.

I recommend reading the rest in the tutorial (p.4), but let me quote some of the remainder of this section, as it connects both programming paradigms with quantitative and qualitative characteristics of programs, such as efficiency, modularity, and determinism.

> While parallel programming is concerned only with efficiency, concurrent programming is concerned with structuring a program that needs to interact with multiple independent external agents (for example the user, a database server, and some external clients). Concurrency allows such programs to be modular; the thread that interacts with the user is distinct from the thread that talks to the database. In the absence of concurrency, such programs have to be written with event loops and callbacks --- indeed, event loops and callbacks are often used even when concurrency is available, because in many languages concurrency is either too expensive, or too difficult, to use.
>
> The notion of "threads of control" does not make sense in a purely functional program, because there are no effects to observe, and the evaluation order is irrelevant. So concurrency is a structuring technique for effectful code; in Haskell, that means code in the IO monad.
>
> A related distinction is between deterministic and nondeterministic programming models. A deterministic programming model is one in which each program can give only one result, whereas a nondeterministic programming model admits programs that may have different results, depending on some aspect of the execution. Concurrent programming models are necessarily nondeterministic, because they must interact with external agents that cause events at unpredictable times. Nondeterminism has some notable drawbacks, however: programs become signifficantly harder to test and reason about.
>
> For parallel programming we would like to use deterministic programming models if at all possible. Since the goal is just to arrive at the answer more quickly, we would rather not make our program harder to debug in the process. Deterministic parallel programming is the best of both worlds: testing, debugging and reasoning can be performed on the sequential program, but the program runs faster when processors are added. Indeed, most computer processors themselves implement deterministic parallelism in the form of pipelining and multiple execution units.
>
> While it is possible to do parallel programming using concurrency, that is often a poor choice, because concurrency sacriffices determinism. In Haskell, the parallel programming models are deterministic. However, it is important to note that deterministic programming models are not sufficient to express all kinds of parallel algorithms; there are algorithms that depend on internal nondeterminism, particularly problems that involve searching a solution space. In Haskell, this class of algorithms is expressible only using concurrency.

# Answer
> 5 votes
A slightly idealised answer, perhaps...

* *Concurrency* is a property of how a program is **written**. If a program is written using constructions like forks/joins, locks, transactions, atomic compare-and-swap operations, and so on, then it is concurrent.
* *Parallelism* is a property of how a program **executes**. If a program executes on more than one computational unit simultaneously, then it is executing in parallel.

# Answer
> 1 votes
There are loads of answers on this, but it can be confusing. I like to think of it this way, and maybe it helps?:

***Concurrent programming*** is code that does not care about the order of execution. Java is a poor language for concurrent programming, but there are libraries and frameworks to help. JavaScript is an excellent language for concurrent programming, and it's often difficult when you want to write something that *isn't* concurrent (e.g., if you want to force the order of execution). Concurrent programming is great for event-driven programming (where order of execution is determined by event listeners, like code running in your browser that acts when you click a button or type into a box).

An example would include creating a hundred HTTP requests. In NodeJS, the simplest solution is to open all 100 requests at once with a callback method, and when the responses come back, a method is executed each time. That's concurrent programming. In Ruby, the simplest (most common) solution is to open a request and handle the response, open the next request and handle the response, etc. For many requests, NodeJS is easier to do in a timely fashion, although you have to be careful to avoid hammering the server or maxing out your outbound connections (easy to do by mistake). You can write the Ruby in a concurrent way, but it's not how most Ruby code is written, and it hurts a little to do it.

***Parallel programming*** is code that can be run simultaneously in multiple threads or processes. This allows you to optimise performance by running the code across multiple CPUs (often including multiple machines, as you might with something like Akka). Because NodeJS is not multi-threaded and there's no parallel execution, you don't have to worry about writing threadsafe code (and most JavaScript code I've seen is not threadsafe) . In Java, even though the language doesn't make concurrent programming the normal pattern, parallel programming is very much built in, and you do often have to worry about thread-safety. If you are writing a Website in Java, typically this will be run in a container that runs each request in a separate thread in the same memory, so anything shared across requests in memory (such as an in-memory cache or configuration) must be thread-safe.

---

Some of the above depends on the scope and boundaries you are talking about. I work on Websites. Most Java code I see is not concurrent programming. Sure, if you zoom out enough, the order that the customer requests come in is not important, but if you zoom in any further than that, the order that things are executed is dictated by the code. But the code is written so that the requests can execute in parallel with lots of shared objects that must be thread-safe.

Meanwhile, most JavaScript code I see is concurrent: it is written in way that the order of execution is unimportant at many levels. But it is not written to support parallel execution in shared memory. Sure, you can execute the same code in parallel across multiple processes, but the objects are not shared, so it is not parallel programming in any meaningful sense.

For additional reading, I do really like the illustrations in the top answer to this question here: https://www.quora.com/What-are-the-differences-between-parallel-concurrent-and-asynchronous-programming

---
Tags: terminology, parallel-computing, concurrency
---


# Question
Title: How to intuitively come up with an example for an ambiguous grammar and how to make that grammar unambiguous?
**I don't get how to intuitively come up with an example for an ambiguous grammar.**

Let's take as an example this grammar:

```
Declaration ::= Type D ;
         Type ::= "int" | "char"
         D ::= "*" D
            |  D "[" number "]"
            |  D "(" Type ")"
            |  "(" D ")"
            |  name

```

I am told outright that this grammar is ambiguous. What is expected of me is to find one example that proves that it is. What I'm interested is what is the thought process that allows you to find an example. Our teacher just gave us one example that would show that we would obtain two different derivation tree like:

```
int *foo[5];  has two derivation tree

            Declaration              Declaration
             /    |   \               /    |   \
           Type   D    ;            Type   D    ;
            |    / \                 |    / \____
           int  *   D               int  /   \ \ \
                   / \____              D    [ 5 ]
                  /   \ \ \            / \
                 D    [ 5 ]           *   D
                 |                        |
                foo                      foo

```

However I have no idea how he thought to himself that int\*foo\[5\] would be the example before doing the trees. **It all boils down to how they did it without trial and error?**

**How to make that grammar unambiguous?** I was also given the task to make the above grammar unambiguous. However I don't know yet again what is the intuition behind making it unambiguous.

They gave us this solution:

```
 Declaration ::= Type D ;
       Type ::= "int" | "char"
       D ::= "*" D
          |  "(" D ")" D'
          |  name D'
       D' ::= "[" number "]" D'
           |  "(" Type ")" D'
           |  empty               <== empty string

```

There must be a pattern in all of this. What it is? What is the general method to solve this type of problem regardless of which grammar is given?

# Answer
The simple way of seeing this class of ambiguities is to observe that if two right-hand sides for the same non-terminal overlap, then they could be applied in either order:

```
 D ::=     "*" D
    |          D "[" number "]"

```

The overlap is pretty clear:

```
 "*" D "[" number "]"

```

Another example, where a right-hand side can overlap with itself:

```
E ::= E "+" E

```

Overlap:

```
      E "*" E
            E "*" E
      -------------
      E "*" E "*" E

```

The solution is to remove the overlap by introducing a new non-terminal for one of the overlapping uses. Here's my solution to the ambiguity in your grammar:

```
Declaration ::= Type D ;
Type ::= "int" | "char"
D ::= "*" D
   E
E ::= E "[" number "]
   |  E "(" Type ")"
   |  "(" D ")"
   |  name

```

Which productions you decide to shift to the new non-terminal is *not* arbitrary; it will define which of the competing parses is correct for the language you are designing. There is no universal answer to that question, so it cannot be done algorithmically.

**Note:** The clumsy solution you have been provided with is probably because your lesson is being mixed with a discussion of top-down parsing. My grammar, though unambiguous, is not suitable for top-down parsing because it is left-recursive. However, the resulting parse tree reflects the syntactic structure of the declaration.
> 1 votes

---
Tags: formal-grammars, programming-languages, tree-grammars
---


title: Simulations between Turing machines

text:
# Question
Title: Simulations between Turing machines
I've got a question. How can i simulate Turing machine with a double-sided infinite tape by a Turing machine with one-sided infinite tape? The condition is, that the simulation of one step of the first machine must be equal to `O(1)` steps of second machine. Do you have any idea, how to do this?

# Answer
> 1 votes
As I understand your question, the double-sided machine has a tape indexed by $\mathbb{Z}$ and the one-sided has a tape indexed by $\mathbb{N}$.

The question then boils down to finding a bijection f between the two sets st. $\forall z \in \mathbb{Z}: |f(z) - f(z+1)| \< k$ for some constant k. Can you find such a bijection:

Hint: k = 3 is sufficient.

---
Tags: turing-machines, simulation
---


# Question
Title: Bipartite graph minimal amount of vertices required
I have a bipartite graph made of two sets (`SET 1` and `SET 2`) and I want to determine how many vertices from the `SET 1` I can remove while still having every vertex of the `SET 2` connected to at least one vertex of the `SET 1`.  In this example, `E` and `F` can obviously be removed as `D` and `C` are connected `5` and `6`.
But we could also remove `B` as `A` and `C` together cover more points. But so far I only have a very slow implementation of this which is to compare every vertex of `SET 1` to every combination of vertices of `SET1`.
Is there any smart way to do this? I've been thinking about Kőnig's theorem but I didn't find a way to use it in this context as it seems to be made for undirected bipartite graphs.

Also, there are some constraints the input follows:
-Every element of `SET 2` is connected to `SET 1`
-Every node of `SET 2` is connected exactly to two vertices of `SET 1`

# Answer
> 1 votes
Let's define a graph $G=(V,E)$, for which:

* Set of vertices $V$ is identical to your `SET1`.
* Two vertices $v\_1,v\_2 \in V$ are connected by an edge, if and only if there exists a vertex from the `SET2`, incident to both $v\_1$ and $v\_2$ in your bipartite graph.

For instance, the graph below corresponds to the bipartite graph from the example in your question:

Now, your problem is reduced to the Minimum Vertex Cover problem on the graph $G$, defined above, so you'll be able to use known algorithms to find minimum vertex cover in your `SET1` **only**.

This graph $G$ doesn't have any special structure, which could be used to find its minimum vertex cover more effectively than in general case. Also, *any* graph can be transformed to your bipartite graph form by splitting each edge by a new vertex. So, it means that your problem is equivalent to the minimum vertex cover problem, which is NP-complete - thanks to @narekBojikian for mentioning that in his answer.

# Answer
> 1 votes
This problem is NP-Hard. I will present a simple reduction from the vertex-cover problem to this problem. This reduction shows that there is probably no polynomial time algorithm for this problem, since such an algorithm will implies a polynomial time algorithm for the vertex cover problem which will implies that P=NP, since the vertex cover problem is NP-complete.

So given a graph $G(V, E)$ as an instance of the vertex cover problem, Let us build the bipartite graph $G'(V\_1, V\_2, E')$, where $V\_1$ is a copy of $V$, $V\_2$ is a copy of $E$ and $E'$ represent the incident relation in the graph, meaning that a vertex $v\_1 \in V\_1$ is adjacent to a vertex $v\_2 \in V\_2$ in $G'$, if the the edge corresponding to $v\_2$ in $E$ is incident to the vertex corresponding to $v\_1$ in $V$. Let $n$ be the number of vertices and $m$ the number of edges in the given graph.

Let us call your problem $P$. We claim that $G$ admits a vertex cover of size $k$, if and only if the problem $P$ on the graph $G'$ admits a solution of size $n - k$.

Proof. Note that $P$ admits a solution of size $n-k$, meaning that there are $k$ vertices adjacent to all vertices in $V\_2$, meaning that there are $k$ vertices in $V$ incident to all edges in $E$, meaning that $G$ has a vertex cover of size $k$.

This proof shows the correctness of the reduction in both directions. (If $G$ admits a vertex cover of size $k$ then $G'$ admits a solution of $P$ of size $n-k$ and if $G'$ admits a solution of size $n-k$ then $G$ admits a vertex cover of size $k$).

This completes the proof that $P$ is NP-hard. @HEKTO showed a reduction in the other direction, proving that $P$ is NP-complete as well.

---
Tags: graphs, bipartite-matching, vertex-cover, bipartite-graph
---


# Question
Title: How to solve the minimum-cost flow problem on a complete graph, with a concave cost function of flow for each edge?
Here is the problem:

Input:

* A series of source/sink nodes at fixed positions with given outwards/inwards flow
* Edges are NOT specified. The edges can connect any nodes.
* The total source and sink flow match
* A concave cost function that gives a cost per edge in terms of flow capacity

Expected output:

* The minimum costing graph (not necessarily fully connected) that connects all sources to sinks and permits the required flow, without creating extra nodes.

Therefore the network topology is unspecified and should be optimized.

Many thanks.

# Answer
> 0 votes
Your problem is $\rm NP$-hard by a reduction from the minimum-weight Steiner tree problem.

Let $G=(V,E;w)$ be a graph with non-negative edge weights $w(e)$, $e \in E$, and let $S \subseteq V $ be a non-empty set of terminal vertices.

The vertex set in your problem will coincide with $V$. Choose the concave function $c\_e(x)$ that describes the cost of sending $x$ units of flow across edge $e$ as $c\_e(x) = w(e)$. Pick an arbitrary terminal $s \in S$ and make it a source with supply $|S|-1$. Make every vertex in $S \setminus \\{ s \\}$ a sink with demand $1$.

There is a Steiner tree $T$ of cost at most $k$ if and only if your problem admits a flow of cost at most $k$.

$\Rightarrow$) $s$ send one unit of flow to each vertex $v \in S \setminus \\{ s \\}$ using the unique path in $T$ between $s$ and $v$.

$\Leftarrow$) Consider the subgraph $H$ of $G$ induced by the set of edges traversed by non-zero flow. Since $H$ contains at least one path from $s$ to each vertex in $S \setminus \\{ s \\}$, it must have a connected component $C$ that spans all the vertices in $S$. Let $T$ be an arbitrary spanning tree of $C$. The cost of $T$ w.r.t. $w$ is exactly the contribution of the edges in $T$ to the cost of the flow. By our choice of the concave functions, this is upper bounded by the cost of the flow itself.

Notice that, by suitably subtracting epsilons from the cost functions, you can adapt this reduction to work for strictly concave functions. In this case it is convenient to relate a flow of cost at most $k$ to Steiner tree of cost at most $\lceil k \rceil$.

---
Tags: graphs, optimization, network-flow, network-topology, topology
---


# Question
Title: How much can matrix multiplication algorithm be parallelized?
You all may know that simple Matrix Multiplication algorithm:

```
for(i = 0; i < n; i++)
   for(j = 0; j < n; j++)
      for(k = 0; k < n; k++)
         C[i,j] += A[i,k] * B[k,j]
      end for
   end for
end for

```

When we want to parallelize it, we can, at first, parallelize the outer loop, which is the most easiest thing to understand, since it is clear that it does not have data dependencies with other loops.

Most tutorial on the web stops here, like we can not parallelize anymore.

But it seems for me that even the second outer loop (the one in the middle):

```
for(j = 0; j < n; j++)

```

can be parallelized.

What about the inner loop?

Is thus possible to parallelize all three loops of a matrix multiplication algorithm or must we stop with parallelizing only the first two loops?

# Answer
> 1 votes
Ypu're starting from a completely wrong point.

The execution time of matrix multiplication does not come from the number of multiplications and additions, it's the number of uncached memory accesses that kill you. Reading a number that's not in any processor cache takes about 100 times longer than a multiplication.

So the first step is rearranging the order of operations to perform as many operations as possible using only data that is present in the fastest processor cache. That's your first step before you even think about doing things in parallel.

The next step is adding multiple sums in parallel, still in one thread. Instead of summing up C\[i,j\] for example you add six sums C\[i, j\], C\[i,j+1\], C\[i, j+2\], C\[i+1, j\], C\[i+1,j+1\], C\[i+1, j+2\] in parallel. This means you are limited by the throughput of operations, not the latency.

The next step is using SIMD instructions. Your processor quite likely has instructions that perform 2, 4 or 8 floating-point operations just as fast as a single floating-point operation.

Once you have done all this, especially the first part where the work is divided up into "blocks", you can easily process multiple blocks on multiple threads. What you need to be careful about is that you have enough cache memory to do so.

# Answer
> 0 votes
You can very well parallelize both outer loops, since no two distinct threads will write to the same memory location.

However, when parallelizing the third loop, conflicts can happen as multiple threads want to update the same location. When you want to do this, you will need atomic operations (supported on all common hardware architectures, in C++ included as *std::atomic*).

Note, that addition is usually as fast as one can get, so parallelizing over the inner loop is usually not because of the speed-up, but for saving memory (the threads won't need all all of the row/column of A/B to calculate their portion anymore)

# Answer
> 0 votes
Here is a parallel algorithm running in $O((\log n))$. As @sonneXo pointed out, each iteration of the two outer-loops is independent of all other iterations assuming a concurrent read model. So the only problem is in summing up the elements in the inner loop. Here is a divide and conquer technique that solves the problem in $O(log(n))$ using $O(n)$ threads.

So given $i, j, s, t$, we want to compute $\sum\limits\_{k=s}^t a\_{ik} b\_{kj}$ recursively. As input we give $i, j, 1, n$ and the algorithm outputs $c\_{ij}$. You can then call the algorithm in parallel on each pair $i,j$ completing the matrix.

Now we describe the recursive algorithm. Given $i, j, s, t$. if $t-s \< c$ for some constant $c$, say $c = 3$, then we compute the sum by hand in constant time. Else, let $m = s + \left\lfloor \frac{t-s}{2} \right\rfloor$. We build two instances of the problem in two new threads one of them solves $i, j, s, m$ and the other solves $i, j, m+1, t$. When the recursion returns, the algorithm only sums up two numbers returned by the recursion and returns the answer.

It is easy to see, why the running time is $O(\log n)$, since in each step we divide the size of the array by two and hence after $\left \lceil \log n \right \rceil$ steps we reach a constant size.

Note that this algorithm is not very efficient in practice due to the over head of creating threads. One algorithm that is efficient in practice, is to divide the array into $\sqrt n$ many pieces, sum up each of them in parallel in $O(\sqrt n)$ time and then sum up the answers again in $O(\sqrt n)$ time resulting in a running time of $O(\sqrt n)$ assuming you can affoard $\Omega(\sqrt n)$ threads running in parallel.

***Note*** The number of used threads can be improved into $O(n / \log n)$ by dividing the column/row into chunks of length $\Theta(\log n)$ and each thread computes the answer sequentially in each chunk in time $O(\log n)$ with at most $O(n/\log n)$ threads and then we sum up the answer in the same divide and conquer scheme as above. Since we are summing at most $O(n / \log n)$ elements we need at most so many threads.

---
Tags: algorithms, parallel-computing, matrices
---


# Question
Title: Confused about substitution in grammar in certain cases
To illustrate my confusion let's say I'm given this unambiguous grammar in BNF:

```
         S ::= T O x
         T ::= empty
         T ::= "if" E "then" T x "else" T
         O ::= empty
         O ::= "if" E "then" T O

```

Here is the corresponding derivation tree:

```
                                         S
                     ____________________|______________________
                    /                    |                      \
                   T                     O                       x
                   |         ____________|_________________
                 <empty>    / |  |             |           \
                           if E then           T            O
                                       ________|_______     |
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T
                                               |        |
                                            <empty>  <empty>

```

Why couldn't we have this:

```
                                         S
                     ____________________|______________________
                    /                    |                      \
                   T                     O                       x
                   |         ____________|_________________
                 <empty>    / |  |             |           \
                           if E then           T            O
                                       ________|_______     |
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T
                                               |        |
                                       ________|_______ \
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T

```

Why is the first T `<empty>`? What are the rules that govern how you substitute the definitions in the graph.

# Answer
> 1 votes
There's no particular reason why the first $T$ should be replaced by $empty$. The other replacement would have been equally acceptable. A grammar rule says "you can replace this string by this other" and no more. In other words, a grammar may generate several strings, depending on which of the grammar's replacement rules are called into play at any stage.

In answer to your last question, there are no rules to specify which substituition you use: the choice is up to you.

---
Tags: formal-grammars, programming-languages, tree-grammars
---


# Question
Title: Verifying whether a description of a shortest path tree is actually the shortest path tree in O(V+E) time
This is from CLRS problem 24.3-5:

> Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for each vertex $v \in V$ . Give an $\mathrm{O}(V+E)$ time algorithm to check the output of the professor’s program. It should determine whether the $d$ and $\pi$ attributes match those of some shortest-paths tree. You may assume that all edge weights are nonnegative.

All the answers I find online, explain how to solve this problem, but not why their solution is correct.

Let us look at what we need to do:

1. We need to make sure that for the source node $s$ we have $s.d = 0$ and $v.\pi = \emptyset$. This can be done in $\mathrm{O}(1)$ time.
2. We need to verify that the $\pi$ table corresponds to a tree. This is simple, we just build the undirected graph corresponding to the $\pi$ table, and then run a DFS traversal to see if the graph has cycles or not. Can be done in $\mathrm{O}(V+E)$ time.
3. For every node $u$ not reachable from $s$, it must be the case that $u.\pi = \emptyset$ and $u.d = \infty$. Another simple check, find everything you can reach in the tree that you drew in step 2, and for every other node do the checking. Another $\mathrm{O}(V+E)$ term.
4. For every edge $(u,v)$ in the shortest path tree it must be true that, $v.d = u.d + w(u,v)$. Check to ensure that this is the case. Because the professor might put random guesses for the distance values that turned out to be correct, but they had absolutely no connection to the shortest path tree given.

Everything until this point is 100% simple and clear. But the last point, is what I find difficult to argue about.

5. Relax every edge of $G$ exactly once, if any distance values change, then the shortest path tree given is wrong, if all stay the same then it is correct.

Why is this true? How to prove that if indeed the shortest path tree is wrong, relaxing every edge of $G$, no matter the order, will definitely improve at least one of the distance values?

# Answer
Relax every edge of $$ exactly once, if any distance values change, then the shortest path tree given is wrong, if all stay the same then it is correct.

Referring to this statement: As in Bellman-Ford, we run the algorithm $|V|-1$ times to compute the single-source shortest path. After this, we run the same algorithm once to check whether any relaxation happened in the graph. If there was any relaxation that means there is a negative weight cycle, and we return False. That's not exactly the case here, however you get the idea! If the algorithm given by the professor was right, then there shouldn't have any room for relaxation because relaxation means that the current shortest path $\mathrm{delta}(s,v)$ is not the shortest ($d(s,v) \> \mathrm{delta}(s,u) + w(u,v)$). Hence, the algorithm was wrong.
> 2 votes

# Answer
Hint: Consider a vertex $v\in V$ with minimal $\delta(s,v)$ , for which $v.d \ne\delta(s,v)$ .
This will help you prove both directions of this claim (even though you stated only one of them - you need to prove both of them in order to prove that this is a correct solution).
> 1 votes

---
Tags: algorithms, trees, shortest-path
---


# Question
Title: Proving that a property is k-inductive with an SMT solver (parametric resettable counter)
I'm following the slides at https://homepage.cs.uiowa.edu/~tinelli/talks/FT-11.pdf where Tinelli explains how k-induction works in the context of SMT based model checking.

A parametric and resettable counter is given as a Kripke structure by the following formulas:

Variables:

* $x := (c, n, r, n\_0)$, where:
    + $n\_0$ is a positive integer (input)
    + $r$ is a boolean (input)
    + $c$, $n$ are integers (internal variables)

Initialization:

* $I\[x\] := (c = 1) \wedge (n = n\_0)$

Transitions:

* $\begin{align\*} T\[x,x'\] := (n' = n) & \wedge (& (r' \vee (c=n)) & \to (c' = 1)) \\ & \wedge (& \neg(r' \vee (c=n)) & \to (c' = c + 1)) \\ \end{align\*}$

Property to prove invariant:

* $P\[x\] := c \le n + 1$

Tinelli uses the following notation:

$I^i:=I\[x^{(i)}\],P^i:=P\[x^{(i)}\],T^i:=T\[x^{(i−1)},x^{(i)}\]$.

He then claims on page 52/90 that the formula $P := c \le n+1$ is an invariant of this system because $P$ is 1-inductive (while incidentally not being 0-inductive). If I'm following correctly, this means that $I^0 \models P^0$ and $I^0 \wedge T^1 \models P^1$ (base case) and $P^0 \wedge P^1 \wedge T^1 \wedge T^2 \models P^2$ (inductive step). In particular it means that the formula $P^0 \wedge P^1 \wedge T^1 \wedge T^2 \wedge \neg (P^2)$ is UNSAT. However, after playing a little with Z3Py I was able to find the following model for this formula and a corresponding representation of a state transition trace with $(c,n,r)$:

* $c^0 = -1, n^0 = 0, c^1 = 1, n^1 = 0, r^1 = \text{True},c^2 = 2, n^2 = 0, r^2 = \text{False}$
* $(-1, 0, \*) \to (1, 0, \text{True}) \to (2, 0, \text{False})$

Intuitively this makes sense. The constraint on $n\_0$ being a positive integer affects the base case formula $I^0$ but not the inductive step, and therefore the above model is a valid model of the induction formula for $i=1$ which means the implication fails.

Of course $P$ is an invariant of this system, but it would seem to me that we cannot show it with k-induction for k = 1.

**What is the gap in my understanding of this material?**

# Answer
> 1 votes
I don't see any gap in your understanding. What you wrote looks correct to me.

Perhaps the author meant to use the property $P := c \le n+1 \land n \ge 1$. I think with that modification, $P$ becomes 1-inductive but not 0-inductive. I suspect the author was looking for a simple example of a property that is 1-inductive but not 0-inductive, and missed a small detail.

Good job catching this!

---
Tags: induction, model-checking, smt-solvers
---


# Question
Title: What are the differences between embedded processor and non-embedded processor?
I read a statement which says

> Almost all non-embedded processors, and many embedded processors, support virtual memory

Anyone who can explain the difference between both types

# Answer
> 0 votes
An **embedded processor** is a type of microprocessor designed into a system to control electrical and mechanical functions. Embedded processors are usually simple in design, limited in computational power and I/O capabilities, and have minimal power requirements. At a basic level, embedded processors are a CPU chip placed in a system that it helps control. You may have heard about RISC architecture. RISC and non-RISC type architectures are common amongst embedded processors.

**Non-embedded processors** on the other hand, provide multitude of services for multi use purposes, and attempt to abstract the operation of the hardware from a casual user. Virtual address space is increased using active memory in RAM and inactive memory in hard disk drives (HDDs) to form contiguous addresses that hold both the application and its data. For sure, all multi purpose processors are supporting virtual memories.

---
Tags: virtual-memory
---


title: What exactly state is in Model Checking

text:
# Question
Title: What exactly state is in Model Checking
So I finally realized the difference between *transition systems* and *automata*, and now am closer to understanding Model Checking. One of the last pieces is understanding what exactly "state" is in Model Checking.

It is mentioned that you create a Kripke Structure, which is pretty much just a state-transition system. But the thing is, I don't know what exactly the states are.

In my confusion, I think I see 3 or 4 different interpretations of states in regards to Model Checking.

1. States are steps in a Control-Flow Graph (CFG).
2. States are combinations of Boolean Variables or Atomic Propositions.
3. States are just identifiers or labels.
4. States are the values of the variables (any data variable, Boolean or not).

There is a problem with (1). Specifically, you may perform an action, and yet the value of all your atomic propositions stay the same. So it seems there is a distinction between "state as in a program step" and "state as in a set of atomic propositions". In scheduling/planning, I think this is how they conceive of states, as CFG nodes along with some Atomic Propositions.

There is a problem with (2) as well. You can create all kinds of combinations of Atomic Propositions, like even creating a Power Set of every number and combination. I wonder if these "objects" are actually called states, or if I am confusing something here. If they are states, then states are completely independent of the program CFG, though it might be correlated in some cases. Also in this case, states can be nested, because you can have states part of larger and larger sets.

My feeling about (3) is that this is what Finite State Automata and other automata typically use for state. But it seems like in some places Model Checking might be defining states as labels instead of more complex objects like (1) and (2) or even (4).

In reactive systems state is considered the "whole application state", meaning the valuations of the state *variables*. I don't think this is what Model Checking means when they talk about state.

So my question is, what exactly state *is* in Model Checking. Until today I have always imagined it as CFG nodes like in (1), in which case there is a relatively small number of them. But now I am starting to think they are more like (2), independent of CFG nodes. I can't tell yet. Program changing/running and state changing are things that *almost* always happen together. But I'm confused, thinking maybe the states in a state-transition graph / Kripke Structure are really just an abstract collection of Boolean Variables or Atomic Propositions. Please let me know if I am wrong.

# Answer
My vote is on (4) from an intuition point of view.

I just started learning this recently so take this with a grain of salt but as mentioned by D.W. the set of states can be anything you want. It is an abstract concept. However, it is natural to think of states as being valuations of the variables in the system. For example, we may think of the current state of the solar system as the current values of all variables of interest to us, such as all positions and velocities of the 8 planets in it.

Seeing it this way has another advantage. If we take the atomic propositions to be formulas of the form $x = v$ where $x$ is a variable and $v$ is a value, then the labeling function is simply the identity function: $L(S) = S$, and an atomic proposition $P$ is true in state $S$ iff $P \in S$.

The fact that the state space becomes the power set of all n-tuples of valuations of variables is not really a downside. Many of these states would simply be unreachable in any practical Kripke structure. As for your concern about states being "nested", first of all note that $S\_1 \subset S\_2$ means that they are actually different states. Secondly, if $S\_1 \subseteq S\_2$, then you have the property that anything true in $S\_1$ is also true in $S\_2$!

In fact, as far as I have seen, this is the interpretation used in many of the practical uses of Kripke structures that I have seen, such as in model checking in the context of formal verification.
> 4 votes

# Answer
A Kripke structure is a mathematical formalism. Formally, a state in a Kripke structure is just a piece of mathematics; it is an element of the set $S$. It's up to us what interpretation we put on it.

Sure, there are some applications where we model a CFG as a Kripke structure, and we let the state represent the current location in the control-flow graph (i.e., the state represents the value of the program counter). That's a modelling decision we make. There's nothing that says we have to do it that way; it's a choice we can make, or not make, according to whatever is useful for our purposes.

Perhaps the key distinction here is between a piece of mathematics and a piece of the real world; the difference between the real-world system and a mathematical model of it; and the correspondence between the two. There are many ways you might be able to model a real-world system. Conversely, there are many ways you might be able to interpret a mathematical structure and use it to model real-world systems.
> 2 votes

---
Tags: data-structures, formal-methods, model-checking
---


# Question
Title: Are number of states in a NFA same as Pumping length?
So i was reading a post on Minimum pumping length of regular language where Yuval Filmus has proved that a pumping lemma might have lesser number of states than a minimal DFA. But What about NFA's? Are NFA's able to give us minimum pumping length?

For example say we have a language L= $(10)^∗$, though for this minimal DFA will have $3$ states but NFA will have only $2$ states, which in fact is the pumping length of the language. So are NFA's able to give us exact pumping length of a language?

# Answer
Here is a counterexample. Consider the language $L = 1^\* + 0^\*1^n$. The minimal NFA for $L$ has $n+C$ states for some constant $C$, but *every* word can be pumped, so the pumping length is 1.
> 3 votes

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


# Question
Title: Doubt regarding Cantor's diagonalization argument
So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider.

I understand the overall argument but have a problem regarding one caveat mentioned in my book.

My book says that some real numbers like 2.000... and 1.999... have different decimal representations but are actually the same real numbers. Suppose we have a bijection $ f: N \rightarrow R$ where $N$ and $R$ are the sets of natural and real numbers respectively. Now, suppose $f(1) = 1.999...$ and no $x \in N$ exists such that $f(x) = 2.000...$. In such a scenario it is possible that the diagonalization argument ends up constructing the real number $2.000...$ which is already in our list since $1.999...$ and $2.000...$ are the same real numbers. To get around this problem, we never select 0 or 9 when constructing our number.

I don't understand two things. First, why do $1.999...$ and $2.000...$ represent the same real number? Second, how never selecting 0 or 9 solves the problem this poses?

# Answer
> 4 votes
There are several issues with your question but perhaps I can clarify some issues.

First off you assume $f(1) = 1.999...$ and also that no $x \in \mathbb{N}$ exists such that $f(x) = 2$ but that's a contradiction in terms because $1.999... = 2$ and thus $f(1) = 2$.

Why does $1.999... = 2$? Well there's an easy answer but not fulfilling answer and a more complicated answer that I find satisfactory. The easy answer is that $1 = \sum\_{i=1}^{\infty}9\*10^{-i}$ (the general form $(N - 1)\*N^{-i}$ holds for all $N$) and $0.99...$ is definitionally $\sum\_{i=1}^{\infty}9\*10^{-i}$

A more satisfactory answer comes from understanding the representation of real numbers as you would in an analysis class and understanding when we define two real numbers to be equal. There are many different representations and I'll get details wrong here if I try and give you a precise example but the basic idea of most representations is to represent a real number as a sequence (sometimes its not a sequence but generally) of finite (generally rational) approximations. So $\[1/1, 1/1, ...\]$ is a real number representing `1.0` and $A = \[9/10, 99/100, 999/1000, ...\]$ is another that as we shale see is equivlent. Notice that the terms in that are the finite sums of $\sum\_{i=1}^{\infty}9\*10^{-i}$. We define the summation to be the sequence of its finite summations. If the sum converges then this defines a valid real number. Why does $\[2/1, 2/1, ...\] = \[19/10, 199/100, ...\]$? Because for any $\epsilon \> 0$ I choose you can find an $N$ such that the difference of the $N$th elements of each sequences is within $\[-\epsilon, \epsilon\]$ or in a nutshell, the approximations become arbitrarily close. Take this paragraph with a grain of salt though, I'm being handy wavy and imprecise.

The traditional proof of cantor's argument that there are more reals than naturals uses the decimal expansions of the real numbers. As we've seen a real number can have more than one decimal expansion. So when converting a bijection from the naturals to the reals into a list of decimal expansions we need to choose a canonical choice. The axiom of choice just lets us do this for free but it sounds like your book tried to do something different. It isn't clear to me what your book did exactly from your description. Here's a potential way but it relies on further knowledge of reals and decimal expansions.

Take for granted that only the rationals with terminating decimal expansions (e.g. not 1/7 or 1/3 but 1/2 = 0.5 and 1/8 = 0.125 etc.. are valid) have two representations. Then its clear that every real number has exactly one non-terminating representation. So for our decimal expansions if we restrict ourselves to the non-terminating expansions we have no ambiguity.

---
Tags: turing-machines, undecidability, discrete-mathematics, real-numbers, uncountability
---


# Question
Title: What would happen if we added this rule to red-black trees?
So, I know that a normal r-b tree has a height of O(logn). What would happen is we let a red node have a red child if its parent is black?

Would the height still be O(logn)? Would you have to have a totally different insertion scheme to maintain the height?

# Answer
Yes it stays $O(\log n)$. Compared to the proof of the original one, we have no three red consecutive on a path from the root to a leaf. The bound on the blacks stays the same in a path. The length of the path is now at most three times the number of blacks which is at most $3O(\log n)=O(\log n)$.

The insertion changes indeed. Now we have strictly more cases, since we are supposed to regard two levels up in the tree after inserting and rotating. However, I think a case distinction suffices as well similar to the one in the original r-b trees.
> 1 votes

---
Tags: balanced-search-trees, red-black-trees
---


title: totally ordered semigroups

text:
# Question
Title: totally ordered semigroups
Given a semigroup is it possible to give a total order to it?

If not possible in the general case then what about the case of finitely generated finite semigroups?

Does there exist a natural extension of the syntactic order given to a semigroup w.r.t. an upper set? (currently it only induces a partial order)

# Answer
> 2 votes
**Monogenic semigroups**. Consider the case of a \[monogenic semigroup\](monogenic semigroup), that is, a semigroup $S$ generated by a single element $s$. If $S$ is finite, then it can be totally ordered if and only if it is aperiodic, that is, if there exists a positive integer n such that $s^n = s^{n + 1}$. In this case, the order could be $s \leqslant s^2 \leqslant \dotsm \leqslant s^n$. If $S$ is not aperiodic, then it contains a finite subgroup, and the only compatible order on a finite group is the equality, as you observed.

If $S$ is infinite, it can also be ordered by $s \leqslant s^2 \leqslant s^3 \leqslant\dotsm $.

**Arbitrary semigroups**. An interesting example is the free monoid $A^\*$ equipped with some shortlex order. Shortlex orders are total and are compatible with the concatenation product.

**Second question**. I am not sure what you mean by a "finitely generated finite semigroup" since every finite semigroup is finitely generated. Thus I suppose that the question is whether the order of a finite ordered semigroup can be a total order. There are some examples which are not monogenic, for instance the ordered semigroup $(S, \leqslant)$ with $S = \\{a,b\\}$, $a \leqslant b$, $aa = ba = a$ and $ab = bb = b$.

**Third question**. See my comment.

---
Tags: regular-languages, finite-automata, algebra, ordering
---