# Question
Title: Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?
Dijkstra's algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$.

> If both source $s$ and destination $t$ are fixed, can we compute the shortest path from $s$ to $t$ **without** computing distances for all other nodes from $s$?

More fundamentally,

> Is single-source single-destination shortest path problem easier (e.g., in terms of worst-case time complexity) than its single-source all-destination counterpart?

# Answer
Nope. In order to find the distance from $s$ to $t$ it is necessary to determine the length of all paths that are at least at the same distance as $t$ is. If $t$ has a "median" distance half of the distances will be known that way.

In certain application areas (with an exponentially sized "implicit" state space) it can still be worthwhile to start searching from both sides and look for nodes that are found in the middle.
> 5 votes

# Answer
I found some comments on the problem in this video lecture on Algorithms (by MIT; from 17min:45sec $\sim$ 18min:30sec), as transcribed as follows:

> It turns out, this is one of the wired things about shortest paths, according to the-state of-the-art we know today, it seems to be the best algorithm for solving the $A$ to $B$ problem (given $s$, given $t$, go from $s$ to $t$) is no easier than this problem (going from $s$ to all vertices).
>
> The best way we know how to solve going from $A$ to $B$ is to solve how to go from $A$ to everywhere else.

Therefore, it seems to be still a hard research-level problem.
> 0 votes

---
Tags: algorithms, complexity-theory, graphs, reference-request, shortest-path
---


# Question
Title: Prove that the complements of pumping-style languages are context-free
> Define $L = L(u,v,x,y,z) = \\{uv^ixy^iz : i \geq 0\\}$, with $u,v,x,y,z \in \Sigma^\*$. Prove that $\overline{L}$ is a CFL for all $u, v, x, y, z$

Clearly, $L$ is a CFL, as it is generated by the grammar:

$S \longrightarrow uAz$

$A \longrightarrow vAy$

$A \longrightarrow x$

I am struggling with this problem, because I don't see how I'd go about constructing a PDA or CFG for $\overline{L}$. The fact that L "looks like" the main condition of the pumping lemma for CFLs must somehow relate, but I am not seeing the connection. Maybe I could do something with morphisms?

# Answer
> 3 votes
The first thing to ask is, why is the claim even true? CFLs, in general, are not closed under compliment, but this language certainly does (yet, it is not regular, so cosure for $\Sigma^\*\setminus L$ cannot be used here). So why is the complement a CFL?

The reason is that the language $L$ is actually *deterministic context-free*, and this class have different closure properties, specifically, it is closed under complementation.

To prove $L$ is a DCFL, we need to build a deterministic PDA for it. There are some technicalities for the case when $v=x$ or $x=y$ or $v=x=y$, but just to give the idea of the construction, let's assume they are all different, $u\ne v\ne x\ne y\ne z$. Since $x,y,u,v,z$ are fixed, it is easy to construct a Deterministic PDA for $L$: it tries to match the input to $u$ (and rejects if it can't), if it finds $u$ it continues to match the input to $v$ at least once (and count the number of times it succeeds, using the stack), the first time it fails, it assumes the input has gotten into the $x$ part, and from there checking the $xy^iz$ part is obvious.

If you reverse the accept/reject of the DPDA of $L$ you will receive a DPDA for $\overline L$, thus also $\overline L$ is deterministic CFL, and specifically, it is a CFL.

# Answer
> 2 votes
Both Ran and Yuval indicate that we obtain a CFL, but that we have to take care of technicalities. In particular that we have to check the relation between the different strings $u,v,x,y,z$. After some pondering I think that we can argue without special cases, working with a grammar rather than a PDA.

Let us define "blocks", these are strings of a certain length, without predefined content. Let $U,V,X,Y,Z$ be blocks of length $|u|,|v|,|x|,|y|,|z|$, respectively.

If a string cannot be divided into blocks $UV^iXY^iZ$, i.e., its length is not of the form $|uxz|+i|vy|$, it belongs to the complement. That is a regular language.

All other strings can be derived by your initial grammar, in "block form". $S\to UAZ$, $A\to VAY$, $A\to X$. Now force the grammar to make at least one mistake. By this I mean at one point it generates block $U$ which is not equal to $u$, or block $u$ which is not equal to $v$, etc.

# Answer
> 0 votes
One way to solve this is to consider the language $$ L' = \overline{L} \setminus \overline{uv^\*xy^\*z}. $$ For "generic" $v,x,y$, it will be the case that $$ L' = \\{ uv^ixy^{i+j}z, uv^{i+j}xy^iz : i \geq 0, j \geq 1 \\}, $$ and we're done. However, this expression for $L'$ is invalid, for example, when $v=x=y$. Nevertheless, this approach probably works after you handle the "atypical" cases. (Since this expression is valid when $=$ is replaced by $\subseteq$, it is enough to determine for which $i,j$ the words $uv^ixy^{i+j}z,uv^{i+j}xy^j$ are in $L$.)

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


title: Is $a^n b^n c^n$ context-free?

text:
# Question
Title: Is $a^n b^n c^n$ context-free?
I am new to grammars and I want to learn context free grammars which are the base of programming languages. After solving some problems, I encountered the language

$$\\{a^nb^nc^n\mid n\geq 1\\}\\,.$$

Can anybody tell me if this is a context free language? I can't make any context free grammar for it and I don't know any other proof.

# Answer
This is my approach to prove that a given language is not a CFL.

Try hard to come up with a Context free grammar for the given language. If you can come up with such a grammar, then the language is indeed a CFL.

If you can't, then you can use the pumping lemma to show that a given language is not a CFL.

Assume L is context free. Then L satisfies P.L. Then there exists n by the P.L. Let z = a^n b^n c^n Because |z|\>=n and z in L, by PL there exist uvwxy s.t.

```
   z = uvwxy
   |vwx| <= n
   |vx| >= 1
   forall i>=0, u v^i w x^i y in L

```

But if there exist u,v,w,x,y satisfying the first three constraints, we can show that there exists an i s.t. the fourth constraint fails.

Case uvw consists only of "a". Then when i=0, the string is not in L (fewer "a"s than "b"s or "c"s).

Case vwx contains only "b"s - similar.

Case vwx contains only "c"s - similar.

Case vwx contains only two types of characters from {a,b,c}. Then uwy has more of the remaining type of characters.

The string vw cannot contain "a"s, "b"s, and "c"s, since vwx is a substring of z and has length \<=n (cannot contain the last "a" and the first "c" both).i.e this is a contradiction and our assumption is wrong that L is CFL.
> 2 votes

# Answer
You are asking two different questions. First, is $\\{a^nb^nc^n : n \geq 1 \\}$ a context-free grammar? Second, is $\\{a^nb^nc^n : n \geq 1 \\}$ a context-free language?

The answer to the first question is *No*, since $\\{a^nb^nc^n : n \geq 1 \\}$ is not a grammar, let alone a context-free grammar; it is a language. What you probably meant to ask was: "Does $\\{a^nb^nc^n : n \geq 1 \\}$ have a context-free grammar?", which is the same as the second question.

The answer to the second question is also *No*. In fact, it is one of the standard examples of non-context-free languages, and as such most textbooks will have proofs to that effect.
> 3 votes

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


# Question
Title: Are if statements unnecessary if a program is represented as an explicit state machine?
This question occurred to me some time ago when I was thinking about whether or not `if` statements are fundamental in computation.

Consider a program that manages a single bank account (for the sake of simplicity). The bank account could be defined as something like

```
Account
{
    int balance; // current amount of Money

    boolean withdraw(int n)
    {
       if (balance >= n)
       {
           balance = balance -n;
           return true;
       }
       else
           return false;
    }

    void deposit(int n)
    {
       amount = amount + n;
    }
}

```

Since the program has no way to known in which state it currently is unless it performs validations using `if` statements, as in the withdraw operation, `if` statements are unavoidable.

However, over the course of time, the program will pass through a finite set of states that can be known beforehand. In this particular case, a state is defined solely by the value of the `balance` variable, hence we would have states: `{balance = 0 , balance = 1, balance = 2...}`.

If we assign each state a number, say state {0,1,2,....} with a 1-1 correspondence to the above set of states, and assign to each operation a number identifier as well (say `deposit = 0 and withdraw = 1`), we could model the program as an explicit transition between states and therefore remove every `if` statement from the code.

Consider that `state = 0` is the state where `balance = 0` and we want to perform a deposit of 50 dollars, if we coded every single possible execution of the deposit function, we could just define the deposit function as

```
void deposit (int n)
{
   deposit[state][n]; // índex deposit instance for state = 0, amount = n;
}

```

`deposit[][]` would be a matrix of pointers for a set of functions that represent each possible execution of deposit, like

```
deposit[0][0] -> balance = balance + 0; state = 0;
deposit[0][1] -> balance = balance + 1; state = 1;

....

```

In the case of withdrawal, it would be like:

```
boolean withdraw (int n)
{
    // índex withdraw instance for the current state and amount=n
    return withdraw[state][n];
}

```

`withdraw[][]` would be a matrix of pointers for a set of functions that represent each possible execution of withdraw, like:

```
deposit[0][100] -> return false; state = state;
...
deposit[200][100] -> balance = balance - 100; return true; state = 100;

```

In this situation, the program the managers the single bank account can be written without using a single `if` statement!

As a consequence however, we have to use A LOT more memory, which may make the solution unreasonable. Also one may put the question of how did we fill the `deposit[][]` and `withdraw[][]` matrices? By hand? It somehow implies that a previous computation that used `if`s as necessary to determine and possible states and transitions.

All in all, are `if`s fundamental or does my example prove that they aren't? If they are, can you provide me an example where this does not work? If they are not, why dont we use solutions like these more often?

Is there some law of computation which states that `if` statements are unavoidable?

# Answer
Literal `if` statements are not fundamental. As you've shown, it's possible to remove them by writing your program as a state machine, though at the gigantic cost of having to have a different version of the `widthdraw()` function for every possible starting balance and withdrawal amount. You can also avoid literal `if` statements by replacing

```
if (condition) {
    foo
} else {
    bar
}

```

with

```
b1 := condition
b2 := not(b1)
while (b1) {
    foo
    b1 := false
}
while (b2) {
    bar
    b2 := false
}

```

On the other hand, doing so has no clear advantages and many disadvantages. The gigantic-table-of-functions approach leads to huge redundancy, is very hard to maintain and is very hard for compilers and CPUs to optimize. If you're lucky, the `while` loop hack might compile to the same code as the simple code with `if` statements but it's much harder to read and much more prone to programmers mistakenly thinking they can optimize it.

At a fundamental level, some form of conditional execution is necessary. If you have no kind of conditional statement at all, then you can only perform a class of very limited programs called "straight-line programs". These are, perhaps surprisingly, useful as a model of computation because they have a fairly simple correspondence with circuits: they correspond to the simplest notion of algorithm, i.e., take your input data and perform a fixed sequence of operations on it. For example, when you compute the length of a 2D vector, you're using a straight-line program: square the $x$-coordinate, square the $y$-coordinate, add the two squares, take the square root (at least, assuming that all those arithmetic operations, including square root, are taken as being built in to your langauge).
> 4 votes

# Answer
Your construction seems a bit tautological. The if statement is itself a form or branching through an array of two addresses, depending on a value that is 0 or 1. Actually, the if statement generalizes to the case statement, which may be implemented as branching through an array. Whether the array is code or static data is immaterial and pretty much in the eyes of the beholder.

Another way to state this is that **your program could be simulated by a Turing machine, which does not have any if statement, and could thus be a positive answer to your question**.

Indeed, a Turing machine should be as good an answer as any other state machine. Compared to a FSA, the only difference is that it can read and write on an infinite tape.

So, if you do not accept the Turing machine as an answer, I wonder whether your problem is not more with eliminating this infinite memory tape, at the expense of replacing it with an infinite program (TM states and transitions).

Then, I am afraid you may just fall into something similar to a Turing Tar Pit, or much worse (a Turing hell?).

The main point is that the technique you are proposing will require your program to have an infinite size, if it is to be equivalent to the original program, using infinite matrices, i.e. really an infinite number of states.

You might not worrry about it, considering that we already work as if we could use unbounded integer in memory. That is true, but we use integer in a very precise way, that is finitely described. As a consequence, it is perfectly possible to mimic computation with arbitrary long integer, and it is actually done in some systems.

One fundamental principle of computer science (and I would add mathematics, but that has to be made precise) is that everything must be finitely definable.

To make any sense, your infinite program would similarly have to follow a finite specification, where your if statement would be back, or the TM with its infinite tape.

If you forget this constraint, then you drastically change the domain of discourse, as you get a continuous (rather than denumerable) infinity of different programs. You are no longer talking of computability with its accepted meaning, and its physical realizability. Actually, I suspect that you can then no longer consider a concept that would ressemble computability (but that is a somewhat fuzzy statement).
> 2 votes

# Answer
On a processor, the if-else statement is ultimately a conditional branching instruction, where the execution address is generated on the basis of some comparison to get to a decision.

On hardware (like on an FPGA) however, if-else is (for example) done using a multiplexer/demultiplexer where the 'condition' is done through the state of the 'select' inputs. In this case, the logic for which branching logic is burned onto hardware, where there's no need for a "next address" generator.

If I understand correctly, your question is whether branching on-the-fly is "fundamental" to computing, or whether it can be circumvented by other ways.

I would say that, yes it is fundamental to computing. On the FPGA, the branch states are usually finite at the level of one mux/demux, therefore, there's no physical analogue to branching. On a processor, however, given the practical limits on memory, condition branching is a fundamental operation.
> 2 votes

# Answer
In a way, if statements are unavoidable at some stage, unless you write things "by hand", but in that case, it is not at all clear that you don't preform branching operations in your brain, so let's leave that aside.

Consider a program P in assembler (to have a low common ground). In assembler, the only branching operation is "if x\>0 goto l1, else goto l2"

So assume you have a program without those. Then, you can define for every line $l$ in the code, a unique line $l'$ that always follows $l$ in the execution. Thus, the program either gets to exit and terminates within $n$ commands ($n$ being the number of lines) or it runs forever.

From this, we learn that if you want to describe a big system, but you want to describe it without branching, then you will need to write it more or less explicitly. If you use branching, you can get things exponentially more efficient.

Also, your question is related to the concept of symbolic representation and symbolic algorithms which can affect the succinctness of representation.
> 0 votes

# Answer
*This is really answering Devian Dover's last question on this theme: **Where does the need for conditionals (if, switch, jump tables, etc…) truly arise?** Since that last question was closed as duplicate to the one I am answering here, I guess it is OK to answer it here. This answer is thus quite different from my previous one here, since the two questions are related rather than duplicates.*

Hoopje's answer shows that Lambda Calculus can create conditionals out of its elementary constructs. Whether they are actually more elementary than conditional is a subjective matter. If you Had a `while` loop plus `exit` statement, that would also let you do conditionals, though a `while` loop may be seen as more complex than a conditional.

Another example is the Post Correspondence Problem (PCP). It can simulate a Turing machine, though it does not even have a concept of execution or evaluation to start with, let alone a conditional.

To take a more amusing example, you can build Turing Machines with Lego bricks, but there is no Lego brick that identifies as an `if` statement.

What you are really asking is an ontological question, and such questions often have only subjective answers. What organization there is to the world is largely made up by your own individual or collective subjective reconstruction of world order. The fact that the universe is organized and structured is not to be denied, but the expression of this structure by laws, the concepts we may put forward as fundamental, may vary without actually changing the structures described.

To formulate it in a more formal way, different systems of axioms could characterize a given unique set of possible interpretations.

You are asking:

> My point is, where do conditionals come from? Where do they stop? Can we avoid them somehow? Can you prove me we need them? If we do, why do we put them at the hardware level? Why does the input of a program have to be compared against values to determine the branch to execute?

So my answer to your quest, rather than your question, is that conditional are one convenient way to express some algorithm is some formalization of what a computation may be. They stop where you choose to make them stop. We can avoid them, and many other concepts, since computation and algorithms can be expressed by totally different means. We do not need them: they happen to be, when we want to look at them, but we can proceed by other means when we do not (want to) see them. We do not have to put them at the hardware level since we do not have to have them at all. We do not have to compare input to anything since computation can be express by other means.

A very negative answer. The point is that the use of conditionals corresponds to a specific model of computation, essentially the von Neumann machine, that has been considered convenient as a fundamental set of concepts to represent computation in physical devices. In a sense, it is pure expediency. It is just one way, among many others, to see the structure and order of the computational world, one that we find easy enough to deal with, and for which we can produce physical simulators (called computers) that are not too expensive to produce or to use.

Conditionals are just one of many way we have to apprehend and express assessment of change or diversity.
> 0 votes

---
Tags: programming-languages, computation-models
---


# Question
Title: Asymptotic runtime for querying an interval tree
Suppose that we have an array of size `n` and we want to build an interval tree for all possible ranges that can be created inside this array. So in our leafs we have the ranges `[0], [1], [2], [3], ... , [n]`, and merging two of them together we end up having the root node holding the range `[0, n]`. For example we have the following interval tree for an array of size 6.

The total amount of nodes is `O(n)`.

I'm trying to understand what's the maximum posible `root - internal node` paths that we need to make in order to answer a query on any range. I know that the total amount of nodes that we are going to visit for any query is in the order of `log n` but I can't see why, which is the reason why I'm asking this question.

For example in the picture above, for the query `[1, 4]` we will do the following visits:

`[0,5] => [0,2] => [0,1] => [1] => [0,1] => [0,2] => [2] => [0,2] => [0,5] => [3,5] => [3,4] => [3,5] = > [0,5] => end`

We have to travel from the root to some other internal node 3 times in total.

Now let's see a different example:

If our query is `[1, 8]` we will have to do 4 root to some other internal node paths, so this doesn't look constant to me, it was 3 before, now it's 4.

So I can't understand why querying in an interval tree is `O(log n)`.

How can you formally prove that querying is indeed `O(log n)`, ie the amount of nodes that your algorithm must visit in order to answer any query is in the order of `log n`?

# Answer
Querying an interval tree is $O(\log n + m)$, where $n$ is the size of the tree and $m$ is the size of the output. This explains your confusion. Note that there is a trivial $\Omega(m)$ lower bound.

Unfortunately I couldn't find an online proof of this bound, and since there are many variants of interval trees and many different queries, it's best if you tried to prove it yourself for your type of interval tree and query.
> 0 votes

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


# Question
Title: Computing the closest match of an automaton and a string
I have a problem where I'm trying to find an efficient algorithm for approximate string matching for an input to the closest string match from an automaton (the input is assumed to be not accepting for the automaton). I've looked around and found Levenshtein Automaton but had trouble finding out how it would be implemented from my automaton.

Also, are there any other methods that would be suitable/worth looking at for my problem?

# Answer
> 2 votes
You can adopt the usual dynamic program to compute the Levenshtein distance between a word $w$ and a regular language $L$ computed by some given NFA without $\epsilon$ transitions. Suppose $w$ has length $n$. For each $0 \leq \ell \leq n$ and state $s$ of the NFA, we will compute $A(\ell,s)$ which is the minimum Levenshtein distance between the $\ell$th prefix of $w$ and a word that causes the NFA to reach state $s$. This quantity is given by the following calculation, involving an auxiliary array $A'$:

1. $A(0,s)$ is the length of the shortest path from the initial state of the NFA to $s$ \[insertion\].
2. $A'(\ell+1,s)$ is the minimum of the following quantities:

* $A(\ell,t)$ if there is a transition from $t$ to $s$ marked $w\_{\ell+1}$.
    * $A(\ell,t)+1$ if there is some transition from $t$ to $s$ \[substitution\].
    * $A(\ell,s)+1$ \[deletion\].
3. $A(\ell+1,s)$ is the minimum of $A'(\ell+1,t)+\kappa(s,t)$ over all $t$, where $\kappa(s,t)$ is the length of the shortest path from $t$ to $s$ in the NFA \[insertion\].

Finally, the distance is the minimum of $A(n,s)$ taken across all accepting states $s$.

This calculation requires that you compute in preprocessing the all-pairs-shortest-path matrix for the directed graph underlying the NFA. Some of the quantities arising in the computation could be infinite.

# Answer
> 2 votes
I am assuming that you mean finite-state automaton (FSA) when you say *automaton*. Actually, this can work for other automata, notably for Push-Down Automata (PDA) and is a nice way to do syntax-error recovery in programming languages compilers. But string matching is usually defined with regular expressions.

The answer to your question is called Levenshtein distance and Viterbi selection. The Levenshtein automata, as defined in wikipedia, will not directly help you, but they are close to the idea. The point is that you actually have 3 automata in this problem, and there are different ways to combine them depending on what you want to achieve.

Here is a hopefully intuitive explanation.

I call $R$ the FSA that is supposed to do the string matching.

Levenshtein distance (or edit distance) to a word in $\mathcal L(R)$ can be computed non-deterministically by a weighted non-deterministic FSA (NFA) $R\_L$ that is doing the following. It has the same number of states as $R$, and all the transitions of $R$ with weight 0. Then for every transition in $R$ labeled with input symbol $a$ it has an $\epsilon$-transition between the same state, with a weight corresponding to the cost of a missing $a$ in the input. For every state $q$, and every input symbol $a$, $q$ has an $a$-transition to itself with a weight corresponding to the cost of an extra $a$ in the input string. Finally, for any pair of transitions $\delta(q,a)=q'$ and $\delta(q,b)=q''$ in $R$, add two transitions $\delta(q,b)=q'$ and $\delta(q,a)=q''$, weighted respectively by the cost of replacing $a$ by $b$, and replacing $b$ by $a$.

A computation of $R\_L$ can recognize any word an give a distance for that word to some word to be matched in $\mathcal L(R)$. It could at the same time output the corrected word that has been approximated.

This does not help you very much, because what you want is a word with the least cost.

So you have to simulate all possible non-deterministic computations, each with its distance counter (and its corrected string), so as to keep the best answers. Here, dynamic programming is your friend as any prefix of a least cost computation is a least cost computation.

If your weighted NFA $R\_L$ has $n$ states, there are only $n$ different states you may be in after reading some prefix $w$ of the input. Since you are only interested in the closest match, you keep only for each state the minimum value of the counter for all computations on $w$ that lead to that state. That is only $n$ state-counter pairs to keep, and from which to do a transition at each reading step.

But what you are computing is only the edit distance, and you may want a bit more than that: the string of the language your input is actually approximating. This again is easy: add to each counter value the corrected input string corresponding to that computational path.

So you keep triples, adding to each pair one of the corrected strings that corresponds to a computation leading to that state-weight pair.

When the input has been scanned and all non-scanning transitions followed, the string associated with accepting states are some of the strings most closely approximated by the input. However, since they may not have the same cost, you want to keep only those with minimum cost. You get only some as you keep only one string with each state. But it is possible to keep them all.

So that is the general idea. Note that the algorithms for measuring the distance for two strings, suggested by Alu's answer is just a special case of this when the FSA recognizes only a singleton set, a single word.

Now this can be obtained more simply by using classical cross product of finite state automata. The idea is that the errors that you wish to accept and correct, with cost, can be formalized by a weighted finite state transducer (or GSM) $T$. Then the automaton you want is obtained by a cross product construction between your initial automaton $R$ and your transducer $T$.

The advantage of this formalization is that it defines easily many different kinds of distances. corresponding to errors that you are willing to accept, such as $a$ can replace $b$ only when following a $c$, with cost $k$. But complex error systems are costly to compute with because of the cross-product that increases the number of states.

I do not have much time right now for details, but I may be adding it later.

# Answer
> -1 votes
The levenshtein distance is what you want. It calculates the diference between two strings. It counts the characteroperations to transform the one string into the other.

For Example:

```
test and taste:
replace 'e' with 'a'    -> +1
then add a trailing 'e' -> +1

```

-\> The levenshtein distance is 2

You can find implementations in many languages here

---
Tags: automata, strings, string-metrics
---


# Question
Title: Selection type generated by nested loops where initial value is current value of parent loop
Consider the generator of the selections:

```
for (i1 = 0;  i1 < 10; i1++)
    for (i2 = i1; i2 < 10; i2++)
        for (i3 = i2; i3 < 10; i3++)
            for (i4 = i3; i4 < 10; i4++)
                printf("%d%d%d%d", i1, i2, i3, i4);

```

Result:

```
0000
0001
0002
...
0009
0011 <-- 0010 is skipped
0012
...
0019
0022 <-- 0020 and 0021 are skipped
0023
...
8999
9999

```

Generated selections have the following property: the order in the selection does not mater, i.e. 0011 0101 1001 1010 1100 are the same.

Basically it is 4-combination of the set { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, ..., 9, 9, 9, 9}

What do you say to name this type of the selection?

I always get stuck when I say:

```
4-xxxxxxxx of the set {0, 1, 2, ..., 9}

```

where xxxxxxxx is the name of this selection.

# Answer
> 0 votes
The sequences your program generates are **non-decreasing sequences**.

---
Tags: combinatorics, notation, selection-problem
---


# Question
Title: Can a petri net fire only one transition at a single moment?
After reading several articles about petri nets, I am confused on how firing works. Can Petri net system fire only one transition out of all active (fire-able transitions) at a single moment? Or are multiple transitions allowed to fire at a single moment?

# Answer
Both.

Only one transition being able to fire at a time is known as *interleaving semantics*. Multiple transitions firing simultaneously is known as *step semantics*. Some people doing concurrency theory only call the latter real concurrency, and they care deeply about the difference; I'm sure the difference has consequences, but I've worked with Petri nets and I've never run into a situation where it mattered.

In a Petri net editor I used to work on, durations could be assigned to transitions - so these "transitions" represent tasks or processes that take a certain time. Once that is possible, clearly it makes a great difference whether two of them can be firing at the same time or not. But I would say such "timed transitions" really aren't transitions; rather, they are shorthands for a transition (start), a place (execution), and another transition (finish).
> 7 votes

# Answer
How many transitions fire at once depends on the interpretation assigned to the Petri Net.

If you want more than one transition to fire at once, you should consider:

```
1. Will the transitions fire using one processor?

```

This is fine. A Petri Net can handle this type of firing because the transitions actually fire one at a time. Consider the Petri Net in the following diagram:

Let m0 be the mark in place P0. Consider the firing rule for T1: m0 = m0 - 1,and the firing rule for T2: m0 = m - 1. It is easy to check if a transition is enabled before firing the transition.

```
2. Will each of the transition to fire use a different processor?

```

This is probably not fine. Using the same example above, consider a processor is responsible for firing T0 and another processor is responsible for firing T2. Each processor checks if its transition is enabled. If it is enabled, the processor fires the transition. Each check may indicate that the transition is enabled. So each processor will proceed to fire the transition. Depending on when each processor reads m0 and writes the computed value of m0, the value of m0 may be 0 or -1.

Postscript

A PDF version of the original answer may be found at http://www.aespen.ca/AEnswers/1416178160.pdf (and the equations are much better to look at). The modifier answer may be found at http://www.aespen.ca/AEnswers/1416975962.pdf.
> -1 votes

---
Tags: computation-models, petri-nets
---


# Question
Title: Solve a recurrence relation with two recursion calls using the iteration method
I can't figure out how to solve this recurrence relation using the iteration method:

$$T(n) = \begin{cases} 0, & \text{if $n=0$} \\ 1, & \text{if $n=1$} \\ 3T(n-1)+ 4T(n-2), & \text{if $n \>1$} \end{cases}$$

# Answer
Hint: Let $S(n) = T(n+1) + T(n)$. We have $S(0) = 1$, and for $n \> 0$, $$ S(n) = T(n+1) + T(n) = \[3T(n) + 4T(n-1)\] + T(n) = 4(T(n) + T(n-1)) = 4S(n-1). $$ Can you take it from here?
> 1 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Enumerating programs as graphs, or executing graphs?
Both programs and simple graphs can be enumerated using natural numbers (positive integers).

However, *what languages or ideas most naturally combine the two?*

For example enumerating programs using graphs instead of natural numbers.

Or executing graphs, in other words code described by a graphs shape instead of by text, and not just for tree shaped graphs.

# Answer
We can summarize your original findings as follows: there is an effective enumeration for programs and graphs. An effective enumeration of a countable set $S$ is a computable bijection between the natural numbers and $S$, that is, a program $P(n)$ such that $S = \\{ P(n) : n \geq 0 \\}$ and $P(n) \neq P(m)$ for $n \neq m$.

There are many countable sets which can be effectively enumerated – there is nothing special about programs and graphs. We can generalize and say that if $S\_1,S\_2$ can be effectively enumerated, then there is a computable bijection between $S\_1$ and $S\_2$ (why?), but this doesn't say much about any relation between $S\_1$ and $S\_2$.
> 1 votes

---
Tags: graphs, programming-languages
---


# Question
Title: Best design of a software controlled page table: to echo the TLB?
I am building some simple system software for the Microblaze FPGA (actually being run on OVPsim at least for now).

The system is to experiment with various memory management regimes.

The first system I want needs to have a very simple paging mechanism and so I want to build a software controlled (only option on a Microblaze) page table.

Is the easiest option just to echo the TLB hardware design - this might waste a few bits but given there are no special circuits optimising this, the simplicity of matching TLB entries to the page table seems like a pretty good choice to me. Is there any reason why I shouldn't do that?

Are there other designs for software controlled page tables that I should look at? (Any papers etc?)

# Answer
Page table structure (and especially page table structure for software managed page tables) was a hot area of research in the mid 1990s. At its root this is just the problem of creating a data structure to represent a map from one set of integers (the keys (virtual addresses)) to another set of integers (physical addresses). So you should expect the answer to have something to do with hash tables or search trees or both. The "best" choice depends on:

* how large your virtual address space is (e.g., 32 vs. 64 bit)
* how large your physical address space is
* how sparse or dense your mapping is (what fraction of the virtual address space you expect an individual process to use)
* how clustered your mapping is (you may only be using 1/10th of 1% of the address space, but all the virtual addresses cluster into one of a few dense regions/segments (the code segment, the stack segment, ...)
* the "natural" page sizes supported by your tlb
* whether you have address space identifiers (ASIDs), and how big they are (thus dictating how frequently they need to be reused.)
* whether you need to be able to use a shared memory abstraction to share data between different processes
* whether you have multiple tlbs that need to be kept coherent with some kind of tlb shootdown
* whether you have a single process and just need to virtualize that single process's address space over a backing store, or whether you are using paging to provide protection between multiple processes
* where and how you are going to store information about pages that have been moved to backing store
* (and more, like how you want to choose pages to replace)

Here are some good things to read:

> Huck, Jerry; Hays, Jim: Architectural Support for Translation Table Management in Large Address Space Machines, *Int'l Symp Comp Arch* (ISCA-20):39-50, 1993. doi:10.1145/165123.165128.

For machines with virtual address spaces that are much larger than the physical address space the inverted page table is the traditional solution. The inverted page table has exactly as many entries as there are physical pages. The entry records the virtual address mapped to that physical address, and also includes a link pointer. You look up a virtual address by hashing it to find a starting entry in the inverted table, then searching the linked list starting at that entry until you either find the virtual address in question, or find the end of the list.

There are a number of problems with inverted page tables. They don't handle having multiple virtual addresses mapped to the same physical address, it is expensive to find all of the physical pages that have been mapped for a particular process (you need to walk the entire table looking for entries with that process's ASID), and you need a different data structure to record information about virtual pages that have been moved to backing store. From a performance perspective the inverted page table does poorly at leveraging spatial locality because adjacent pages hash to disparate locations in the inverted page table. The Huck and Hays paper suggests variations on the inverted page table to address some of the inverted page table's shortcomings.

> Talluri, Madhusudhan; Hill, Mark D; Khalidi, Yousef A: A new page table for 64-bit address spaces, *ACM Symposium on Operating Systems Principles* (SOSP-15):184-200, 1995. doi:10.1145/224056.224071.

This paper suggests a different approach to dealing with the locality problems of the inverted page table. Essentially the inverted page table is used for super-blocks made up of some number (16 in the paper) of normal pages. Thus you get the nice behavior of the inverted page table (proportional to the size of physical memory) but get some locality benefits because subsequent tlb misses tend to be for other pages in the same super-block.

> Bala, Kavita; Kaashoek, M Frans; Weihl, William E: Software Prefetching and Caching for Translation Lookaside Buffers, *USENIX confernce on Operating Systems Design and Implementation* (OSDI-1):18, 1994.

This paper suggests that no matter what structure you use for the page table, you should augment the hardware TLB with a large, direct-mapped, software tlb. The hardware tlb usually needs to be quite small so suffers from capacity misses. You try to cover a large percentage of the capacity misses by finding the appropriate entry in the direct-mapped software tlb. The hope is that the software tlb is relatively quick and covers most accesses, and then you can use a more complicated structure (like a forward-mapped page table) for the few remaining misses.

So there are lots of choices, and there are lots of variables to consider. The best data structure choice really depends on the characteristics of your particular machine and your particular workload. You are trying to optimize for a sparse, but chunky, mapping function, trying to make sure you can handle operations beyond just lookup efficiently, and trying to leverage the spatial locality in the address stream to minimize cache misses while accessing the page table.
> 3 votes

---
Tags: memory-management, paging
---


title: Calculating genus of graph

text:
# Question
Title: Calculating genus of graph
How to calculate genus of arbitrary graph? I am interested in any algorithm, even it based on full search.

# Answer
One way that always works and is relatively easy to turn into code is Edmond's rotational embedding scheme. Let $G$ be a connected graph with vertices $V(G)=\\{v\_1, v\_1, \dotsc, v\_p\\}$. For every vertex $v\in V(G)$ choose a permutation $\pi\_v$ of the vertices adjacent to $v$. Then the collection of permutations $\pi\_{v\_i}$ determine an embedding of $G$ in a orientable surface $S\_n$ of genus $n$, and, conversely, every embedding of $G$ in $S\_n$ is determined by some collection of permutations as described above.

For example, consider $K\_4$ with vertices labeled $\\{1, 2, 3, 4\\}$ and permutations $$\begin{align} \pi\_1 &= (2\ 4\ 3)\\ \pi\_2 &= (1\ 3\ 4)\\ \pi\_3 &= (1\ 2\ 4)\\ \pi\_4 &= (3\ 1\ 2) \end{align}$$

The permutations will correspond to the counterclockwise order in which the adjacent vertices are encountered in the embedding (hence the term *rotation*). The permutations give rise to permutations, $\pi$, of the directed edges, defined by $\pi((v\_i, v\_j)) = (v\_j, \pi\_j(v\_i))$. In the example above, we'll have $$\begin{align} \pi((2, 1))&=(1, \pi\_1(2)) = (1, 4)\\ \pi((1, 4))&=(4, \pi\_4(1)) = (4, 2)\\ \pi((4, 2))&=(2, \pi\_2(4)) = (2, 1) \end{align}$$ and we're back where we started, having generated a 2-cell $(2, 1, 4)$. Starting the process with the directed edge $(1, 2)$ gives rise to a 2-cell $(1,2,3,4,1,3,2,4,3)$ and we stop here, having used all 12 directed edges in $K\_4$. We know that for an orientable 2-cell embedding in $S\_n$ of a graph with $p$ vertices, $q$ edges, $r$ faces we'll have $$ p-q+r=2-2n $$ in this case we have $p-q+r=4-6+2=0=2-2n$ so $n=1$, meaning that $K\_4$ has genus no larger than 1.

Of course, as presented this is a *terribly* inefficient algorithm, since there will be factorially many permutations for each vertex. There are some tweaks that will speed this up and there are some more modern approaches/modifications one could use (Edmond's paper came out in 1960), but the upshot is still that there's no efficient way to compute the genus of a graph.
> 5 votes

---
Tags: algorithms, graphs
---


title: Numbering levels of a tree

text:
# Question
Title: Numbering levels of a tree
I find the need to use an explicit level numbering for a tree. i.e. in the tree:

```
    A
   / \
  B   B
 /\   /\
C  C C  C

```

should I number the level C the 3rd and A as the first, or the opposite? As going 'up' the tree is going towards A; should the numbering reflect that as well? If can, please supply an authorized CS reference.

Thanks!

# Answer
There's no such thing as "an authorized CS reference", since nobody has the authority to declare how tree levels should be numbered.

The "height" of a vertex is its distance from the root (or distance plus one; see another question about the definition) so it probably makes sense to start at the top in most cases. But you should use whichever numbering is most convenient in your situation.
> 2 votes

---
Tags: trees
---


# Question
Title: How does the Earley Parser store possible parses of an ambiguous sentence?
I've got a pretty basic question concerning the Earley parser: In case of syntactic ambiguity ( *S -\> NP VP(V NP(NP PP))* vs. *S -\> NP VP(VP((V NP) PP)* ), are both parses stored in one chart or in two?

the grammar im talking about is the following: `S -> VP NP
VP -> V VP
VP -> VP PP
NP -> NP PP
NP -> Det N
PP -> P NP` so you while parsing could either attach a PP to an NP or to an VP.

my question is detail is how the *graphical chart* would look like, meaning the positions of predict, scan and complete. I was assuming that both parses would be stored in one (big) chart. So S' will then be found in, let's say, s\[0\]\[8\] and s\[0\]\[16\] ? Is that right?

An attached image or link with a graphical chart parsing through an ambigous sentence would help.

# Answer
This is an example of what the graphical chart looks like when there are n tokens in the string:

$\begin{array}{} \[1,1\] & \[1,2\] & \[1,3\] & \cdots & \[1,n\] \\ & \[2,2\] & \[2,3\] & \cdots & \[2,n\] \\ & & \[3,3\] & \cdots & \[3,n\] \\ & & & \ddots & \vdots \\ & & & & \[n,n\] \end{array} $

Because $S$ is the root of the grammar, the two parses of $S$ will be stored in the $\[1,n\]$ cell of the chart. Here as you can already guess, $\[i,j\]$ stands for the position indices of the parses, in other word, the span.

In case of $S$, the positions span the whole string. If the positions do not span the whole string, what you have is a set of valid constituent parses in that span.

So the answer to your question is: Possible parses are stored in the **same chart**, they may be stored in **different cells** of the *chart* if their **spans** are different. If their *spans are the same*, they are stored in the *same cell* in the *chart*.

Btw, I think the first two rules in your grammar do not look right. Maybe you want

`S -> NP VP` and `VP -> V NP` instead.
> 1 votes

---
Tags: algorithms, parsers, ambiguity
---


title: Converting to CFG from a CFL?

text:
# Question
Title: Converting to CFG from a CFL?
I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me.

Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem for generating a CFG. The Problem statement is to find a CFG that generates the following CFL: $$\\{a^ib^jc^k \mid i,j,k\geq 0\text{ and } i\neq j\text{ or } i\neq k\\}$$

Now I am trying hard to find one but I am not successful. Is there any easy approach to construct a CFG for a CFL?

# Answer
> 7 votes
As @babou indicated, there's no algorithmic way to produce a CFG from a description of a CFL, meaning that the problem is more art than science. There are, though, some idioms that turn out to be useful in practice.

**Idiom 1**. First, ignore the condition $i,j,k\ge 0$ for the moment, since that condition usually turns out to be easy to express in a grammar.

**Idiom 2**. See if the language can be expressed as the union or concatenation of simpler languages (intersection and complement are of less help, since CFLs aren't closed under these operations). In your case, the **or** in your original statement is a clue. Express your language as the union of simpler languages: $$ \\{a^ib^jc^k\mid i\ne j\\}\cup\\{a^ib^jc^k\mid, i\ne k\\} $$

**Idiom 3**. If you have an inequality, as you do here, note that we can express the $i\ne j$ condition as another **or**, namely $i\ne j\Longleftrightarrow (i \> j) \lor (i\< j)$, so $$ \\{a^ib^jc^k\mid i\ne j\\}=\\{a^ib^jc^k\mid i\>j\\}\cup\\{a^ib^jc^k\mid i\<j\\} $$ **Idiom 4**. Separate the problem into concatenated pieces if possible. For this example, we note that the $a^ib^j$ part will have nothing to do with the $c^k$ part, so we might start out grammar with the production $S\rightarrow TU$, where $T$ will generate the $a^ib^j$ and $U$ will generate the $c^k$ part. The latter is easy, and now we fill in the omission in idiom 1, writing $U\rightarrow cU\mid \epsilon$ (since if the requirement had been, say, $k\>0$ we could just use $U\rightarrow cU\mid c$).

**Idiom 5**. Now what to do with the $a^ib^j$ part, where $i\>j$? Simple, write it as $a^na^jb^j$ for some $n\>0$. To get an arbitrary number of a's in front, we can use $T\rightarrow aT$. Eventually we'll stop generating a's and will switch to the matching a's and b's, using yet another variable $V$, so we'll have $T\rightarrow aT\mid aV$.

**Idiom 6**. Finally, to generate a matching number of a's and b's we work from the inside out, placing one of each on the ends, so we'll have $V\rightarrow aVb\mid \epsilon$. This is very common when dealing with CFLs.

Finally, then, we have the grammar for one part of our language: $$\begin{align} S&\rightarrow TU\\ T&\rightarrow aT\mid aV\\ U&\rightarrow cU\mid\epsilon\\ V&\rightarrow aVb\mid\epsilon \end{align}$$ Of course, we still have a lot of work to do, but the rest is largely of the same form. Yes, it is complicated; all I can offer is that it gets easier with practice. Eventually, you might get to the stage where you'll often say "I've seen a problem like this before; maybe I can do something similar".

# Answer
> 3 votes
Unfortunately there is no simple algorithmic rule for this type of problem. You have to understand properties of CF languages and how they can be expressed with grammars.

Here is a further hint for your problem.

Can you write a grammar for the language

$L\_1= \\{a^ib^jc^k \mid i,j,k\geq 0\text{ and } i\neq j\\}$

**However**, Rick Decker is right. I tend to see the building of grammars as a black art. But any art, however black, has its own know-how, techniques, heuristics, and incantations which may or may not work depending on various factors (else it would not be an art :).

This leads me to idiom 2bis, which could be added to the others:

**Idiom 2bis** When the conditions of the original statement, setting constraints between the variables, include an **and** connective (explicit, or implicit as in $a\<b\<c$), it may be a clue that you have an intersection of two languages. Then if it is clear that one of them is a regular language, you should concentrate on the other which probably carries the CF difficulties of the problem. The reason is that CF languages are closed under intersection with regular set: given a CF grammar for one and a regular grammar (or FSA) for the other, it is easy to get algorithmically a grammar for the intersection. However, if both arguments of the intersection are CF, there is a good possibility that the language you are considering is not CF since the intersection of two CF languages is not in general CF ... though it may be CF in some cases.

For example, in the language considered in the question, the condition $i,j,k\geq 0$ is **and**ed with other conditions, but this is not really a problem, because it defines no constraint between $i$, $j$, and $k$. However, the two inequalities define such constraints. And it is actually the case that if the **or** were replaced by an **and**, the language would no longer be CF.

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


title: What is a CNF Satisfiability

text:
# Question
Title: What is a CNF Satisfiability
I am trying to understand the concept of CNF satisfiability, can someone throw some light on

1) what does 3- CNF, 4- CNF etc.. mean?

2) What does yes and no instance mean and can someone provide an example for the same ?

I am learning this subject at school and having hard time gathering basics of this concept.

Any help would be appreciated

# Answer
> 2 votes
Let's define the terms:

atom = the same thing you called variable; e.g. "x", "y", "z", etc.

literal = an atom or its negation; e.g "x" or "¬x".

clause = a disjunction of literals; e.g. (x∨y∨¬z∨w).

CNF: A formula is said to be in Conjunctive Normal Form (CNF) if it consists of AND's of several clause. For instance, (x∨y)∧(y∨¬z∨w) is a CNF formula.

The following problem is K-SAT: Given a CNF formula f, in which each clause has exactly K literals, decide whether or not f is satisfiable. That is, whether there is a an assignment to the atoms such that f evaluates to TRUE.

3-SAT and 4-SAT are the special cases of K-SAT problem.

For details, http://en.wikipedia.org/wiki/Boolean\_satisfiability\_problem

---
Tags: complexity-theory
---


# Question
Title: polynomial time reduction of 2 langauges
If we can reduce a language y to x.

`x ≤P y`

how do I prove

```
 x(complement) ≤P  y (complement)

```

# Answer
The definition of many-one reducibility means that, if you've proven that $X\leq Y$, you get $\overline{X}\leq\overline{Y}$ for free.
> 2 votes

---
Tags: complexity-theory, reductions, polynomial-time
---


# Question
Title: Finding Triples that satisfy modulo equation in $O(n\log n)$ time
Given $n$, I am trying to count the number of values $(a,b,c)$ that satisfy the following equation in $O(n\log n)$ time. I do not need the values themselves only the number of total values that satisfy the equation

$$a^2 + b^3 = c^4 \mod n\\,,$$

where $a,b,c \in\\{0,1,....,n-1\\}$ and $n$ is any natural number.

Does anybody have any idea how to do this? Obviously checking all values yields $O(n^2)$ time.

I am able to compute the triples for a given value of $c$ within the desired bound since you can build a BST in $O(n\log n)$ time where the keys are the particular modulo values in $b^3$ and the values are the number of instances they appear. Then by calculating $((c^4 \\!\\!\mod n) + n - (a^2 \\!\\!\mod n)) \\!\\!\mod n$ for every value of $a$ and doing a search for that key in $b$ we achieve the desired runtime.

How can I achieve the same result for every value of $c$ rather than a specific one though?

I presume the $O(n\log n)$ run-time comes from some form of binary search, sorting or binary search tree but I am not sure exactly how to achieve this for all the values of $c$ rather than a specific one. Any help is appreciated. Thank you.

# Answer
Hint: Use FFT to multiply the polynomials $$ \sum\_a x^{a^2 \pmod{n}}, \qquad \sum\_b x^{b^3 \pmod{n}}. $$
> 1 votes

---
Tags: algorithms, search-algorithms, binary-trees, binary-search, modular-arithmetic
---


# Question
Title: Expressing pseudo-polynomial runtime solely in terms of the input size
In case we have an algorithm which is pseudo-polynomial and runs in $O(n^2C)$ for some $C$ that is encoded in binary. Is it correct to say that if $C=2^n$ then $O(n^2C)=O(n^22^n)$ and because $n=\log C$ we can write that $O((\log C)^22^n)=O(2^n)$ because $2^n$ grows more rapidly than $\log C$?

# Answer
> 1 votes
You are correct that the running time is $O(n^2 2^n)$, but according to the definition of big O, it is *not* the case that $n^2 2^n = O(2^n)$, since $n^2 2^n$ grows faster than $2^n$. What is true is that for every $\epsilon \> 0$, $n^2 2^n = O((2+\epsilon)^n)$.

Often it is convenient to hide such "small" factors, and write $O(n^2 2^n) = \tilde{O}(2^n)$. The usual definition of $\tilde{O}(\cdot)$ is this: $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n)(\log g(n))^k)$. In practice this is almost always used when $g(n)$ is either a polynomial or an exponential. When $g(n)$ is a polynomial, $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n)(\log n)^k)$, and we say that $\tilde{O}$ hides polylogarithmic factors. When $g(n)$ is exponential (that is, $g(n) = e^{An^B}$ for some $A,B\>0$), $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n) n^k)$, and we say that $\tilde{O}$ hides polynomial factors.

---
Tags: algorithms, asymptotics, runtime-analysis, pseudo-polynomial
---


# Question
Title: Show that every infinite language has a non-regular subset
I'm trying to solve this problem:

> Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular

But can this be correct? If I have the language $\\{a\\}^\*$ for example, that's infinite but you can make a DFA for any sub-language of it, right?

There's a hint that this can be proved using diagonalization, but I think I must be misunderstanding the question.

# Answer
Consider the language $L = \\{a^n \mid n \text{ is prime}\\}$. $L$ is a subset of $\\{a\\}^\*\\!$, which is a regular language but it is not regular so has no DFA.
> -3 votes

# Answer
The powerset of the language contains all the sublanguages. This will be uncountably infinite, but there are only countably many regular languages (for a particular, finite alphabet)
> 20 votes

# Answer
**Hint.** An infinite language $\mathcal{L}$ doesn't necessarily contain words of all possible lengths but it must contain words of infinitely many different lengths. You can use this to get a non-regular subset of the original language (in fact, even an undecidable subset). For a sketch of how to continue, mouse-over the yellow region below.

> Let the set of lengths of words in $\mathcal{L}$ be $\\{\ell\_1, \ell\_2, \dots\\}$ and let $U$ be any undecidable set of natural numbers. The language $\\{w\in \mathcal{L}\mid |w| = \ell\_u \text{ for some } u\in U\\}$ is a sublanguage of $\mathcal{L}$ and is undecidable – so it's certainly not regular.
> 6 votes

# Answer
If $L$ itself is not regular, we are done. Otherwise, $L$ satisfies the pumping lemma: there is an integer $p \ge 1$ such that for any $w \in L$ such that $|p| \ge w$, there exist $x$, $y$ and $z$ such that $|y| \ge 1$, $|x y| \le p$ and $\forall i \ge 0, x y^i z \in L$. Since $L$ is infinite, there exists a word in $L$ that satisfies $|p| \ge w$; let $x$, $y$ and $z$ be the corresponding words given by the pumping lemma. The language $L' = \\{x y^i z \mid i \in \mathbb{N}\\}$ is a subset of $L$. Let $L'' = \\{x y^i z \mid i \text{ is prime}\\}$: this is a subset of $L$ which is not regular. One way to see that this language isn't regular is that it doesn't satisfy the pumping lemma. Another way is to use the classification of word lengths of regular languages.

There's a stronger result that any infinite language has a subset that is not decidable. Diagonalization is a reasonable way of proving this. I don't think diagonalization would be particularly useful to prove the existence of a non-regular subset.
> 5 votes

# Answer
You can prove this using diagonalization. Let $R\_1,R\_2,\ldots$ be an enumeration of the infinite regular languages. We will construct a descending sequence $L = L\_0 \supseteq L\_1 \supseteq L\_2 \supseteq \cdots$ and an increasing sequence $X\_0 = \emptyset \subseteq X\_1 \subseteq X\_2 \subseteq \cdots$ such that $R\_n \setminus L\_n \neq \emptyset$, and furthermore $L \setminus L\_n$ and $X\_n$ are finite for all $n$, $X' = \bigcup\_n X\_n$ and $L' = \bigcap\_n L\_n$ are infinite, and $L' \supseteq X'$.

At stage $t$, we construct $L\_t$ and $X\_t$. If $R\_t \setminus L\_{t-1} \neq \emptyset$, we set $L\_t = L\_{t-1}$. Otherwise, $R\_t \subseteq L\_{t-1}$. The set $\Delta = L\_{t-1} \setminus R\_t$ is infinite, since otherwise $L = R\_t \cup \Delta \cup (L \setminus L\_{t-1})$ would be regular, and in particular we can choose some $x \in \Delta \setminus X\_{t-1}$ and set $L\_t = L\_{t-1} - x$. In both cases we set $X\_t = X\_{t-1} + \min L\_{t-1}$.

By construction $R\_n \setminus L' \supseteq R\_n \setminus L\_n \neq \emptyset$, and so $L'$ is not equal to any infinite regular language, and so to no regular language.

---

This arguments works if we replace the class $\mathcal{L}$ of regular languages with any other class which is closed under word addition (i.e., $L \in \mathcal{L}$ implies $L+w \in \mathcal{L}$). The argument is constructive in the sense that the $t$th smallest word is either in $X\_t$ or in $L\setminus L\_t$. When $L$ is itself regular and $\mathcal{L}$ is the class of regular languages, this makes the resulting language decidable, thus improving on the cardinality argument given by Nathan Dunn. While in this particular case there are more direct solutions, diagonalization could work in more general situations.
> 1 votes

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


# Question
Title: Encoding the pigeonhole principle in CBMC
> CBMC is a Bounded Model Checker for ANSI-C and C++ programs. It also supports SystemC using Scoot. It allows verifying array bounds (buffer overflows), pointer safety, exceptions and user-specified assertions.

For the pigeon-hole principle I understand that the constraints are:

1. Each Pigeon is in some Hole.
2. Two different Pigeon can't be in same hole.

Let's take an example of 4 pigeons and 3 holes. I need to convert this into a CBMC check. I'm trying using two for loops, but I can't find how to do it.

# Answer
If I understand correctly, you're actually looking for a technique to check if an out-of-bounds condition exists (more pigeons than pigeonholes).

Here's some example code that fits your analogy. I think you're asking about this technique as an analogy to whatever problem you're actually trying to encode, but next time be direct with what problem you want to solve rather than an analogy :)

```
/* pigeonhole.c */
int main() {
  _Bool holes_occupied[3];
  unsigned int pigeon;
  for (pigeon = 0; pigeon < 4; ++pigeon) {
    holes_occupied[pigeon] = 1;
  }
  return 0;
}

```

Run with:

cbmc --bounds-check pigeonhole.c

VERIFICATION FAILED (with error trace)
> 2 votes

---
Tags: satisfiability, discrete-mathematics, software-verification
---


# Question
Title: Show whether the language with almost as many 0 as 1 in every prefix is regular
This is the exercise:

> Let A be a language defined over the alphabet Σ = {0, 1} composed by the strings with the property that in every prefix, the number of 0s and the number of 1s differ by at most 2. Determine if A is a regular language and prove it.

Ok, as @roi-divon commented, A is a regular language. I've tried to obtain de minimal DFA accepting A but I haven't got it... Someone knows?

# Answer
The language is regular.

Denote

$ L^k = \\{ x \ | \ \forall \alpha \in Prefix(x): |\\#\_0(\alpha)-\\#\_1(\alpha)| \leq k \\} $

Your language is $L = L^1$.

We shall prove, using Myhill-Nerode theorem that each $L^1$ is regular (actually for any $k,\ L^k$ is regular).

Define equivalence classes of $R\_L$ as follow:

* for $-k \leq i \leq k: \ S^i = \\{ x \ | \ \\#\_0(\alpha)-\\#\_1(\alpha) = i, \forall \alpha \in Prefix(x): |\\#\_0(\alpha)-\\#\_1(\alpha)| \leq k \\}$
* $S\_{out} = \\{ w | \exists \alpha\in Prefix(x): |\\#\_0(\alpha)-\\#\_1(\alpha)| \gt k\\}$

We can see that $L^k = \bigcup\_{-k \leq i \leq k}S^i $

Clearly, the equivalence classes are not empty, they don't intersect and the union is $\Sigma^\*$

Assume $x,y \in S\_{out}$, we show that $x R\_L y$: clearly from every $z \in \Sigma^\*: \ xz,yz \notin L$ (have "bad" prefixes")

Assume $x,y \in S^i$, and assume there is a $z \in \Sigma^\*$ such that $xz \in L$ but $yz \notin L$. Then $yz$ has a prefix $y \beta$ such that the difference between 0's and 1's is larger than k ($\beta$ is prefix for z). By counting the number of 0's and 1's of $x \beta$ we get that it's larger then k, in contradiction that $xz \in L$

Now we show that if $x,y$ in different classes, then $(x,y) \notin R\_L$.

Assume $ x \in S^i, \ y \in S\_{out}$: then for $z = \epsilon: \ xz = x \in L, yz = y \notin L$. Therefore $(x,y) \notin R\_L$

Assume $x \in S^i, \ y \in S^j$, and $j \neq i$. w.l.o.g, $i \> j$. Examine $z = 0^{k-i+1}$. Counting 0's and 1's, we get that $xz \notin L$, and $yz \in L$. Therefore $(x,y) \notin R\_L$

By that We've proved that $L = L^1$ is regular
> 1 votes

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


# Question
Title: Evaluating Statements Using a Parse Tree
I'm building a compiler. I already have a parse tree which I built using Bison for a grammar similar to the ANSI C grammar in this link. I see that for multiplicative expression in my parse tree, there can be 3 children e.g.

```
child 1: multiplicative_expression
child 2: '*'
child 3: cast_expression

```

I expect to implement a new class for interpreting the parse tree. However, I have no idea how to even traverse the parse tree in order to evaluate the statements. How do I traverse the tree properly in order to interpret all the types of statements? I want to interpret not only multiplicative statements but also if-else statements etc.

# Answer
An expression is composed usually of an operator (or function) applied to some arguments, or in the simplest case, just a constant (aka literal) or a variable.

For evaluation:
The value of a constant is that constant, The value for a variable is the current value stored in that variable, as each variable corresponds to a memory location where values can be stored. The value of an operator or function applied to arguments is obtained by evaluating arguments (recursively) and then applying the operator or function to the values thus obtained.

Actually, things can be more complex for a function (and some operator), depending on parameter passing mechanisms or evaluation modes (lazy or not), but that is to complex to explain at this level of discourse.

In your example the operator is child 2, and the two other children are arguments.

In general the algorithm does pretty much what you would do if you had to interpret the program by hand. That should be a good guide.
> 1 votes

---
Tags: algorithms, graph-traversal, interpreters, syntax-trees
---


title: Algorithms online problems

text:
# Question
Title: Algorithms online problems
I'm trying in vain to find some online (classical) algorithms problems to deeply exercise "complexity" and maybe see (even try) mathematical demonstrations.

As far as I can see, the sites that I found (CodeChef, Project Euler) seem to be more programming oriented, even if I like the format and their challenge. That is, even when speed is somehow important, you cannot not know the exact complexities values for the algorithm (the lovely greek letters), maybe some demonstration of the efficiency of the solution.

An online course or a book is acceptable if it is more problems oriented. In my opinion, these are the kind of questions that a development top company should ask anyway.

# Answer
Cormen, Leiserson, Rivest and Stein's *Introduction to Algorithms* (MIT Press, 3rd edition, 2009) is a good book for understanding and solving time complexity and correctness of algorithms mathematically.
> -1 votes

---
Tags: algorithm-analysis, reference-request
---


# Question
Title: Is there a name for the 'scope tree' organization?
I could describe JQuery as a library that allows you to easily select elements on and traverse the DOM, the DOM would be the name of the tree or organizational structure of the HTML.

When you are describing what JS (or any other language) scope bubbles up from the local scope, to its parent scope, to its parent scope, to its parent scope, ...., until there are no more parent scopes, where you have reached the global Object scope, what would you call this scope organization?

# Answer
> 3 votes
As Raphael says in his comment, this is a hierarchical scope organization. But this can qualified any kind of tree structured scope, and you state in the title that it is tree structured.

The whole purpose of this hierarchy is to allow reusing the same name in a different scope, for some other naming purpose. So, given a name, you have to decide where to lokk for its meaning, in what scope.

As you suggest, you start for the current scope (to be defined ...) and you buble up to parent scopes until you find a definition for that name (a declaration usually). The first one you find is usually supposed to be the right one.

But there is a major problem remaining: which is the parent scope of any given scope? There are two major policies regarding this: **static scoping** also called **lexical scoping**, and **dynamic scoping**.

Static scoping corresponds roughly to the way scopes are embedded according to the program text. Dynamic scoping corresponds to the way scopes are embedded according to program execution.

So, for example, take a `function foo` that is declared in your program. If defines a new scope, with the variables local to `foo`. If the function uses a variable `x` that it does not declare, the meaning of the variable must be found in the parent scope. For dynamic scoping, the parent scope is that of the scoping structure (function, method, module, and whatever creates new scopes) that called the function `foo`. For static scoping the parent scope is the scoping structure in which the function `foo` was declared.

Static scoping is usually preferred because the meaning of a programming construct is independent of where it is actually used (possibly many different places), and depends only of where it is defined (only one place). Hence program analysis, understanding, and maintenance is usually much easier with static scoping.

The story goes that dynamic scoping was invented more or less by accident, as it was used in the first Lisp interpreter in the late 1950s. People were not yet aware of the difference at the time. When they found out (see the Funarg controversy), the language was being used and it was to late. Until Scheme came in as a statistically scoped version of Lisp.

But there can be other ways of organizing scopes, of importing one scope into another, and so on. I suggest that you read the wikipedia page on scope, which you should have done before asking.

---
Tags: terminology, data-structures, programming-languages, variable-binding
---


# Question
Title: Show that the tree resulting from BFS is a spanning tree?
Given that $G$ is some connected and undirected graph, and I want to run BFS on it from some starting vertex. How can I show that $T = \\{ \\{\text{predecessor}\[u\], u\\} \mid u \text{ is a vertex}\\}$ is a spanning tree of $G$?

# Answer
> 2 votes
Observe that any spanning tree of $G$ contains every vertex of $G$, and has no cycles. Use induction to show that on every iteration, the process creates no cycles (and also visits every vertex).

# Answer
> -1 votes
I have no idea about data structure you are going to use, but you probably have all of your vertexes and for each vertex list of it's neighbours. A general approach should be:

After each step in your traversal check the list. If new vertex is a visited vertex then there is a loop in your graph an it's not a tree. (check your graph is a tree or not)

Another condition is to check coverage of your graph. When your traversal completed the visited list should contain a complete set of graph vertexes.(check for spanning)

---
Tags: graphs, spanning-trees
---


# Question
Title: Why is $O(\log_{M/B} N/M)$ the same as $O(\log_{M/B} N/B)$?
Where $N$ is the size of the input, $M$ is the size of your main memory and $B$ the amount of elements that you can transfer in one I/O.

My idea is that since $B$ is usually much smaller than $M$ we can have

$O\left(\frac{N}{B}\log\_{\frac{M}{B}}\frac{N}{M}\right) = O\left(\frac{N}{B}\log\_{\frac{M}{B}}\frac{NB}{MB}\right)$

so $\frac{B}{M} \<1$

but I'm new to complexity theory so I'm not sure if it's the correct reasoning.

# Answer
Your construction will work just fine: $$\begin{align} \log\_{M/B}\frac{N}{M}&=\log\_{M/B}\frac{NB}{BM}=\log\_{M/B}\frac{N}{B}\cdot\frac{B}{M}\\ &= \log\_{M/B}\frac{N}{B}+\log\_{M/B}\frac{B}{M}\\ &= \log\_{M/B}\frac{N}{B}-1 \end{align}$$ Since the two terms differ by 1, they're asymptotically equal.
> 3 votes

---
Tags: asymptotics, arithmetic
---


# Question
Title: Hamming Weight to find the sum of 1 bits in the range between A and B inclusive
I am trying to find the sum of 1 bits in the range between **A** and **B** inclusive,

where -2^31 \<= A \<= B \<= 2^31 - 1

**Input Format:**

The first line contains the number of test cases T (\<=1000). Each of the next T lines contains two integers A and B.

I have used Hamming Weight algorithm to solve this problem. Though I have used memoization version of Hammnig Weight algorithm, it runs out of time.

```
mf = [-1 for i in range(65536)]

def count_1s(x):
    """It counts the number of 1 bits in an given 32 bit integer"""
    if (x > 65535):
        return count_1s(x&0xFFFF) + count_1s(x>>16)
    elif (mf[x] != -1):
        return mf[x]
    else:
        count = 0
        while(x > 0):
            x &= (x-1)
            count += 1
        mf[x] = count
        return mf[x]

t = int(input())

for i in range(t):
    a = [int(number) for number in input().split()]
    count = 0

    for j in range(a[0], a[1]+1):
        if (j < 0):
            count += 32 - count_1s(-j-1)
        else:
            count += count_1s(j)

    print(count)

```

So I am in a need of improving this algorithm. Are there any ways to improve this algorithm? or I should use some other algorithm to solve this problem?

**Link for Input:**

https://hr-testcases.s3.amazonaws.com/56/input02.txt?AWSAccessKeyId=AKIAINGOTNJCTGAUP7NA&Expires=1416339544&Signature=5bf736TpbPUWcQZ%2FbGijtBHbVeM%3D&response-content-type=text%2Fplain

**Required Output:**

https://hr-testcases.s3.amazonaws.com/56/output02.txt?AWSAccessKeyId=AKIAINGOTNJCTGAUP7NA&Expires=1416339722&Signature=NUwWGdUVsvttRWx0janzsxncDtY%3D&response-content-type=text%2Fplain

# Answer
> 1 votes
The basic idea is *not* to manually go over all numbers from $A$ to $B$. For example, suppose $A = 0$ and $B = 2^n-1$. The $k$th bit of a number in $\\{0,\ldots,2^n-1\\}$ is $1$ exactly half the time, so the total number of $1$s is $n2^{n-1}$. Similarly, if $A = x2^n$ and $B = x2^n + 2^n-1$ then the number of $1$s is $n2^{n-1} + 2^nH(x)$, where $H(x)$ is the Hamming weight of $x$. In the general case, you have to decompose the range $\[A,B\]$ into a small number of ranges of the form just described. You should be able to do this with at most $2n$ or so ranges, where $n$ is the length of $B$ in bits.

---
Tags: algorithms, logic, runtime-analysis
---


title: Proof of Dijkstra Algorithm Optimality

text:
# Question
Title: Proof of Dijkstra Algorithm Optimality
Has it been proven that Dijkstra's algorithm is optimal for asymptotic worst case of single-source shortest path on directed graphs? (Assume no preprocessing)

I became curious when Wikipedia mentioned it as the 'best known' rather than the 'best possible'. Is a proof of its optimality an open problem?

# Answer
> 6 votes
There is no non-trivial complexity lower bound on any interesting problem. In particular, any algorithm not running in $O(|V|+|E|)$ is not known to be tight. That said, you might be able to show a lower bound in some restricted model, say the decision tree model. For example, it might be possible that any comparison-based algorithm must make $\Omega(|E|+|V|\log|V|)$ comparisons in the worst case, though I am not aware of any such work on the single-source shortest path problem. See also the related question on cstheory.

Another avenue for obtaining conditional lower bounds is accepting some widely believed complexity assumption such as the Exponential Time Hypothesis or some version of the 3SUM hypothesis (whose strongest version was recently disproved by Grønlund and Pettie), though I'm not aware of any such work either in the present case.

---
Tags: algorithms, algorithm-analysis, graphs, shortest-path
---


title: Prove a language is regular

text:
# Question
Title: Prove a language is regular
I am asked to find

> Prove that the following languages are regular languages:
>
> (a) $\\{a^nb^ma^k \mid n\geq3,m\geq1,k\geq1\\}$
>
> (b) $\\{a^n \mid n\neq3 \text{ and } n\not\equiv2 \mod7\\}$
>
> (c) $\\{a^nb \mid n\geq2\\}\cup\\{ab^m \mid m≥3\\}$

I have a vague understanding of pumping lemma, and how to prove a language is not regular, but was hoping that someone could walk through (a) with me to give me a better understanding and allow me to do the rest on my own. I think I must make an automaton but I am not sure how, as this does not seem finite to me?

# Answer
> 0 votes
Note that the language in (a) consists of strings that start with $\mathtt{aaaa}^r\dotsc$ where $r\ge 0$. Make use of the idea that a state in a FA can "record" the answer to a yes/no question. To process the first part, use a FA with four states, $$\begin{align} q\_0:&\text{ we've seen $0\ \mathtt{a}$'s so far}\\ q\_1:&\text{ we've seen $1\ \mathtt{a}$ so far}\\ q\_2:&\text{ we've seen $2\ \mathtt{a}$'s so far}\\ q\_3:&\text{ we've seen $3$ or more $\mathtt{a}$'s so far}\\ \end{align}$$ Obviously, in state $q\_0$ on input $\mathtt{a}$, we'll go to state $q\_1$, in state $q\_1$ on an $\mathtt{a}$ we'll go to state $q\_2$, in state $q\_2$ on an $\mathtt{a}$ we'll go to state $q\_3$ and in state $q\_3$ on an $\mathtt{a}$ we'll stay in state $q\_3$. That takes care of the first part, $\mathtt{a}^n$ where $n\ge 3$. Do the same thing for the other two parts and you'll have a FA for the language.

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


title: I want to learn algorithms

text:
# Question
Title: I want to learn algorithms
I did study applied math and dealed almost exclusively with the creation of ode/pde solver code. Now, I want to increase my knowledge in some aspects and I want to learn some basic algorithms like A\*, MinMax, ... (not limited to searching; I am also interested in the basics of optimization and machine learning) **and** their implementation.

Is there a good resource (book, online course) available for me to learn this from? Any help is appreciated. I have no other CS-related background except my math degree.

# Answer
> 0 votes
Consider the textbook (from my undergrad years, many years ago):

Bazaraa, M. S.; Jarvis, J. J.; and Sherali, H. D. (1990). Linear Programming and Network Flows. 2nd Edition. New York: John Wiley.

Consider the recent edition of the textbook too.

---
Tags: algorithms
---


title: n-th non-decreasing sequence

text:
# Question
Title: n-th non-decreasing sequence
I have a generator of non-decreasing sequences of numbers 0..M:

```
M = 9;
c = 0; //counter

for (i1 = 0;  i1 <= M; i1++)
    for (i2 = i1; i2 <= M; i2++)
        for (i3 = i2; i3 <= M; i3++)
            for (i4 = i3; i4 <= M; i4++)
                printf("%d. %d%d%d%d", ++c, i1, i2, i3, i4);

```

Result:

```
1. 0000
2. 0001
3. 0002
...
10. 0009
11. 0011
12. 0012
...
19. 0019
20. 0022
21. 0023
...

```

I need to calculate ONLY the n-th element. For example:

```
input: n = 21
result: 0023

```

It takes O(M^4) iterations to calculate it

1. How can I calculate the n-th element more efficiently? (without generating all previous elements)
2. Is there an O(1) algorithm for this problem?
3. If not how can we show that there is no such algorithm.

Thank you!

# Answer
> 0 votes
This is yet another example of combinatorial enumeration. There are altogether $\binom{M+4}{4}$ different quadruples. Given $j\_0$, there are $\binom{M+3-j\_0}{3}$ quadruples with $i\_0 = j\_0$. This means that the first $\binom{M+3}{3}$ quadruples start with $0$; the following $\binom{M+2}{3}$ start with $1$; the next $\binom{M+1}{3}$ start with $2$; and so on. In this way, given a number between $1$ and $\binom{M+4}{4}$, you can find $i\_0$.

You then zoom in on a list of length $\binom{M+3-i\_0}{3}$, and again you are given a $1$-based index to it. There are $\binom{M+2-(j\_1-i\_0)}{2}$ quadruples with $i\_1 = j\_1$. This means that the first $\binom{M+2}{2}$ quadruples start with $i\_0,i\_0$; the following $\binom{M+1}{2}$ with $i\_0,i\_0+1$; and so on. Having found $i\_1$ this way, you can find $i\_2$ and $i\_3$ by repeating the same argument twice more.

The same argument, run in reverse, can be used to calculate the index given the quadruple. Assuming binomial coefficients can be calculated in constant time and that integer arithmetic is constant time, this algorithm runs in time $O(4\cdot M)$, or $O(4\cdot\log M)$ with $O(4\cdot M)$ preprocessing (for fixed $M$). I'm including the $4$ since if you had $t$-tuples instead of quadruples, you could replace it with $t$.

---
Tags: algorithms, combinatorics
---


# Question
Title: Is randomly building a BST different from random sampling whole trees?
What is the difference between a randomly built binary search tree (using n keys )and choosing a binary search tree (of n key) from a random distribution

# Answer
> 0 votes
You want to distinguish

> randomly built binary search tree

from

> choosing a binary search tree from a random distribution.

Let me first tell you why this is not a well-posed query. Neither version is completely specified; the first misses the process by which the tree is built as well as the used random source, the second lacks a specification of the distribution to be used. In particular, the "randomly built" trees *are* "chosen from a random distribution"!

Now I'll assume that you (or your teacher) made the "usual" assumptions and reformulate the models.

1. Starting with the empty tree, we insert keys $s\_1, \dots, s\_n \in \[1..n\]$ successively (with BST insertion). The sequence is chosen uniformly at random from all permutations of $\[1..n\]$.

This is the famous *random permutation model*.
2. Pick a tree uniformly at random from all BSTs with keys $\[1..n\]$.

There are several ways to see that the two models define different random distributions.

1. There are $n!$ different permutations but only $C\_n = \frac{1}{n+1} \cdot \binom{2n}{n}$ BSTs. Show that it is not possible to distribute the permutations evenly, i.e. $C\_n$ does not (always) divide $n!$.

In particular, for $n=3$ we have six permutations but five BSTs.
2. For $n=3$, enumerate all trees and notice that four trees result from one permutation each while the fifth results from *two*. Ergo, the random permutation model is not uniform.
3. Know (from earlier studies) that BSTs have average height $\Theta(\log n)$ in the random permutation model but $\Theta(\sqrt{n})$ in the uniform model.

The first is a standard result found in most textbooks on the matter. The latter, admittedly, a less known result by Flajolet and Odlyzko \[1\]; the method of analysis has broader relevance and the result generalises to many families of trees.

---

1. The average height of binary trees and other simple trees by P. Flajolet and A. Odlyzko (1982)

# Answer
> -1 votes
**Randomly built binary search tree** : When binary tree is built by picking n keys one by one randomly from a set of keys.

While **binary search tree from a random distribution** mean there are all possible ways of binary tree with n keys from a set of keys . and you are picking directly one of the tree.

Only way of making a random binary tree is different.

Randomly built binary search tree will be more efficient to make than the later one.

but both will result in estimated search time of O(log n)

---
Tags: data-structures, binary-trees, search-trees, randomness, sampling
---


title: Proving a language is not regular

text:
# Question
Title: Proving a language is not regular
I need to prove that the following language is not regular

> $\\{c^mb^na^n \mid n\>0,m\geq0\\}$

But I am not sure how to do that for this particular one. I vaguely understand pumping lemma, but every example I see is in the form

> $\\{a^nb^n \mid n\>0\\}$

Or something similiar. This does not help me with my problem, because I dont fully understand pumping lemma and am not sure how to do it for two variables that have no dependency on each other. I know to take a length P from L, and I also need a string s\>=P. Which then becomes P=xyz, but it is this step that confuses me.

# Answer
There are many ways to solve this. Here are some:

1. If $L = \\{c^m b^n a^n : n\>0, m\geq 0\\}$ were regular then so would $L \cap b^\*a^\*$ be.
2. The words $\\{ b^n : n \> 0 \\}$ are pairwise inequivalent modulo $L$, so $L$ is irregular according to Myhill-Nerode.
3. The pumping lemma works if you ignore the $c$ part.
> 1 votes

---
Tags: regular-languages
---


# Question
Title: How do I compute the huge numbers which occur in el gamal decryption?
I'm trying to do decryption using el gamal. The formula to get the message M is $$ M=\frac{b}{a^x} mod \\:P $$ In one case, we may have $$ M=\frac{18}{62^{62}} mod \\: 71 $$ This value cannot be computed on a calculator as $62^{62}$ gives an infinite value. How do we get the value of M?

# Answer
> 1 votes
Two techniques will be of use here and in many similar problems. To find $(1/a)^b\pmod n$,

1. First, compute $1/a = a^{-1}\pmod n$. In your example, compute $62^{-1}\pmod{71}$, namely, the modular inverse of $62\pmod{71}$. That happens to be $63$.
2. Then use repeated squaring to find $(1/62)^{62}\equiv63^{62}\pmod{71}$, which will be 8. This relies on the fact that $a^{62} = a^{32+16+8+4+2}=(a^{32})(a^{16})(a^{8})(a^{4})(a^{2})$ where, reading from the right, each value is the square of the preceding one, meaning that you can find $a^{62}$ using 9 modular multiplications, rather than 61.

---
Tags: modular-arithmetic
---


# Question
Title: Returning m greatest elements from k sorted array
We have $k$ sorted arrays, $A\_1\[1...n\_1\],...,A\_k\[1..n\_k\]$, where $n\_1+n\_2+...+n\_k=n$.

How can we get the $m$ greatest elements in running time $O(k + m\lg k)$?

I have tried to use MIN-HEAP size of $k$ since we have $k$ arrays. I have to navigate through the ends of the $k$ array somehow. By extracting the min of heap and getting new element from respective array was my idea but it does not work. I could not figure out getting m greatest elements.

# Answer
Your idea works out. The idea is to maintain a heap of size $k$ which contains exactly one element from each array. For each array $A\_i$, we maintain an index $p\_i$ which keeps track of the position of the current element in the array. Initially, $p\_i = n\_i$, and we insert $A\_i\[n\_i\]$ into the heap. We then repeat the following $m$ times:

1. Extract the maximum element from the heap.
2. If the extracted element belonged to $A\_i$, then we decrease $p\_i$ by one and insert $A\_i\[p\_i\]$ into the heap.

The initialization phase takes time $O(k)$, and the extraction phase takes time $O(m\log k)$, for a total of $O(k+m\log k)$. You can prove that the extracted elements are indeed the $m$ largest ones.
> 2 votes

---
Tags: algorithms, arrays, selection-problem
---


# Question
Title: Proving Linear Time Temporal Logic formula □ ◊ f ⇔ ◊ □ f
I am new to this topic, Linear Time Temporal Logic and I am trying to prove this equivalence --

$\Box\Diamond f \Leftrightarrow \Diamond\Box f$

This is my take --

Basic definitions:

$(\sigma, j) \models \Box f: \forall k \\, \[(k \ge j) \Rightarrow ((\sigma, k) \models f)\]$

$(\sigma, j) \models \Diamond f: \exists k \\, \[(k \ge j) \Rightarrow ((\sigma, k) \models f)\]$

Here, $(\sigma, j) \models f$ means $\sigma$ satisfies $f$ at $\sigma(j)$, for more details about this syntax, please see here.

Now the LHS:

$\begin{eqnarray} (\sigma, j) \models \Box \Diamond f & : & \forall k \\, \[(k \ge j) \Rightarrow ((\sigma, k) \models \Diamond f)\]\\ & \equiv & \forall k \\, \[(k \ge j) \Rightarrow \[\exists p \\, \[(p \ge k) \Rightarrow ((\sigma, p) \models f)\]\]\]\\ & \equiv & \forall k \\, \[(k\<j) \vee \[\exists p \\, \[(p\<k) \vee ((\sigma,p) \models f)\]\]\]\\ & \equiv & \forall k \\, \exists p \\, \[(k\<j) \vee (p\<k) \vee ((\sigma,p) \models f)\]\\ & \equiv & \forall k \\, \exists p \\, \[(p\<k\<j) \vee ((\sigma,p) \models f)\]\\ \end{eqnarray} $

Again, the RHS:

$\begin{eqnarray} (\sigma, j) \models \Diamond \Box f & : & \exists k \\, \[(k \ge j) \Rightarrow ((\sigma, k) \models \Box f)\]\\ & \equiv & \exists k \\, \[(k \ge j) \Rightarrow \[\forall p \\, \[(p \ge k) \Rightarrow ((\sigma, p) \models f)\]\]\]\\ & \equiv & \exists k \\, \[(k\<j) \vee \[\forall p \\, \[(p\<k) \vee ((\sigma,p) \models f)\]\]\]\\ & \equiv & \exists k \\, \forall p \\, \[(p\<k\<j) \vee ((\sigma,p) \models f)\]\\ \end{eqnarray} $

Now if we look at the last line of the both sides, the statement

$\forall k \\, \exists p \\, \[(p\<k\<j) \vee ((\sigma,p) \models f)\] \equiv \exists k \\, \forall p \\, \[(p\<k\<j) \vee ((\sigma,p) \models f)\]$

needs to be true to complete the proof, however intuitively, this is not true.

What I am missing? How do I proceed? Any idea?

# Answer
> 9 votes
You are not missing anything. These expressions are indeed not equivalent. Assume $f$ in your case is an atomic proposition. Then the computation: $f,\neg f,(f,\neg f)^\omega$ satisfies $□◊f$, but not $\Diamond \square f$.

Intuitively, $\Diamond \square f$ means "After a finite prefix, there is always $f$", while $\square \Diamond f$ means: "There are infinitely many $f$s".

By the way, you have some mistake in your semantics. It should be: $(\sigma,j)\models \Diamond f$: $\exists k\[k\ge j\wedge (\sigma,k)\models f\]$.

---
Tags: logic, proof-techniques, linear-temporal-logic, temporal-logic
---


# Question
Title: How to write a DFA where the second digit is equal to the last digit of binary strings?
I'm having some trouble writing a DFA for the language $$\\{w =b\_1\dots b\_k \in\\{0, 1\\}^\* \mid b \ge 2 \text{ and } b\_2=b\_k\\}\\,.$$

What I thought for this is writing a DFA where there are 4 states, that accepts at the states (00) and (11), where the 1st element in the state is the 2nd element in the string, and the 2nd element in the DFA is the last element in the string. After trying to draw out examples this clearly doesn't work. I'm quite lost, any advice?

# Answer
You are on the right track.

When constructing a DFA, you have to consider what information you need to store to decide in the end whether the string is accepted or not. The information you need is indeed: the second symbol of the string and the symbol which was read last. So you need four states to store all combinations of these two flags, and the accepting states are the ones where the second symbol and the last symbol are equal. The only thing you still need to do, is glue these states together.

First, there is a third kind of information: the length of the string. If you have read less than two symbols, you are not in one of four states mentioned earlier. So there are six states:

```
A: no symbols have been read (this is the initial state)
B: one symbol has been read
C: at least two symbols have been read, the second symbol is a 0 and the last a 0
   (this is an accepting state)
D: at least two symbols have been read, the second symbol is a 1 and the last a 0
E: at least two symbols have been read, the second symbol is a 0 and the last a 1
F: at least two symbols have been read, the second symbol is a 1 and the last a 1
   (this is a in accepting state)

```

To finish the automaton, you have to consider what happens to the state if you read in a 0 or a 1. This will then give you the transition function.
> 4 votes

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


# Question
Title: Applying the context-free pumping lemma to a language with crossed nestings
For proving language $\\{a^nb^mc^nd^m \mid n,m \> 0\\}$ is not context free. Do I have to use $z = a^pb^pc^pd^p$ as pumping lemma string where $p$ is pumping length?

Or do I have to use a string that would reflect than $n$ and $m$ does not have to be the same length?

# Answer
> 2 votes
Pumping lemma lets you construct new strings belonging to the context-free language.

To prove that the language is not context-free you can take some string $s$ from L, use pumping lemma to construct a new string $s1$ which must belong to $L$ (because you used pumping lemma to construct it!). Then you show that $s1$ does not belong to L =\> contradiction.

Choice of original $s$ is yours. So yes, you can use $z = a^pb^pc^pd^p$ in your proof.

---
Tags: formal-languages, context-free, pumping-lemma
---


title: Runtime of Euclidean Algorithm

text:
# Question
Title: Runtime of Euclidean Algorithm
Given two $n$-bits numbers $a$ and $b$, I am not sure on how to find the runtime of the euclidean algorithm for finding the $\gcd$ of $a,b$. The problem (for me) in here is that apart from the size of $a$ and $b$, I don't feel like I have any other information that will help me to know what is the runtime of the algorithm. I saw somewhere that the number of rounds is $\log\_2 a = n$, but, assuming this is correct, I have no intuition as for why it is such?

My question is for an explanation to how much time it takes to calculate the $gcd$ (as a function of $n$)? Is it linear in $n$?

# Answer
Let's analyze two consecutive steps of the GCD algorithm: given $a \> b$, we compute $c = a \pmod{b}$ (replacing $a$) and $d = b \pmod{c}$ (replacing $b$). The two new numbers $c,d$ we are left with satisfy

$$ c+d \leq b \leq \frac{1}{2} (a+b). $$

So the sum of the two numbers decreases by a factor of at least a $1/2$ every two iterations. If $a,b$ are at most $n$-bit long, then at the start of the algorithm, $a+b \leq 2^{n+1}$. After $2(n+1)$ steps, the two remaining numbers have sum at most $1$, so by that time the algorithm must have terminated.
> 4 votes

---
Tags: algorithm-analysis, runtime-analysis, number-theory
---


# Question
Title: Construction of graph with given Wiener Index
Given the sum of weights of shortest paths between all vertices in a graph, how can I construct a connected graph that satisfies the given sum? That is, how can a graph with a given wiener index be created?

# Answer
> 1 votes
This question is addressed on the Wikipedia page Wiener index. Gutman, Yeh and Chen showed that there are no (unweighted) graphs with Wiener index 2 or 5, but all other values are attainable. In a subsequent paper, Gutman and Yeh determine which Wiener indices are attainable on bipartite graphs, and on the way explain how to prove the earlier result, an explanation which we reiterate here.

Consider the clique on $n$ vertices. Its Wiener index is $\binom{n}{2}$. Pick a vertex $v$ from the clique. Suppose we remove $m$ edges $(x\_1,y\_1),\ldots,(x\_m,y\_m)$ not adjacent to $v$. Since $x\_i,y\_i$ are connected via $v$, each edge we remove increases the Wiener index by one, and so the resulting Wiener index is $\binom{n}{2} + m$. The maximal number of edges we can remove is $\binom{n-1}{2}$, which corresponds to a Wiender index of $\binom{n}{2} + \binom{n-1}{2} = (n-1)^2$. We deduce that for every $n$, there are graphs having Wiener index $\frac{n(n-1)}{2}$ to $(n-1)^2$. Let's list these ranges for small $n$, starting with $n = 2$: $$ \[1,1\], \\; \[3,4\], \\; \[6,9\], \\; \[10,16\], \\; \[15,25\], \ldots $$ Denoting the intervals as $\[a\_n,b\_n\]$, starting with $n=5$ we have $a\_{n+1} \< b\_n$, which is not hard to check directly. Therefore, in this way we can construct graphs of any Wiener index other than $2$ or $5$.

It remains to rule out 2 and 5. First, note that a graph of $n$ vertices has Wiener index at least $\binom{n}{2}$. Since $\binom{4}{2} = 6$, it is enough to consider all graphs on at most 3 vertices:

1. A path of length 1 has Wiener index 1.
2. A triangle has Wiener index 3.
3. A path of length 2 has Wiener index 4.

These are the only connected graphs on at most 3 vertices.

---
Tags: algorithms, graphs
---


# Question
Title: Amortize time for a counter with the operations INCREMENT and DECREMENT
Let a binary counter with the operations INCREMENT and DECREMENT.

I need to show that you can't implement this kind of counter with constant amortized time per operation.

Hence, I need to show that there's a series of $N$ operations with amortized time of $\omega(N)$.

**My Try:**
Let's assume we made $2^k-1$ INCREMENT operations. Hence, our counter is a sequence with $k$ 1's. Now, Let's consider a sequence of $N$ operations alternating between DECREMENT and INCREMENT (DEC,INC,DEC,INC,DEC...)

Each operation must be $\Theta(k)$. Somehow, I need to figure out that it has to be that the amortize time is $\omega(N)$. How?

# Answer
Your solution is on track. As you comment, if you increment a counter $2^k-1$ times and then do $m$ increment/decrement operations, in total you must have modified at least $km$ array positions (this will serve as our lower bound on the running time). In your case $N = 2^k-1 + m$. If you choose, for example, $m = 2^k+1$, then $N = 2^{k+1}$ while the lower bound is $km \geq \log\_2 N \cdot (N/2) = \Omega(N\log N)$. This shows that the amortized running time is $\Omega(\log N)$, which is certainly superconstant.

We can easily get a matching (non-amortized) upper bound. If we only perform $N$ operations, then the value of the counter is in the range $\[-N,N\]$, and so takes $O(\log N)$ bits to represent. It is not difficult to implement increment and decrement so that they take time linear in the length of the representation, so $O(\log N)$ in this case.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, amortized-analysis
---


# Question
Title: What complexity class is this ciruit problem?
I'm exploring an algorithm that solves k-SAT. It uses a ton of preprocessing, so I'm thinking that this will be a circuit bounds.

Without knowing the runtime, I speculate on how quickly it will solve k-SAT instances. It will either solve all instances of k-SAT with probability $p$, or it won't be able to solve any instances. The runtime is based on $p$. Essentially, it runs in quasi-polynomial time.

So essentially, what we have is an algorithm that runs in time $2^{O((\log{n})^{c\_1})}\cdot O(c\_2 + q)$, and solves all instances with probability $\frac{2^q-1}{2^q}$, or it can't solve any instances. Here, $c\_1$ and $c\_2$ are constants.

It also requires space polynomial in $q$.

I'm trying to find what complexity class this is, and what is known about it.

**SOME NOTES**

Just to ensure I've described this correctly, I have an algorithm that either solves all instances, or it can't solve any. We can say it uses $2^{2^n}$ preprocessing. Then, it runs in time that is quasi-polynomial multiplied by a function of $q$.

**THE QUESTION, AGAIN**

What complexity class is this, and what is known about it?

# Answer
Assuming that the probability is over the randomized preprocessing and $p \> 0$, by fixing the correct random choice you get a circuit of size $S = O(2^{\log^{O(1)} n} q^{O(1)})$ for $k$-SAT. The corresponding complexity class is non-uniform circuits of size $S$. If, for example, $q$ is quasipolynomial ($2^{\log^{O(1)}n}$), the you get a non-uniform circuit of quasipolynomial size.

We usually don't care too much about the time required to construct the circuit unless it is very low.
> 1 votes

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