# Question
Title: Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism?
I'm working on a problem related to Latin squares, and I want a method for what essentially boils down to the decision problem:

*Input*: A finite, simple graph G.
*Output*: `YES` if G has a non-trivial automorphism, `NO` otherwise.

Hence...

**Question**: Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism?

We could use Nauty or Bliss (and possibly some other packages) to compute the whole automorphism group, but I don't need it; all I need to determine is whether or not it's trivial.

It's possible this decision problem is theoretically equivalent in complexity to "compute the whole automorphism group" in some way. I'm not sure.

For my purpose, "efficient" basically means "faster in practice than computing the whole automorphism group", but I'm also interested in the theory behind it.

# Answer
Since you are also interested in the theory behind it, I would give you a quasi-polynomial time algorithm for your problem.

For each pair of vertices $u\neq v$ (of same degree) in $G$, we try to see if it it possible to *swap* $u$ and $v$.

To do this, make a copy of $G$, call it $G'$. Now, delete $u$ from $G$, delete (copy of) $v$ from $G'$.

Then, for each $w\in N(u)$ attach to it a very long path, but only *polynomially long*.

Then, for each (copy of) $w\in N(copy\ of\ v)$ attach to it a very long path, but only *polynomially long*.

All the mentioned above very long path, but *polynomially long*, should be of the same length.

Call Babai's algorithm on the input of this newly produced pair of graphs.

If for any pair $(u, v)$, we have a $YES$ answer from Babai's, answer $YES$ and halt.

If none returns a $YES$ answer, answer $NO$ and halt.

Clearly, attaching to all vertices in $N(u)$ and $N(v)$ forces the graph isomorphism of Babai's inner working mechanism of his algorithm to only map vertices in $N(u)$ to $N(v)$. Thus, if Babai's answer is $YES$ then we can safely plug in back $u$ and $v$ to have a non-trivial automorphism of $G$, since $G'$ is a copy of $G$.

The run-time complexity is still quasi-poly.
> 2 votes

---
Tags: algorithms, graphs, reference-request
---


# Question
Title: ACM Collegiate Programming Contest: Blue Balloon Parallelogram counting
The problem is from the ACM Collegiate Programming Contest: 5924 - Parallelogram Counting

**Problem Description**

The International Consortium for Parallelogram Counting (ICPC) wants to move into the digital age and automate their parallelogram counting. They want to count the number of parallelograms formed by universities in various countries. For each country, they have a map which is divided into a regular n × n grid. In each cell of the grid, they have indicated whether a university is present or not (there are never two universities in the same grid cell).

After some argument, they have settled on the following definition of a parallelogram: it is a set of four distinct points (A, B, C, D), such that AB and CD are parallel and have the same length. Note that a parallelogram can have zero area. Two parallelograms are considered different if one contains a point that the other does not; simply considering the same four points in a different order does not make a new parallelogram.

**Input**

Input consists of multiple test cases, each describing a country.

Each case begins with a line containing the integer n (1 ≤ n ≤ 500), the size of the grid. This is followed by n lines of n characters. Each character is either a ‘1’ to indicate that a university is present, or a ‘0’ to indicate that no university is present, in the corresponding grid cell. There are no spaces between the characters.

The last case is followed by a line containing ‘-1’, equivalent to n == −1. There will be at most three test cases in which n \> 20.

**Output**

For each country, output a line containing the number of parallelograms formed by universities in that country. Note that this number might be large.

**Input** `4
1101
1000
0001
0011
4
1111
0000
0000
1111
3
111
111
111
-1`

**Sample Output** `3
16
22`

I've been able to parse the input and create an array for each country, but I can't seem to understand how they calculate the number of parallelograms formed.

# Answer
For better visualization, I use "." instead of "0" to indicate that no university is present.

The first test case in the sample input has 3 admissible parallelograms.

```
1101      11..   1...   .1..
1000      ....   1...   1...
0001      ....   ...1   ...1
0011      ..11   ...1   ..1.

```

The second test case in the sample input has 16 admissible parallelograms.

```
1111      1111   ....   11..   11..   11..   .11.   .11.   .11.
0000      ....   ....   ....   ....   ....   ....   ....   ....
0000      ....   ....   ....   ....   ....   ....   ....   ....
1111      ....   1111   11..   .11.   ..11   11..   .11.   ..11

          ..11   ..11   ..11   1.1.   1.1.   .1.1   .1.1   1..1
          ....   ....   ....   ....   ....   ....   ....   ....
          ....   ....   ....   ....   ....   ....   ....   ....
          11..   .11.   ..11   1.1.   .1.1   1.1.   .1.1   1..1

```

The third test case in the sample input has 22 admissible parallelograms.

```
111    11.   11.   11.   11.   .11   .11   .11   .11   ...   ...   ...
111    11.   .11   ...   ...   11.   .11   ...   ...   11.   11.   .11
111    ...   ...   11.   .11   ...   ...   11.   .11   11.   .11   11.

       ...   1.1   1.1   ...   .1.   1..   ..1   1..   .1.   .1.   .1.
       .11   1.1   ...   1.1   1.1   1.1   1.1   11.   11.   .11   .11
       .11   ...   1.1   1.1   .1.   ..1   1..   .1.   1..   ..1   ..1

```

For $n\le6$, a brute-force search is able to calculate the number of parallelograms within a second. For example, a 6x6 grid of all "1"s has 2273 parallelograms. The search iterates through all possible combination of 4 cells. For each 4 cells, check if they are distinct and each of them stores "1" and they can form a parallelogram. If not, skip. If yes, add them to the result set. This result set is initialized as an empty set before the brute force begins. Two parallelograms are consider the same if and only if their four points are the same as sets. To speed up the comparison of two parallelograms, the four cells of a parallelogram are always sorted in the lexicographical order. Then two parallelograms are the same if and only if they have the same first, second, third and fourth cell. This simple algorithm by brute-force search is meant to be the correct algorithm whose result can be used to verify the result of more complicated algorithm in the small cases. Apparently, to finish the actual task, a much faster algorithm must be developed.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Incremental strongly connected components
For a changing directed graph, I would like to maintain information about strongly connected components. The graph operations are incremental: only vertex addition and edge addition. What data structures achieve the best known amortized complexity for these operations?

If the graph was undirected, the answer would be the union-find structure. And as undirected graphs can be seen as special cases of directed graphs, the (ever so slightly) superconstant lower bound carries over.

For a linear upper bound, the strongly connected components can be computed from scratch after each edge addition, without recycling any data at all. I wonder if there is any way to do better.

In the setting where I need this, I somehow expect non-trivial SCCs to be the exception rather than the rule. And in the absense of cycles I can achieve linear time in total (that is amortized constant time per operation). \[EDIT:\] Let me clarify what I mean. Of course, in the absense of cycles I do not need to keep track of SCCs at all. The amortized constant time is for what I do in my setting *besides* worrying abouts SCCs.

So I would also be interested in data structures that are, in general, not better than the above upper bound but use amortized constant time per operation as long as the graph remains a DAG.

# Answer
> 15 votes
To the best of my knowledge, the best algorithm for **decremental** strongly connected components is presented in \[1\] with $O(m \sqrt{n} \log n)$ total expected update time.

> \[1\] Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time - Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Łącki, Nikos Parotsidis - https://ieeexplore.ieee.org/document/7782945 \- FOCS 2016

**Update: The new best Algorithm for decremental SCCs is $O(m (\log n)^4)$ presented in \[5\]**

> \[5\] Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time \- Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen -https://arxiv.org/abs/1901.03615 \- accepted at STOC 2019

The best algorithm for **incremental** strongly connected components is presented in \[2\] with $O(m^{1/2})$ update time per edge.

> \[2\] Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance - Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan -https://arxiv.org/abs/1105.2397 \- 2012 ACM Trans. Algorithms

It is an open question if those two problems can be solved faster.

For **fully dynamic strongly connected components** conditional lower bounds are known. Worst-case lower bounds are also known for decremental/incremental strongly connected component maintenance. For details look in \[3\] and \[4\].

> \[3\] Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture - Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak - https://arxiv.org/pdf/1511.06773.pdf \- STOC 2015
>
> \[4\] Popular conjectures imply strong lower bounds for dynamic problems \- Amir Abboud, Virginia Vassilevska Williams - https://arxiv.org/pdf/1402.0054.pdf \- FOCS 2014

All of these results hold for general graphs. Better results are known for planar graphs.

The result you mention about DAGs is well known:

> Amortized efficiency of a path retrieval data structure - G. F. Italiano - https://www.sciencedirect.com/science/article/pii/0304397586900988 \- TCS 1986

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


# Question
Title: solving large nonlinear systems in parallel
I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations. Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to solve the linear system to get the update increment. I am solving the system on a single 24 core, 64GB workstation with a NVIDIA Quadro K4000 GPU. However as the number of unknowns exceeds 1e5 and/or the Jacobian matrix gets more dense, there is not enough memory on the GPU to fit the compressed Jacobian matrix on the device. Using the CPU cores allows the Jacobian matrix to fit into memory, however the compute time is very long.

I would like to use a cluster of the above mentioned workstations to solve either the nonlinear system or the linear update increment system, however I am not sure how to go about decomposing the system of equations into pieces that can be tackled via a distributed memory approach. The equations include radiative transfer, and therefore it is not easy to decompose the domain geometrically as the Jacobian matrix is dense.

Does anyone know about distributed memory approaches to solving large dense linear equation systems?

All help is greatly appreciated!

PS I have looked into the parallelised nonlinear solvers implemented in PETSc, however this is a clunky c library and one must write there entire problem in terms of the PETSc interface which I would like to avoid if possible. I would be more interested in understanding the details as to how a distributed memory parallelised nonlinear or linear solver works...

# Answer
The main point of Krylov-Newton is that it does not require computing and storing the whole Jacobian matrix. It only requires the ability to *apply* the matrix to a vector.

The stardard approach is to do a little bit of pencil and paper work to figure out how to express the action of the derivative without actually computing and storing the whole matrix. If this is not possible, one can try to figure out a compressed representation of the matrix.

For problems where the matrices are dense, but the long range interactions are low rank (I think many radiative transfer problems would fall in this category..?), **fast multipole** or H-matrix type methods tend to be very effective.

It's difficult to give further advice without knowing more specifics of the problem.
> 4 votes

# Answer
You could also consider nonlinear variants that do not need Jacobian inversions. For Jacobians that look like Hessians, there are quasi-Newton algorithms. You can also try Anderson Acceleration and the related nonlinear GMRES. We try to cover the taxonomy of these solvers in Composing Scalable Nonlinear Algebraic Solvers
> 2 votes

---
Tags: distributed-systems, parallel-computing, linear-algebra
---


# Question
Title: About the relationship between non-termination and inconsistency?
I've been trying to get into Agda and I noticed that it doesn't have recursion, which implies that it isn't *Turing-Complete*.

From what I could understand, **if** Agda had *recursion*, it would make itself an *inconsistency* from a type theory perspective.

Something stuck to my mind: **Is it possible to exist a language that it isn't strongly normalizing but, yet, consistent?** Or does the **existence** of recursion *mandatorily* implies inconsistency?

# Answer
# Some trivial type systems

Let the set of types be $\bot,\top$ and the sets of terms be $a,b$, with typing rules

$$ \vdash a:\top \qquad \vdash b:\top $$ and computational rules $$ a \to b \qquad b \to a $$

Then, the resulting system has no (weakly/strongly) normalizing terms, yet it is consistent since no term inhabits $\bot$.

We can also allow recursion on $\top$, if we want.

$$ \dfrac{ \Gamma, x:\top \vdash e:\top }{ \Gamma \vdash {\sf rec}\ x. e\ :\top } $$ with the obvious computational rule $$ {\sf rec}\ x. e \to e\\{{\sf rec}\ x. e/x\\} $$

# On adding full recursion

Of course, we can't allow unrestricted recursion on $\bot$, otherwise ${\sf rec}\ x.x:\bot$ leads to an inconsistency.

# Adapting more serious type systems

If we take any strongly normalizing typed lambda calculus, we can modify the computational rules to add a silly reduction step $$ t\to t $$ for any term $t$.

The new calculus has as inhabited types the same inhabited types, so it preserves consistency. The calculus is not even weakly normalizing, though.
> 4 votes

---
Tags: formal-languages, functional-programming
---


# Question
Title: Can a safe state in Banker's Algorithm cause deadlock eventually?
I know that unsafe state does not always mean deadlock. That is a situation that banker's algorithm does not detect deadlock accurately. I am just wondering if there is any example of a safe state that deadlocks?

# Answer
**No deadlock as long as you keep running the Banker's algorithm.**

By definition, a state is considered safe if it is possible for all processes to finish executing, which means there is no deadlock.

In order to avoid triviality, the question should be asking whether a safe state might change into deadlock. Assume the system is in a safe state (or the system is safe in short) initially. If you are able to run the Banker's algorithm, then

1. each time a request for resources is raised, the system will

* either reject the request so the state will not change, meaning the system is still safe of course.
    * or it will grant the request after it have been verified that after the requesting process has obtained those resources the system will still be safe, meaning the system is still safe.
2. each time some resources is returned, the system will obviously still be safe.

So, you can see that almost by definition and design, a safe state never goes into deadlock under the Banker's algorithm.

A more interesting question might be whether the system guarantees to make progress. The answer is yes, too. For any process, it is assumed that maximum number of instances of each resource type may not exceed the total number of resources in the system. It is also assumed that when a process gets all its requested resources it must return them in a finite amount of time. Suppose at some point of time, no process is able to run yet because of its lack of resources. Since the system is safe, resources will be allocated upon requests continuously until one of process is able to get all the resources it needs, meaning that process will start to run and progress will be made. After some finite amount of time, that process, having made some progress, must return all its requested resources to the system. Now the system is sort of back to square one but with progress made.

For a more rigorous analysis, you can check *Selected Writings on Computing: A Personal Perspective*, Springer-Verlag, 1982, by the algorithm's designer Edsger W. Dijkstra.
> 1 votes

---
Tags: operating-systems, deadlocks
---


# Question
Title: Is it there any computer/cellular automaton/brain to compute logically impossible and incomputable things?
Is it there any computer or cellular automaton or model of the brain where they could compute logically impossible things and incomputable things?

For example, if we wanted to compute/simulate/think about a universe where 1+1=3 (which would gives as result a universe where literally everything could happen, possible or impossible things; where we could do logically impossible things like drawing a line that intersects a circle at three points, factorizing number 181 or finding a solution to Russell's Set, defined as a list of things that both contains itself and does not contain itself at the same time, without resorting to weird definitions of list/contain/etc, i.e. in the context of naive set theory) we would find immediately important problems:

If 1+1=3, everything equals everything at the same time. Everything is also unequal to everything at the same time. If you hold that as a general assumption, then everything is inconsistent. What this means is that given an algorithm and an input, there is no one output. There are infinitely many outputs. In some contexts infinite possible outputs is not an issue (subject to whether or not you assume the axiom of choice) if those outputs fall on a computable distribution. But in the event that we have exploded logic, there is no such computable distribution. Which means that everything both is and isn't an appropriate output. "1+1=apple".

So could there ever be some computer/cellular automaton/brain that could compute these? Is it there any model of such machine/brain? Even if it is physically impossible given the physics that we have in our universe, is it there any model of that?

# Answer
This question is just playing with words. According to Ludwig Wittgenstein, "whereof one cannot speak, thereof one must be silent". OK, I don't know what that quote means. Well, I do not know what this question means either. Or, possibly, I know exactly what this question means even better than OP.

What does not it mean by "everything impossible can happen?" This sounds like a beginner philosopher just starting his journey or a seasoned philosopher in search of unknown territories. It sounds like the merging of waves and particles but many times crazier.

What cannot happen in reality could happen in virtual reality. What cannot happen in virtual reality could happen in pure mind. (Please notice I am stealing the concepts.) Everything impossible happens right here. I mean, it is happening right there inside that sentence.

Does human mind work logically? Does the current question indicate a new passage to new knowledge? Is there anything here that can salvaged just like the negative number, irrational number, imaginary number?

Enough (playing with words) is enough. Let us get down to the ground truth. Suppose some "computer or cellular automaton or model of the brain where they could compute logically impossible things and incomputable things". **Can you imagine a way in which that computing thing could bear some positive influence on our world and our understanding of the world in ordinary ways? That request/question is the most reasonable answer to your question, as I see it.** All those once "illogical" but not eliminated creations have practical applications, as for example, negative numbers helps us solve equations with positive numbers and for example, some aspects of the world is better described by the imaginary or complex numbers.

(This question and this reply belongs possibly to Philosophy Stack Exchange)
> 4 votes

---
Tags: computability, logic, cellular-automata
---


# Question
Title: Minimize Manhattan distance travel algorithm
I am trying to find the name of an algorithm for a game I am making. I am pretty sure it exists, but I have no idea what name it has.

Say I have a matrix like:

$$ \begin{array}{|r|r|r|} \hline \hphantom{-}1 & -1 & 0 \\\hline 0 & 0 & 1 \\\hline 0 & 1 & -2 \\\hline \end{array} $$

I know that the sum of each element of the matrix is zero.

And an operation $f$ which sums two elements of the matrix together and replaces both of them with this sum. In our example $f( a\_{1,1} a\_{1,2} )$ (where $a\_{r,c}$ is the element of the matrix at row $r$ and column $c$) would lead to

$$ \begin{array}{|r|r|r|} \hline \hphantom{-}0 & \hphantom{-}0 & 0 \\\hline 0 & 0 & 1 \\\hline 0 & 1 & -2 \\\hline \end{array} $$

The cost of this operation is the Manhattan distance between the two points, in this case $1$.

Now, I want to find the moves that:

* make each element of the matrix go to $0$
* minimize the total cost

Is there an algorithm (or a combination of them) that does that? Sorry for the laymen lingo, I am not a programmer myself!

# Answer
> 1 votes
You could always try the A\* algorithm. It might not be optimal but it is something you could try, and depending on how big the matrix is it might be good enough. You'll need to design an appropriate heuristic (e.g., maybe the number of elements that are non-zero, divided by two?).

---
Tags: algorithms, matrices
---


# Question
Title: Introductory explanation of the Big-Oh properties
I've noticed that Big-Oh notation actually has some properties such as *summation*, *product* but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic problems.

1) Is it possible to explain these properties in plain English?

2) Can these properties be applied to Big-Omega and Big-Theta notations?

Please leave any intuitive material that can help the understanding of these properties (and others).

Thanks.

# Answer
Let's start by considering the positive numbers. There is a notion of order: $$ x \leq y. $$ We can add and multiply numbers, and the order relation respect these operations: $$ x \leq y, z \leq w \Longrightarrow x + z \leq y + w, xz \leq yw. $$

Big O notation is very similar. We consider, for simplicity, functions which accept a natural number as input, and output a positive real. We define an order relation: $$ f = O(g) \text{ iff there exists } C \> 0 \text{ such that } f(n) \leq Cg(n) \text{ for all } n. $$ (The funny notation $f = O(g)$ is just a notation for an order relation. Sometimes $f \ll g$ is used instead, but this is not common in computer science.)

This is similar to what we had above, with two important differences:

1. Since we have a function rather than a single value, we need the inequality to hold for all inputs.
2. We put in the extra constant $C$. This has the effect of identifying functions which differ only by a constant factor.

In more details, if $Af(n) \leq g(n) \leq Bf(n)$ for all $n$ then $g$ is "equivalent" to $f$ in the sense that $f = O(h)$ iff $g = O(h)$ and $h = O(f)$ iff $h = O(g)$.

The big O order relation also respects addition and multiplication: $$ f = O(g), h = O(k) \Longrightarrow f + h = O(g + k), fh = O(gk). $$

---

For positive numbers, we have not only $\leq$ but also $\geq$. These are related by $$ y \geq x \text{ iff } x \leq y. $$ The relation corresponding to $\geq$ for functions is $g = \Omega(f)$, defined by $$ y = \Omega(x) \text{ iff } x = O(y). $$ This order relation also respects addition and multiplication.

---

What happens if $f = O(g)$ and $f = \Omega(g)$? When this sort of situation happens in the universe of numbers, that is when $x \leq y$ and $x \geq y$, then the two numbers are equal: $x = y$. In the case of functions, we don't get equality, but rather the notion of equivalence that was mentioned above: $Af(n) \leq g(n) \leq Bf(n)$ for some positive $A,B$. In this case we write $f = \Theta(g)$.

You can think of $f = \Theta(g)$ as an analog of equality. Indeed, it is possible to quotient by this equivalence relation and work with functions "up to constant factors", but there is no need to understand this point of view when working with asymptotic notation. It suffices to understand that if $f = \Theta(g)$ then, for the most part, $f$ and $g$ are interchangeable.

(They are not interchangeable when appearing in the exponent: for example, $n^2$ and $n^3$ don't have the same asymptotic rate of growth, although $2 = \Theta(3)$. They are also not interchangeable if appearing at the base of a non-constant exponent: $2^n$ and $3^n$ have different rates of growth.)

An important special case is $Cf = \Theta(f)$ (for $C \> 0$). That is, in most cases $f$ and $Cf$ are interchangeable. In other words, asymptotic notation hides constant factors. This is one of the advantages of big O notation.

---

Big O notation satisfies the following peculiar property: $$ f + g = \Theta(\max(f,g)). $$ This useful property allows us to simplify expressions: for example, $n^2 + n = \Theta(n^2)$. Generalizing this, if $f$ is a degree $d$ polynomial, then $f = \Theta(n^d)$.
> 2 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Proving whether $\bf{K}$(Happy $\lor$Sad) $\implies$ $\neg \bf{K}($Happy) is satisfiable, valid or unsatisfiable
I have a question that I am stuck on reasoning about knowledge. For the following statement, I need to show whether it is valid, satisfiable or unsatisfiable:

$\bf{K}$(Happy $\lor$Sad) $\implies$ $\neg \bf{K}($Happy)

I have done the following:

Let e w be an interpretation where e is the set of possible worlds and w is the real world. Then we need to show that for any interpretation, e w satisfies $\neg \bf{K}$(Happy $\lor$Sad) $\lor$ $\neg \bf{K}$(Happy).:

Now assume that such an interpretation e w satisfies $\bf{K}$(Happy $\lor$Sad). This would mean for all w' $ \in$ e, e w' satisfies $\bf{K}$(Happy $\lor$Sad). However in a world w'' = {$\neg Happy, \neg Sad$}, then the interpretation e w'' does not satisfy $\bf{K}$(Happy $\lor$ Sad).

Therefore, we have a contradiction and for any interpretation e w, e w satisfies $\neg \bf{K}$(Happy $\lor$Sad).

Similarly, assume an interpretation e w satisfies $\bf{K}($Happy). However, if we have a world(s) where $\neg$Happy is true, then e w'' does not satisfy $\bf{K}($Happy). Therefore for any e w, e w satisfies $\neg \bf{K}($Happy) and thus the statement is valid.

I'm not sure whether my proof is correct and if not, could give me a hint on how to go about with this question.

# Answer
> 1 votes
The formula is either satisfiable or unsatisfiable. Only when it is satisfiable, it may also be valid.

To rule out that the implication is *valid*, show that its negation is satisfiable, that is, construct a model that satisfies the LHS but not the RHS. (Hint: a model with just one possible world suffices.)

Next, rule out that the implication is *unsatisfiable* by providing a model that satisfies the RHS. (Hint: again, a model with just one possible world will do.)

After these two steps, you're left with the answer.

---
Tags: knowledge-representation, reasoning
---


title: Left-Right-Rotation of AVL-Tree

text:
# Question
Title: Left-Right-Rotation of AVL-Tree
For AVL-Tree there exists the following Rotations for Balancing:

* Left Rotation
* Right Rotation
* Left-Right Rotation
* Right-Left Rotation

My Question is about the Naming for the Double-Rotations. Sometimes a Left-Right Rotation is defined as a Left-Rotation followed by a Right-Rotation. This is for me the logical case. Sometimes a Left-Right Rotation is defined as a Right-Rotation followed by a Left-Rotation.

Is there a reason for this different definitions? I think it is only a Exchange of the terms - but why?

# Answer
I would say they are just personal preferences without any particular naming rules or standard attached. Just as you said, it is only a exchange of the terms. There is negligible if any other difference.

The logical choice for me is also letting Left-Right Rotation be the Left-Rotation followed by a Right-Rotation.

However, a few people might prefer to recognize Left-Right Rotation as primarily a Left-Rotation (the larger rotation) with a Right-Rotation before it (as a delta operation). In this way, both Left-Rotation and Left-Right-Rotation moves the (larger) right subtree to the left.

In case you might think this is the whole story, here is more naming confusion and conflict. People may even differ on which tree rotation should be called Left-Rotation and which one should be called Right-Rotation! Not only with AVL trees, but possibly also with other kinds of binary search trees that use rotations to maintain balance. Here is an excerpt from the wikipedia item for tree rotation.

> In discrete mathematics, **tree rotation** is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations.
>
> There exists an inconsistency in different descriptions as to the definition of the direction of rotations. *Some say that the direction of rotation reflects the direction that a node is moving upon rotation (a left child rotating into its parent's location is a right rotation) while others say that the direction of rotation reflects which subtree is rotating (a left subtree rotating into its parent's location is a left rotation, the opposite of the former).* This article takes the approach of the directional movement of the rotating node.

So, should we take some action to make it more consistent? Probably not necessarily. As far as I have experienced and as far as I have checked\[1\]\[2\]\[3\]\[4\]\[5\], **the approach taken by Wikipedia, which calls the rotation in the counterclockwise direction left rotation and which calls the left rotation followed by right rotation left-right rotation is far more popular.** I will stick to that approach myself. I would recommend you stick to that approach, which you are comfortable with as well.
> 2 votes

---
Tags: data-structures, balanced-search-trees
---


# Question
Title: How pictures and videos are usually loaded in Memory?
Lets assume I'm talking about Jpeg and Mp4 and a general video player(not sure if different ones load it differently, if they do please tell)

So do video players (process) usually load the entire Jpeg or Mp4 including metadata into its own memory space right? like lets say we have a 1920x1080 picture with 10 bytes of metadata, does the picture viewer's process loads this into its own heap or maybe stack? and does it read it sequentially in order to display it?

I'm asking this because i want to know what stops criminals to for example inject some part of a video or picture with malware, lets say 10 malicious instructions are hidden in that file in a frame of a video or part of a picture, what stops the operating system with no good anti virus from executing these malicious instructions?

# Answer
> 2 votes
Just having malicious instructions loaded into memory is not a problem in itself. Instructions (code) is just binary, so it might be stored in the data segment.

Where it becomes a problem is if something causes that code to be executed. It's not clear why a video player would jump to data inside an image. If it had a security vulnerability, that could happen, but if it has a vulnerability, almost by definition bad things could happen, so that's not really saying much.

---
Tags: operating-systems, memory-management, virtual-memory, security, filesystems
---


# Question
Title: Does there exist a finite automaton for the given language?
The question is simple and given as, alphabet $A$ is $\\{a, b\\}$, and language $L$ over $A$:

$L = \\{w: w \in \\{a, b\\}^\*, n(a) - n(b) = 1 \mod 3\\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of $b$.

My answer is that it's not a regular language because the modular expression can be simplified as. $n(a) =n(b) +3k+1$ and hence there is a comparison in between the two alphabets. Further comparison are infinite but a finite automaton has only finite memory which are associated with states.

So we can say the above language is not regular hence no finite automaton for it. But there is a problem, I have read a book by Linz in which the above question was given stating that find the regular expression for it. I am a bit confused so any help will be appreciated. I would also be interested in a general approach to answer this type of question.

# Answer
Your reasoning about comparisons would be correct, if there were infinitely many numbers. But there's only three of them modulo $3$.

The automaton can be constructed directly. You need three states, one for each of the residues: $0$, $1$ and $2$. Then every $a$-transition should correspond to an increment and $b$-transition to a decrement.
> 1 votes

# Answer
As Dimitri has already said, the number of comparisons will only be 3. Consider the three states: q0 - where the n(a) - n(b) mod 3 = 0

q1 - where n(a) - n(b) mod 3 = 1

q2 - where n(a) -n(b) mode 3 = 2

Out of these q1 will be final state.

The DFA will be:

Note: If we get n(b) more than n(a). say n(a) is 0 and n(b) is 2, the automaton still works as -2 mod 3 is 1.
> 1 votes

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


# Question
Title: How does the problem of "Scheduling to Minimize Lateness" exhibit optimal substructure?
The problem of "Scheduling to Minimize Lateness" is as follows (Section 4.2 of the book "Algorithm Design" by Jon Kleinberg and Eva Tardos):

> ***Input:*** A finite set $J = {J\_1, J\_2, \ldots, J\_n}$ of $n$ jobs, their processing time $t\_1, t\_2, \ldots, t\_n$ and deadlines $d\_1, d\_2, \ldots, d\_n$. We assume that all jobs were available to start at the common start time $0$.
>
> ***Output:*** A schedule of these jobs to minimize their maximum lateness.
> Suppose a job $J\_i$ is scheduled at time $s\_i$, then its lateness is defined to be $l\_i = s\_i + t\_i - d\_i$ (it is $0$ if $s\_i + t\_i \le d\_i$.)

It is known that this problem can be solved by a greedy algorithm which schedules the jobs in the non-decreasing order of their deadlines.

---

I am confused about its optimal substructure property (not explicitly described in the book).

Let $L(s, S)$ be the optimal lateness obtainable from scheduling the jobs in $S$ which are available to start at the common start time $s$.

On the one hand, by enumerating over the possible first jobs to schedule, we get the following recurrence:

$$L(s, S) = \min\_{1 \le i \le n} \Big(\max\big(L(0, \\{J\_i\\}), L(t\_i, J \setminus \\{J\_i\\})\big)\Big).$$

*Intuitively*, this problem exhibits optimal substructure.

On the other hand, it seems that the problem does *not* exhibit optimal substructure with respect to the form of subproblems defined above.
To illustrate this, consider three jobs $J = \\{J\_1, J\_2, J\_3\\}$ with processing time $t\_1 = 6, t\_2 = 2, t\_3 = 2$ and deadlines $d\_1 = 2, d\_2 = 7, d\_3 = 8$. An optimal solution is to schedule $J\_1, J\_3, J\_2$ in that order, producing a maximum lateness of $4$. However, this optimal solution does *not* contain the optimal solution to the subproblem of scheduling $\\{J\_2, J\_3\\}$ given the common start time $t\_1 = 6$, which is $L(6, \\{J\_2, J\_3\\}) = 2$ by scheduling $J\_2, J\_3$ in that order.

This contradicts the "definition" of the optimal substructure property given in CLRS (Sections $15.3$ and $16.2$; 3rd edition):

> A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.

---

***Problem:*** How does the problem exhibit optimal substructure?

# Answer
Let us refine the "definition" of the optimal substructure property given in CLRS into two definitions.

> A problem exhibits **strongly** optimal substructure if **every** optimal solution to the problem contains optimal solutions to subproblems.
>
> A problem exhibits **weakly** optimal substructure if **there is at least one** optimal solution to the problem contains optimal solutions to subproblems.

What you see in the problem of "Interval Scheduling to Minimize Lateness" is the weakly optimal substructure. Take your example of three jobs $J=\\{J\_1, J\_2, J\_3\\}\\,$ with processing time $t\_1=6,t\_2=2,t\_3=2\ $ and deadlines $d\_1 = 2, d\_2 = 7, d\_3 = 8.\\,$ One optimal solution is to schedule $J1,J2,J3\\,$ in that order, which contains optimal solutions to all subproblems.

Weakly optimal substructure happens often when the goal of an optimization problem is not restricting enough to guarantee every optimal solution must contain optimal solutions to subproblems.

Here is a version of the interval scheduling problem that exhibits strongly optimal substructure. There are two changes in the problem statement compared to the previous one. What is to be minimized is their total lateness instead of their maximum latess. Also the lateness of a job is allowed to be negative. While this version of the problem is rather trivial to solve, it does serve to illustrate the concept of strongly optimal substructure.

> ***Input:*** A finite set $J= \\{J\_1, J\_2, \ldots, J\_n\\}\\,$ of $n$ jobs, their processing time $t\_1, t\_2, \ldots, t\_n$ and deadlines $d\_1, d\_2, \ldots, d\_n$. We assume that all jobs were available to start at the common start time $0$.
>
> ***Output:*** A schedule of these jobs to minimize their total lateness. Each job must continue processing once started. At any time, there can be at most one job that is being processed. Suppose a job $J\_i$ is scheduled at time $s\_i$, then its lateness is defined to be $l\_i = s\_i + t\_i - d\_i\\,$. The total lateness is the sum of all $l\_i$.
> 4 votes

---
Tags: algorithms, optimization, dynamic-programming, scheduling
---


# Question
Title: Understanding NFA (nondeterministic finite automaton) with a null transition
I'm reading Computer Science: An Interdisciplinary Approach. It mentioned an NFA (nondeterministic finite automaton) with a null transition, as shown above, recognizes all binary strings that do not contain `bba` as a substring.

I didn't quite understand why it says so. If the null transition happens before reading the `bba`, it stuck at state 2 and will report yes at the end?

# Answer
If a run of an automaton reaches a state where it has no legal transitions for the next input character, that run rejects immediately.

So, in your example, if the automaton makes the null transition, it can read $bb$ while staying in state $2$. But when it reads the $a$, it has no legal transition so that run rejects. Any run that stays in states $0$ and $1$ must also reject, because those two states are rejecting states. Therefore, the automaton does indeed reject all strings containing $bba$.
> 1 votes

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


# Question
Title: Complexity of Solving a System of Polynomial Equations
It can be easily seen that solving systems of polynomial (i.e. not necessarily linear) equations is NP-Hard via reduction from SAT. Furthermore, because the existential theory of the reals is decidable in PSPACE, solving systems of polynomial equations is as well. What else is known about the complexity of this problem? For example, I have been unable to determine if it is known to be $\exists R$-Complete, or PSPACE-Complete.

# Answer
Solving systems of polynomial equations over the reals is $\exists \mathbb R$-complete by definition, and it is a major open problem whether this complexity class equals PSPACE. See this.
> 3 votes

---
Tags: complexity-theory, logic, np-hard
---


# Question
Title: Trying to simplify a particular regular expression
The question is as follows

$$(a^\* (ba)^\* )^\* (b+\epsilon) = (a+b)^\* (b+\epsilon)\\,.$$

But I am unable to solve this regex expression. My answer is as follows:

\begin{alignat\*}{2} (a^\* + (ba)^\* )^\* ( b+\epsilon)\qquad &\text{(using property} (a^\* b^\*)^\* = (a^\*+b^\*)^\* = (a+b)^\*\text{)}\\ =(a+ ba)^\* ( b+\epsilon)\qquad &\text{(using the above again)} \end{alignat\*}

This is my final answer but it is not as stated on the right side of the proof. So can you tell where am I doing wrong? Is my proof correct?

# Answer
Assume the notations used in the question is the ones as described in the Wikipedia entry on regular expression for formal language theory. More specifically, it is the variant where "+" is used for alternation. (If you want to interpret the question in the notation used in common programming languages, please check the first version of this answer. Also note this updated answer renders the some comments below outdated. Thanks to the commenters!)

Suppose the task is to determine whether the following equality of regular expressions is correct, $$(a^\* (ba)^\* )^\* (b\text{+}\epsilon) = (a\text{+}b)^\* (b\text{+}\epsilon)$$ then the answer is NO.

Why? Let us consider word $bb$. The right side is, in fact, the set of all words over the alphabet $\\{a,b\\}$. In particular, the right side contains $bb$. Can the left side contains $bb$? If the first $b$ in $bb$ comes from the part $(b\text{+}\epsilon)$, then it must be the end of the word, but there is another $b$ following the first $b$. If the first $b$ comes from the part $(ba)$, then it must be followed by an $a$, which is not the case. Since the right side contains $bb$ but the left side does not, the equality cannot hold.

Now suppose the task is to simplify the left side of that incorrect equality, $$(a^\* (ba)^\* )^\* (b\text{+}\epsilon)$$ then a likely answer is, as given and proved by OP correctly, $$(a\text{+}ba)^\*(b+\epsilon)$$ The equality of these two regular expressions can also be understood easily by observing that the language is the set of all words over the alphabet $\\{a,b\\}$ that have no two consecutive $b$'s.
> 3 votes

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


# Question
Title: is a deterministic algorithm for breadth-first traversal possible (binary heap)
Imagine I have a binary heap, traversed in a breadth first manner like so:

```
                  0
       1          |           2
  3    |    4     |    5      |     6
7 | 8  |  9 | 10  |  11 | 12  |  13 | 14

```

To the left of root (0) is 1, to the right is 2, to the left of 1 is 3 to it's right is 4 etc.

So node 13 corresponds to the following pattern (right right, left, (or 0,0,1, perhaps)).

The question is, is there an equation, function, or algorithm that will produce the pattern to get to any node without actually producing the entire tree and traversing it?

Say I didn't create the tree in memory (it's just a virtual tree). How would I know that in order to get to 8 I need to start at root and go: left,left, right (1,1,0)?

Is this computable without creating the tree, and traversing it? If so what is the pattern for 42? is it easily calculable (is it linear) ?

I'm sorry for not knowing all the CS terms (I'm not a cs major, but I want to know if there's a deterministic algorithm to produce a path to any node, if so, whats it's computational efficiency) ?

# Answer
> 3 votes
Binary trees can have different structures. Every node can have at most two children. At most means you might have 2 children, you might have one child or no child. This leads to different structural possibilities for the binary tree.

There is no definite pattern to tell how to find a particular node. Closest you can get to a pattern is when you have a binary heap, but in a heap it is fix that the binary tree will be complete binary tree i.e. all the internal nodes will have two children and the leaf nodes at the last level will be as left as possible. For a heap you can determine the left child as $2\*i + 1$ and right child as $2\*i+2$ where $i$ is the index of node and $i = 0$ for root node.

In the worst case a binary tree can degenerate to a linked list which means you would have to proceed linearly to find the element you want. So, we can say how will the search of a node proceed totally depends on the structure of the binary tree.

To find a node basically traverse the tree with any of DFS or BFS.

# Answer
> 2 votes
As far as I have understood your question, you are looking for an algorithm that gives you the sequence of operation, given the number, if numbers arranged as you have mentioned. For example what will be operations to reach the number 42. If that's the case:

1. First thing to consider is whether the no. X is even or odd. If X Is even then last operation would be right Else last operation would be left.

E.g. 13 is odd so last operation from. Its parent will always be left. If it's an even no. e.g. say 8, The last operation is right. For 42 last operation should be right.
2. Next what will be X's parent? If X is even X/2 - 1 else (X-1)/2 For 42: parent = 20

Now you have got the parent, just check how to reach the parent by following step 1. Keep on doing till you get 0.

For 42 : 1 4 9 20 42 So : left right left right right

Complexity: How many times you can halve X to make it reach 0? What should be power of 2 to make it X? Ans : log X (base 2).

---
Tags: binary-trees
---


# Question
Title: is this language regular and why pumping lemma doesn't work?
I was told that this language is regular but as I can show below, pumping lemma is not working for it. What am I doing wrong? Is this language really regular? Why?

# Answer
Your use of the pumping lemma is incorrect. First, to show that the pumping lemma fails to hold in the case of your string $S$ (and thereby prove $L$ non-regular), you would have to show that *every* choice of $y$ fails. You've picked a specific $y$.

Second, $S'$ is in $L$. Simply take the whole $S'$ string as $b$ and let $a$ be empty. *Every* string of zeros and ones is in $L$ the same way, so $L = \\{0, 1\\}^\*$ and $L$ is regular.
> 6 votes

# Answer
It's a "trick" question. The language is regular because \begin{align\*} \\{aba^{\mathrm{R}}\mid a,b\in\\{0,1\\}^\*\\} &= \big\\{\varepsilon b\varepsilon^{\mathrm{R}}\mid b\in\\{0,1\\}^\*\big\\} \cup \big\\{a b a^{\mathrm{R}}\mid a\in\\{0,1\\}^+,\ b\in\\{0,1\\}^\*\big\\}\\ &= \\{0,1\\}^\* \cup \big\\{a b a^{\mathrm{R}}\mid a\in\\{0,1\\}^+,\ b\in\\{0,1\\}^\*\big\\}\\ &= \\{0,1\\}^\*\\,. \end{align\*}
> 8 votes

# Answer
Write the word $s'$ as

$$ s' = 0^{(p-\beta)} \left(1^p01^p0^{\beta} \right)0^{(p -\beta)} $$ to see that it is in fact in $L$.
> 6 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Karp hardness of digraph coloring without monochromatic dicycle
Problem statement:

> **Input**: a digraph $G(V, A)$ and a natural number $k$
>
> **Output**: **YES** if it is possible to color all vertices of $V(G)$ by $k$ colors such that no directed cycle is monochromatic, **NO** otherwise

Is this an $NP$-complete problem?

# Answer
Yes, it is NP-complete. There appears to be a straightforward reduction from graph coloring. If $G\_u$ is an undirected graph, define the directed graph $G\_d$ by replacing each undirected edge $(v,w)$ in $G\_u$ with two directed edges $(v,w)$ and $(w,v)$. Then $G\_u$ can be colored with $k$ colors iff $G\_d$ can be colored so that there is no monochromatic directed cycle.
> 1 votes

# Answer
Our problem is $\mathrm{NP}$-complete by a Karp reduction from $\mathrm{NAE}$-$\mathrm{3SAT}$

In fact, both the undirected and directed version are $\mathrm{NP}$-complete. First, we will describe the reduction for the undirected version. Then, we show how to orient all the edges of the undirected graph to obtain a digraph to finish the reduction for the directed version.

**REDUCTION FOR UNDIRECTED VERSION**

Given an instance of $\mathrm{NAE}$-$\mathrm{3SAT}$, we will construct an undirected graph such that there exists a solution for the $\mathrm{NAE}$-$\mathrm{3SAT}$ instance if and only if it is possible to color the vertices of this graph by $2$ colors such that no cycle is monochromatic.

For each clause $j$, create a $K\_3$ cycle each vertex of which corresponds to one literal of clause $j$.

Now, for each pair of opposite literals (one positive and one negative literal of the same variable) $l\_{jm}=x\_i$ and $l\_{kn}=\lnot x\_i$, we connect them by a gadget as follows. (Here, $l\_{ab}$ is literal $b$th of clause $a$, where $1\leq b\leq 3$)

The gadget to connect $l\_{jm}$ and $l\_{kn}$ is described now:

* Connect $l\_{jm}$ and $l\_{kn}$ by an edge
* Create $3$ new vertices $a$, $b$, $c$ (each gadget has its own three vertices like these)
* Connect these $3$ vertices $a$, $b$, $c$ to form a $K\_3$ cycle
* Connect each of $a$, $b$, $c$ with both $l\_{jm}$ and $l\_{kn}$

Call the obtained undirected graph $G$. Set $k=2$. The reduction returns the instance $(G,k)$ of our problem.

Now, we prove the correctness of our reduction (for the undirected version).

*If the given $\mathrm{NAE}$-$\mathrm{3SAT}$ is satiafiable*, then given a solution, one can color all the $\mathrm{TRUE}$ literal-vertices $\mathrm{RED}$ and all the $\mathrm{FALSE}$ literal-vertices $\mathrm{GREEN}$. For each gadget described above, we color $a$ and $b$ by $\mathrm{RED}$ and $c$ by $\mathrm{GREEN}$. Next, we show that this is a solution to the produced instance of our problem.

Clearly, we use only $k=2$ colors as required. For each $K\_3$ corresponding to one of the clauses, its $3$ vertices cannot be colored by the same color, because a solution to an $\mathrm{NAE}$-$\mathrm{3SAT}$ instance would make every clause containing both $\mathrm{TRUE}$ literal (colored $\mathrm{RED}$) and $\mathrm{FALSE}$ literal (colored $\mathrm{GREEN}$).

For each gadget of $2$ opposite literals $l\_{jm}$ and $l\_{kn}$, we have that these $2$ are colored by different colors. So, every cycle (contained in this gadget) that contains both these two vertices is already non-monochromatic. Only one other cycle (contained in this gadget) is the $K\_3$ of $a$, $b$ and $c$. But as mentioned above, $a$ is colored $\mathrm{RED}$ and $c$ is colored $\mathrm{GREEN}$. All other possible cycles in $G$ need to cross from a $K\_3$ clause to other $K\_3$ clause by passing through a gadget. But, to pass through a gadget of, say $l\_{jm}$ and $l\_{kn}$ (colored by different colors), such a cycle has to be non-monochromatic.

*Conversely, if we can color $G$'s vertices by $2$ colors without making any cycle monochromatic*, then we will now show that the given $\mathrm{NAE}$-$\mathrm{3SAT}$ instance is satiafiable.

For each literal-vertex $l\_{jm}=x\_i$, if $l\_{jm}$ is colored $\mathrm{RED}$, we assign $x\_i$ to $\mathrm{TRUE}$, otherwise assign it to $\mathrm{FALSE}$.

For each literal-vertex $l\_{jm}=\lnot x\_i$, if $l\_{jm}$ is colored $\mathrm{RED}$, we assign $x\_i$ to $\mathrm{FALSE}$, otherwise assign it to $\mathrm{TRUE}$.

Since each clause is a $K\_3$ cycle, it has to contain both $\mathrm{RED}$ literal-vertex (assigned to $\mathrm{TRUE}$) and $\mathrm{GREEN}$ literal-vertex (assigned to $\mathrm{FALSE}$).

It is left to prove the consistency of the above mentioned assignment. This is guaranteed by the gadgets. Suppose to the contrary that there exist two oppisite literals $l\_{jm}$ and $l\_{kn}$ colored by the same color, that w.l.o.g. we can assume to be $\mathrm{RED}$. Then it is impossible to properly color $a$, $b$ and $c$. Indeed, since $a$, $l\_{jm}$ and $l\_{kn}$ form a cycle, we deduce that $a$ must be colored $\mathrm{GREEN}$. Similarly, $b$ and $c$ are also colored $\mathrm{GREEN}$. But, now the cycle $(a,b,c)$ is monochromatic. Thus, the above assignment is consistent. And we obtain a solution to the given $\mathrm{NAE}$-$\mathrm{3SAT}$.

**REDUCTION FOR DIRECTED VERSION**

We use exactly the same above reduction. Now, we have to orient all the edges of $G$ to obtain a digraph. For each, $K\_3$ clause cycle, we are free to choose one of two ways to turn it into a directed cycle (dicycle). For each gadget of two opposite literals $l\_{jm}$ and $l\_{kn}$, we can orient to have an arc $(l\_{jm},l\_{kn})$ (the other way can be finished similarly). Now, we orient to make $3$ cycles: $(l\_{jm},l\_{kn},a)$, $(l\_{jm},l\_{kn},b)$, $(l\_{jm},l\_{kn},c)$. Then, we make one more cycle, namely $(a,b,c)$. By orienting like this, we can use all the above arguments for the undirected version. Note that the possible dicycles that cross from clause to clause still have to be non-monochromatic.
> 1 votes

---
Tags: np-complete, np-hard, np
---


# Question
Title: $L$ is a context free language so prefix$(L)$ is also a context free language
In case $L$ is context free language. $L\_1 \setminus L\_2 = \\{x\in \Sigma ^\* : \exists y\in L\_2$ s.t $xy\in L\_1 \\}$ when $L\_2$ is regular, is a context free language, thus using $L\_1 = L$ ,$L\_2 = \Sigma ^\*$ one conclude that prefix$(L)$ is context free. However I wish to build a grammar for prefix$(L)$. My attempt so far was as follow: $L$ has a Chomsky's normal form grammar, $(N,T,S,P)$ so I defined the grammar $(N\cup N' , T, S, P\cup P')$ when $N' = \\{A' : A\in A\\}$ ,$P' = P\cup \\{A\rightarrow BC' : A\rightarrow BC \in P \\} \cup \\{A' \rightarrow t : t\in T, A\rightarrow t \in P\\} \cup \\{A' \rightarrow \varepsilon\\} $ my idea was that the non-tagged terms will be fully producted as in the usual grammar and the tagged terms might product a terminal or an $\varepsilon$. Yet I didn't succeed to prove it's a correct grammar for prefix$(L)$.

# Answer
> 2 votes
Let $G$ be a Chomsky's normal form grammar for $L$. So $G = (N,T,S,P)$ when $P\subseteq\\{A\rightarrow BC , A\rightarrow a : A,B,C \in N , a\in T \\}$. We will defined $G'$ as follows: $G'= (N\cup N'\cup \bar{S} ,T,\bar{S},P')$ when:

* $N' = \\{A' : A\in N\\} $
* $P' = P\cup\\{\bar{S} \rightarrow S' | \varepsilon \\} \cup \\{A'\rightarrow BC'|B' : A\rightarrow BC \in P\\} \cup \\{A'\rightarrow a|\varepsilon : A \rightarrow a \in P\\}$

Observation - let $A \in N$ we define $L(A) = \\{w\in T^\* : A\Rightarrow^{\*}\_G w \\}$, So, in $G'$ , $A'\Rightarrow^{\*}\_{G'} w\in prefix(L(A))$.

* proof, by induction over production steps:

+ $A'\rightarrow^1w\in T^\* \Rightarrow w \in \\{a,\varepsilon\\}$ due to $P'$ definition. So in $G$ ,$A\rightarrow a$ thus $\\{a,\varepsilon\\} \in prefix(L(A))$.
    + assumption - $\forall A'\in N'$, $A'\Rightarrow^{k \<n}w\in prefix(L(A)) $
    + $A'\Rightarrow^n w\in T^\*$, so $A'\rightarrow^1 \gamma\Rightarrow^{n-1} w$, thus $\gamma \in \\{BC' , B'\\}$: In case $\gamma = B'$ then $B'\Rightarrow^{n-1} w\in prefix(L(B))$ and $A'\rightarrow B' \Rightarrow A\rightarrow BC \in P$ then $prefix(L(B)) \subseteq prefix(L(A))$. If $\gamma = BC'$, $B$ products $w\_1 \in prefix(L(A))$ because $A\rightarrow BC \in P$, and $BC \Rightarrow^\* w\_1w\_2\in L$ when $B \Rightarrow^\* w\_1 , C\Rightarrow^\*w\_2$, and $C'$ products $w\_{2}' \in prefix(L(B))$ from the assumption. Thus $A' \Rightarrow w\_1w\_2'$ which is a prefix of $w\_1w\_2 \in L(A)$.

$L(G') \subseteq prefix(L)$:

* $\bar{S} \rightarrow^1 \varepsilon$ , $\varepsilon \in prefix(L)$.
* $\bar{S} \Rightarrow ^n w\in T^\* \setminus \\{\varepsilon\\}$ , so $\bar{S}\rightarrow S'\Rightarrow ^{n-1}w$ now, using the first observation we made $S' \Rightarrow^\* w\in prefix(S) = prefix(L)$.

So $\bar{S} \Rightarrow^\* w\in T^\*$ means $w\in prefix(L)$.

$prefix(L) \subseteq L(G')$:

Observation : in case $A\Rightarrow^\* w\in T^\*$, then $A' \Rightarrow^\* w' \in prefix(w)$ for all $w'\in prefix(w)$.

proof by induction over $w$'s length:

* $A\rightarrow a$ $\Rightarrow$ $A' \rightarrow a$ and $A'\rightarrow \varepsilon$, due to $P'$ definition, when $prefix(a) = \\{a,\varepsilon\\}$.
* $A\Rightarrow^\* w, |w|=n$, so $A\rightarrow BC \Rightarrow^\* w\_1w\_2 =w$ when $B \Rightarrow^\* w\_1 ,C \Rightarrow^\* w\_2$ (from $P$'s definition in chomsky's form). For $w'\in prefix(w)$:

+ in case $w' \in prefix(w\_1)$, then $B'\Rightarrow^\* w'$ from the induction assumption ($|w'|\<n$, and the assumption stands for every $A'\in N'$ ). So $A'\rightarrow B' \Rightarrow^\* w'$ as wanted.
    + in case $w' = w\_1w\_2'$ when $w\_2'\in prefix(w\_2)$ the same arguments holds for $c' \Rightarrow^\* w\_2'$, thus $A'\rightarrow BC' \Rightarrow^\*w\_1w\_2'$.

For $w \in prefix(L)$:

* in case $w = \varepsilon $ , $\bar{S} \rightarrow \varepsilon$.
* otherwise $\exists z\in T^\*$ such that $wz \in L$, so $S\Rightarrow\_G^{\*} wz$ and by the observation we made $S'\Rightarrow^\* w'\in prefix(wz)$ for all $w'\in prefix(wz)$ and particularly $w$ it self. So $\bar{S} \rightarrow S'\Rightarrow ^\* w$. Thus $w\in L(G)$

---
Tags: context-free
---


# Question
Title: how to find a node that is known to everyone but doesn't know anyone?
Problem I am trying to solve is this:

There are n nodes, and for every pair of node $X$ and $Y$, the relation "$X \space knows \space Y$" is either $T$ or $F$. It is possible that "$X \space knows \space Y$" but "$Y \space doesn't \space know \space X$".

We are trying to find if a special node exists: that is known to everyone but doesn't know anyone. How can you find out if such node exists by using only this type of query: For any nodes $X$ and $Y$, ask $X$ "$if \space X \space knows \space Y$". This query can be asked unlimited amount of times, but the total number of queries should be $O(n)$. I can think of $O(n^2)$ case but how to do it with $O(n)$ queries? Thanks!

# Answer
> 1 votes
This can be done with the help of an auxiliary stack and elimination technique. Let us call the node we are looking for the `special node`. We can make certain conclusions by examining the relation of any two nodes as following :

1. If node A knows node B, then A is surely not the `special node` and B may be the `special node`.
2. If node A doesn't know node B, then B is surely not `special node` and A may be the `special node`.
3. We repeat above two steps till we are left with only one node.
4. Examine the last node if it doesn't know anyone and is known to everyone.

**Algorithm: (uses auxiliary stack)**

1. Push all the nodes on the stack.
2. Pop off top two nodes from the stack, discard one node based on the observations made.
3. Push the remained node onto stack.
4. Repeat step 2 and 3 until only one node remains in the stack.
5. Check the remained node is the one we are looking for.

Why do we need the last step?

Because we have examined all the nodes relative to only one node which is adjacent to it on the stack but we don't know its relation with other nodes. So we need to ensure that the potential candidate for the `special node` is actually the `special node`.

This will require $3(n-1)$ comparisons in total. So the complexity is $O(n)$.

---
Tags: algorithms, graphs
---


# Question
Title: Why do we set conditions f(n) ≥ n resp. f(n) ≥ log(n) the Time resp. Space Hierarchy?
In the Space (Time) Hierarchy Theorem and also fully space (time) constructibility of two function we have the condition: being greater than $log(n)$ (being greater than $n$).

Why do we have these conditions?

# Answer
A concise answer would be: To have enough time (resp. space) to do the diagonalization jobs.

Remember that both of these separation results are just using diagonalization techniques. In particular, to separate bigger time/space bound apart smaller time/space bound, one use the bigger bound (by just ONE machine) to diagonalize over all the possible smaller time/space-bounded machines.

And to do that, one needs to know when to finish (on each input) in case of time hierarchy, or where to prohibit the crossing (on each input) in case of space hirachy. This is possible only when the bigger bound is constructible. For time, constructibility at least requires $\geq n$. For space, constructibility at least requires $\geq log(n)$.

---

For full constructibility, it is not necessary to require any thing. But note that while constant functions are fully constructible (in time and space), functions in between like $log log(n)$, $log log log(n)$ (for space), $\sqrt{(n)}$, $n^{2/3}$ (for time) are not so. *Informally*, the *spectrum* of **full constructibility** is not *continuous*.

Lastly, one can even separate the notions of time constructibility by reasonable conjectures.
> 2 votes

---
Tags: complexity-theory, time-complexity, complexity-classes, space-complexity
---


title: Maximum trailing zeros of the path

text:
# Question
Title: Maximum trailing zeros of the path
Problems:

A table with $n$ rows and $m$ columns is filled with number from $1$ to $100$ (duplication allowed). The player starts at $(1, 1)$. He can only move right or down. The goal is to reach $(n, m)$. Let $S$ be the product of numbers the player has met along the way to $(n, m)$. Find maximum number of trailing zeros of $S$ if the player moves optimally.

What I think about this problem is to use Dynamic Programming. $S$ is equal to $2^x\times5^y\times other\ primes$ so the answer should be $min(x, y)$ but finding maximum $x$ or $y$ is not optimal. $min(x, y)$ instead should be maximized. Please help with this problem.

# Answer
> 1 votes
For each cell $(i,j)$, store the set of possible pairs $(x,y)$'s.

Now, DP by scanning row-major from top row to bottom row, for each cell $(i,j)$, only needs to consider $(i,j-1)$ and $(i-1,j)$ (if any), either choose or not to choose $(i,j)$. So from the stored set in $(i,j-1)$ and $(i-1,j)$, compute $(i,j)$'s set easily.

Try to finish the above idea in details. And then code it in your favorite programming language will quickly improve your DPing skill.

---
Tags: dynamic-programming, number-theory
---


# Question
Title: Why some Huffman codes have efficiency better than others?
Consider the alphabet $\mathcal{A}=\\{a\_0,a\_1,a\_2,a\_3\\}$ with the the following corresponding probabilities:

1. $\\, p\_{A,1}=\\{0.5,0.3,0.15,0.05\\}$
2. $\\, p\_{A,2}=\\{0.5,0.25,0.125,0.125\\}$

The entropy for the first case is $H(A,1)= 1.65$, and for the second is $H(A,2)=1.75$. The Huffman code for both can be $\\{0, 10, 110, 111 \\}$ or $\\{1, 01, 001, 000 \\}$. The average lengths are $\bar{L\_{A,1}}=1.7$ and $\bar{L\_{A,2}}=1.75$. The efficiencies are $97.14 \\%$ and $100 \\%$ for case $1$ and $2$ respectively. Why is that? The only reasonable explanation is the probabilities themselves. In the second case, it is somehow equally divided. Can anyone explain?

# Answer
> 1 votes
First off, though the codes you gave are what the Huffman coding process produces, they aren't the only possible prefix codes for those two cases of sources.

For example, imagine if you used the code $\\{\texttt{00}, \texttt{01}, \texttt{10}, \texttt{11}\\}$ \- then the average length is $2$ and the efficiencies drop to $82.5\\%$ (case 1) and $87.5\\%$ (case 2).

What the Huffman coding process guarantees is the most efficient prefix code *possible for a given source*, not a perfectly efficient code for every source.

So your question really is "why is it possible with some sources to make 100% efficient Huffman codes, and with other sources the most efficient possible Huffman code is less than 100% efficient?"

The answer there is that if you have a perfectly efficient Huffman code, then it's impossible to tell the difference between a stream of (source -\> Huffman code) and a stream of uniformly random $\texttt{0}$s and $\texttt{1}$s. In your case number 2, with the first Huffman code, you have that situation: a stream of the source encoded by the Huffman code begins with $\texttt{0}$ half the time, and with $\texttt{1}$ half the time. When it starts with $\texttt{0}$, you start a new character from the source and so the next digit naturally is also evenly distributed. When it starts with $\texttt{1}$, half the time the next digit is $\texttt{0}$, half the time $\texttt{1}$, etc. This property (that after any sequence of bits, the chance of the next bit being $\texttt{0}$ or $\texttt{1}$ is $\frac{1}{2}$) means that the resulting binary stream has an entropy of 1 bit of entropy per output bit. (The same as a random binary source)

However, in case 1, (again using the first Huffman code) after seeing a $\texttt{1}$ in the stream, you're more likely to see a $\texttt{0}$ than a $\texttt{1}$. This means that the binary stream you get by connecting your source to the Huffman code has an entropy of less than 1 bit of entropy per output bit. (and therefore, that the binary stream is carrying less information per output bit than a random binary source)

The perfect match in case 2 happens because the probabilities of the source are all (negative) powers of $2$ and the probability of each output symbol matches the probability that a uniformly random noise source would output the symbol's Huffman string. Basically, the maximum possible efficiency for a Huffman code is a measure of how well a source's output probabilities can be approximated in binary.

Note that if we took your case 1 source and considered outputs two at a time, we'd be able to better approximate the probabilities in binary, and therefore get a more efficient Huffman code:

$$ \begin{array}{|c|l|l|} \hline \mathrm{output}& p & \mathrm{Huffman}\\,\mathrm{code} \\ \hline a\_0a\_0 & 0.25 & \texttt{10} \\ \hline a\_0a\_1 & 0.15 & \texttt{000} \\ \hline a\_0a\_2 & 0.075 & \texttt{0100} \\ \hline a\_0a\_3 & 0.025 & \texttt{01110} \\ \hline a\_1a\_0 & 0.15 & \texttt{001} \\ \hline a\_1a\_1 & 0.09 & \texttt{110} \\ \hline a\_1a\_2 & 0.045 & \texttt{1110} \\ \hline a\_1a\_3 & 0.015 & \texttt{011010} \\ \hline a\_2a\_0 & 0.075 & \texttt{0101} \\ \hline a\_2a\_1 & 0.045 & \texttt{1111} \\ \hline a\_2a\_2 & 0.0225 & \texttt{011000} \\ \hline a\_2a\_3 & 0.0075 & \texttt{0110011} \\ \hline a\_3a\_0 & 0.025 & \texttt{01111} \\ \hline a\_3a\_1 & 0.015 & \texttt{011011} \\ \hline a\_3a\_2 & 0.0075 & \texttt{01100100} \\ \hline a\_3a\_3 & 0.0025 & \texttt{01100101} \\ \hline \end{array} $$

This has an average code length of $3.3275$, whereas the double-output source has an entropy of $3.30$ for an efficiency of $99.04\\%$.

If you continued this process to 3 symbols at a time, you'd be able to get a $99.24\\%$ efficient code. To 4 symbols, $99.43\\%$ efficient.

---
Tags: huffman-coding
---


title: Matrix to Multi-level security

text:
# Question
Title: Matrix to Multi-level security
How to convert access control matrix to Bell-LaPadula. Can teach me step by step What best way to control converting Bell-LaPadula Model lattice using Access Control Matrix

Matrix GIVEN

$\quad\quad\quad\quad$`O1 O2 O3 O4
 S1 w r w rw
 S2 rw r
 S3 w w r
 S4 w w w r
 S5 rw rw r`

convert to BLP lattice diagram

# Answer
> 0 votes
Subject S2 has read-write access to Object 1, which is something no other subject has. On the other hand, subject S2 has no rights to Objects 2 and 3, which is something no other subject has. So Subject S2 has incomparable rights to all other subjects.

Similarly S1 is incomparable to the others.

S4 clearly has more rights than S3. S5 clearly has more rights than S3.

So the subjects' "security levels" can be shown like this:

$\\,\\,\\,$`S5 S4
 \ / S1 S2
 S3`

(I don't know this subject before your question so this is just my impression. This subject has been discussed in three questions at cs.stackexchange.com in the past.)

---
Tags: security
---


title: Is Countable set always countable?

text:
# Question
Title: Is Countable set always countable?
Why some sets are countable and some are not countable? Say regular set are countable but how (0+1)\* will be countable? It is an infinite string, then how it could be a countable set? How the set of all non-decreasing functions from N to N are countable? How the set of all finite partitions of N are uncountable?

# Answer
As said the question completely belongs to mathematical sector , specifically to discrete mathematics but in my opinion information has no bounds , so does the question

coming to your question ,its indeed an application of discrete mathematics in theory of automata ,so here is your answer. loosely speaking that countability of has little to no relation with being a set is finite or infinite. first thing , if a set is countable then the only condition associated of being it countable is that the cardinality the set ( total number of elements in set) should be lower or equal to that of natural number of positive integers. To simplify it more we can assign a unique natural number to all the elements of the set (please bear that although you may argue that the the list will go to infinte but as said in that infinite list we will have one-to-one correspondence on natural number to that of the elements of set. loosely speaking the condition of being countable is more of a theoritical aspect )

Now if the set is finite then off course its cardinality (number of elements in set) will be less than that of natural numbers, because we can assign a unique natural number which are equal to number of element of the given . The definition of countable set for infinite set may get tricky,but it could be understood . i will take the example of language given by the regex ( 0+1) \*. firstly the set of strings in language L =( 0+1) * are infinite which makes the set an infinite set. now apply the definition of being countable set we get that the language is indeed countable reason being we could have a unique list in which each element of the language is assign a unique natural number , however the list is infinitely long but this does not mean we have not assigned a unique natural number to elements of set. so yeah the language is counatble.

Now you may say that this could be done to all infinite set ,making all infinite set counatble, but actually this is not true. for your sake take one more example , this being the countability of set of real numbers. well you cannot assign a number to each real number reason being say you are numbering all the real number between 0 and 1, you will always find a real number which you have not numbered , say you have numbered like 1= 0.01,2 = 0.011, and so on but you missed 0.001 , now suppose you assigned a number to it also say, 3=0.001, well you lost many more numbers which being say ,0.0001,0.000001....and so on, so you will not able to list all the numbers hence the set is uncountable.

for just sake of clarity you can try a question like power set of language L and if you reach the conclusion that power set of language L= (0+1)\* is uncountable then you have got what is countable and uncountable set.
> 1 votes

---
Tags: automata
---


# Question
Title: Karp hardness of a guarding set in digraph
Our problem is to decide whether a digraph has a *guarding set* of size at most $k$. Definitions are following.

A digraph $G(V,A)$ has $V(G)$ as its vertex set and $A(G)$ as its arc set. A guarding set $S\subseteq V(G)$ is a set of vertices such that:

> For each vertex $v\in V(G)$, some of its incoming neighbor $u$ (i.e. $(u,v)\in A(G)$) is included in $S$ (i.e. $u\in S$) and some of its outgoing neighbor $w$ (i.e. $(v,w)\in A(G)$) is included in $S$ (i.e. $w\in S$)
>
> In case of empty incoming neighborhood or empty outgoing neighborhood, the vertex $v$ itself must be included in $S$. In other word, we may think that the incoming neighborhood and outgoing neighborhood of $v$ both include $v$.

Informally, imagine a facility in which one can enter at some entry points and exit at some exit points, a guarding set for this facility needs to be placed at least at some entry point (maybe where one can enter secret area of the facility) and at some exit point (maybe where one can bring out the secrets from the secret areas inside). Hope that this suffices to explain the terminology.

Our problem is now formally defined:

> **Input**: A digraph $G(V,A)$ and a natural number $k$
>
> **Output**: **YES** if $G$ has a guarding set of size $k$, otherwise **NO**

What is complexity of this problem?

# Answer
> 1 votes
It is NP-complete (it is obviously in NP) by reduction from the dominating set problem.

Given an instance $G=(V,E)$ of the dominating set problem, split each vertex $v$ into two vertices $v\_{\mathrm{in}}$ and $v\_{\mathrm{out}}$, and for each edge $(u,v)\in E$, construct two edges $(u\_{\mathrm{out}},v\_{\mathrm{in}})$ and $(v\_{\mathrm{out}},u\_{\mathrm{in}})$. We claim that $G$ has a dominating set of size $k$ iff the newly-constructed graph (say $G'$) has a guarding set of size $2k$.

If $G$ has a dominating set $S$ of size $k$, easy to see $\\{v\_{\mathrm{in}}\mid v\in S\\}\cup\\{v\_{\mathrm{out}}\mid v\in S\\}$ is a guarding set of $G'$, which has size $2k$.

On the other hand, suppose $G'$ has a guarding set $S'$ of size $2k$. Let $S'\_{\mathrm{in}}=S'\cap\\{v\_{\mathrm{in}}| v\in V\\}$ and $S'\_{\mathrm{out}}=S'\cap\\{v\_{\mathrm{out}}\mid v\in V\\}$, then either $S'\_{\mathrm{in}}$ or $S'\_{\mathrm{out}}$ must has size at most $k$. Without loss of generality, say $\left|S'\_{\mathrm{in}}\right|\le k$, then $S=\left\\{v\mid v\_{\mathrm{in}}\in S\_{\mathrm{in}}'\right\\}$ is a dominating set of $G$. This means $G$ has a dominating set of size $k$.

---
Tags: complexity-theory, graphs, np-complete, np-hard, np
---


# Question
Title: How to find $L_q = \emptyset$, a state that is not reachable for any given string?
In the book Introduction to Languages and the Theory of Computation, I'm reading section 2.6 on how to minimize the number of states in an FA.

I'm having trouble understanding a notation defined as $L\_q$. Here's what the book says:

> Suppose we have a finite automaton $M = (Q, \Sigma, q\_0, A, \delta)$ accepting $L \subseteq \Sigma^\*$. For a state $q$ of $M$, we have introduced the notation $L\_q$ to denote the set of strings that cause $M$ to be in state $q$:
>
> $$L\_q = \\{ x \in \Sigma^\* | \delta^\*(q\_0, x) = q\\}$$.
>
> The first step in reducing the number of states of M as much as possible is to eliminate every state $q$ for which $L\_q$ = $\emptyset$, along with transitions from these states. None of these states is reachable from the initial state, and eliminating them does not change the language accepted by $M$.

I tried looking at this automaton to try to understand this definition:

How can any of the states $1$ through $5$ be $L\_q = \emptyset$ if I can find a string that can reach every state for this FA?

That is I can reach state $2$ with string $a$, and state $5$ with string $ab$, etc. Is this a correct way to approach this?

# Answer
You're right. There is no such state with $L\_q = \emptyset$

The first step in the minimization algorithm is: "delete all nonreachable states".
> 5 votes

# Answer
one more thing you can add is that , a state having $L = \emptyset$ cannot be reached from start state with any transition. hence if a state exists without being reached by start state then the language associated with that state is $\emptyset$ . further during dfa unless not specified for minimization such state does not exists
> 0 votes

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


# Question
Title: SAT for positive CNF clauses with exactly half of the variables being true
I am focusing here on *positive even SAT* problems, that is a CNF for which all literals are positive, and in which an even number *n* of variables occur. This is obviously trivial : just set all variables to true and all clauses are satisfied. The same if we look for an assignment that would have all but one variables being true (unless the problem is 1-SAT, which is also trivial)

But I am wondering if we could find an algorithm that searches for some solution (or proves the absence of solutions) with exactly half of the variables being true, the other half being false. Have you an idea of how to create this algorithm ? And what could be its complexity ?

# Answer
Your problem is NP-complete by the modern presentation of Schaefer's dichotomy theorem.

You can also prove its NP-completeness by direct reduction of SAT to your problem. If a CNF formula has $n$ variables $x\_1 \dots x\_n$ introduce $n$ new variables $y\_1 \dots y\_n$ and add 2-CNF clauses that force each $y$ variable to have the opposite value of the corresponding $x$ value. I.e. $$(x\_1 \lor y\_1)$$ $$(\lnot x\_1 \lor \lnot y\_1)$$ $$(x\_2 \lor y\_2)$$ $$(\lnot x\_2 \lor \lnot y\_2)$$ $$\dots$$ $$(x\_n \lor y\_n)$$ $$(\lnot x\_n \lor \lnot y\_n)$$

All solutions to the resulting formula will have half the variables with true values and half false.

For unaltered formulas, you don't need a special algorithm to find half-true half-false solutions. Take any CNF formula with an even number of variables and then add CNF clauses encoding a chain of adder circuits that sums the values of all the variables. Next, add a comparison circuit that is only satisfied if the sum is one-half the total number of variables. Run a normal SAT solver on the result and it will output only solutions where one-half the original variables have a true value. This is a somewhat naive solution but it gets the job done.

Search the literature a bit more and you will discover SAT solvers that accept pseudo-Boolean constraints in addition to CNF. With these you can write out the $x\_1 + x\_2 + x\_3 + \dots + x\_n = n / 2$ equation explicitly and the solver will either churn out the adder circuits for you or just handle the equation internally.

Your special SAT problem is also readily transformed into a 0-1 integer programming problem for which there are solvers available.
> 1 votes

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


# Question
Title: How does modulus affect the regularity of language?
the question is as follows, further the notation used are standard as used in theory of computation $$L = \big\\{ w : w \in \\{a,b\\}^\*,\ |n(a) - n(b)| = 2k\\}\\,.$$

Beware 'K' is not a fixed integer its a set of natural number , so 2k means all natural nunbers divisible by 2 and so on for 3k , 4k... .I think the above language is irregular or its finite automata can't be formed. Firstly the above question in basic language can be thought of as modulus of difference of number of $a$ and number of $b$ is divisible by $2$ or is even , similar to this reasoning we can extend this to more general like $3k$, $4k$, $5k$,... and so on. Secondly we know that any condition which have comprise the difference between the symbols would have infinite possible comparison between symbols, like an equation of $n(a) - n(b) =0/1/2/3...$ needs infinite states of finite automata which makes them irregular.

But here with the use of modulus it seems no different as here also we will need many comparison between symbols.

Thirdly its more of a general question like when define regularity of language $L$ over condition like, $n(a) - n(b)\bmod 3 =0$, we say the all strings can be classified as having either remainder $0$,$1$,$2$ which by using Myhill-Nerode theorem proves the language regular. But why cant we use the same analogy over the relation like $n(a) -n(b)=2$ saying the all the strings would either have a difference $2$ or not. Further if you could answer the regularity of $n(a)- n(b) = 2k$, also how does taking modulus effect its regularity and how does it makes the states of finite automata finite which before applying modulus were infinite if you could a graphical representation would be appreciated.

# Answer
> 3 votes
You seem to be assuming that, to determine whether $n(a)-n(b)$ is a multiple of $m$ requires us to computer $n(a)$ and $n(b)$, subtract them, and then calculate the remainder. You're correct that a finite automaton can't do that, but it's not the only way.

The first thing to note is that you can computer $n(a)-n(b)$ directly. Initially, you've seen no $a$s or $b$s so the difference is zero. Each time you see an $a$, the difference increases by one; each time you see a $b$, the difference decreases by one. OK, that's a bit smarter but it still requires us to compute the value $n(a)-n(b)$, which could still be arbitrarily big, so still can't be done with a finite automaton.

The second thing to note is that, because of the way that modular arithmetic works, $$(x-y)\bmod m = ((x\bmod m) - (y\bmod m)) \bmod m\\,.$$ In other words, you can do everything modulo $m$. Each time you read an $a$, the difference increases by one *modulo $m$*. and each time you read a $b$, it decreases by one *modulo $m$*.

This means that you can recognize the language with an automaton with $m$ states: one for each value of $n(a)-n(b)\bmod m$.

# Answer
> 2 votes
For the given language $|n(a) - n(b)|$ will be even only if either $n(a)$ and $n(b)$ are both odd or both even.

In any case the total no. of symbols should be even.

So we have two states: q0 : where the total no. of symbols is even (accepted state)

q1: where the total no. of symbols is odd.

In general: $|n(a) - n(b)| = mk\ $ for some $k\ge0$ if and only if $n(a)\mod(m) = n(b)\mod(m),$ i.e. both number of 'a's and number of 'b's have same remainder when divided by $m$.

now difference between $n(a)\mod(m)$ and $n(b)\mod(m)$ can be $0, 1, 2, 3, 4, \cdots, m-1$.

So there will be $m$ states, each representing the difference : $n(a) - n(b) \mod(m)$. The state diagram will be something like:

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


# Question
Title: Different iterations of regular expressions
A four-part question dealing with formal languages and regular expressions:

1. How many *basic* regular expressions (using only the rules **0**/ϵ, **1**/∅, \*, +, and •) are there to match a given string?
2. How many using just \*, +, and •?
3. How many using just + and •?
4. How many using just •?

# Answer
First, note that, over any finite alphabet, there are countably infinitely many regular expressions. This is immediate from the fact that regular expressions are finite strings (which gives the upper bound) and that $a$, $aa$, $aaa$, ... are all regular expressions (which gives the lower bound). From now on, I'm just going to say "infinite" instead of "countably infinite" because we've established that nothing in this context is uncountable.

If you're allowed to use $\varepsilon$, there are infinitely many regular expressions that match $abcd$: for example, $abcd\epsilon^n$ for all $n\geq 0$.

If you're allowed to use alternation, there are infinitely many: for example, $abcd$, $(a+a)bcd$, $(a+a+a)bcd$, ... .

If you want regular expressions that match only the string $abcd$, Kleene star isn't useful. If it's applied to any regexp that matches any non-empty string, then the resulting regexp will match strings of arbitrary length, so will be invalid. If it's applied only to regexps that are equivalent to $\varepsilon$ then we could have already used those regexps to get infinitely many regexps for $abcd$, as in the $\varepsilon$ case. The only remaining case is that $\emptyset^\*\equiv\varepsilon$, so Kleene star and $\emptyset$ together yield infinitely many regexps for $abcd$. However, this case isn't relevant in your case structure, since you eliminate $\varepsilon$ and $\emptyset$ from consideration at the same time.

If you're only allowed concatenation, then there is exactly one regular expression that matches $abcd$: $abcd$ itself.
> 0 votes

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


# Question
Title: Why the universal Turing machine simulation in O(TlogT) cannot be applied to transform multi-taped Turing machine into single-taped?
Recently, I've read Hennie's Paper. I understood the construction of buffer zones, but why can't it be applied to yield a single-taped Turing machine?

# Answer
Just because that UTM itself requires $2$ tapes to do its task that efficient. Removing one tape, the magic is gone.

But assuming you have the fantasy power to do efficient $1$-tape simulation, what gains do we have then?

That should be the question rather than your question.
> 2 votes

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


# Question
Title: Big-O with nested loops and "variables" in the T(n)
So, I need to find the T(n) and then Big-O (tight upper bound) for the following piece of code:

```
int sum = 0;
for(int i = 1; i < n; i *= 2) {
    for(int j = n; j > 0; j /= 2) {
        for(int k = j; k < n; k += 2) {
            sum += i + j * k;
        }
    }
}

```

Now from what I calculated for the loops, **first loop runs log(n) times**, **second loop runs (log(n) * log(n)) times** and the third loop is the one which is causing confusion, because I believe it runs for **(n - j)/2 times**. My question is can I **assume it to be n/2 times**, because I think it won't be a tight upper bound if I do that. Or is there a different approach that I am missing?

# Answer
> 0 votes
One common way to arrive at a tight big-$O$ upper bound of the complexity of an algorithm is to estimate one. Then prove that estimate works.

Let me take your computation by nested loops as an example.

---

In this post $\log(x)$ means $\log\_2(x)$. The first loop runs $\lceil\log(n)\rceil$ iterations. For each iteration in the first loop, the second loop runs $\lfloor\log(n)\rfloor+1$ iterations. For each iteration in the second loop, the third loop runs $\lfloor(n - j+1)/2\rfloor$ iterations, where $j\>0$ is the loop variable of the second loop. Ignoring the floor function, the addition by the constant 1, the subtraction by $j$, the division by the constant 2 and the constant number of operations executed by each iteration in the third loop, I will estimate the upper bound of the number of total operations as $O(\log(n)\log(n)\\,n)$.

Is that $O(n\log^2n)$ a tight upper bound of the the number of total operations $T(n)$? Yes, it is indeed.

---

Firstly, let us show it is an upper bound. We can assume $n\>2$. Let $c\_3$ be the number of operations executed by each iteration of the third loop. $$ T(n) \le (\lceil\log(n)\rceil) (\lfloor\log(n)\rfloor+1)(n/2)c\_3\\ \le (2\log(n))(2\log(n))(n/2)c\_3\\ \le (2c\_3)n\log^2n $$

Now let us show it is tight. Let us do not count the first iteration of the the second loop. That is, let us only consider the operation done by the second loop starting from $j=\lfloor n/2\rfloor$. Then for each iteration in the second loop, the third loop runs $⌊(n−j+1)/2⌋ \ge n/2-1$ iterations. Then for $n\ge6$, $$ T(n) \ge (\lceil\log(n)\rceil) (\lfloor\log(n)\rfloor)(n/2-1)c\_3\\ \ge (\log(n))(\log(n)/2)(n/3)c\_3\\ \ge (c\_3/6)n\log^2n\\ $$

So we have proved from the ground up.

---

The above proof, although rigorous and clear, is not the usual way to reason about the big-$O$ because it is so exact as to require too much thinking. That is almost the kind of computation needed to get the exact asymptotic approximation. Here is a simpler version assuming you are familiar with the big-$\Theta$ notations.

The first loop run $\Theta(\log(n)$ iterations. For each iteration in the first loop, the second loop runs $\Theta(\log(n)$ iterations. For all but the first iteration in the second loop, the third loop runs between $n/2$ to $n$ iterations, which is $\Theta(n)$ iterations. In the first iteration of the second loop, the third loop runs no iteration. So $$T(n)=\Theta(\log(n)(\Theta(\log(n)-1)\Theta(n)=\Theta(\log(n))\Theta(\log(n))\Theta(n)=\Theta(n\log^2(n))$$ which implies $O(n\log^2n)$ is the tight upper bound.

---

By the way, in all computations above we are not counting the operations to maintains the indice $i,j,k$. That is ignored by convention, because they will not change our approximation in big $O$-notations unless in extraordinary situations. Or because in many situations we are only interested in the number of the "real" operations.

The reasoning about the big-$O$ notations can be an art or a precise process. On the one hand, you can be very "sloppy" when you are trying to get an estimate and even when you are reasoning. That is because you can hide or absorb constant factors into the notations. That way you can arrive at a possible answer very quickly. With practice and experience, you can be certain immediately most of the times once you got an estimate. On the other hand, you can also verify every part of the "sloppy" process by rigorous mathematical deduction or by applying a set of valid shortcut rules. In the end, we will arrive at a precise conclusion using the big-$O$ notations.

---
Tags: time-complexity, asymptotics
---


title: Transitive reduction of DAG

text:
# Question
Title: Transitive reduction of DAG
I am looking for O(V+E) algorithm for finding the transitive reduction given a DAG.

That is remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still reach after removal of edges.

If this is a standard problem, please point me to some model solution.

# Answer
> 12 votes
We can solve this problem just by doing DFS from each vertex.

1. For each vertex $u \in G$, start the DFS from each vertex $v$ such that $v$ is the direct descendant of $u$, ie. $(u,v)$ is an edge.
2. For each vertex $v'$ reachable by the DFS from $v$, remove the edge $(u, v')$.

The overall complexity of the above is the complexity of running $N$ DFS', which is $O(N(N+M))$.

# Answer
> 3 votes
Not what you are looking for. But just for the purpose sharing knowledge, you can do that with $O(|E|)$ *messages* if you assume that each vertex to act as a *processor*. Note each vertex has a comparable value. Therefore, there exists some vertices such that they are larger than all their neighbors. These vertices do the following:

1. Let $u$ be the maximum smaller neighbor of $v$,
2. send a message to $u$ and include edge $(v,u)$ in the output.
3. For every neighbor $w$ of $u$ and $v$ (and smaller than both), do not include $(v,w)$ in the output.
4. Repeat the steps until all edge $(v,v')$ for a smaller neighbor $v'$ of vertex $v$ is either included or not included in the output.

Now if a node $v$ received a message from every larger neighbor (i.e. all the edges $(v',v)$ are either included or not included, then node $v$ acts as if it was the largest in its neighborhood. That is, it performs the previously mentioned 4 steps.

This algorithm terminates in $O(|E|)$ *messages* in a distributed environment. I know this is not what you are asking for.

# Answer
> 1 votes
**Lemma:** If there is an edge V -\> Y and Y is also an *indirect* successor of V, (e.g., V -\> W -\>+ Y) then the edge V -\> Y is transitive and not part of the transitive root.

**Method:** Keep track of the transitive closure of each vertex, working from terminal to initial vertices in reverse topological order. The set of indirect successors of V is the union of the transitive closures of the immediate successors of V. The transitive closure of V is the union of its indirect successors and its immediate successors.

**Algorithm:**

```
    Initialise Visited as the empty set.
    For each vertex V of G,
        Invoke Visit(V).

    Visit(V):
        If V is not in Visited,
            Add V to Visited,
            Initialise Indirect as the empty set,
            For each edge V -> W in G,
                Invoke Visit(W),
                Add Closure(W) to Indirect.
            Set Closure(V) to Indirect.
            For each edge V -> W in G,
                Add W to Closure(V),
                If W is in the set Indirect,
                    Delete the edge V -> W from G.

```

This assumes that you have some efficient way of keeping track of sets of vertices (e.g., bit maps), but I think this assumption is made in other **O**(V+E) algorithms too.

A potentially useful side-effect is that it finds the transitive closure of each vertex of G.

# Answer
> 0 votes
I solved the same problem but it was not exactly the same.It asked for the minimum no of edges in the graph after reduction such that the vertices originally connected are still connected and no new connections are made. **As it is clear, it doesn't say to find the reduced graph but how many redundant edges are present.** This problem can be solved in O(V+E). The link to explanation is https://codeforces.com/blog/entry/56326. But I think to make the graph actually, it will have high complexity than O(N)

---
Tags: algorithms, graphs, dag
---


# Question
Title: Are there any more complex problems than the Totality Problem that appear in the practical world?
We know the Halting Problem is in the 1st level of arithmetical hierarchy. We know that the Totality Problem is in the 2nd level of arithmetical hierarchy. What are some examples of problems in the 3rd (or higher) level of arithmetical hierarchy. +1 for problems which instances are solved in the practical world (programmers, mathematicians, etc.).

# Answer
> 4 votes
Let $\\{W\_e\\}\_{e\in\mathbb N}$ be a canonical list of the recursively enumerable, i.e., computably enumerable, i.e., Turing recognizable, languages (or sets).

The property that $W\_e$ is actually recursive, i.e., computable, is $\Sigma^0\_3$: $$\exists d\forall n(n\in W\_e\leftrightarrow n\not\in W\_d).$$

It is at the 3rd level of the hierarchy: it is not of lower complexity than $\Sigma^0\_3$. See e.g. Soare: Recursively enumerable sets and degrees, Theorem 3.4, for the proof.

---
Tags: computability, reference-request
---


# Question
Title: Big O Notation Simplification in the fraction form
How should I approach this one a(n) = $\frac{n^3}{log^{3}(n)}$. As We can tell that $n^3$ grow much faster than $log^{3}(3)$. All of sudden, not sure what to do, found this \[post\]\[1\], which is also in the fraction form, Do we calculate out $\frac{n^3}{log^{3}(n)}$ or just pick $n^3$. Eventually, the accurate number is not needed, but I somehow understand what it can simplify to and compare with other Big O, such as \begin{equation} 2^{n^{0.008}} \end{equation} Any hint is appreciated

Sorry for my first typo while using LaTex it is \begin{equation} 2^{n^{0.008}} \end{equation} instead of $(2^{n})^{0.0008}$

# Answer
> 2 votes
It is indeed confusing if you are expecting some kind of simpler form.

However, **${n^3}/{\log^{3}n}$ is already in the simplest form** in term of big-$\Theta$ notation. Consequently, it is also sort of the best form in term of big-$\Omega$ notation or big-$O$ notation. It is certainly true that $n^3/\log^3n = O(n^3)$. However, that kind of big-$O$ bound are usually frowned upon since it is obviously not tight, $n^3/\log^3n = o(n^3)$. In fact, in a similar vein, many time-complexities is described by $\Theta(n\log n)$, $O(n\log n)$ or $\Omega(n\log n)$, where the factor $\log n$ cannot be or is not removed.

The point is that although you can ignore the asymptotically insignificant terms in a sum to arrive at a simpler big-$O$ (or big-$\Theta$, big-$\Omega$) bound, you cannot do away with any unbounded factors without losing significant asymptotical information. For example, it is correct that $n^3+\log^{3}n=O(n^3)$ or $n^3+\log^{3}n=\Omega(n^3)$ or $n^3+\log^{3}n=\Theta(n^3)$, but neither $n^3/\log^{3}n=\Omega(n^3)$ nor $n^3\log^{3}n=O(n^3)$ is correct.

If you want to compare $n^3/\log^3n$ with $(2^{n})^{0.008}$, you can proceed as the following. $$\text{Since } n^3/\log^3n = O(n^3) \text { and } n^3=o((2^{0.008})^n), \text{ so } n^3/\log^3n =o((2^{0.008})^n)$$ where the second equality comes from the fact $2^{0.008}\>1$ and the fact that any polynomial function grows slower than any increasing exponential function, which is proven in another answer of mine. Please note that I am using the little $o$-notation, which means basically "asymptotically growing slower than".

If you want to compare $n^3/\log^3n$ with $2^{n^{0.008}}$, you can proceed as the following. $$\text{Since } n^3/\log^3n = O(n^3) \text { and } n^3=2^{3\log\_2n} = o\left(2^{(n^{0.008})}\right), \text{ so } n^3/\log^3n =o\left(2^{n^{0.008}}\right)$$ where the second equality comes from the fact $\log\_2n=o(n^{0.008})$, which is also proven in that answer of mine since $\log\_2n=(\log\_2e)\log n$.

You can check the reference question and answers on sorting functions for good advices and more detailed and systematic treatment.

---
Tags: asymptotics
---


title: What is an infinite language?

text:
# Question
Title: What is an infinite language?
I just started reading about formal language theory and what i have learnt so far that:

**Alphabet** is a finite set of symbols.

**String/Word:** is always finite.

Because a language is set of strings of symbols and per definition alphabet and strings both are finite then how can a language be infinite?

I searched a lot but did not find any explaination so i am asking this question here, any help would be great for me.

# Answer
Every individual string is finite, but there are infinitely many different ones. For example, $0$, $00$, $000$, $0000$, ... .
> 1 votes

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


# Question
Title: If a language is contained in other langauge, is it of the same complexity?
If some language $L$ is in **P**, and some other language $K$ is contained in $L$, does that mean that $K$ is also in **P**?

Thanks :)

# Answer
No. $\Sigma^\*\in\mathbf{P}$ and every langauge is a subset of that – even undecidable ones.
> 6 votes

---
Tags: turing-machines, computability, complexity-classes
---