# Question
Title: Why are types and grammar non-terminals so distinct?
Sorry ahead of time if some of my terminology is inaccurate, my formal training isn't quite to the level it should be.

Almost all programming languages with types separate built-in functions `a + b` and user defined functions `f(x)` into different steps of the compiler. `a + b` is dictated by some grammar that says something like `expr ::= expr + term`, and is dealt with by the parser. The precedence/associativity of operations is also defined by the parser, and all user defined functions are dumped into a common bucket. `f(x)` is defined by a declaration that requires `x` to be some type, and the result to be a particular type - which is then commonly checked post-parse in static analysis.

Thinking about it, it seems as though `f` (assuming for example, `f` goes from `int` to `bool`) could be defined in a grammar similar to

```
bool ::= "true" | "false" | bool-expr
bool-expr ::= "f" "(" int ")"
int ::= int-constant | int-expr ...

```

But doing some searches, it seems as though computer science research around types and grammars are formal, but always distinct.

Sure, there are practical concerns. Grammars tend to be static, preventing user defined functions from being... user defined. Grammars tend to be hard to make correctly/unambiguously, and letting random users meddle is troublesome. Having huge grammars would be more troublesome than doing the same sort of work split off to a more limited type-checker.

But there's all sorts of research which is done regardless of practical concerns. I find it hard to believe that the two research areas wouldn't benefit from ideas from each other. And by treating types like non-terminals (or vice versa), it seems as though you get quite a few benefits not commonly available (function overloading by return type, extensible language using types rather than a separate meta-language, better integration of user defined operators).

Given my lack of training though, I'm guessing there's simply something I'm missing that breaks the correspondence or that it was researched and promptly discarded due to something obvious to others. So what am I missing?

---

Clarification for svick's comment

*function overloading by return type*:

Since statements/expressions would need to be integrated with types, statement would need to map to `void` or `unit` or some analogy - and expressions would be typed as above. For example, `f(x:int) -> void` and `f(x:int) -> int`, only one is viable as a statement. This requires function signatures to be processed before implementations (akin to C), but that is rather implied for all of the approach.

*extensible language without meta-language*:

By making types act like grammar non-terminals, it would allow the parser behavior to vary based on function declarations (and the various symbols in scope). Consider the above example where statements are required to be `void`. `f(x)` would not even parse without some declaration that both matches that input and results in `void`. The function/variable/type declarations of the language effectively become the meta-language. But that's what programmers do already...

*better integration of user defined operators*:

Previous extensible languages had approaches to user defined operators, requiring the user to define precedence (usually some numeric value, relative to the built-in operators), and associativity. Having user defined and built-in operators/functions "speak the same language" as it were should provide a more uniform interaction between the two.

But mostly, the benefits I would expect are more theoretical. Things that can be proven/used about grammars could be applied to type checking and vice versa if types and non-terminals had some correspondence.

# Answer
> 2 votes
## About operators and syntax extensions

Dave Clark comment is correct: "types is about semantics, grammar non-terminals is about syntax." This said, you are perfectly right that the semantic and syntactic issues could, possibly should, be both in the hands of the programmer, or at least of the project designer. Indeed, that has actually been the case for various languages, including older ones from the early 1970s, when the concept of extensible languages was popular.

But first you should get your concepts rights. Though the addition may be seen as a built-in function, that is not what characterizes it in the context of your question. A built-in function is just a function that happens to be predefined in the standard environment of the language. For example `sqrt` (square-root) or `abs` (absolute value) may be builtin functions in a language, but they are still defined implicitly as `function sqrt(r:real):real; ....` and `function
abs(z:real):real; ....`, though `abs` is often overloaded to work also with `integer`.

There could also be a built-in function `plus`, possibly overloaded, that would perform additions. But who would use it. We prefer to write it with the operator `+`.

There are built-in operators such as `+`, and one might want the programmer to be able to define new ones.

The use of operator has to do with the way we write things. It is a syntactic issue. Using them does not help you to do more, but it allows you to say it differently, if you think that makes things easier to write or read and understand, or simply makes them closer to standardized notations.

So you should see operators as nothing more than a special notation for calling some function, which may or may not be extended to new functions. **Defining operators has nothing to do with typing.** Whatever semantic problems it causes can be caused as well with the simple use of functions. But if it extends the syntax, it may create syntactic problems such as grammatical ambiguity.

Operators are often overloaded, like `+` that can be used for both `integer` and `real`, and possibly for `boolean` disjunction or `set` union. But functions can be overloaded as well. It is only a notational issue. And one constraint, for both functions and operators, is that you cannot overload them using twice the same type signature, but that is a semantic problem: finding which fuction is actually associated with what is written, functionally or with an operator.

Regarding extensions of a language, there are many ways to do it. One way is to allow overloading of existing operators with new function, having new type signatures. Some languages limit it at that.

Another possibility is to introduce new user defined operators, possibly written as a sequence of characters, such as `>=`, or `**`, or `and`, and then associate functions with them. This can be done without touching the grammar, by defining for example the associativity (left or right) and the precedence level of binary operators, or the position of the argument for unary ones. Analysing the actual structure of expression could be handled separately from the context-free parsing of the syntax, thus not be really a parser issue. but more associated with expressions evaluation.

A third possibility is to allow the introduction of new rules in the grammars, but that requires appropriate techniques to properly associate semantics to these rules, which can be very open, and thus quite complex to handle.

Note also that we tend to see operators as unary prefix and binary infix, but there are many other forms, such as postfix for factorial $n!$, or the absolute value notation (endfix?): $|x|$, and more.

A last point is that, though the grammatical structure shoud remain manageable, mostly for users to understand, the syntactic complexity is not a major issue for modern syntax analysis techniques. I seems that there is a tradition of trying to have very efficient parsers, but it is not clear that the performance bottleneck is still there (maybe for some programming environments). We can analyze quite efficiently ambiguous languages.

Ambiguity may be a problem, when too frequent. But frequent ambiguity can probably be detected statically, event though the problem is not decidable in general (I do not know whether there has been work in that direction). Then, ambiguity can be treated by the parser as a syntax error, requiring the programmer to write things differently.

Actually, it may well be that the syntax is not ambiguous, but the typing is. While a big expression is parsed correctly, the overloading of functions or operators can be such that there is ambiguity as to what code (function body) should actually be understood.

A very simple example is:

```
function f(x:S):T1; ....
function f(x:S):T2; ....
function g(z:T1):T; ....
function g(z:T2):T; ....
declare u:S, v:T .....
  .....
  v := g(f(u))

```

It is not possible to decide which pair of functions f and g is actually being called, because the typing of the expression is ambiguous.

A language such as Ada (at least in its first release) allows such ambiguity that is detected by the compiler. I would consider it a semantic ambiguity, though some people consider type checking as part of syntax. Whatever the case, is that any better or any worse than syntactic ambiguities that would be detected by the parser.

I avoided giving concrete examples (there are many) because my memory may fail me and I and not sure which language allows what. When I need to know, I look.

## About types

You question is mixing a lot of (I think) unrelated issues. So It is taking me time to sort it out.

The existence of operators and their properties is not really related to typing, as I explain above.

I think I finally understand what you are trying to say with the example using `bool` as non-terminal.

However I fail to see how it relates to the use of operators, which comes first in your question. And I do not see what it is supposed to bring you in terms of programming power.

This said, there is something like it that is possible, associating types with non-terminal. It is actually a way to integrate type checking in the syntax, though I do not know that it has ever been used for programming languages. It is used for natural languages, and is called *feature structures*. For example it can be used to test number, gender or case agreement in natural language analysis, which is quite close to type agreement.

The idea is to associate parameters with non-terminal, which then become some kind of predicate. It can be seen as using an infinite number of CF rules, all derived from a finite set by instantiating the parameter to all possible values. But actually it is used by instantiating the parameters as needed with unification.

This is possible because CF grammars may be seen as a special type of Horn Clauses with binary predicates (the two arguments are the indices of the ends of the corresponding substring in the program text). Adding a type arguments to the grammar non-terminals is just adding a third argument to the corresponding Horn clauses.

---
Tags: formal-grammars, programming-languages, semantics, typing
---


# Question
Title: Is emptiness of the intersection of the languages of two TMs decidable?
Let

$\qquad \mathrm{DISJOINT} = \\{ \langle M\_1,M\_2 \rangle : M\_1, M\_2 \text{ are TMs and } L(M\_1) \cap L(M\_2) = \emptyset\\}$.

How do I know if this language is decidable or not? And How do I prove my answer?

# Answer
> 2 votes
Assuming you have a decider $R$ for DISJOINT, you could use this to make a decider D for $E\_\text{TM} = \\{\langle M\rangle\mid L(M)=\emptyset\\}$ as follows:

```
D(<M>) =
   return R(<M>, <A>)

```

where $A$ was a TM, selected in such a way that $\langle M\rangle\in E\_\text{TM}$ if and only if $(\langle M\rangle, \langle A\rangle)\in\text{ DISJOINT}$. All that's left for you is to find the $A$ and show that it satisfies the needed conditions. (There are a couple of ways to make this choice.)

# Answer
> 1 votes
Hint: If DISJOINT were decidable then even the special case in which $M\_1$ is some fixed machine which accepts all inputs is decidable. This is the language $\\{ \langle M \rangle : L(M) = \emptyset \\}$, which you might be more familiar with.

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


# Question
Title: Show that finding a minimum-weight subgraph that includes all marked nodes is NP-hard
We've been given a weighted graph with marked nodes. We want to make a minimum-weight subtree from this graph that contains all marked nodes.

I want to show that this problem is NP-hard. Is there any idea to which problem is the best for reduction to this problem?

# Answer
> 2 votes
This is the problem of finding a **Steiner tree** in the graph. It's one of the **NP**-complete problems in Karp's original paper; the reduction there is from **Exact cover by 3-sets**.

# Answer
> 0 votes
I think vertex cover can be easily used when we consider edges as nodes and mark only those nodes that has a correspend edge in G. I think it will work

# Answer
> 0 votes
You can use reduction using Dominating set.

Given an input $G$ and $k$ for Dominating set, you create a new graph with a root node. Create a node for each node in the original graph. Connect the root node with each node by edge of cost 1. Connect each node with each other with edge of cost 0 if they are connected in the original graph. Make all the nodes as marked. The weight for the decision version will be $k$ (the set size in the input).

If there is a tree that covers all marked nodes, then we look at all the edges of weight 1 that come from the root. The nodes (other than the root) of these edges are the dominating set of size k in the original input. This is because the tree covers all nodes, so all nodes in the original graph connect with the resulting dominating set of size $k$ that we found.

The other direction is also straight-forward. We select the nodes that are in the dominating set of size $k$ and connect them with the root. All other nodes must be connect with this tree because these $k$ nodes form a dominating set. Because there are $k$ nodes connecting with the root so the weight of the tree is $k$.

The problem is also in NP because one can verify coverage and weight easily. So the problem is NP-complete overall.

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


# Question
Title: Which measure of sortedness explains the phase transition in Quicksort's runtime?
I'm currently creating a program to analyse the pathological cases of Quicksort. Namely, the transition of complexity from $O(n^2)$ to $O(n \log n)$ as a data set gets less ordered. Since Quicksort is a value-based algorithm, the choice of pivot determines its efficiency. We usually (Quicksort 3, and choosing a random element aside) select the first or last element as the pivot in an array. Therefore, since a good pivot is one that splits the array in half symmetrically, a more disordered array will make selecting a good pivot easier; or at least reduce the likely hood of running into the pathological case.

My program gradually randomises this array by swapping some elements each time. When I started to plot the graph of this using gnuplot I notice the trend I expected; a exponential distribution, branching off to a uniform distribution.

My question is, how do I quantify a level of disorder in a array? Is their a better way to gradually make an array of values more disordered?

# Answer
> 4 votes
Inversions are one way to measure "disorder" in a list:

> Let $A\[1..n\]$ be an array of $n$ distinct numbers. If $i \< j$ and $A\[i\] \< A\[j\]$ then the pair $(i,j)$ is an ***inversion*** of $A$.

However, it's not the only such measure. In general, this concept is formalized in the notion of ***presortedness*** \- roughly:

> An integer function on a permutation $\sigma$ of a totally ordered set that reflects how much $\sigma$ differs from the total order.

The survey papers by Mannila \[1\] and Estivill-Castro & Wood \[2\] might be good places to start.

The question How to measure "sortedness" is related.

---

\[1\] Heikki Mannila. "Measures of Presortedness and Optimal Sorting Algorithms." IEEE Transactions on Computers 34.4 (1985): 318-325.

\[2\] Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.

# Answer
> 3 votes
There is an analytical result for something similar (but not identical) to your model of unsortedness:

Banderier et al. \[1\] precisely analyze the expected number of comparisons needed by Quicksort on a *partial permutation* of the sorted list of length $n$:

> For a parameter $p\in\[0,1\]$ (that might depend on $n$), we select each element in the initially sorted list i.i.d. with probability $p$. Then, we randomly permute only the selected elements.

For $p=1$, you get random permutations, for $p=0$ we retain the sorted list. Quicksort then needs asymptotically $2\frac np \ln n$ comparisons on average for such a partial permutation (Remark below the proof of Theorem 1 in \[1\]).

As a consequence, when $p = O\bigl(\frac{\log n}n\bigr)$, Quicksort needs a quadratic number of comparisons, whereas for a constant $p$, Quicksort is linearithmic. There is, however, no sharp transition between those two extremes, if you choose $p$ in the right way (depending on $n$), any behavior between the extremes is possible.

---

\[1\] Cyril Banderier, René Beier, Kurt Mehlhorn "Smoothed Analysis for Three Combinatorial Problems", MFCS 2003, LNCS 2747, 2003, pp 198-207: http://link.springer.com/chapter/10.1007/978-3-540-45138-9\_14

---
Tags: algorithms, algorithm-analysis, quicksort
---


# Question
Title: Reversing a List from a Context-Free Grammar
Let's say I have a struct\_declaration\_list of the following type. How do I reverse it?

```
struct_declaration_list
    : struct_declaration
    | struct_declaration_list struct_declaration
    ;

```

P.S. Sorry I don't know the exact name of this kind of list so I can't search. I just have this grammar.

# Answer
> 3 votes
Your question is not very precise. I assume you want the list of `struct_declaration` to start from the other end in the parse tree.

Your grammar gives you a `struct_declaration_list` that looks like

```
         SDL
        /   \
      SDL    SD
     /   \
   SDL   SD
  /   \
SDL   SD
 |
SD

```

If you reverse the order in the second part of the rule, you reverse "the pointers" in the list, which may be understood as reversing the order.

```
struct_declaration_list
    : struct_declaration
    | struct_declaration struct_declaration_list
    ;

```

Then the parse tree looks like:

```
   SDL
  /   \
 SD   SDL
     /   \
    SD   SDL
        /   \
       SD   SDL
             |
            SD

```

The left-to-right order of SD is in both cases that of their occurrence in the input string (the program).

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


# Question
Title: What is the purpose of ϵ-transitions in PDA?
$A = \\{a^i b^j c^k\mid i = j\text{ or } j = k; i, j, k \ge 0\\}$. In its push down automaton should not there be the red colored transition instead of the black colored one?

# Answer
Yes, you could substitute the red transition for the black one below and have an equivalent PDA. With the black one, you allow the possibility that when reading $\mathtt{b}$s, you make a nondeterministic switch to the state where you expect to see a $\mathtt{c}$. If you do, it's as if you followed the red transition. In other words, either PDA will accept a string in $A$.

By the way, you could do a similar thing between the first and the second states of the upper branch.

The moral is that here are many roads to the top of the mountain, grasshopper.
> 1 votes

# Answer
You may notice that when $i=j=k=0$ you get the empty word, which is thus in the language. Hence, you need to accept the empty word. Allowing to reach a final state without ever reading anything is one way to accept the empty word, and it is here easily achieved with the $\epsilon$-transitions.

You may also note how $\epsilon$-transitions are convenient to actually produced the PDA as the "union"of two PDAs.

Actually, it is a convenient way to allow any of $i,j,\text{ and }k$ to be $0$.

Of course, there are other ways to get this result, without $\epsilon$-transitions. But the automaton may be more complicated. Such variation on how to write automata do not always change the family of languages, but may help to write more natural or intuitive descriptions.

**Regarding your example, and the transition in red.**

*The transition in red cannot replace the $\epsilon$-transition between the same states.*

If you take $i=3, j=0,\text{ and }k=0$, you have the string $a^3$ which is in the language, but is not accepted by the modified automaton.

It cannot be accepted by the upper part of the automaton which acceptes only when $i=j$.

It cannot be accepted by the bottom part of the automaton since the accepting state can be reached only by scanning a $c$, and there is none when $j=k=0$.

With the the black $\epsilon$-transition, reading a $c$ is optional, while it becomes compulsory with the red transition.
> 1 votes

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


title: Are regex crosswords NP-hard?

text:
# Question
Title: Are regex crosswords NP-hard?
I was fooling around the other day on this website: http://regexcrossword.com/ and it got me wondering what the best way to solve it was.

Can you solve the following problem in polynomial time or is it NP-hard?

> Given an NxM grid with N regular expressions for the columns and M for the rows, find any solution to the grid such that all the regular expressions are satisfied, or say that no solution exists.

# Answer
> 11 votes
The problem is NP-hard.

We show this by reducing vertex cover:

> Given a graph $G=(V,E)$ and a threshold $k$, is there a subset $V' \subseteq V$ of cardinality at most $k$, so that each edge in $E$ is incident to at least one node in $V'$?

We translate this into a regex crossword with $|E|+1$ columns and $|V|$ rows as follows:

All columns, except for the first, correspond to an edge. They get a regex $0^\*1(0|1)^\*$.

All rows correspond to a vertex. They get a regex that allows to write either

* a $1$ in the first column and each column corresponding to an edge incident to that node and zeroes in all other columns, or
* $0^\*$

Finally, the first column counts the size of the vertex cover. It gets a regex, that allows for at most $k$ ones.

The correspondence between solutions to the regex crossword and vertex covers should be obvious.

**Example:**

Find a vertex cover of size 2 for the following graph:

$V\_A = 0^\* \big| 10110$

$V\_B = 0^\* \big| 11101$

$V\_C = 0^\* \big| 10011$

$V\_D = 0^\* \big| 11000$

$Counter = 0^\* \big| 0^\*10^\* \big| 0^\*10^\*10^\*$

$E\_1 = 0^\*1(0|1)^\*$

$E\_2 = 0^\*1(0|1)^\*$

$E\_3 = 0^\*1(0|1)^\*$

$E\_4 = 0^\*1(0|1)^\*$

Lastly, you can set up the "crossword" so that $V\_A$ through $V\_D$ are the top regexes and $Counter$ and $E\_1$ through $E\_4$ are the left side regexes.

Solving this regex crossword give you a vertex cover of size 2 for nodes $V\_A,V\_B$ or $V\_C,V\_B$.

If we change k to be 1 and $Counter$ to be $0^\* \big| 0^\*10^\*$ as another example, the regex crossword is impossible to solve because there is no vertex cover of size 1.

# Answer
> 2 votes
The question remains NP-complete even when all the regular expressions are equal. http://arxiv.org/abs/1411.5437

---
Tags: complexity-theory, np-hard, regular-expressions
---


# Question
Title: "Print 'em all game" for Turing machines
Suppose that we have a tape restricted to $n$ cells on binaryalphabet $\Sigma = \\{0,1\\}$ and initially filled with zeroes.

We want to build a Turing machine $M\_n$ (or better a Linear Bounded Automata) that "prints" all the $2^n$ numbers on the tape, i.e. for all $x \in \[0..2^{n-1}\]$ there is a time $t\_x$ during the computation in which the tape content is exactly $x$. Note that we can build an "optimized" Turing machine for every $n$.

At every step the head must move left or right.

> What is the minimum number of steps $T(n)$ required?

We can easily see that $2^n-1 \leq T(n) \leq n 2^n$.

But how much can we "optimize" it?

For example for $n=3$ there is an optimal $2^n-1$ sequence:

```
t0:  >0 0 0
t1:   1>0 0
t2:   1 1>0
t3:   1>1 1
t4:  >1 0 1
t5:   0>0 1
t6:   0 1>1
t7:   0>1 0

```

# Answer
> 1 votes
If you use a Gray code then you can get $O(2^n)$. The Gray code described in the Wikipedia article modifies at time $t$ the position $p\_t$ which is the index of the right-most 1 bit in $t$. The resulting position sequence is $$ 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, \ldots $$ You are interested in $\sum\_t |p\_{t+1}-p\_t|$: $$ 1,1,2,2,1,1,3,3,1,1,2,2,1,1,4,4,\ldots. $$ We can see that half the time this is $1$, a quarter of the time it's $2$, one eighth of the time it's $3$, and so on. The total average value is roughly $$ \sum\_{n = 1}^\infty \frac{n}{2^n} = 2. $$ So the head moves roughly $2^{n+1}$ times compared to your lower bound of roughly $2^n$.

---
Tags: turing-machines, constant-time
---


title: Guessing Number Game

text:
# Question
Title: Guessing Number Game
I was solving this question. It is as follows

> Joe picks an integer from the list $1,2,\cdots,N$ with a probability $p\_i$ of picking $i$ for all $1\leq i \leq N$. He then gives Jason $K$ attempts to guess his number. On each guess, Joe will tell Jason if his number is higher or lower than Jason's guess. If Jason guesses Joe's number correctly on any of the $K$ guesses, the game terminates and Jason wins. Jason loses otherwise. If Jason knows all $p\_i's$ and plays optimally, what is the probability he wins?
> $1\leq N\leq 200000$
> $1\leq K\leq 20$

I tried this problem by dynamic programming. Let $DP\[i\]\[j\]\[k\]$ stores the winning probability such that the number is between $i$ and $j$ inclusive and only $k$ chances are left. So
$$DP\[i\]\[j\]\[k\] = \max\_{i\leq l\leq j} \\{p\_l + DP\[i\]\[l-1\]\[k-1\] + DP\[l+1\]\[j\]\[k-1\]\\}\\DP\[i\]\[j\]\[1\] = \max\_{i\leq l\leq j}p\_l\ \quad \quad \text{Base Case}$$ But since the range of $N$ is very high this solution is not feasible. So while I was seeking an $\mathcal{O}(n)$ solution I came across the following solution(on the internet which got accepted)

* Sort($p\[\]$)
* $\sum\_{i=0}^{\min(n,2^k-1)}p\_i$

If we run both the solution on input $N=5,K=2, p=\[0.2, 0.3, 0.4, 0.1, 0.0\]$ we get the same answer. So, my question is how is the above algorithm working and can we get to the same conclusion starting form my dp formulation{if it is correct}.

# Answer
The reason why the sorting solution works is that if you are given $K$ guesses, then with any deterministic strategy you can only guess at most $2^K - 1$ values. This can be proved by induction, first noting the base case $K = 1$ and then for $K + 1$, note that after you guess the first value then you have $K$ guesses left and you guess either on the left or right of your original guess depending on the outcome of the original guess, so by induction that gives $2(2^K - 1)$ values you can guess after the first, so if you add the original guess then you get $2^{K+1} - 1$.

Furthermore, if any of these $2^K - 1$ values is the correct value, it will be guessed and you will win. None of the other $N - 2^K + 1$ values will ever be guessed. So the probability that you win is the sum of the probabilities for the $2^K - 1$ values your deterministic strategy can guess. Obviously the optimal solution is to take the top $2^K - 1$ probabilities.
> 2 votes

# Answer
After a few months, my head has become clearer and it seems quite easy to see how this works.

If you have 1 guess, you pick the one with highest probability.

If you have 2 guesses, you pick the 3 with highest probability. The first guess, you pick the second one among the three. The second pick, you are directed to either of two sides of the first pick. Each side leads to the case of 1 guess, and on each side you already have the top 2 prob located in each. This is optimal. Prob of winning is the sum of the 3 prob.

..

So the clear pattern is that when you have $k$ guesses, you pick the top $2^k - 1$ with highest probabilities. The first pick is on the middle of the top $2^k - 1$. After that you recurse on either side of the middle one. On either side, you have the top $\frac{(2^k - 1) -1}{2} = 2^{k-1} - 1$ probabilities located there because the way you pick the middle pivot and that you take the top $2^k - 1$.

This gives the probability for winning as the sum of the top $2^k - 1$ probabilities.
> 0 votes

---
Tags: algorithms, dynamic-programming
---


title: Help on using the pumping lemma?

text:
# Question
Title: Help on using the pumping lemma?
I'm trying to prove that a language is not regular. That language is:

{w ∈ {a, b}\* | amount of a's in w is equivalent to the amount of b's in w, mod 2}.

I have an inkling that this language is not regular, so when I go to apply the pumping lemma, I would apply it on some subset of the language, and the pump on that, right? So, let's say I choose to pump on a, and then I'm able to produce a string that should be in the language, but it isn't. I can do this because when I pump on a, I can produce a string that is not in the language because it will not be the same mod 2. But, I am having a hard time understanding if this is really true. I'm trying to construct a DFA that is able to count the amount for a's and b's, but I'm not having much success. Am I right or wrong?

# Answer
> 3 votes
This language is regular. Since you're looking for equivalences mod 2 we need only consider the evenness or oddness of the count of the two kinds of symbols in the input. Consider a finite automaton with four states: EE, EO, OE, OO, where state EE records that the number of $a$'s seen so far is even and the number of $b$'s is also even. Similarly, being in state EO means you've seen an even number of $a$'s and an odd number of $b$s. States OE and OO are defined similarly.

Now consider the transitions between states. For example, in state EO with input a, the number of $a$'s changes from even to odd, while the number of $b$'s doesn't change, so we have the transition $\delta(\text{EO}, a) = \text{OO}$. The other seven transitions are defined similarly.

The start state is EE, since you've seen 0 $a$'s and 0 $b$'s and obviously 0 is an even number. The final states are EE and OO, for obvious reasons.

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


# Question
Title: Turing recognizable & decidable: binary strings with even length. Let A = {(M) | M is a DFA such that L(M) is not the same as EVEN}
Having trouble with this homework problem. In order to show that A is Turing recognizable and decidable.

$\text{EVEN} = \text{binary strings with even length}$

$Let\\;A = \\{(M) | \\,M\\; \text{is a DFA such that L(M) is not the same as EVEN}$

1. $\text{Show that A is Turing-recognizable}$
2. $\text{Show that A is decidable}$

So, at first glance it seems we need to just find a word that M accepts that is an odd length binary string. I'm a bit lost at where to start though.

I believe I'd start by using the TM from Theorem 4.1 of Sipser's Introduction to Theory of Computation which states if a DFA is a decidable language we can use Turing machine T to test if it's decidable:

$\text{T = "On input (B,w) where B is a DFA and w is a string:}$

1. $\text{Simulate B on input w}$
2. $\text{If the simulation ends in an accept state - accept, otherwise reject"}$

# Answer
The language is clearly recognizable: given a DFA $M$, simulate it, in minlex order, on every word, and see if there is a word $w$ such that $|w|$ is odd, and $w$ is accepted by $M$, or if there exists a word $w$ such that $|w|$ is even, and $w$ is not accepted by $M$. In both cases - accept.

However, this machine doesn't show the decidability of the language.

In order to decide the language, it is easier to proceed as follows: Let $A$ be a DFA that accepts the language EVEN. Fix such a DFA.

Now, given $M$, we need to decide whether $L(M)=L(A)$. If you feel comfortable with automata, you can just say that this is decidable, and that's it.

If you're not that comfortable yet, consider the following: Given two DFAs $B,C$, it is easy to construct a DFA $D$ such that $L(D)=L(B)\cap \overline{L(C)}$, and it is also easy (well, decidable in NLOGSPACE) whether $L(D)=\emptyset$. The latter test is equivalent to deciding whether $L(B)\subseteq L(C)$. Thus, you can decide whether $L(M)\subseteq L(A)$ and $L(A)\subseteq L(M)$, which amounts to deciding whether $L(A)=L(M)$, and you are done.
> 2 votes

---
Tags: formal-languages, turing-machines
---


# Question
Title: Why apply the assumed decide für HALT to the input and its code?
In the lecture notes I have got in class I have the following proof for the halting problem not being recursive

> 1. Assume $H$ is recursive and TM $M\_1$ decides it.
> 2. Construct $M\_2$ that
>     1. gets input $x$ in $\\{0,1\\}^\*$ and transform it into $x\*code(x)$
>     2. applies $M\_1$ to $x * code(x)$
> 3. if x is in SA (Self Accepting), $M\_1$ halts on $Y$ if x is in SA (Self Accepting), $M\_1$ halts on $Y$
> 4. $M\_2$ decides SA, hence a contraddiction

In this prove, I am confused on what would $x\*code(x)$ correspond to. Is the input followed by the coded input? Why would we want to do so?

# Answer
> 1 votes
Let $H=\\{(\langle M\rangle, x)\mid M, \text{ when given input }x, \text{ halts}\\}$. In other words, the language $M$ consists of all pairs of TM descriptions and words, such that the TM halts on that word.

Let $SA=\\{\langle M\rangle\mid M, \text{ when given its own description, halts}\\}$. You're given the fact that $SA$ is undecidable.

Suppose, to the contrary, that $H$ was decidable, so that there was a TM $M\_1$ such that when given a pair, $(\langle M\rangle, x)$, of a TM $M$, and a word $x$ $$ M\_1((\langle M\rangle, x)) = \begin{cases}\text{accept}, & M(x) \text{ halts}\\ \text{reject}, & M(x) \text{ doesn't halt}\end{cases} $$ We'll use this to build a decider, $M\_2$, for SA, establishing the desired contradiction. Define

```
M2(<M>) =
   if M1((<M>,<M>)) = accept  ; does M halt on its own description?
      return M(<M>)           ; if so, this will always halt
   else
      return reject

```

Now if $M$ halts on its own description, the **if** test will detect that and so we can simulate the action of $M$ on $\langle M\rangle$, be sure it halts, and return the result, either accept or not. If $M$ doesn't halt on its own description, we reject. The upshot is that we'll have built a decider, $M\_2$ for $SA$, so have a contradiction, and hence our assumption that $H$ was decidable, must be false.

---
Tags: computability, turing-machines, undecidability, decision-problem, halting-problem
---


# Question
Title: BCNF Decomposition: Confusion regarding given answer
I encountered the following question:

Given a relation R(A, B, C, D) with the following functional dependencies:
A -\> B, C -\> D, B -\> C.

The BCNF Decomposition of R is:

A) {(A,B), (C,D), (B,C)}
B) {(A,B), (C,D), (A,C)}
C) {(B,C), (A,D), (A,B)}
D) All of the above

According to my understanding the solution should be D) ALL of the above.
This is because for each schema, the condition for BCNF holds as given by this link: http://www.cs.sfu.ca/CourseCentral/354/jpei/slides/UsingBCNF-3NF.pdf (Page 18)

The other two do not preserve some dependencies but in BCNF decomposition it may happen that the dependencies are not preserved.

However, the answer is given as (A). Please can someone explain? Thanks.

# Answer
> 0 votes
For the relation R(A, B, C, D) with the following functional dependencies:

```
1.A -> B
2.C -> D
3.B -> C

```

candidate key = A

The correct way to decompose a relation such that it satisfies BCNF property is following.

The FD 2 and 3 are violating the BCNF property(LHS should be key) i.e to convert the relation into BCNF it is needed to be decomposed.

To decompose this find the FD which violates the BCNF property in our case FD 2 and 3 violates.

Seprate out this FD into a different relation i.e our new relation is

```
R1 = (A,B) with FD A-> B
R2 = (B,C,D) with FD B->C and C->D

```

Again for the R2 the key is B and FD C-\>D violates the BCNF property we further split R2 into R12 and R22

```
R12  = (B,C) with FD B->C
R22  = (C,D) with FD C->D

```

Now the final obtained relation after decomposition is

```
R1 = (A,B) with FD A-> B
R12  = (B,C) with FD B->C
R22  = (C,D) with FD C->D

```

The above relations are the only decomposition of R that satisfies BCNF property.

For more insights refer this http://www.cs.toronto.edu/~faye/343/f07/lectures/wk12/moreBCNF.pdf

---
Tags: database-theory, normal-forms, decomposition
---


# Question
Title: Example of reduction such that it is not many-one reduction while it is not turing reduction
I am reviewing things I learned, and I can't suddenly come up with an example of reduction that is not many-one, but Turing reduction. Can anyone present such an example?

# Answer
A simple example would be a reduction from e.g. $SAT$ to it's complement $\overline{SAT}$, which works as follows: given a formula $\varphi$, you can decide whether $\varphi$ is satisfiable by deciding whether $\varphi\in \overline{SAT}$, and then negating the answer. This is a Turing reduction, since you use an oracle for $\overline{SAT}$ to solve $SAT$.

A similar example can be constructed for HALT and it's complement, if you want decidability, rather than complexity.
> 2 votes

---
Tags: computability, reductions
---


# Question
Title: What is one method used to prove each palindrome is in its own Myhill-Nerode equivalence class?
I understand how you can use a contradiction in regard to a DPDA to show a language has finitely many Myhill-Nerode equivalence classes, but what is the method used to show each string of a language accepting palindromes is in its own Myhill-Nerode class?

Thanks

# Answer
There is no "method". You need to use an ad hoc proof, that for each pair of words $a,b$ comes up with a word $w$ such that either $aw \in L$ and $bw \notin L$ or vice versa. We can assume that $|a| \geq |b|$.

If $b$ is not a prefix of $a$ then $aa^R \in L$ but $ba^R \notin L$, since otherwise $ba^R = (ba^R)^R = ab^R$, implying that $b$ is a prefix of $a$.

If $b$ is a prefix of $a$ then $|b| \< |a|$, since otherwise $b = a$. Let $\tau$ be a letter such that $b\tau$ is not a prefix of $a$ (i.e., if $a = bx$, where $x \neq \epsilon$, let $\tau$ be some letter different from the initial letter of $x$). Then $a\tau a^R \in L$ but $b\tau a^R \notin L$, since otherwise $b\tau a^R = (b\tau a^R)^R = a \tau b^R$, implying that $b\tau$ is a prefix of $a$.
> 2 votes

---
Tags: formal-languages
---


# Question
Title: Need a hint! Karger's algorithm versus Kruskal, spanning tree distribution
Let G = (V,E) be a unit-capacity graph with n vertices and m edges.

Let T denote all the spanning trees in G.

If we run Karger's algorithm, we will get a random spanning tree in T formed by the contracted edges, we denote this distribution of spanning trees by D1.

On the other hand, if we assign a random weight in (0,1) to each edge and compute a minimum spanning tree using Kruskal's algorithm, then another distribution D2 over T is obtained.

Show that the distributions D1 and D2 are identical.

I have no idea where to start. Any hint is helpful!

# Answer
> 7 votes
You should show that at each step, both algorithms select an edge with the same probability distribution. For example, the first edge that is contracted by Karger's algorithm is a uniformly random edge. Similarly, if you choose the weights at random, the first edge that is chosen in Kruskal's algorithm is a uniformly random edge.

What about the next edge? Karger's algorithm selects another uniformly random edge. After removing the first edge, the remaining edges are ordered completely at random. Hence the next edge chosen by Kruskal's algorithm is also uniformly at random.

From the third edge hence, some edge choices would be bad – will close a cycle. However, by design it doesn't happen in both algorithms, and otherwise the chosen edge is uniformly random.

This is the idea of the proof, and it remains to make it formal. That's your task.

---
Tags: graphs, randomized-algorithms, spanning-trees
---


# Question
Title: How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value?
The **max-flow min-cut theorem** states that the value of the maximum flow is equal to the minimum cut capacity.

It is possible that the max-flow and min-cut is equal to $\infty$.

However, reading **Introduction to Linear Optimization by Bertsimas and Tsitsiklis**, I get the impression that the max-flow and min-cut problems are dual to one another.

From duality theory, I know that, if the primal has finite optimal value then the dual has finite optimal value. Also, if the primal has **unbounded** optimal value, then the dual is infeasible and vice versa.

In the case of the max-flow and min-cut problems, how can they both have **unbounded** optimal value ??

# Answer
> 5 votes
Here is an example of this anomaly in linear programs:

$$ \begin{align\*} & \max x & & \min \infty y \\ s.t.\\; & x \leq \infty & s.t.\\; & y \geq 1 \\ & x \geq 0 & & y \geq 0 \end{align\*} $$

The solution to both programs is $\infty$. What goes wrong?

The duality theorem only works when all coefficients are finite. If you go through a proof of the duality theorem you'll see exactly where it fails, and this is a nice exercise.

I should also stress that $\infty$ isn't usually regarded as a legitimate number in these contexts. If we assume all coefficients are real numbers, then $\infty$ is nothing else than a *type mismatch*.

---
Tags: optimization, linear-programming
---


# Question
Title: Pierce's Types and Programming Languages : circular definition of terms?
In Pierce's book, on page 26-27 it is given a definition of terms for a simple language using inference rules.

In the picture below it is marked by red highlighting **the problematic part**.

What is Pierce referring to exactly by the red-highlighted word `term` in this context?

Is he referring to the terms given by the grammar on page 24 ?

In that case I see no point in defining the terms using the inference rules given in the Definition 3.2.2 because he is using the definition of terms already defined by the grammar on page 24, so there is no point in defining it again.

How should one really understand what the red-highlighted word `term` refers to on page 27, so that the definition 3.2.2 makes sense ?

The only way the last sentence would make sense to me if it would be changed to something like this: `... replacing each t by every possible term that has been generated inductively so far.`, meaning that the highlighted word `term` does not refer to the `terms` defined on page 24 but to the terms which already have been generated inductively by the inference rules given in Def 3.2.2.

What do you think ?

The grammar from page 24:

```
t ::=                                   terms:
      true                       constant true
      false                     constant false
      if t then t else t           conditional
      0                          constant zero
      succ t                         successor
      pred t                       predecessor
      iszero t                       zero test

```

From page 26:

> 3.2.2. DEFINITION \[TERMS, BY INFERENCE RULES\]: The set of terms is defined by the following rules
>
> $$\begin{gather} \texttt{true}\in\mathcal{T} \qquad\qquad \texttt{false}\in\mathcal{T} \qquad\qquad 0\in\mathcal{T}\\\\ \frac{\texttt{t}\_1\in\mathcal{T}}{\texttt{succ t}\_1\in\mathcal{T}} \qquad \frac{\texttt{t}\_1\in\mathcal{T}}{\texttt{pred t}\_1\in\mathcal{T}} \qquad \frac{\texttt{t}\_1\in\mathcal{T}}{\texttt{iszero t}\_1\in\mathcal{T}}\\\\ \frac{\texttt{t}\_1\in\mathcal{T} \qquad \texttt{t}\_2\in\mathcal{T} \qquad \texttt{t}\_3\in\mathcal{T}}{\texttt{if t}\_1\texttt{ then t}\_2\texttt{ else t}\_3\in\mathcal{T}} \end{gather}$$

From page 27:

# Answer
Part of your intuition is correct: "terms" really means "the collection of terms generated thus far". I think you will also find in Pierce a definition that makes this explicit on the next page (Definition 3.2.3).

What Pierce is actually doing is giving three equivalent and common ways of presenting syntax. In fact, the first one (page 24) is what you often see in papers and programming language specifications. Definition 3.2.2 is a way of understanding this as an inductive set of rules. And Definition 3.2.3 is a way of understanding the inductive set of rules by explicitly building larger terms from smaller terms.
> 5 votes

---
Tags: formal-grammars, type-theory, induction, typing, types-and-programming-languages
---


# Question
Title: How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar?
Suppose $L$ is an infinite CFL, and $G$ is a grammar with finitely many ambiguous strings which generates $L$. Is it possible to convert $G$ into an unambiguous grammar which also generates $L$? If so, how would I go about doing this? One starting approach I see is to have rules of the form $S \longrightarrow w $ in the new grammar, where $w$ is a string that was ambiguous in the original grammar. I'm not sure; however, how I'd go about modifying the original grammar to a further extent. Of course, we'd like to keep much of $G$ for our new grammar, insofar as $G$ unambiguously generates strings of sufficient length.

# Answer
Here is the skeleton of the proof. I leave it to you to fill in the details.

Let $R$ be a FSA recognizing the set $A$ of ambiguous strings of $G$ (yes, I am generalizing a bit the problem to regular sets of ambiguous words, since it is no harder). Let $\bar R$ be a DFA recognizing the complement $\bar A$ of $A$: $\bar A=\Sigma^\*-A$.

We can use the cross-product construction for intersection of the languages of a CF-grammar and a FSA, applying it to $G$ and $\bar R$ to get a CF grammar $G'$ that recognnizes $L'=L-A$. This grammar $G'$ is not ambiguous, since it has exactly the same parse trees as $G$, up to renaming of non-terminals (and the ambiguous words have been removed). The FSA $\bar R$ has been chosen deterministic to make sure it has at most one accepting computation on any input, and thus does not introduce new ambiguities.

Then, Since the language $A$ is regular, it is easy to produce a non-ambiguous CF (or regular) grammar $F$ that recognizes $A$.

Then, given the two non-ambiguous grammars $G'$ and $F$, generating respectively $L'=L-A$ and $A$ which have an empty intersection, it is easy, with one extra production rule, to produce a non-ambiguous grammar $G''$ that recognizes the union $L'\cup A=(L-A)\cup A=L$.

So the non-ambiguous grammar $G''$ generates the language $L$. QED

That is all very nice, but given some CF grammar G you may not be able to do all this, even when it is actually possible.
> 3 votes

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


# Question
Title: simple lower bound for constructing a Spanning tree
i have to demonstrate that under the assumptions{Bidirectional Links, Total Reliability (no error during the execution), Connectivity, Distincts ids values, Multiple inititators (entities that starts the algorithm} the problems of constructing a spanning tree takes at least $\Omega(m)$ messages, where $m=|E|$

# Answer
> 0 votes
i tried to solve this problem in this way:

Assume that there exists a correct SPT protocol $A$ thatuses fewer than $m$ messages. This means that there is at least one link in $G$ where no message is transmitted. Consider an execution of the algorithm on $G$, and let $e = (x, y) \in E$ be the link where no message is transmitted by $A$.

Now construct a new graph $G^{'}$ from $G$ by removing the edge $e$ and adding a new node $z$ and two new edges $e1 = (x, z)$ and $e2 = (y, z)$. Set $z$ in a noninitiator status ($z$ does not starts the execution of the algorithm). Run exactly the same execution of $A$ on the new graph $G$ : since no message was sent along $(x,y)$ in the original execution in $G$, $x$ and $y$ never send a message to $z$ in the current execution in $G^{'}$ ; and since $z$ is not an initiator and does not receive any message, it will not send any message.

At the end of the alghoritm a tree $T$ should have been constructed, however, $z$ is not part of $T$, and hence $T$ does not span $G$.

in other words $A$ works only if $z$ is in a **initiator** status, therefore $A$ is not correct.

---
Tags: distributed-systems, lower-bounds, spanning-trees
---


# Question
Title: Implement opposite() method to tell if there are two opposite numbers, (x,-x)
> Let a dictionary with the operations `insert()`, `delete()` and `search()`. Each one of them has time complexity of $O(logn)$. Implement (efficiently) `opposite()` operation which return true if there are two opposite numbers in the dictionary (i.e. $5$ and $(-5)$)

I advised to use another data structure.

I thought about a binary search tree. We maintain a binary search tree and for every `insert()` we also insert the item into the tree.

What do you think?

# Answer
Here is what they intended you to do. You keep a counter of the number of opposite elements, which starts at zero. When inserting an element $x$, you insert both the true element $x$ and the dummy element $-x$; if $-x$ was already there, then you increase your counter of opposite elements. Similarly, when deleting $x$ you delete both $x$ and $-x$, and possibly decrease the counter.
> 1 votes

---
Tags: data-structures, time-complexity, asymptotics
---


# Question
Title: Can a solvable problem be encoded in a recursively enumerable language?
Imagine I have a turing machine that can decide on a specific problem using a language. My question is that that problem (that can be decided by a TM M, with language L) can be encoded in a new language that is recursive enumerable.

If yes, this would mean that every solvable problem can encoded in recursive language; if not, a problem can be encoded in a recursive and/or recursive enumerable L and the problem could become semi-decidable for a different language.

Any clarification on this?

# Answer
Almost immediately from definitions, one has:

* A solvable (decidable) problem can be encoded as (not in) a recursive language.
* A semi-decidable problem can be encoded as (not in) a recursively enumerable language.
> 3 votes

---
Tags: turing-machines, decision-problem
---


title: How to write CFG for languages

text:
# Question
Title: How to write CFG for languages
How do you write the CFG for the following language:

{ax by c ax+y}

Is there some formula or rules I need to follow? An explanation will be so appreciated.

What I tried is:

First I broke ax+y into axay which gives:

{ax by c axay}

Then

S ---\> aSa | B
B ---\> bB | c

The problem I am facing now is how to include ay.

# Answer
> 1 votes
As per advice from others:

Rewrite into $a^xb^yca^ya^x$.

Now it is easy to see the nested structure (or symmetry in the exponent)

So we will have

* $S\_1 \rightarrow a S\_1 a$ $|$ $S\_2$
* $S\_2 \rightarrow b S\_2 a$ $|$ $c$

---
Tags: context-free
---


title: Natural language query processing

text:
# Question
Title: Natural language query processing
I am trying to implement a natural language query preprocessing module which would, given a query formulated in natural language, extract the keywords from that query and submit it to an IR (information retrieval system) system.

At first, I thought about using some training set to compute TF-IDF values of terms and use these values for estimating the importance of single words. But on second thought, this does not make any sense in this scenario - I only have a training collection but I dont have access to index the indexed IR data. Would it be reasonable to only use the IDF value for such estimation (is IDF enough to establish weight of a term in general)? Or maybe another weighting approach?

Could you suggest how to tackle this problem? Usually, the articles about NLP processing that I read talks about training and test data sets. But what if I only have the query and training data?

# Answer
> 1 votes
I don't know the relative sizes and the nature of your problem, these details could completely change the view. But generally, if the only thing you have at your disposal is a small set of test documents, I would not recommend using that for term weighting at all. A small set of documents would give you an illusion of coverage, a skewed set of weights that would not accurately cover the domain. If you do have general access to the IR system, though, you could try using the system itself for obtaining statistics by hitting it with random words and recording the number of search results, for example.

---
Tags: natural-language-processing, information-retrieval
---


# Question
Title: Single Source Shortest Path: What does the weights on the vertex and edges tell you?
In MIT's open courseware (http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf), I do not see how computing a set of numbers on the edge and the vertex will produce the shortest path.

Can someone please explain what information I can get by looking at the above example? How can I tell what is the shortest path to where?

# Answer
> 1 votes
In this example, the numbers on the edges are "given" - they are weights of the edges of the graph in which you want to compute the shortest paths from the source vertex S to all other vertices.

The rest of the information on this graph is the *result* of the shortest path computation (though this slide doesn't give the algorithm used to compute it - the algorithm is given in subsequent slides).

The result consists of two parts:

* The numeric value of the shortest distance from S to each other node. Every node is labeled with its shortest distance. E.g. it's 0 for S itself, -2 for C, 8 for D, etc.
* The "shortest paths tree", which allows to reconstruct the actual shortest path to any vertex, not just the length of the path. More on it below.

The actual shortest paths are encoded in a peculiar way, relying on the fact that if you take all edges that participate in at least one shortest path from S to some other vertex, you'll get a tree. Here's why:

Take any vertex - e.g. B. The shortest path from S to B is S-C-A-B. The vertex A is B's "predecessor" ("parent") in this path. For a fixed vertex S, obviously each other vertex has a predecessor (parent). On this picture, "X's predecessor is Y" is denoted as $ X.\pi = Y $.

What's a structure where each vertex has a parent? It's a tree! So we obtain a tree of shortest paths. This tree is a subset of the graph's edges. On your picture, the edges included in this subset are highlighted with red color.

This tree can be used to reconstruct the shortest path from S to any vertex. E.g., for vertex D, its parent is B, B's parent is A, A's parent is C, C's parent is S, so we get S-C-A-B-D.

Note that this tree construction relies on a certain (rather obvious) property of shortest paths: for any vertex, the shortest path to it goes through the shortest path to one of its adjacent vertices.

---
Tags: graphs, shortest-path
---


title: What is the point of finite automata?

text:
# Question
Title: What is the point of finite automata?
Why learn finite automata when Turing machines do exactly the same thing? Turing machines accepts the same languages and more so what's the point?

# Answer
> 17 votes
Turing machines express all computation, so studying turing machines is studying computation in general; theorems that are true about all turing machines are true about all computations. Necessarily, these have to be extremely general and rather vague or weak theorems. If the only thing you know about a computation is that it's implementable using a Turing machine, that's very little knowledge to work with.

Finite automata are a very particular class of computations. Because they are so restricted, you can **do less** using a finite automaton, but you can **say/know more** about one. There are tons of very useful theorems that are only true for finite automata but not for arbitrary computations; algorithms and data structures for working specifically with finite automata. E.g., in practical terms, if you compile a regular expression to a finite automaton, you know for sure that it terminates in linear time on every input, you can optimize that automaton, you can think of very efficient ways to write finite-automata evaluators, seek ways to implement incremental evaluation, etc. - none of these problems are solvable or even make sense for "computations in general".

Think of the difference between turing machines and finite automata as the difference between all natural numbers and prime numbers. How would you answer if someone asked you why do we need to study prime numbers, when we already have the concept of natural numbers?

# Answer
> 9 votes
We bother with finite automata precisely because they *don't* do exactly the same thing as Turing machines. As you say in your second sentence, Turing machines accept the same languages *and more* (my emphasis).

Turing machines are much more powerful. Of course, in many ways, that's a good thing. Why would you ever want to use a less powerful model of computation? Well, in many circumstances, that less powerful model is good enough for what you need. Using the less powerful model means you have certain guarantees. For example, a finite automaton operates in linear time, whereas a Turing machine might take any amount of time or even not terminate for some inputs. This also often makes it easier to prove things about automata than Turing machines.

Automata are also good in teaching terms: you can get students used to the simpler model before moving on to more complex machines such as pushdown automata and Turing machines. Indeed, it's natural to view PDAs as automata with stacks, and Turing machines as automata with tapes.

There are also correspondences with automata and other systems, which are evidence that automata aren't some arbitrary thing. You probably know they're equivalent to regular expressions; they also define exactly the same class of languages as monadic second-order logic.

# Answer
> 1 votes
I will try not to repeat what was well said in previous answers, but I think it may be worth underscoring some points.

When you take a very general problem, it may have no algorithmic solution, it may be undecidable. That means there is no finite way of describing a systematic way of solving the problem in all cases. Typically, questions that you ask about a Turing Machine (TM) are often undecidable (see Rice theorem).

When you restrict your problem to a subclass, to TM with specific properties, then you can find a solution. And if you restrict enough, you may even be able to find efficient solutions. This is actually a restatement of jkff's answer that "*you can do less, but you can say more*". But not exactly, by being able to say more, there are things that you can do on specific problems that you would not be abled to do otherwise.

Since many programming languages are Turing complete, many things that you would like to know about programs are undecidable. This is often a problem as you need the information to do such things as program optimization. You are blocked by the generality of the problem. But sometimes, though undecidable in general, a question may be decidable for a large subset of the general problem. It may even be that the undecidability results from a combination of features of the language that are know to be seldom used. So studying a restricted class of solution may become decidable and yield useful results.

Another point is that a lot of problems map naturally on regular languages or FSA. Then, when you have to deal with such problems, why make things complicated with a too powerful TM, when a simple FSA will do the job. Do you really need a truck to go to the drugstore buy a pack of chewing gum. And FSA are useful and sufficient for many purposes, both practical and theoretical.

Another way to put it is that a FSA is just a TM with specific properties: it never write, and it scans the non-blank part of the tape only once from left to right (actually, all that matters is that it does not write). So whatever is said about FSA is actually simply said about TM having specific properties.

But that is something we do all the time. For example you can study the properties of equilateral triangles. When you do that, you do not keep repeating, *a triangle with thre equal sides*. You make a definition: *an equilateral triangle is a triangles that has three equal sides*, and then you just use the new terminology. Sometimes definition can be more complex, making the convenience undispensable. Well, talking of FSA is the same: a name for a specific kind of TM, so that you can be less verbose when studying it.

Or to be even more mundane. When you say: *on a sunny day I do not take my umbrella*, think of what the sentence would become if you had to replace *sunny* and *umbrella* by their definition or description. Not to mention the other words of the sentence.

# Answer
> 0 votes
A point not made in earlier answers, is that finite automata model real-world computing devices because any device you can really build has only a finite amount of memory.

---
Tags: turing-machines, automata
---


# Question
Title: Does Second chance Page replacement algorithm suffer with Belady's anomaly?
In Second chance Page replacement algorithm(clock algorithm), if all the Reference bits are set to one, then the algorithm behaves just as FIFO.

Considering this case, can we conclude that Second chance algorithm also suffers from Belady's anomaly?

# Answer
This is not true. This is only a special case in once instance of 2nd chance algorithm. All reference bits set to one does not persist for each page that tested for a page replacement. Since LRU does not suffer from Belady's anomaly, and since 2nd chance is an approximation to LRU, then it follows that 2nd chance does not suffer from Belady's anomaly.
> -1 votes

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


# Question
Title: Show there exists a turing machine with the following properties
I'm struggling to understand a question I've been given. The question asks: Let $\psi$ be a boolean formula in $n$ variables. There are $2^n$ different combinations of assigning values to the variables. Consider the problem of deciding whether (strictly) more than $2^{n−1}$ of these assignments satisfy the formula $\psi$. We will call the language that corresponds to this decision problem, $L$.

From this I can tell that if $x\_1, x\_2, ..., x\_n$ are the $n$ variables which can be either true or false. I understand why there would be $2^n$ different assignings for the formula, as each variable can be assigned 1 of 2 values. But then what is $\psi$ exactly, is it an assignment such as $\psi$=($x\_1 \lor x\_2 \lor ... x\_n$). But then the later part of the question doesn't make any sense. Can someone please explain in more detail what it means by "deciding whether (strictly) more than $2^{n−1}$ of these assignments satisfy the formula $\psi$"?

The question is then to show that there exists a turing machine $M$ and polynomials $T$ and $p$, with the following properties:

• For every input $x$, $M$ terminates after at most $T(|x|)$ steps.

• If $x\in L$, then $Pr\_{t∈\small\\{0,1\small\\}^{p(|x|)}}$\[$M$ accepts $\<x, t\>$\] $\>$ 1/2.

• If $x\notin L$, then $Pr\_{t∈\small\\{0,1\small\\}^{p(|x|)}}$\[$M$ rejects $\<x, t\>$\] $≥$ 1/2

Where $Pr\_{t∈\\{0,1\\}^{p(|x|)}}$\[$M$ accepts $\<x, t\>$\] means the probability, for a give $t$ from the set $\\{0,1\\}^{P(|x|)}$, that M accepts the input $\<x,t\>$ is greater than 1/2. This is similar to the definition of bounded error probabilistic polynomial time(BPP), except that the definition for BPP have both equalities as $≥$, so I'm guessing I need to show that the language L is in BPP. But how would I even start the proof to show that he language is indeed in BPP. Also the definition of a language in BPP is not identical to what is mentioned in the question, so maybe there's a different approach to answering the question. Also, I don't need to explicitly find the polynomials $p$ and $T$, but instead argue that they exist.

Any help to assist me with the question would be much appreciated

# Answer
Look again at your definitions. $\psi$ is a formula of $n$ variables, eg. $\psi\_1 = x\_1 \vee x\_2$ or $\psi\_2=x\_1 \wedge x\_2$, on 2 variables.

Now the question asks whether or not there are more than $2^{n-1}$ assignments to $x\_1, x\_2, ...$ that satisfy the formula. In other words, assignments that make $\psi$ evaluate to true. For the above example, $\psi\_1$ has 3 satisfying assignments (out of the $2^2=4$ possible assignments), while $\psi\_2$ is satisfied only by a single assignment (namely, $x\_1=x\_2=\text{true}$). So $\psi\_1 \in L$ and $\psi\_2 \notin L$.

If you understand so far, then finding a probabilistic TM that accepts any formula with the above conditions with probability at least $1/2$ is trivial. I'll let you think about it some more.
> 2 votes

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


# Question
Title: Turing Machine Decidable: What right does the definition have to say what's not in language L?
I'm having trouble understanding the definition of Turing Decidable. The definition goes something like this:

> TM M decides language L iff the strings in L put M into the Accept state and the strings NOT IN L put M into the Reject state

My problem is.. the strings "NOT IN L"? How can the definition be based on what's *not* in L? Shouldn't the definition be more like this?

> TM M decides language L iff the strings L put M into the Accept state or the Reject state.

Then you can divide L into two subsets - those that are accepted, and those that aren't. But they're all *decided* by M, no?

# Answer
> 6 votes
(I'll convert the comment into an answer)

First, definitions:

$L$ is a language, that is, a set of words where each word has a finite length. If all the words that ever exist are denoted as $\Sigma^\*$ then any language is $L\subseteq \Sigma^\*$. Words that are not in $L$ are in a different subset we denote $\overline L=\Sigma^\*\setminus L$. Both $L$ and $\overline L$ can be infinite (i.e., have infinite many words). Still, each word in $L$ or in$\overline L$ is of finite length.

Now, assume that we have a TM that never goes into an infinite loop (such TMs are called *deciders*). If it never goes into a loop, it means that for any input word, it will either halt and accept or halt and reject.

If we used your second definition, then any $L$ will be $L=\Sigma^\*$, since all the words are either accepted or rejected.

So the answer is that the first definition is correct. A decider $M$ (a TM that always halt!) splits the space of all the possible words $\Sigma^\*$ into two disjoint subsets, the words that are accepted by $M$, denoted $L(M)$ and the ones rejected by $M$, denoted $\overline{L(M)}$. Again, $\Sigma^\*=L(M) \cup \overline{L(M)}$, since every word is either accepted or rejected.

# Answer
> 3 votes
You are right that $M$ makes a decision about every string, but this does not put them in $L$. Your second definition would lead to every (decidable) language being the same (any decider *always* ends up in a Reject or Accept state, so by the second definition every decider would decide every language).

To draw an analogy, take for example the language $English$, and the Turing Machine stand-in $Me$. If you present a word to me, I can decide (hopefully!) whether the word is in $English$ or not, but the words that make me say $No$ are not in $English$ - i.e. the language consists only of the words that are in it, it is *not* two sets (those that make me say $Yes$ and those that make me say $No$).

Going back to the maths, this is what the first definition says, but is a more precise manner appropriate for computability: the TM $M$ decides $L$ if for every string $\omega$ it says $Yes$ if $\omega \in L$ and $No$ if $\omega \notin L$.

---
Tags: turing-machines
---


# Question
Title: Is there any algorithm can solve the following equations efficiently?
$$ x\_1 + x\_2 + \cdots +x\_n = c\_1 $$ $$ \frac{x\_1^2}{2} + \frac{x\_2^2}{2} + \cdots +\frac{x\_n^2}{2} = c\_2 $$
$$ \cdots $$ $$ \frac{x\_1^n}{n!} + \frac{x\_2^n}{n!} + \cdots +\frac{x\_n^n}{n!} = c\_n $$

$c\_1,\cdots,c\_n$ are known constants. $x\_1 \cdots x\_n$ are the unknown variables to solve.

# Answer
One way, which is numerically probably a bad idea, is to use Newton's identities. They give the value of the elementary symmetric functions given the power sums, and from the elementary symmetric functions you can construct a polynomial whose roots are the answers to your problem. Let $p\_k = k! c\_k$, and let $e\_k$ be the sum of all $\binom{n}{k}$ products of $k$ variables out of $x\_1,\ldots,x\_n$. Newton's identities state that $$ ke\_k = (-1)^{k-1} p\_k + \sum\_{i=1}^{k-1} (-1)^{i-1} e\_{k-i} p\_i. $$ Using these identities, you can compute $e\_1,\ldots,e\_n$. Now consider the polynomial $$ P = x^n + \sum\_{i=1}^n (-1)^i e\_i x^{n-i}. $$ The unique solution to your equations are the $n$ roots of $P$.

As an example, let's do the case $n = 2$. We have $e\_1 = p\_1$ and $$ 2e\_2 = -p\_2 + e\_1 p\_1 = p\_1^2 - p\_2. $$ The polynomial $P$ is therefore $$ x^2 - p\_1 x + \frac{p\_1^2-p\_2}{2}. $$

For $n=3$ we calculate additionally $$ 3e\_3 = p\_3 - e\_1 p\_2 + e\_2 p\_1 = p\_3 - p\_1 p\_2 + \frac{p\_1^2-p\_2}{2} p\_1 = \frac{2p\_3 - 3p\_1p\_2 + p\_1^3}{2}. $$ The polynomial $P$ is therefore $$ x^3 - p\_1 x^2 + \frac{p\_1^2-p\_2}{2}x - \frac{2p\_3 - 3p\_1p\_2 + p\_1^3}{6}. $$
> 7 votes

---
Tags: algorithms
---


title: Free and bound variables

text:
# Question
Title: Free and bound variables
I am familiar with free and bound variables theory , but while learning I somewhere saw this lambda expression

> ((lambda var ((fn1 var) & (fn2 var))) argument)

From what I have learned it seems to me as `var` is bounded in both `fn1` and `fn2`. But the reference from where the expression is taken says that both `var` are free and hence can be substituted by `argument` while doing *β-reduction* .

Someone please clear my doubt.

# Answer
> 9 votes
In the usual mathematical notation: $(\lambda \color{blue}{x}. (\\& (f\_1 \color{green}{x}) (f\_2 \color{green}{x}))) A$

The two green occurrences of $\color{green}{x}$ in the subterms $f\_1 \color{green}{x}$ and $f\_2 \color{green}{x}$ are bound in the term $\lambda \color{blue}{x}. (\\& (f\_1 \color{green}{x}) (f\_2 \color{green}{x}))$. The binding occurrence is the blue $\color{blue}{x}$.

When evaluation $(\lambda \color{blue}{x}. (\\& (f\_1 \color{green}{x}) (f\_2 \color{green}{x}))) A$ by beta-reduction of the top redex, the result is the substitution of $A$ for the free occurrences of $x$ in the body of the lambda abstraction. If $\\&$, $f\_1$ and $f\_2$ are variables, then the result is simply $$ (\lambda \color{blue}{x}. (\\& (f\_1 \color{green}{x}) (f\_2 \color{green}{x}))) A \to\_{\beta} (\\& (f\_1 A) (f\_2 A)) $$ If $\\&$, $f\_1$ and $f\_2$ are lambda-terms, then they may contain free occurrences of $x$, which need to be substituted. $$ (\lambda \color{blue}{x}. (\\& (f\_1 \color{green}{x}) (f\_2 \color{green}{x}))) A \to\_{\beta} (\\&\[x\leftarrow A\] (f\_1\[x\leftarrow A\] A) (f\_2\[x\leftarrow A\] A)) $$

Note that the notion of free or bound variable is really a free or bound **occurrence** of a variable, in a given term. A variable is often said to be free in a term if it has a free occurrence. For example, in the term $(\lambda \color{blue}{x}. (\\& (f\_1 \color{green}{x}) (f\_2 \color{green}{x}))) (g \\, \color{magenta}{x})$, the green occurrences of $\color{green}{x}$ are bound, and the magenta occurrence of $\color{magenta}{x}$ is free. In the term $\\& (f\_1 \color{green}{x}) (f\_2 \color{green}{x}))$, the two occurrences of $\color{green}{x}$ are free.

# Answer
> 5 votes
## In a nutshell

There are two issues that justify the statement of your reference:

* The free or bound character of a variable depends on how much context you are considering, and whether it contains a binding occurrence of the variable
* A variable may be re-bound within the scope of an existing binding, so that removing that binding does not preclude that some occurrences may still be bound.

## More detailed explanation

There are really several issues, some of which do not seem to be emphasized by Gilles'answer, which is very good and need not be duplicated here for the issues it addresses (as I understand it).

Being free or bound is a property of variable occurrences, not of variables themselves. Note that the occurrence that follows the $\lambda$ (in blue in Gilles'examples) is a binding occurrence, and is neither free nor bound.

The other issue is that, for a given occurrence, being free or bound is dependent on the part of the context you are considering.

If you examine the example: $$\color{purple}{(}\lambda \color{blue}{x}. \color{red}{(\\& (f\_1 \color{green}{x}) (f\_2 \color{green}{x}))}\color{purple}{)}A$$ the $\color{blue}{\text{blue}}$ occurrence of $x$ is a binding occurrence. The $\color{green}{\text{green}}$ occurrences of $x$ are bound by this binding occurrence whenever you consider a context that includes the binding occurrence, such as the whole $\lambda$-expression or just the part between the $\color{purple}{\text{purple}}$ parentheses.

But if you consider a smaller context, abstracting away the part containing the binding occurrence, as for example the sub-expression in $\color{red}{\text{red}}$, the $\color{green}{\text{green}}$ (occurrences of the) variable $x$ are free in this subexpression.

So being free or bound is dependent on the occurrence considered and on the context considered.

But it may be said that variable $x$ is free in some (sub-)expression when it constitutes a context where $x$ is never bound. Note that a variable $x$ can be free for some occurrences and bound for others in the same $\lambda$-expression, depending on the scope of binding occurrences.

The confusion you are confronted with comes from the fact that when you do the $\beta$-reduction, applying the function between $\color{purple}{\text{purple}}$ parentheses to the argument $A$, you replace the whole redex by just the part in $\color{red}{\text{red}}$ where the variable $x$ is indeed free, now that the binding occurrence is removed, prior to making the substitution of $x$ for the arguments.

But the situation could be more complex. There could be several binding occurrences of $x$ as in:

$$\color{purple}{(}\lambda \color{blue}{x}. \color{red}{(\\& (f\_1 \color{green}{x}) (\lambda \color{magenta}{x}.f\_2 \color{green}{x}))}\color{purple}{)}A$$

Now both $\color{green}{\text{green}}$ $x$ are bound, but the first is bound by the $\color{blue}{\text{blue}}$ binding occurrence, while the second is bound by the $\color{magenta}{\text{magenta}}$ binding occurrence.

When you do the $\beta$-reduction as before, you remove as before the $\color{blue}{\text{blue}}$ binding occurrence of $x$ and substitute the now free occurrences of $x$ for the argument. But only the first green occurrence is free, while the second is still bound by the $\color{magenta}{\text{magenta}}$ binding occurrence.

That is why your reference insisted that the variable occurrences were (now) free for being substituted by the arguments. There could also be non free occurrences, as in the example I just gave, despite the fact that a binding occurrence of the variable had been removed.

---
Tags: logic, lambda-calculus, variable-binding
---


title: Some questions about NP / coNP / CSP

text:
# Question
Title: Some questions about NP / coNP / CSP
I need help with the following mock exam questions. True or false?

**1.)** If a non-trivial $(\neq \emptyset, \Sigma^\*)$ finite set is NP-complete, then $P = NP$.

*True. Every finite set is in $P$ and because of the $NP$-completeness every set in $NP$ can be reduced to this set. Is it right?*

**2.)** $NP \subseteq coNP$ $\Leftrightarrow$ $NP = coNP$.

*I don't know if the "$\Rightarrow$" case holds. I only know $P \subseteq coNP$ and $P \subseteq NP$.*

**3.)** For every fixed $k$ the problem $k$-$CLIQUE$ can be modeled as a Constraint Satisfaction Problem.

*I have no idea. We've had $3$-$COLOR$ and $3$-$SAT$ as examples but also the fact that not every NP-problem can be expressed in terms of a CSP.*

Thanks in advance!

# Answer
2) Suppose that $\mathsf{NP} \subseteq \mathsf{coNP}$: in particular, SAT is in $\mathsf{coNP}$, and its complement coSAT, the set of boolean formulas that are not satisfiable, is in $\mathsf{NP}$. But coSAT is coNP-complete, so that we have a coNP-complete language in $\mathsf{NP}$, i.e. $\mathsf{coNP} \subseteq \mathsf{NP}$.

3) This depends on your definition of a CSP, I guess. Following the definition of a non-uniform CSP, the constraint satisfaction problem of a relational structure $\Gamma$ is the set of relational structures $\Delta$ on the same signature such that $\Delta$ homomorphically maps to $\Gamma$. Here, the signature is $\\{E\\}$, where $E$ is a binary relational symbol that indicates adjacency in graphs. Suppose that there exists $\Gamma$ such that $\mathrm{CSP}(\Gamma)$ is the $k$-CLIQUE problem. Then, letting $K\_k$ be the $k$-clique, we have that $K\_k$ homomorphically maps to $\Gamma$. But if $v$ is any vertex of $K\_k$, we have that $\\{v\\}$ homomorphically maps to $K\_k$, and since the composition of homomorphisms is a homomorphism, we have that $\\{v\\}$ has a homomorphism to $\Gamma$, a contradiction since $\\{v\\}$ does not contain a $k$-clique. Thus, the k-CLIQUE problem cannot be represented as a non-uniform constraint satisfaction problem.

Please let me know if the definition I used for the CSP is not the one you are used to!
> 1 votes

---
Tags: complexity-theory, complexity-classes, np, co-np
---


# Question
Title: An infinite language with no infinite RE or co-RE subsets?
Are there any languages that are infinite (that is, they contain infinitely many strings) but which do not have any infinite subsets that are RE or co-RE languages? This seems related to simple sets, but I can't seem to find any examples of languages with these properties.

Thanks!

# Answer
> 5 votes
Let's prove a more general result using diagonalization. Suppose $L\_1, L\_2, \ldots$ is a countably infinite list of infinite languages. Then there is an infinite language $L$ that doesn't contain any of them.

We construct $L$ in infinitely many steps. At each step $t$, we keep a list of words $A\_t$ in the language, and a list of words $B\_t$ outside the language; these will be monotone increasing, that is, $A\_t \subseteq A\_{t+1}$ and $B\_t \subseteq B\_{t+1}$. The lists $A\_t,B\_t$ will always be finite and disjoint, and furthermore $|A\_t|$ will grow without bounds. We can take $L$ to be the union of all $A\_t$.

Let $A\_{-1}=B\_{-1} =\emptyset$. At step $t$, let $B\_t = B\_{t-1} \cup \\{x\\}$ for some $x \in L\_t \setminus A\_{t-1}$, and $A\_t = A\_{t-1} \cup \\{y\\}$ for some $y \notin B\_t$. Now $|A\_t| = |B\_t| = t$.

Step $t$ ensures that $L$ doesn't contain $L\_t$, and at the same time that $|L| \geq t$. Taking $t\to\infty$, we deduce that $L$ is infinite and is not a superset of any $L\_t$.

---
Tags: computability
---


title: Hadoop MapReduce Word Counting Example

text:
# Question
Title: Hadoop MapReduce Word Counting Example
In an example of the application of MapReduce provided by University of Utah, it says that Map() function emits \<"hello", 1\> every time it sees hello where the reduce function counts the number of instances "hello" occurs

My question is if this is the case, why isn't reduce doing \<"hello", {1,1,1,1,1,1,1,1,1,1,1,1...}\>, where each 1 is an instance Map() emits a key,value pair? In the example it wrote something like \<"hello", (3,5,2,7)\>, what does it mean?

Also, why do you need MapReduce to do this? I can just use an linked list on my computer.

Thanks

# Answer
> \[...\] it says that Map() function emits \<"hello", 1\> every time it sees hello where the reduce function counts the number of instances "hello" occurs

Not quite: It appears the mapper reads each file, counts the number of times a word appears, and outputs a single `(word, count)` pair per *file*, rather than per occurrence of the word. The reduce step then sums these. `("hello", 1)` indicates that "hello" appeared once in a given file, `("hello", 3)` indicates three appearances in a file, etc.

In the example for the reduce step, it appears four files were mapped, and that "hello" appeared 3 times in the first, 5 in the second, etc.

> Also, why do you need MapReduce to do this?

Via wiki MapReduce is "for processing parallelizable problems across huge datasets using a large number of computers\[.\]" Meaning, if your task is to count the number of times "hello" appears in four small documents, you likely don't need MapReduce. But if your task is to count the appearances of *all* words that appear in a large set of documents, then the only way to accomplish this is a practically useful time may require distributing across multiple processors.
> 2 votes

---
Tags: algorithms, parallel-computing, cluster
---


# Question
Title: Finding nearest of a list of points on Euclidian plane to a given reference point
**Problem formulation:** Given a list $L$ of $n$ points in the Euclidian plane and a reference point $R$ also in that plane, find a closest point $P\in L$ such that, for all $X\in L$, $|PR|\le|XR|$.

**Aditional constrains:** Trivial algorithm will just iterate all candidate points in $L$, compute their distance to $R$ and select the closest. Complexity of that is $O(n)$, but the number of points may be huge – I need an algorithm that runs in time $O(\log n)$.

Any preprocesing (building data structures etc.) can be done with $L$ but it should run in $O(n\log n)$ time.

**Problem extensions:** In case that there are multiple closest points $P$ with the same distance from $R$ it would be nice if the algorithm identified that and returned all of them.

I will actually need to detect $m$ nearest points ($m$ is much smaller then $n$). I can do that by running algorithm to find single closest point $m$ times, each time excluding previously found points from search. However it would be nice it the algorithm could be extended to find $m$ closest points in one call.

# Answer
You can build a **2d binary search tree** for the points in $L$ and then have closes-point queries done in expected $O(\log n)$ time: (see this presentation by Robert Sedgewick, pp.26-27). However, the worst-case time is still $O(n)$. An example of the worst-case input is the situation when all the points from $L$ lie on a circle and $R$ is the center of that circle.
> 1 votes

---
Tags: algorithms, computational-geometry, euclidean-distance
---


# Question
Title: Why would this Semidefinite Program be Dual Infeasible?
My semidefinite program amounts to two constraints, $L\_1 = 0$ and $L\_2 = 0$ where $L\_i$ are linear functions of my variables $x\_{ij}$ with the additional constraint that the $x\_{ij}$ matrix is positive semidefinite. I see no way that this program would be infeasible, because just setting every variable to 0 would satisfy all the constraints.

I have written the semidefinite program according to SPDA format. In this format, my SDP is the dual program. When I solve it with the software csdp, it tells me that the "dual program is infeasible."

Here is the particular SDP:

```
2
1
11
0.0 0.0
0 1 1 10 1.0
1 1 1 10 .25
1 1 3 10 .25
1 1 6 10 -.25
1 1 8 10 -.25
1 1 9 10 -.5
2 1 2 11 -3.0
2 1 3 11 -4.0
2 1 4 11 1.0
2 1 5 11 1.0
2 1 6 11 -4.0
2 1 7 11 3.0
2 1 9 11 1.0

```

csdp outputs `This is a pure dual feasibility problem.
Iter: 0 Ap: 0.00e+000 Pobj: 0.0000000e+000 Ad: 0.00e+000 Dobj: 0.0000000e+000
Iter: 1 Ap: 1.00e+000 Pobj: 5.6521881e+000 Ad: 9.00e-001 Dobj: 0.0000000e+000
Declaring dual infeasibility.
Success: SDP is dual infeasible
Certificate of dual infeasibility: tr(CX)=1.00000e+000, ||A(X)||=1.38778e-017` \`

# Answer
> 7 votes
The original poster seems to misunderstand the distinction between "primal infeasible" and "dual infeasible."

The output from CSDP shows that the problem is primal feasible ($X=0$ is a primal feasible solution) but that the primal problem is unbounded. By weak duality, the corresponding dual problem is infeasible.

If you just want a primal feasible solution and don't care about the primal objective value, then you can get this in a couple of ways:

1. You can use the "certificate" returned by CSDP. This is a matrix $X$ such that $X$ is positive semidefinite and $A(X)=0$. Any positive multiple of this matrix is a primal feasible solution to your SDP.
2. You can add an additional constraint that causes the objective function to be bounded. A simple choice would be trace(X)=100.

By the way, it's easy to confirm this using another SDP solver such as SeDuMi or SDPT3 or SDPA.

---
Tags: optimization
---


title: How to prove that this is NP complete?

text:
# Question
Title: How to prove that this is NP complete?
I'm trying to prove that if P = NP, then {⟨a, b, c⟩ : a + b = c} (as addition over N) is NP-complete.

I think I managed to prove that it is in NP, but I'm not sure what would be a good NP complete problem to reduce to would be, or what algorithm to use. Any ideas?

# Answer
Your language is in P; try to figure out why. If P=NP, all non-trivial languages in P are NP-complete, and in particular this one.
> 2 votes

---
Tags: complexity-theory, formal-languages
---


# Question
Title: If pref(L) is regular, does that imply L is regular?
I have this exercise for homework:

> Say we have a language `L`. we know that the language `pref(L)` (all the prefixes of `L`, including all the words in `L` itself) is a regular language. Does this imply that the language `L` is regular as well?

I took the NFA of `pref(L)` and divided it (via 2 epsilon transitions from `q0`) to 2 separate NFA's, as 1 defines `L` and the other defines `pref(L)\L`.

What I actually got is a NFA for `L`, which means it is regular.

I am not sure this is the way or if it legal. I'd be glad for another lead.

# Answer
What you say doesn't make sense. How can you operate with a NFA for $L$ if you cant be sure that $L$ is regular?

Try to consider this language $$L=\\{ uu \mid u \in \Sigma^\*\\}$$ This language is not regular, it is not even context-free, which can be shown with the pumping lemma. I think from here you can continue by yourself. What is $\text{pref}(L)$?
> 3 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Question regarding Cook-Levin theorem proof
I know a key part of the Cook-Levin theorem proof (as presented in the book by Sipser) is that given two rows of configurations, if the upper row is a valid configuration of a nondeterministic Turing machine $N$, and every 2×3 window is consistent with $N$, then the second row is either identical with the upper row or follows from it by a transition of $N$.

Would this still remain true if we were to replace the 2x3 window with a 2x2 window?

# Answer
No, it would not. The reason is that the encoding of configurations might change in 3 consecutive places with a single transition. Specifically, this happens with transitions where the head moves to the left.

For example, consider the configuration $aabqcaa$, which means that the tape contains $aabcaa$ and the head is on $c$. Now, assume that we have the transition $\delta(q,c)=\\{(s,d,L)\\}$. So the $c$ should be replaced with $d$, the head should move left, and the state should change to $s$. Thus, the new configuration is $aasbdaa$. You can see that the change is in 3 consecutive places.

Had you only tracked changes is 2x2 windows, you should have allowed (for example) $qc$ to turn to $bd$, meaning that you allow the head to just "disappear".
> 5 votes

---
Tags: complexity-theory, formal-languages
---


title: What is alternative parenthesizations?

text:
# Question
Title: What is alternative parenthesizations?
I'm a person using english as the second language and reading CLRS book at a slow pace due to my poor english. I have a problem with understanding the meaning of the word 'alternative'. In page 303 on CLRS, says:

> we should convince ourselves that exhaustively checking all possible parenthesizations does not yield an efficient algorithm.Denote the number of alternative parenthesizations of a sequence of n matrices by P(n). Since we can split a sequence of n matrices between the kth and (k+1)st matrices for any k = 1,2,...,n-1 and then parenthesize the two resulting subsequences independently, we obtain the recurrence ...(omitted)

What is the word 'alternative parenthesizations'? is this word equivalent to the 'all possible parenthesizations' in the above block quote? searching dictionary for the word 'alternative' is not helpful to me. Thank you in advance.

# Answer
Depending on the context, "all alternative parenthesizations" means either "all possible parenthesizations" or "all possible parenthesizations apart from the one we were just talking about."

The sense of the word "alternative" being used here is "one of two or more available possibilities."
> 2 votes

---
Tags: terminology
---


# Question
Title: What is the practical relevance of textbook mutual exclusion algorithms?
There's been a fair amount of research on mutual exclusion algorithms - e.g. a lot of it is presented in classic textbooks such as The Art of Multiprocessor Programming, where an entire chapter is devoted to them.

I'm wondering what are the practical situations where one might need these algorithms during engineering of a concurrent system, rather than use typical language- and OS-provided synchronization primitives (say, provided by the pthread library)?

I can think of many special cases where I'd imagine the standard primitives are not specifically tuned for them, e.g. "one frequent reader and one infrequent writer", or vice versa, or "exactly one write operation, many readers", etc. - are any of the textbook mutual exclusion algorithms significantly better in practice in such situations?

To put it shortly: Which mutual exclusion algorithms are of practical relevance to an engineer who already has a typical language-provided library of concurrency primitives at their disposal?

# Answer
Answer: none. That's not what those sections of Herlihy and Shavit's The Art of Multiprocessor Programming are about. In the chapters on mutual exclusion Herlihy and Shavit are not giving you alternatives to the `pthread` library, they are showing you how it is *implement* the equivalent of the `pthread` library.

Chapter 2 of Herlihy and Shavit is titled "Mutual Exclusion." It gives a variety of classic algorithms for implementing the equivalent of `pthread_mutex_lock()` with only sequentially consistent shared memory. My answers https://cs.stackexchange.com/a/12632/7459 and https://cs.stackexchange.com/a/30249/7459 discuss the importance of these implementations, and have a pointer to one that is practical for use on machines that have no built-in hardware synchronization operations. (Lamport's 1987 paper in ACM Trans. on Computer Systems).

Chapter 7 of Herlihy and Shavit gives a variety of spin and queue lock implementations of the equivalent of `pthread_mutex_lock()`, and Chapter 8 expands to discuss `pthread_cond_t` (condition variables), `pthread_rwlock_t` (reader/writer locks), and briefly touches on `semaphores`. There may be situations in which `pthread_rwlock_t` could be used as an alternative to `pthread_lock_t` for performance reasons (but usually not) and in Posix you need to use `semaphores` for inter-process synchronization.

Chapters 9 through 16 are mostly discussing applications (various kinds of concurrent containers). Chapter 17 briefly discusses the equivalent of `pthread_barrier_t`.

All that said, Herlihy and Shavit are two of the most vocal proponents of *transactional memory* and a variety of kinds of non-blocking (and wait-free) synchronization. These techniques are intended as *alternatives* to mutual exclusion in certain cases. Herlihy and Shavit sprinkle various non-blocking implementations throughout Chapters 9 through 16, and then go into detail on transactional memory in Chapter 18.

Transactional memory and other non-blocking synchronization techniques are intended to deal with the problem that some poorly designed algorithms require threads to hold their critical sections for a very long time. Transactional memory and truly non-blocking synchronization are not currently practical alternatives in any real situation, but the techniques for transforming blocking data structures into non-blocking data structures are useful in practice for minimizing the amount of time a blocking data structure stays in its critical section. (Often you can reduce the size of the critical section down to just a couple of machine instructions.)
> 6 votes

---
Tags: reference-request, concurrency, mutual-exclusion
---


# Question
Title: Is There a Programming Language That Embraces Globals?
All programming languages have globally defined symbols. While best practices invariably abjure their use as mutable entities the philosophy of what is mutable and what is not mutable is highly context dependent. Technologies like JIT compilation and type inference generate code on the fly based on the context in which symbols are dynamically referenced.

This makes me wonder exactly how far can this be taken. Have languages been researched that are oriented around embracing global references?

For an example of what I'm thinking of, in Perl there is a "local" command that allows you to save the value of a symbol that is global to the current dynamic scope, modify the symbol as though global within that scope, and automatically restore its prior global value upon return. This differs from ordinary concepts of local variables in that the nested dynamic scopes inherit the binding. It also means that all code references, as well as data references, would be potentially dynamic.

I'm sure features other than a Perl-like "local" would be necessary to make it more wieldy (or less unwieldy for programming in the large, as the case may be). An example of a more powerful dynamic scoping feature would be Javascript's "with" statement which allows unqualified references (without the object reference itself being repeatedly specified) to the properties of an object within the "with"'s dynamic scope.

The point here is that there are different ways of attacking the problem of programming in the large and some may be more conceptually clean than others in the sense of Ockham's Razor in that there is no escaping global symbols so we may as well make the best of them.

In more abstract terms, Quine suggested a similarly radical approach, at least in spirit, to applying Ockham's Razor in formal logic's use of the "name":

> “Chief among the omitted frills is the name. This again is a mere convenience and is strictly redundant, for the following reasons. Think of ‘a’ as a name, and think of ‘F(a)’ as any sentence containing it. But clearly ‘F(a)’ is equivalent to ‘(∃x)( a = x & F(x))’. We see from this that ‘a’ need never occur except in the context ‘a =’. But we can as well render ‘a =’ always as a simple predicate ‘A’, thus abandoning the name ‘a’. ‘F(a)’ gives way thus to ‘(∃x)(A(x) & F(x))’, where the predicate ‘A’ is true solely of the object ‘a’.
>
> “It may be objected that this paraphrase deprives us of an assurance of uniqueness that the name has afforded. It is understood that the name applies to only one object, whereas the predicate ‘A’ supposes no such condition. However, we lose nothing by this, since we can always stipulate by further sentences, when we wish, that ‘A’ is true of one and only one thing:
>
> (∃x)A(x) & ~ (∃x,y)(A(x) & A(y) & ~(x=y) )”
>
> “(This identity sign “=” here would either count as one of the simple predicates of the language or be paraphrased in terms of them.)”

PS: Part of the reason I ask this question is that I did a multitasking/multiuser OS on the 8088 back in the mid '80s that had a "push and set" macro that I used extensively to create very compact code that, it seemed to me, ran quite fast. This was a small system -- under 25,000 lines of code -- but it did work well in it specialized function as a 24 user instant messaging/bbs system.

# Answer
> 4 votes
This seems to me (as to some commenters) to be simply dynamic scoping. It was used often in Lisp to change the behavior of system functions to get some extra features, or perform hidden actions such as monitoring of programs. The cost is indeed that large programs may be difficult to manage and maintain. Since then, there was a long battle between static and dynamic scoping, I would guess that static scoping supporters provided techniques to do what was formerly done by dynamic scoping. The book I would look for such techniques is Abelson and Sussman: Structure and Interpretation of Computer Programs.

It is available on the web in different formats, including html and pdf

---
Tags: programming-languages, logic, software-engineering, variable-binding
---


# Question
Title: What is oblivious RAM and how does it work?
Could anybody explain me what exactly oblivious RAM is?

I found the following explanation which makes it kind of clear to me, but I would like to get a sense of the technical aspects:

> Encryption is not always enough to ensure privacy. If an adversary can observe your access patterns to encrypted storage, they can still learn sensitive information about what your applications are doing. Oblivious RAM solves this problem by continuously shuffling memory as it is being accessed; thereby completely hiding what data is being accessed or even when it was previously accessed.

# Answer
> 10 votes
Oblivious RAM is an interface between a program and the physical RAM that when you perform a read or write, does both at the same time on the physical RAM to hide if you are reading or writing. Plus, it shuffles the memory from time to time so that an adversary seeing only accesses to the physical RAM cannot know whetever you accessed the same data twice or accessed two different data. Thus hiding the access patterns to the physical RAM.

Instantiations I know of rely on oblivious sort, which is a way of sorting elements in a list by comparing and eventually swapping elements in an order predefined, that does not depend on the comparison results.

---
Tags: terminology, computer-architecture, security, memory-hardware, memory-access
---