title: Tool/app for learning category theory?

text:
# Question
Title: Tool/app for learning category theory?
Being a programmer I appreciate the errors given by a compiler for a programming language and come to rely on the compiler's error as a safety net.

In learning category theory I would like to have some tool that also acted as a safety net letting me experiment with diagrams and pointing out my mistakes when I make one. Does such a tool/app exist?

I know this is more of a math question, but I am asking here because I am looking for an answer from those with and understanding for computer science.

# Answer
There are at least three encodings of (aspects of) Category Theory in Coq. Approaches using a proof assistant guarantee correctness by design, though I don't know whether they will enhance understand. You'll then have both the proof assistant and Category Theory to learn.

If you want a reasonably introductory, computer science-oriented book, it's hard to beat *Categories and Computer Science* by R. F. C. Walters. His examples are mostly about data types and automata, rather than programming languages and lambdas. *Conceptual Mathematics* by Lawvere and Schanuel is also quite digestable.

One approach combining these two is to use this Coq formalisation with Steve Awodey’s Book. The formalisation covers closely what is in the book. There's also a blog post about it.

That said, Category Theory is tough and its relationship with programming quickly becomes quite distant, and so one needs to rely on one's mathematical background (which is now getting on to be 20 years old).
> 7 votes

# Answer
Please have a look at this blog:

Introduction to Category Theory in Scala

It uses Scalaz libray for category theory. There are some in Haskell.
> 2 votes

# Answer
If you are looking for a tutorial application :

> The Introduction to Graphical Database for Category Theory (GDCT) is a research project at Mount Allison University. It allows for the creation, editing, and storage of finitely presented categories.
> 2 votes

---
Tags: category-theory
---


# Question
Title: When can one use a $O(n)$ time sorting algorithm?
Some sorting algorithms like counting sort/insertion sort can work in $O(n)$ time while other algorithms such as quicksort require $O(n \log n)$ time.

As I understand it, it's not always possible to use the $O(n)$ sorting algorithms. What are those cases when they can not be used?

# Answer
In the comparison model, where all you are allowed to do is to compare two elements, and without further assumptions, we can prove that no sorting algorithm can do better than $O(n\log n)$.

If you want to sort in $O(n)$, you need either a stronger model, or additional assumptions.

For example, if you can bound the range of the numbers you are sorting, you can use bucket-sort, which is $O(n)$ (time).

A different example is spaghetti-sort: if you can implement the $\max$ function over $n$ elements in $O(1)$, then you can sort in $O(n)$.

You see here that different assumptions can allow you to sort in $O(n)$. There is no characterization of exactly which assumptions allow it.
> 7 votes

---
Tags: algorithms, sorting
---


# Question
Title: How to construct this generalized xor without needing an extra vector?
## Operator - Generalized Symmetric Difference

If you take binary xor and generalize it to other radices you can do so by the absolute value of the difference of each element in a radix vector. However this doesn't have the same properties as the binary symmetric differene. The reason is that in throwing away the "sign" of the difference we are unable to reconstruct an operaand given the result and the other as we can in binary xor. So we lose the nice property

ABA = B

However we keep other nice properties like

A0 = A

AA = 0

There is a way to maintain this property. However, as far as I can tell it involves emitting 3 vectors for any result. The first vector is the usual symmetric difference, the other two vectors are binary vectors of equal length to the first that record the sign of the result, one such vector for each order of the operands, on being the binary complement of the other. In this way, an original operand can be recovered, given the result and the other opernad, AND that other operands "sign" vector.

For example :

Say we have 2 base 10 vectors corresponding to the numbers 1137 and 9284, what i s the xor of these two numbers in base 10?

```
        7  3  1  1              4  8  2  9

        4  8  2  9              7  3  1  1

Signed
Result  3 -5 -1 -8             -3  5  1  8

Sign
Vector  0  1  1  1              1  0  0  0

Symmetric
Difference              3 5 1 8

```

Recover 1137 given 8153 and 9284

```
3  5  1  8
+  -  -  -
4  8  2  9

7  3  1  1

```

My question is : is there a better construction of generalized symmetric difference in any radix \> 2 such that we don't need to 'remember the sign' ?

# Answer
> 6 votes
The most common definition of `xor` is $a\oplus b=(a+b)\bmod 2$, on vertices applied to every coordinate seperately of course. In base-10 case, you have to introduce two operations: $a\oplus b=(a+b)\bmod 10$ and $a\ominus b=(a-b)\bmod 10$. (Notice that in base-2 case they coincide). Now you have

$$c=a\ominus b \quad\text{for coding}\quad\text{and}\quad a=c\oplus b \quad\text{for decoding.}$$

---

Actually, you can use $\ominus$ for both operations, just a bit cleverer:

$$c=b\ominus a \quad\text{for coding}\quad\text{and}\quad a=b\ominus c \quad\text{for decoding.}$$

This works because $a=b\ominus c=(b-c)\bmod 10=(b-(b\ominus a))\bmod 10 $ $= (b-(b-a)\bmod 10)\bmod 10=a\bmod 10=a$.

---
Tags: discrete-mathematics, xor
---


# Question
Title: Factorial usage within proof using the pumping lemma
We are going over the pumping lemma in class and we recently went over the following example:

1. Let $$ L = \\{ w \mid w \text{ has a different number of 0s and 1s} \\} $$
2. Consider $$ s = 0^P1^\left(P+P!\right) $$
3. $ s $ can be divided into $ s = xyz $
4. Consider $$ y = 0^m; 0 \leq m \leq P $$
5. Let $ i = \frac{P!}{m} + 1 $
6. $$ xyz = 0^\left(P + \left(i - 1\right)m\right)1^\left(P + P!\right) \notin L $$

Forgive me if the example is not put together well. This example didn't quite get finished in class. Feel free to expand on this if need be.

However, my question is how does one know to use a factorial in the first place when approaching this proof?

# Answer
Let's choose a different word in step 2, say $s' = 0^a1^b$, where $a$ and $b$ depend on $P$ and $a \geq P$ (to force an $y$ that has the form $y=0^m$).

It's important to show that for any length $m, 1\leq m \leq P$ there is no valid division $s' = xyz, y = 0^m$ (valid means it fulfils the conditions of the pumping lemma).

So for every such $m$, we need an $i$ such that: $xy^iz = x0^{im}z = 0^{a-m+im}1^b = 0^{a+(i-1)m}1^b {! \atop =} 0^b1^b$. This means that $m$ must divide $b-a$ **for every $m$**. One number $b-a$ that fulfils this, is $P!$, so e.g. $a=P$, $b=P+P!$, the least common multiple of $1,\dots,m$ is another possible choice for $b-a$.
> 4 votes

---
Tags: pumping-lemma
---


# Question
Title: Finding a '1' cell with a '0' to its right in a binary array
Given an array of size n that holds ones and zeros I need to find an index of a `1` cell that has `0` to his right (in then next cell) there could be more than one pair in a given array, any one of them is fine. The array is not sorted, but we do know that the first element is `1` and the last element is `0`.

The search should be in $O(\log n)$ time. I'm thinking that a binary search variation is the answer but I'm not sure how.

# Answer
> 7 votes
After viewing the original question, it seems that you have an additional piece of information: you know that the first element is 1 and that the last element is 0. This is crucial!

So indeed you can solve it with binary search: first observe that if the first element is 1 and the last is 0, there must be subsequence of the form $1,0$ in the array.

Denote the array by $A\[1,...,n\]$. If $A\[n/2\]=1$, then there is a $1,0$-subsequence in the subarray $A\[n/2,...,n\]$. If $A\[n/2\]=0$, then there is a $1,0$-subsequence in the subarray $A\[1,...,n/2\]$.

So you can use Binary search, which takes $O(\log n)$ time.

---
Tags: algorithms, arrays, search-algorithms, binary-search
---


# Question
Title: Doron ZEILBERGER's P = NP computer proof
In 2009 Doron has published a paper stating "Using 3000 hours of CPU time on a CRAY machine, we settle the notorious P vs. NP problem in the affirmative, by presenting a “polynomial” time algorithm for the NP-complete subset sum problem.". I've been looking for other people's opinions on this but I haven't found anything significant. Has this problem been officially settled? is this a correct solution? I am not able to assess the paper because of my limited knowledge. What do you guys think ?

Paper : http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/pnp.pdf

# Answer
That paper is a hoax. If you look, it just throws numbers around for a *huge* polynomial bound, purports to solve a problem by "Laurent polynomials" without *any* clue on how they relate to the problem, shifts to integrals and estimates them by numerical means "sufficiently precisely" (and that is supposed to give the huge degree polynomial somehow). And nowhere are the 3000 hours of CRAY time to be seen.
> 11 votes

# Answer
It is a sort of joke CS or Google IQ test. It's usually worth checking the semi-official "crank" list for these types of proofs maintained by Woeginger.

> At the end of April 2009, Doron Zeilberger wrote me: \[...\] However, you should add that this was meant as an April Fool's Joke, since apparently, some people didn't get that it was meant as a joke, and while the paper has some valid general statements abouts humans, the "proof" itself is complete gibberish (and of course, intentionally so).
> 6 votes

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


# Question
Title: computability - decidability of a prefix language
For any language $L$ over $\\{0,1\\}^\*$, a language $L'$ can be defined as $\\{ a | ab \in L \text{ for some } b \in \\{0,1\\}^\* \\}$.

If $L$ is decidable, is $L'$ decidable?

I think that $L'$ should be decidable because we can create a Turing machine for $L'$ that will run the decider for $L$ on the input $w$ for $L'$, accept if it accepts, and otherwise will enumerate all the possible strings $b$ and run $wb$ on $L$. Does that make sense?

# Answer
> 2 votes
Pick some self-terminating encoding of Turing machines. (That means that the encoding of one Turing machine is never a prefix of the encoding of another.) Consider the language $L$ consisting of strings $Mn$, where $M$ is an encoded Turing machine, $n$ is interpreted as a number, and $M$ halts within $n$ steps (on the empty input).

Does that answer your question?

---
Tags: computability, undecidability
---


# Question
Title: Formally describing a sensor network language
I have a language for sensor networks (generates C code) and I want to define the formal semantics of it.

The language has this form:

```
{STATE name_state:
EVERY time
SELECT {variable [, variable] ...}
[SENDIF send_condition]
[CHANGEIF change_condition GOTO new_state];
} ...

START IN initial_state;

```
* The initial state of the program is specified by the START IN instruction.
* Each state is defined by the STATE instruction.
* In the specification of each state the clauses EVERY and SELECT are compulsory and the clauses SENDIF and CHANGEIF are optional.
* The CHANGEIF clause is only not specified when there is a single state.

What type of formal semantics is more convenient to use?

# Answer
> 1 votes
In general, axiomatic semantics is the nicest form of semantics, but is difficult to obtain for anything but the most simple languages, and subject of much current research. Denotational semantics is a vague term, if you mean domain theoretic semantics, then I advise against it. In general using operational semantics is easy and natural, especially if you use state-based SOS (structural operational semantics). The fact that you already have a translation into C is a strong indication that this would work in your case, because C can be seen as a state-based formalism.

Indeed your translation into C is a formal semantics of your sensor network language, albeit a painfully detailed one. So I guess you want a formal description that isto omit some level of detail (e.g. integers are 'real' mathematical integers and not some kind of finite modulo arithmetic). For this state-based SOS tends to be ideal.

# Answer
> 2 votes
Backus-Naur form used to be popular for these purposes. Another possibility is Wirth syntax notation. You can find other possibilities in the "see also" section of the article on Backus-Naur form.

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


# Question
Title: Anti-symmetry of polynomial time reductions
I read somewhere that, if $A\leq\_p B$ and $B\leq\_p A$, then it is said that $A\equiv\_p B$. What exactly does this mean? Is it saying that both $A$ and $B$ are the exact same level of complexity?

# Answer
> 7 votes
$A\equiv\_p B$ is by definition $A\le\_p B$ and $B\le\_p A$.

It means that they are in the "exact same level of complexity", but only with respect to polynomial time reductions! For example, if $A\in LOGSPACE$ and $B\in NLOGSPACE$, then trivially $A\equiv\_p B$. But clearly $A$ and $B$ are not in the "same level of complexity".

This is part of a general observation about reductions: A reduction that is computable by a machine that works in $t(n)$ time (resp. $s(n)$ space) is only useful if you use it in classes that are provable at least as strong as $TIME\[t(n)\]$ (resp. $SPACE\[s(n)\]$), and are conjectured to be stronger.

So, polynomial time reduction are used in $NP$ and $PSPACE$, $LOGSPACE$ reductions are used in $NLOGSPACE$, etc.

---
Tags: complexity-theory, reductions
---


# Question
Title: Tasks in which recursion is either the fastest or only way to produce a result
I've just finished studying recursion at university. One thing that stood out for me however was that in both the lectures and in the practical we completed, all the tasks we were asked to do could be performed faster, and in less code, using iterative means.
This was something the lecturer confirmed.

Could somebody please give me some examples of situations when recursion is a better solution than iterative techniques? Additionally, are there any situations in which recursion is the *only* way to sole a problem?

# Answer
> 6 votes
There are no questions which can only be solved with recursion. This is because they can be solved with Turing machines, which don't use recursion.

The set of problems which can be solved with a TM are exactly the same as the ones which can be solved with recursion (or its formal model, the Lambda Calculus).

In particular, if you want to simulate recursion iteratively, the way to do this is to use a data structure called a stack (which simulates the call stack for functions).

As for algorithms that can be solved better using recursion, there are tons. I'm surprised that your recursive versions were longer, as recursion usually leads to less code. This is one of the reasons haskell is gaining popularity.

Consider the algorithm quicksort, for sorting lists. In rough pseudocode, it's as follows:

```
function quicksort(list)
    if length(list) <= 1
        return list
    pivot = first element of list
    lessList = []
    equalList = []
    greaterList = []
    for each element in list:
        if element < pivot, add to lessList
        if element == pivot, add to equalList
        if element > pivot, add to greater list
   sortedLess = quicksort(lessList)
   sortedGreater = quicksort(greaterList)
   return sortedLess ++ equalList ++ sortedGreater

```

where ++ means concatenation.

The code isn't purely functional, but by dividing the list into different parts, and sorting each sublist recursively, we get a very short $O(n\log n)$ sort.

Recursion is also very useful for recursive data structures. Often times you'll have a traversal on trees, of the following form:

```
function traverseTree(tree)
    if (tree is a single node)
        do something to that node
    else, for each child of tree:
         traverseTree(child)

```

# Answer
> 3 votes
Anything that can be implemented through recursion can be implemented through iteration, and vice versa. So there is no task which it is impossible to accomplish without recursion (assuming a programming language that has the usual iterative constructs).

The cost of transforming a recursive program into an equivalent interative one is up to polylogarithmic time in most settings, and close to constant time (depending on the size of the code, but not on the size of the data) in practice. This is because the gist of the transformation from a recursive program to an iterative program is to push a record on a global stack every time a function is called, and pop that record when the function returns. This doesn't make any significant change to running time, other than memory management for the additional stack. So where a recursive program exists, an equally fast equivalent iterative program exists (for reasonable values of “equally”).

For some recursive programs, a transformation to an iterative program can significantly increase the complexity in terms of code maintenance. All that stack management can amount to significant amounts of code, especially to ensure that you have captured the right data in stack records.

A typical example where recursion is natural and avoiding it is cumbersome is tree traversal. Consider a program that manipulates binary trees and must often traverse them. A recursive traversal goes like this:

```
def traverse(tree):
    do_something(tree.node_payload)
    if tree.left_child != None: traverse(tree.left_child)
    if tree.right_child != None: traverse(tree.right_child)

```

An iterative traversal requires explicit stack maintenance — and this is a simplified example which doesn't maintain local data as it traverses the tree:

```
def traverse(tree):
    stack = new_empty_stack()
    stack.push(tree)
    while not stack.is_empty():
       node = stack.pop()
       do_something(tree.node_payload)
        if tree.left_child != None: stack.push(tree.left_child)
        if tree.right_child != None: stack.push(tree.right_child)

```

Exercise: write a recursive program that sums the elements of a tree of integers multiplied by their depth. Write an iterative program that does the same thing.

---
Tags: recursion
---


title: How does interpreting a script work?

text:
# Question
Title: How does interpreting a script work?
Suppose I have a script (`.vbs`, for example) that is stored in a file. How does the code in the file get converted into machine instructions? What is between the vbs file and the processor?

# Answer
"Scripting" languages are typically *interpreted*, not compiled. That means that there will be a program called the "interpreter" for that language, which reads the programs written in the language, and executes them. You can start reading about interpreters from the Wikepedia entry:

http://en.wikipedia.org/wiki/Interpreter\_(computing)

A compiler, on the other hand, *translates* a program in the programming language into machine language, and lets the CPU execute the machine language program. The only reason for compiling instead of interpreting is for *speed*. The CPU can typically execute the translated machine language program about 10-100 times faster than any interpreter. The reason is that the CPU is implemented in hardware. Otherwise, there is nothing that a CPU can do that a program can't.

Interpreted programs runs slow as compared to compiled ones due to the difference in execution process.

Scripting languages are usually used for expressing high-level operations. For such things, the speed advantage of the CPU becomes much less significant. So, interpreting them can be competitive to compiling them.
> 7 votes

# Answer
That depends on a lot of factors. If it is a pure interpreter (like most shells), the interpreter reads each line/instruction, analyzes it, and executes it. If it is a pure compiler, the program (or a part of it) is read in, analyzed, and then the machine language is written out to run later. Many programming languages are implemented by compiling into a fake machine language (like Java's Virtual Machine; Python and Perl does so too, but not so overtly), and the fake machine language is then interpreted.

This is a *vast* area, to get an idea of how a real compiler works a good introduction is Fraser and Hanson's "A Retargetable C Compiler: Design and Implementation", the full code of the compiler is available.
> 3 votes

---
Tags: programming-languages, compilers, interpreters
---


# Question
Title: Equivalence of NFA and DFA - proof by construction
I was looking at the construction proof showing the equivalence of NFA and DFA from Sipser's text. It started by taking number of states of DFA as $\mathcal{P}(Q)$, where $\mathcal{P}(Q)$ is the set of subsets of $Q$.

My doubt is when we construct DFA from NFA, all the subsets may not occur in that DFA. So how could we write that the number of states of DFA constructed is $\mathcal{P}(Q)$.

# Answer
> 4 votes
It is true that this construction may result in a DFA with unreachable states. The general construction begins simply by including all possible states, then adding the appropriate transitions, so typically the resulting DFA won't be the *smallest* DFA that accepts the same language (in terms of the number of states).

An alternative approach is to only add states as you generate the transitions (rather than adding all states at the start). This will give you only reachable states, but even then, this DFA may not be the smallest possible.

Nonetheless both approaches result in a DFA that accepts the same language as the initial NFA.

Thus given an NFA with $q = |Q|$ states, we can always generate a DFA with $2^{q} = |\mathcal{P}(Q)|$ states that accepts the same language as the NFA.

Generating the *minimal* DFA is a slightly different question (but we know that it will have *no more* than $|\mathcal{P}(Q)|$ states).

# Answer
> 4 votes
If you indeed follow the construction in the way you describe, then there might be states which are unreachable from the starting state. That's allowed in a DFA, though you can go ahead and remove them without affecting the operation of the automaton.

---
Tags: automata, nondeterminism, automated-theorem-proving
---


# Question
Title: Is there an efficient test for if an NFA accepts a subset of another NFA?
So, I know that testing if a regular language $R$ is a subset of regular language $S$ is decidable, since we can convert them both to DFAs, compute $R \cap \bar{S}$, and then test if this language is empty.

However, since this requires converting to DFAs, it's possible that the DFAs, and thus the testing algorithm, will be exponential in terms of the number of states in the input NFAs.

Is there a known way to do this in polynomial time? Has this problem in general been proved Co-NP complete?

Note that the problem is in Co-NP since a word accepted by $R$ but not by $S$ would be a polynomial certifier that $R \not \subseteq S $.

EDIT: this is incorrect, as there is no guarantee that such a word would be polynomial in the number of states.

# Answer
> 15 votes
The problem of deciding language containment in NFAs is $PSPACE$-complete. To prove this, it is easy to reduce from the universaility problem for NFAs (testing whether $L(A)=\Sigma^\*$) So, in a way, you have to determinize, but you may do so on-the-fly.

Your observation about co-NP is wrong (but nice). Such a witness can indeed be checked in polynomial time in *the witness*, but the shortest witness itself may be exponential in the length of the input. Since $PSPACE=co-PSPACE$, then deciding non-containment is also $PSPACE$-complete.

To state things more carefully, deciding whether $L(A)\subseteq L(B)$ is $PSPACE$ in the size of $B$ (since only $B$ needs to be complemented), and $NLOGSPACE$ in the size of $A$.

# Answer
> 4 votes
You should have a look at Jean-François Raskin's paper Antichain Algorithms for Finite Automata.

In our experiments, the antichain-based inclusion test performed one or two orders of magnitude better than the "traditionally" approaches.

If I remember correctly, this algorithm is implemented in the libAMoRE++ library.

# Answer
> 3 votes
One of the best, most thorough state-of-the-art and highly optimized, free FSM libraries available online is the AT&T FSM library. It implements "fsmdifference" exactly as you describe, requiring a determinized epsilon-free FSM to do the difference. One idea is to minimize one or both of the FSMs before doing the difference, that may help in some cases. (i.e. determinizing is not the same as minimizing.) This package also has an "approximate" or "greedy" minimization that is designed to be possibly faster than a full minimization.

However, studying similar problems, I believe there is some generalization or construction of FSMs that do not appear in the literature that can help with this problem by avoiding the determinization step, i.e. basically inverting an NFA without creating an additional determinized FSM. The idea is to traverse the NFA edges "in parallel" and keep track of the set of nodes that are part of the current "superstate" (set of states) just like with the standard determinizing algorithm. Then, the NFA complement accepts if and only if the set of current superstate nodes are "all nonaccepting" (in contrast to the determinizing construction which accepts iff "any accepting").

However, I have not seen this written up before and don't see it via a quick online search. There are many references that suggest or imply that the only way to work with the complement of an NFA is to determinize it.

Here are two "nearby" references that might be useful for some ideas. I would be interested to hear of any/others that are "closer". You mention you are working on program verification, which may be a field that has more direct research on the problem.

\[1\] Construction of Intersection of Nondeterministic Finite Automata using Z Notation Nazir Ahmad Zafar, Nabeel Sabir, and Amir Ali

\[2\] Complementation Constructions for Nondeterministic Automata on Infinite Words Orna Kupferman and Moshe Vardi

---
Tags: algorithms, regular-languages, automata, np-complete, decision-problem
---


# Question
Title: How can I argue that $3\mathsf{SAT}\leq_p \mathsf{IndSet}$ is polynomial in time?
Given the reduction $3\mathsf{SAT}\leq\_p \mathsf{IndSet}$ as follows:

How can I argue that it's in polynomial time? I understand how the reduction works, but even though it appears rather trivial, I can't explain why it's efficient.

> To place $\mathsf{IndSet}$ in $\mathsf{NP}$-Hard, we will show $3\mathsf{SAT}\leq\_p \mathsf{IndSet}$:
>
> Given $$\phi=\bigwedge\_{m=1}^{n}(x\_m\vee y\_m\vee z\_m)$$ with $m$ clauses, produce the graph $G\_\phi$ that contains a triangle for each clause, with vertices of the triangle labeled by the literals of the clause. Add an edge between any two complementary literals from different triangles. Finally, set $k=m$. In our example, we have triangles on $x,y,\overline{z}$ and on $\overline{x},w,z$ plus the edges $(x,\overline{x})$ and $(\overline{z},z)$.
>
> We need to prove two directions. First, if $\phi$ is satisfiable, then $G\_\phi$ has an independent set of size at least $k$. Secondly, if $G\_\phi$ has an independent set of size at least $k$, then $\phi$ is satisfiable. (Note that the latter is the contrapositive of the implication "if $\phi$ is not satisfiable, then $G\_\phi$ does not have an independent set of size at least k".)
>
> For the first direction, consider a satisfying assignment for $\phi$. Take one true literal from every clause, and put the corresponding graph vertex into a set $S$. Observe that $S$ is an independent set of size $k$ (where $k$ is the number of clauses in $\phi$).
>
> For the other direction, take an independent set $S$ of size $k$ in $G\_\phi$. Observe that $S$ contains exactly one vertex from each triangle (clause) , and that $S$ does not contain any conflicting pair of literals (such as $x$ and $\overline{x}$, since any such pair of conflicting literals are connected by an edge in $G\_\phi$). Hence, we can assign the value True to all the literals corresponding with the vertices in the set $S$, and thereby satisfy the formula $\phi$.
>
> This reduction is polynomial in time because $\Huge\dots?$

I've looked at many different examples of how this is done, and everything I find online includes everything in the proof except the argument of why this is polynomial. I presume it's being left out because it's trivial, but that doesn't help me when I'm trying to learn how to explain such things.

# Answer
> 7 votes
You are given a formula, and you will construct a graph. You can argue the reduction is polynomial time by analyzing the time you need to construct the graph. The transformation is an algorithm: write each step down, and analyze them. If every step takes polynomial time, you have shown the reduction runs in polynomial time.

Scan the clauses of the formula in time that is linear in the number of clauses. Scan the 3 literals in every clause. Build 3 vertices, with labels corresponding to the literals in a clause. This you can do in constant time, clearly. Once you have built a triangle, add it to your graph. With reasonable assumptions, you can do this in linear time, but details naturally depend on the way you represent your graph. Nevertheless, the time taken will be polynomial.

Finally, you only need to add edges between any two complementary literals from different triangles. Scan your triangles. For every literal in the triangle, scan through every other triangle, and see if there is a complementary triangle. If so, add an edge. This process takes polynomial time; for every triangle you are scanning every other triangle, so think of something quadratic. After every triangle has been scanned, $G\_\phi$ has been built.

---
Tags: complexity-theory, reductions
---


# Question
Title: How to define at least one occurrence of a string between two tokens in bottom up LALR(1) parser grammar
I am trying to define a non terminal symbol in a LALR(1) grammar (with CUP parser). It is requested that

```
the <code> token must appear exactly twice,
while the <hour> token must appear at least once.

```

In the end I came up with this definition:

```
section     ::= hour_l CODE SC hour_l CODE SC hour_l ;
hour_l      ::= /* epsilon */
            | hour_l HOUR SC ;

```

where `SC` is a separator (semicolon) between tokens and `hour_l` is the non terminal symbol for hour's list. This solution has a problem: `HOUR` can be absent, because `epsilon` can be reduced from `hour_l`. Is there a clever solution other than specifying all possibilities or using the semantic capabilities of CUP (ie. putting a counter of how many times `HOUR` is present in `section`)? I'd prefer not to use semantics in order to achieve this; in fact, it seems to me this is syntax related.

Thanks

# Answer
My solution, suggested by a friend, is to use a Finite State Machine. I drew a Deterministic Finite Automata, and $C$ is the final state accepted by this machine:

I then transformed it into a right regular grammar:

```
section     ::= c ;
a           ::= CODE SC ;
b           ::= a CODE SC ;
c           ::= c HOUR SC | b HOUR SC | e CODE SC ;
d           ::= HOUR SC | d HOUR SC ;
e           ::= e HOUR SC | a HOUR SC | d CODE SC ;

```

Hope it helps.
> 2 votes

---
Tags: formal-grammars, parsing
---


# Question
Title: If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular?
Say, $L \subseteq \\{0\\}^\*$. Then how can we prove that $L^\*$ is regular?

If $L$ is regular, then of course $L^\*$ is also regular. If $L$ is finite, then it is regular and again $L^\*$ is regular. Also I have noticed that, for $L = \\{0^p \mid p \text{ is a prime}\\}$, $L$ is not regular, $L \subseteq \\{0\\}^\*$ and $L^\*$ is regular.

But how to show this for any subset $L$ of $\\{0\\}^\*$ ?

# Answer
> 9 votes
Assume that $L$ contains two words $w\_1$ and $w\_2$ such that the lengths of these words, $|w\_1|$ and $|w\_2|$, have no factors in common. Then, we have that the longest word that cannot be formed by concatenating these words has length $(|w\_1|-1)(|w\_2|-1) - 1$ (Frobenius number). That is to say, if there are words in the language whose lengths don't have a common factor, then all words of a certain minimal length are in the language $L^\*$. It's easy to see this is regular since, of necessity, there are a finite number of equivalence classes under the Myhill-Nerode indistinguishability relation.

What if the lengths of all words in $L$ share a common factor? Well, It's not hard to see that in such cases, $L^\*$ is also regular. Simply note that instead of all words whose lengths are greater than some minimal length being in $L^\*$, it will instead be true that all words whose lengths are a multiple of the GCD of word lengths will be in $L^\*$, and no words whose lengths aren't multiples of this GCD will be, and since $(L^k)^\*$ is regular for any integer $k$, $L^\*$ is also regular.

This is pretty informal, but everything you need to formalize this should be here.

# Answer
> 4 votes
The basic idea is that in a language built on a one-letter alphabet, every sufficiently long word is a concatenation of shorter words. So when you take a word $w$ in $L^\*$, i.e. a concatenation of words in $L$, there is a core $\mathring{L}$ such that $w$ is a concatenation of words in $\mathring{L}$. Thus $L^\* = \mathring{L}^\*$. It turns out that $\mathring{L}$ is finite, hence it and $L^\*$ are regular.

Let $M$ be a subset of $L$ and $w$ a word in $L$. $w$ can be expressed as a concatenation of words in $L$ iff $|w|$ can be expressed as a sum of elements of $S \subset \mathbb{N}$ where $S$ is the set of lengths of words in $M$. Thus the problem reduces to expressing an integer as a sum of integers in a particular set (with repetitions allowed): can $|w|$ be expressed as $k\_1 s\_1 + \ldots + k\_m s\_m$ with $\forall i, s\_i \in S$ and $k\_1 \in \mathbb{N}$?

This is a well-known problem in arithmetic, and the answer is that if the coefficients $(k\_i)$ can be negative ($k\_i \in \mathbb{Z}$), $|w|$ is expressible iff it is a multiple of the greatest common divisor of the elements of $S$: $\gcd S$. With a requirement for non-negative coefficients, this still holds for sufficiently large $|w|$.

Consider the infinite sequence $(g\_i)\_{i\ge\min S}$ defined by $g\_i = \gcd (S \cap \[0,i\])$. This is a decreasing sequence of integers (starting with $g\_{\min S} = \min S$, so it is constant after a certain index $j$; and $g\_j = \gcd S$. By the Chinese remainder theorem, every element of $S$ can be expressed as $k\_1 s\_1 + \ldots + k\_m s\_m$ with $\forall i, k\_i \in \mathbb{Z}$ and $\\{s\_1, \ldots, s\_m\\} = S \cup \[0,j\]$. If $x \in S$ and $x \ge s\_1 \cdot \ldots \cdot s\_m$ then you can pick all non-negative coefficients.

Enough arithmetic. Let $\mathring{L} = \\{w \in L \mid |w| \le g\_j\\}$. Every word in $L$ can be expressed as a concatenation of words in $L$ whose length is at most $g\_j$, i.e. $L \subseteq \mathring{L}^\*$. Since we also have $\mathring{L} \subseteq L$, we have $L^\* = \mathring{L}^\*$, which is regular since $\mathring{L}$ is finite hence regular.

---

Alternatively, use the characterization of regular languages in single-letter alphabets.

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


# Question
Title: Prove that 2-Colourability is in L from Undir-Reachability is in L
Let Undir-Reachability be the following problem: given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G?

I need to prove that the 2-Colourability is in L, by knowing that Undir-Reachability belongs to the complexity class L.

I don't know how to start.

# Answer
> 4 votes
Hint: a graph is not bipartite if there is a walk of odd length from a vertex to itself.

---
Tags: complexity-theory, graphs, space-complexity, colorings
---


# Question
Title: Modeling timing characterists of an architecture
I am building a system and I have a couple of architectures in mind. I want to have an idea of which architecture is likely to be most performant (quickest).

I can make different decisions like 1) Do everything in one thread 2) Separate this part into one thread, that part into another thread since it can run in parallel and so on

Instead of actually building the system in two different ways and seeing how it performs, is there a way to quickly model/prototype the system where I can express the above concepts and the times it takes for inter thread I/O etc (of which I have a very good estimate) and use the model/prototype to estimate which architecture is better?

# Answer
> 1 votes
The simple answer is to just build the *simplest* architecture that gives the results you want. You will have lots of problems anyway, making the system more complex than strictly required is just making more work. And a simple architecture is probably more performant than a more complex one, and easier to work with for further analysis.

Once it is running, check if the performance is enough. If it isn't, *measure* where it doesn't is up to the task (programmers are *notoriously* unreliable at estimating that, another reason not to "optimize" before seeing results), *then* go searching for ways of increasing performance. The most gain can be gotten by architecture changes, then selection of algorithms and data structures, and at the very end local changes (but most of those your compiler will make anyway). Independent of the above, a faster machine might be cheaper than the programmer time required to redo the code.

---
Tags: efficiency, software-engineering
---


# Question
Title: Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete
I need to prove that the following problem $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete.

Given a finite set of variables $V$, a finite set of inequalities of the form $x \le y$ (where $x, y \in V$) and a finite set of equalities of the form $x=a$ (where $x \in V$ and $a \in \\{0,1\\}$), is there an assignment of values from $\\{0, 1\\}$ to the variables satisfying all the inequalities and all the equalities?

How can I start to resolve the proof?

# Answer
> 2 votes
Hint: Directed reachability is NL-complete.

# Answer
> 1 votes
Hint: This is 2SAT in disguise.

---
Tags: complexity-theory, graphs, reductions, space-complexity
---


title: Optimal partition of a set of pairs

text:
# Question
Title: Optimal partition of a set of pairs
Suppose we have a set $S = \\{(a\_1,b\_1),...,(a\_n,b\_n)\\}$ where $a\_i \< m$, $b\_i = m-a\_i$, $m \in \mathbb{Z}^{+}$, $m\>2$ and $n$ is an even number greater than $3$. What is the most efficient algorithm to determine if it is possible to partition $S$ into two distinct subsets, $C$ and $D$, of equal size such that

$\sum\_{a \in C} a \> \sum\_{b \in C} b$ and $\sum\_{a \in D} a \> \sum\_{b \in D} b$

or $\sum\_{b \in C} b \> \sum\_{a \in C} a$ and $\sum\_{b \in D} b \> \sum\_{a \in D} a$ ?

For example, if $S = \\{(56,44),(48,52),(43,57),(60,40)\\}$, $C = \\{(56,44),(48,52)\\}$, and $D = \\{(43,57),(60,40)\\}$.

I am considering iteratively matching a pair with the best value of $a$ with a pair with the worst value of $a$. Is there another algorithm?

# Answer
> 2 votes
If I understood well the problem:

$S = \\{ (a\_1, m-a\_1), (a\_2, m-a\_2), ..., (a\_n, m-a\_n),\\; m\>2 $

$\sum\_{a\_i \in C} a\_i \> \sum\_{a\_i \in C} (m - a\_i)$ and $\sum\_{a\_j \in D} a\_j \> \sum\_{a\_j \in D} (m - a\_j)$ is equivalent to

$\sum\_{a\_i \in C} a\_i \> m * |C| - \sum\_{a\_i \in C} a\_i$ and $\sum\_{a\_j \in D} a\_j \> m * |D| - \sum\_{a\_j \in D} a\_j$ is equivalent to

$2 * \sum\_{a\_i \in C} a\_i \> m * |C|$ and $2 * \sum\_{a\_j \in D} a\_j \> m * |D|$ is equivalent to

$2 * \sum\_{a\_i \in C} a\_i \> m * |S| / 2$ and $2 * \sum\_{a\_j \in D} a\_j \> m * |S| / 2$ is equivalent to

$4 * \sum\_{a\_i \in C} a\_i \> m * |S|$ and $4 * \sum\_{a\_j \in D} a\_j \> m * |S|$

Then given an instance of the PARTITION problem $\Pi$, $S = \\{ a\_1, ..., a\_n \\}, \sum a\_i = 2k$

Add two equal big integers $z \>\> k$ such that $z = t * (|S|+2) - k + 1$; the equivalent partition problem $\Pi'$ is $S' = S \cup \\{a\_{n+1}=z, a\_{n+2}=z\\}$, $\sum = 2(k+z)$ i.e. the sum of the elements of the two equal partitions must be equal to $k+z$

Now you can set $m = 4\*((k+z)-1)/|S'|$ which is an integer: $m = 4 * ( k + t\*|S'| - k + 1 - 1)/|S'| = 4 * (t - 1) * |S'|$ and your problem inequalities become:

$\sum\_{a\_i \in C} a\_i \> k+z-1$ and $\sum\_{a\_j \in D} a\_j \> k + z - 1$

And it have a solution if and only if $\Pi'$ has a solution.

---
Tags: algorithms, optimization
---


title: Convert CTL* formula to CTL

text:
# Question
Title: Convert CTL* formula to CTL
I have a CTL\* formula: $\mathsf{EF}\[p\land \mathsf{AX}\[q\ \mathsf{U}\ r\]\]$ but in my application, I am limited to CTL. To my understanding, this formula is no valid CTL and I wonder whether I can transform it (preserving semantic, of course). The CTL\* formula should express "there exists a path on which $p$ holds and from that point, in all subsequent states, $q$ holds until $r$ eventually holds".

Is this correct and is there a way to convert it to CTL?

# Answer
> 2 votes
A somewhat late response:

The formula $AX(p U q)$ is equivalent to the CTL formula $AXA(pUq)$: Consider a state that satisfies the former, then in all the paths from it, after one transition it holds that $pUq$. Thus, in all the paths after one transition, we reach a state from which all the paths satisfy $p U q$, so the state satisfies the latter. The converse is obvious, sine the second formula is harder to satisfy.

So an equivalent CTL formula is $EF\[p\wedge AXA(pUq)\]$.

---
Tags: logic, computation-tree-logic
---


# Question
Title: DFA Minimization: Finding all equivalence classes of $\mathsf{R_L}$ for language $011(0+1)^*011$
How do we find all equivalence classes of $\mathsf{R\_L}$ for a language?

Say I'm trying to look for all equivalent classes for the regular language $\mathsf{L}$ is $011(0+1)^\*011$.

Here's an example they give us in the book http://books.google.com/books?id=VEHYzv0GHt8C&pg=PA73&lpg=PA73&dq=ding+du+example+2.51&source=bl&ots=P8gAls0z7f&sig=HIsMb7rcD3hKZHYzi8fYZsyrLQ8&hl=en&sa=X&ei=5N0nUfSoJ6We2gWOv4HYDQ&ved=0CDMQ6AEwAA

ps The relation $\mathsf{R\_L}$ is an equivalent relation. $\mathsf{R\_L}$ on $\Sigma^\* as:$ $xRy$ iff $(\forall w)\[xw \in \mathsf{L} \Leftrightarrow yw \in \mathsf{L}\]$

# Answer
> 3 votes
You may want to look at Sipser's "Theory of Computation" for a full explanation. Technically, you must first define the problem. What do you mean by "find the equivalence classes"? You probably mean that you want to find a representative of each class, or to find an algorithm that given a word, classifies it to a class.

Probably the easiest way to do so, is to construct a DFA for the language, and then minimize it. By the correctness proof of minimization, the states of the minimal DFA correspond to the equivalence classes.

EDIT: The example in the book doesn't show you how to find the equivalence classes algorithmically. It just shows an example of finding them based on intuition and clever thinking (as you would do with a general mathematical problem). There is no general way to do that.

What the example demonstrates is that if you find these classes, then you can construct a minimal DFA. The interesting point is that the converse is also true.

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


# Question
Title: Proof-sketch on the language accepted by a Turing machine
Let $T$ be a Turing machine whose accepted language is $L(T)$. Let $X$ be another language. How do you approach a proof like $L(T)\subseteq X?$

# Answer
In order to prove that any machine, automaton or grammar satisfies $L(T) \subseteq X$ you have to translate your intuition of how it was designed into hard facts. What is the intended meaning of a certain configuration, how where the states chosen? So you have to divide the operation of the machine into phases. Like, "if the TM is in state $q$ on the left of the tape, it will move right, marking half of the symbols $A$ ending in state $q$ on the leftmost cell used". If the design of the machine is done right, such explanations usually suffice, if they can be easily understood. Otherwise one has to apply induction, on whatever seems interesting (like the remaining symbols $A$).

Let me try to add an example, what I would consider sufficient "proof". A Turing machine deciding the language $\\{ a^{2^n} \mid n\ge 1\\}$. States used $p\_0,p\_1,p\_O,p\_E,\ell,p\_A,p\_R$, accepting state $p\_A$, rejecting $p\_R$. Tape alphabet $\\{a,X,B\\}$, with $B$ for blank. Instructions in the order (state, symbol, new state, new symbol, direction).

We scan the tape from left to right. In each scan we halve the number of $a$'s. When the number of $a$'s on the tape is $1$ we accept, otherwise when the number is odd we reject (and halt), finally when the number is even, we return to the leftmost symbol on the tape.

Start in state $p\_0$, indicating $0$ $a$'s read. Other states $p\_1,p\_E,p\_O$ for single, even, odd number of $a$'s read.

* $(p\_0,a,p\_1,a,R)$, $(p\_1,a,p\_e,X,R)$, $(p\_E,a,p\_O,a,R)$, $(p\_O,a,p\_E,X,R)$, move right, crossing out every second $a$.
* $(p,X,p,X,R)$, for $p = p\_0,p\_1,p\_E,p\_O$, ignore symbol $X$.
* $(p\_0,B,p\_R,B,L)$, $(p\_1,B,p\_A,B,L)$, $(p\_E,B,\ell,B,L)$, $(p\_O,B,p\_R,B,R)$, make decision on reaching the right end of the tape, as explained above.
* $(\ell,\sigma,\ell,\sigma,L)$, $\sigma = a,X$
* $(r,B,p\_0,B,R)$ in state $\ell$ move left to first symbol on tape, ending there in state $p\_0$.

Finally, note we reject on empty tape.
> 5 votes

# Answer
The main approach is to start with arbitrary word $w$ in $L(T)$ and then show that $w$ is also in $X$. In order to do so, you will probably need see the "relation" between $L(T)$ and $X$.

The specifics highly depend on $T$ and $X$, but generally, there are two ways:

1. From the description of $T$ you figure out what $L(T)$ is, and then you can forget about Turing machines - you have two sets $A=L(T)$ and $B=X$ and you need to show $A\subseteq B$ using standard set theory.
2. Analyze the connection between $T$ and $X$, and then show that any word $w$ that the TM accepts must have some properties, that are defined by $X$.

As said, different definition for $T$ and $X$, will change your approach.

Just to complete the answer, let's have two simple examples.
**case 1** Let $T$ be the Turing Machine over $\\{0,1\\}$ that accepts $\\{0,00,000,...\\}$. Let $X=\\{ w\mid w$ has more zeroes then ones $\\}$.
*proof.* Clearly, any word that has only zeroes will have more zeroes than ones, thus $L(T) \subseteq X$.

**case 2** Let $T$ be some Turing machine. Let $X$ be the language accepted by a Turing machine $T'$ that on input $w$, runs $T$ on all the words $u$ of length $|w|$ and rejects only if all of them are rejected by $T$.
*proof.* If $w$ is accepted by $T$ then it must be accepted by $T'$: it cannot be that $T'$ rejects, since $T$ accepts at least in the case where $u=w$ (possibly in other cases aswell). Thus $L(T) \subseteq L(T')$.
> 4 votes

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


title: Evaluation of reverse Polish notation

text:
# Question
Title: Evaluation of reverse Polish notation
We only consider the reverse Polish notation as an arithmetic expression.

Formally, RNP is a sequence consisted of numbers and arithmetic operators: $+,-,\*,/$, and its syntax is: $$\newcommand\RNF{\mathrm{RNF}}\newcommand\num{\mathrm{number}}\newcommand\op{\mathrm{operator}}\RNF=\num\\,\big\vert\\,\RNF,\RNF,\op$$ and its value $$\newcommand\eval{\operatorname{eval}}\eval\num=\num$$ $$\eval\RNF\_1,\RNF\_2,\op=\eval\RNF\_1\ \op\ \eval\RNF\_2$$

The following pseudo code to evaluate $\eval\RNF$ is quoted from K&R:

```
while (next operator or operand isn't empty)
  if (it's a number)
    push it
  else if (it's an operator, say +,-,*,/)
    pop operands
    do operation
    push result

```

The algorithm is somewhat straightforward, but it's not as evident as considered. I found it difficult to formulate a loop invariant for the outer while-loop, and it's quite hard to prove the algorithm through Floyd-Hoare logic.

Through some search work, I found a related question, about the unambiguity of RPN. Unfortunately, I don't think the answer to that question is a rigorous proof.

# Answer
How do you define the semantics of RPN? Ignoring the print commands, I would imagine a recursive definition that, given a sequence of operations, tells you what the state of the stack is like. From this definition it is straightforward to prove the correctness of the algorithm. In order to add prints, the recursive definition should also include the sequence of numbers printed. To add errors, the recursive definition should give either a pair as above or the error symbol.

Edit: Here is how you would formally define the semantics, which in the simplified case are a partial mapping from a sequence of operations to a sequence of numbers (the stack). It is only partial since sometimes arguments might be missing.

The function $F$ is defined as follows. First, $F(\lambda)=\lambda$, where $\lambda$ is the empty sequence. $F(\sigma,n) = F(\sigma),n$, where $\sigma$ is a sequence. If $F(\sigma) = \tau,a,b$ then $F(\sigma,+) = \tau,a+b$. If $|F(\sigma)| \leq 1$, then $F(\sigma,+)$ is undefined. Other arithmetic operations are handled in a similar fashion, only you need to make sure not to divide by zero.

Given the semantics, the proof of correctness is rather boring, and I'd rather not spell it out. The loop invariant is essentially the function $F$.
> 3 votes

---
Tags: algorithms, formal-languages, software-verification
---


# Question
Title: Confusion related to time complexity of fast fourier transform
I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT.

It says that lets say I have a polynomial of degree n-1. I want to evaluate the polynomial at $2n^{th}$ roots of unity. For that I can use divide and conquer rule

I will divide my polynomial into evens and odds i.e,

$A(x) = A\_{even}(x^2) + xA\_{odd}(x^2)$

Now if I want to evaluate A at one of the $2n^{th}$ roots of unity. I can break it into evaluating the $n^{th}$ root of unity at two polynomials $A\_{even}$ and $A\_{odd}$ and then add the results with complexity O(n).

They have shown the results to be O(nlogn). However, I think this is for evaluating the value of the polynomial at one of the roots not all the $2n^{th}$. But the book seems to say it is the total complexity. I am a bit confused.

Can anyone please explain this to me? I am confused

# Answer
If you compute by recursion each unit root at a time, it will indeed be costly. However, observe that when you compute $A\_{even}(\omega\_{n/2}^i)$ and $A\_{odd}(\omega\_{n/2}^i)$, you actually gain two values for $A$. For $i\< n/2$ we have that:

$A(\omega^i\_n)=A\_{even}(\omega\_{n/2}^i)+ \omega\_{n}^i\cdot A\_{odd}(\omega\_{n/2}^i)$

$A(\omega^{i+n/2}\_n)=A\_{even}(\omega\_{n/2}^i)+ \omega\_{n}^{i+n/2}\cdot A\_{odd}(\omega\_{n/2}^i)$

This ability to compute two values using a single computation of $A\_{even}$ and $A\_{odd}$ allows for the divide and conquer approach to reduce the time to $O(n\log n)$.
> 2 votes

---
Tags: algorithm-analysis, fourier-transform
---


# Question
Title: What graph data structure works fastest with Dijkstra's algorithm?
What data structure should I store my graph in to get the best performance from the Dijkstra algorithm?

Object-pointer? Adjacency list? Something else?

I want the lowest O(). Any other tips are appreciated too!

# Answer
Implementing Dijkstra's algorithm with a Fibonacci-heap gives $O(|E|+|V|\log |V|)$ time, and is the fastest implementation known.

As for the representation of the graph - theoretically, Dijkstra may scan the entire graph, so an adjacency list should work best, since from every vertex the algorithm scans all its neighbors.
> 3 votes

---
Tags: algorithms, data-structures
---


# Question
Title: Multithreaded access to a persistent linked list data structure
I previously asked a question about persistent data structures here. After that I came across an article that introduced persistent data structures. I have got a question on the following figure from the same article, where it describes how to implement a persistent linked list:

The author says:

> Inserting a new item into a persistent singly linked list will not alter the existing list but create a new version with the item inserted into it. Instead of copying the entire list and then inserting the item into the copy, a better strategy is to reuse as much of the old list as possible.

Since the two versions (Red and Yellow + Red) have common nodes (specifically, the last three Red nodes), how can one access these two versions simultaneously, for example in a multithreaded application?

# Answer
> 4 votes
Such list is intended to be immutable - the shared nodes will never be written to. There is no problem with several threads reading from the same memory location.

---
Tags: data-structures, concurrency, persistent-data-structure
---


# Question
Title: Confusion related to a divide and conquer problem
I have some confusion related to a divide and conquer problem. Here is the problem

> You’re consulting for a small computation-intensive investment company, and they have the following type of problem that they want to solve over and over. A typical instance of the problem is the following. They’re doing a simulation in which they look at n consecutive days of a given stock, at some point in the past. Let’s number the days i=1,2,...,n; for each day i, they have a price p(i) per share for the stock on that day. (We’ll assume for simplicity that the price was fixed during each day.) Suppose during this time period, they wanted to buy 1,000 shares on some day and sell all these shares on some (later) day. They want to know: When should they have bought and when should they have sold in order to have made as much money as possible? (If there was no way to make money during the n days, you should report this instead.)
>
> For example, suppose n = 3, p(1) = 9, p(2) = 1, p(3) = 5. Then you should return “buy on 2, sell on 3” (buying on day 2 and selling on day 3 means they would have made $4 per share, the maximum possible for that period).
>
> Clearly, there’s a simple algorithm that takes time $O(n^2)$: try all possible pairs of buy/sell days and see which makes them the most money. Your investment friends were hoping for something a little better.
>
> Show how to find the correct numbers i and j in time O(n log n).

**Solution**

> We’ve seen a number of instances in this chapter where a brute-force search over pairs of elements can be reduced to O(n log n) by divide and conquer. Since we’re faced with a similar issue here, let’s think about how we might apply a divide-and-conquer strategy.
>
> A natural approach would be to consider the first n/2 days and the final n/2 days separately, solving the problem recursively on each of these two sets, and then figure out how to get an overall solution from this in O(n) time. This would give us the usual recurrence T (n) ≤ 2T(n/2) + O(n), and hence ￼O(n log n).
>
> Also, to make things easier, we’ll make the usual assumption that n is a power of 2. This is no loss of generality: if n′ is the next power of 2 greater than n, we can set p(i) = p(n) for all i between n and n′. In this way, we do not change the answer, and we at most double the size of the input (which will not affect the O() notation).
>
> Now, let S be the set of days 1,...,n/2, and S′ be the set of days n/2+ 1, . . . , n. Our divide-and-conquer algorithm will be based on the following observation: either there is an optimal solution in which the investors are holding the stock at the end of day n/2, or there isn’t. Now, if there isn’t, then the optimal solution is the better of the optimal solutions on the sets S and S′. If there is an optimal solution in which they hold the stock at the end of day n/2, then the value of this solution is p(j) − p(i) where i ∈ S and j ∈ S′. But this value is maximized by simply choosing i ∈ S which minimizes p(i), and choosing j ∈ S′ which maximizes p(j).
>
> Thus our algorithm is to take the best of the following three possible solutions.
>
> ```
> . The optimal solution on S.
> . The optimal solution on S′.
> . The maximum of p(j)−p(i), over i∈S and j∈S′.
>
> ```
>
> The first two alternatives are computed in time T(n/2), each by recursion, and the third alternative is computed by finding the minimum in S and the maximum in S′, which takes time O(n). Thus the running time T(n) satisfies T(n) ≤ 2T(n/2) + O(n), as desired.

Can anyone explain what's going on here? I didn't get how this algorithm actually works. I know they are dividing the days into first half and second half. But I didn't get this part specially

> Our divide-and-conquer algorithm will be based on the following observation: either there is an optimal solution in which the investors are holding the stock at the end of day n/2, or there isn’t. Now, if there isn’t, then the optimal solution is the better of the optimal solutions on the sets S and S′. If there is an optimal solution in which they hold the stock at the end of day n/2, then the value of this solution is p(j) − p(i) where i ∈ S and j ∈ S′. But this value is maximized by simply choosing i ∈ S which minimizes p(i), and choosing j ∈ S′ which maximizes p(j).

# Answer
What I'd have done is to scan the array of prices, keeping track of the best range seen so far and the best starting point for the range ending here. I.e., when standing at day $k$, know the best range before $k$ (say $i$ to $j$, and its value $b$; and keep track what $l$ is so that the range $l$ to $k$ is maximal, say $B$, and if $B$ is better than $b$ adjust things accordingly. Extend the range to $k + 1$, and repeat.). This algorithm is $O(n)$. But that's just me...

\[This algorithm isn't original, it's from Bentley's "Programming Pearls", where a delicious story on a very similar problem (maximal subrange sum) is discussed from an $O(n^3)$ algorithm down to the given $O(n)$, passing through the $O(n \log n)$ algorithm sketched by OP.\]
> 3 votes

---
Tags: algorithms, algorithm-analysis, divide-and-conquer
---


# Question
Title: first order logic resolution unification
Assuming I have shown part of the knowledge base in the clausal format:

```
[1] p1(banana).

[2] not p1(X) or p2(Y).
[3] p1(X) or not p3(F).

```

... and more rules.

Most of the books, would do something like this:

```
[1,2] {X=banana} p2(Y).

```

and more steps.

First question: is it equally correct to do something like follows:

```
[2,3] {X=X} p2(Y) or not p3(F).

```

and then continue with resolution.

Second question: What if different variables were used in each clause, could I do the same as above, for example we had:

```
[2] not p1(X1) or p2(Y1).
[3] p1(X2) or not p3(F2).

[2,3] {X1=X2} p2(Y) or not p3(F2).

```

Thank you in advance

# Answer
Assuming $X$ here is a variable, rather than an atomic proposition, then first you must specify what is the quantification for 2 and 3. I assume that it should be

$\forall X,Y \neg p1(X)\vee p2(Y)$, and similarly for 3. In this case, what can be done is to replace $X$ and $Y$ with each atomic proposition available, in order to obtain a propositional knowledge base, and work on that.

What you suggest to do with 2,3 is sound only under universal quantification, but if you have only universal quantification, it is useful indeed.

For your second question: the name of the variable means nothing, so your substitution is sound also there. Indeed, the claim $\forall Y, P(Y)$ is equivalent to $\forall Z, P(Z)$. You can first change the names, if it makes you happy :)

I'll remark that usually, in resolution-guided proofs, it is more useful to resolve a concrete expression with a quantified rule. For example, resolving $P(a)$ with $\forall X P(X)\to Q(X)$ in order to obtain $Q(a)$. This is more likely (heuristically) to get you towards the proof of a claim.
> 2 votes

---
Tags: artificial-intelligence, first-order-logic, knowledge-representation
---


# Question
Title: String of minimum length in $\{a, b\}^*$ not in a regular expression
I'm doing an exercise in my book, the question is to find a string of minimum length in $\\{a, b\\}^\*$ not in the language corresponding to the given regular expression.

a. $b^\*(ab)^\*a^\*$

My answer: $aab$

b. $(a^\* + b^\*)(a^\* + b^\*)(a^\* + b^\*)$

My answer: $abab$

c. $a^\*(baa^\*)^\*b^\*$

My answer: $bba$

d. $b^\*(a + ba)^\*b^\*$

My answer: $abba$

I came up with my answers by trial and error. I don't know for sure if these are the shortest possible strings. Is the best method trial and error, or would there be some better algorithmic way?

# Answer
> 11 votes
First, *the* string of minimum length might not be defined properly since it might not be unique.

Here is a way to find a string of minimum length:

1. Convert the regular expression to a nondeterministic finite automaton.
2. Convert the nondeterministic automaton into a deterministic one.
3. Use a breadth first search until you encounter the first nonfinal state (if there is one at all).

# Answer
> 5 votes
your answers look good.

To do this properly, it might helpful to convert the expression into the equivalent language (i.e., using English words to describe it), however, for certain expressions this language will be very complicated.

Another "algorithmic" way is to convert it to a DFA/NFA, and then check all the strings lexicographically, until you find one which is not accepted. The same can be done directly using the regular expression, but this might be somewhat more tricky at times.

---
Tags: formal-languages, regular-languages, regular-expressions, check-my-answer
---


# Question
Title: Data structure and algorithms for a medical diagnosis software
For an academic question, I plan to design a medical diagnosis system. Given a description of symptoms, produce a list of probable diseases (with closeness matching). I'm having some trouble finding papers for getting started. Which algorithms and data structure should I consider?

# Answer
> 3 votes
Machine learning algorithms and techniques are very successful and best practice in this area (clustering and classification techniques could be uses). For example in Machine Learning Techniques for AD/MCI Diagnosis and Prognosis or Medical decision support systems based on machine learning, thesis written by Chih-Lin Chi.

You can use simple records in database as the data model.

# Answer
> 3 votes
The field of probabilistic graphical models is often used for medical diagnosis, and some tools have been implemented. See this example, for a start.

Also see this.

---
Tags: algorithms, machine-learning
---


# Question
Title: CPU Cache is managed by which software component?
CPU caches are used by exploiting temporal and spatial locality. My question is who is responsible for managing these caches? Is this Operating system that identifies a particular access pattern and then manages (i.e store the data in) cache, using low level OS function calls?

# Answer
> 8 votes
The CPU cache handles each and every access to memory, that is just too fast to be under software control. It is entirely built into the hardware, either on the CPU chip itself or on the motherboard.

# Answer
> 13 votes
The CPU caches are operational from the very moment on when the CPU is powered up. Neither the BIOS nor an OS are strictly speaking “necessary” to control the caches. The BIOS and the OS can change cache configuration settings in the CPU but they don’t control the normal operation, this is all built into the CPU itself.

# Answer
> 3 votes
It is totally **depends** on your hardware platform (For example Nios® II provides some instruction for managing caches). You should read the **instruction and assembly** language. Some processor provide you some instructions to manage cache in some level. for example WBINVD provides Write back and flush Internal caches; initiate writing-back and flushing of external caches (or INVD).

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: How to apply the pumping lemma to $\{0^m 1^n \mid 2n \leq m \leq 3n, m,n \geq 0 \}$?
I'm not really sure the how you would go about proving this language isn't regular with the pumping lemma:

$L= \\{0^m 1^n | 2n \leq m \leq 3n, m,n \geq 0 \\}$

Does this indicate that $S = 2$, so we start by by using a string $\geq 2$?

# Answer
For pumping lemma proofs, we have to remember that only strings *longer* than the pumping length are guaranteed to be "pumpable" (if the language is regular). Unfortunately we don't (typically) know what the pumping length is, so we have to work a little more abstractly than picking a fixed length string.

In this case, given pumping length $p$, we can take the string $s=0^{3p}1^{p}\in L$ (i.e. we choose the string where $n=p$ and $m=3n=3p$). Now if $L$ were regular, we'd be able to divide $s$ up into three parts $s=xyz$ where:

* $|xy|\leq p$
* $|y| \> 0$
* $xyz \in L \Leftrightarrow xy^{i}z\in L $ for all $i\in\mathbb{N}$

So with our $s$, we know that $y$ must be a string of $0$'s, as $y$ is non-empty and is a subtring of the first $p$ characters.

Then if we pump *up* (never forget that pumping *down* is also a possibility - consider $0^{2p}1^{p}$) we get the string $s'=0^{3p+|y|}1^{p}$. As $|y|\>0$, clearly $s' \notin L$, which contradicts the pumping lemma, therefore $L$ cannot be regular.
> 2 votes

---
Tags: regular-languages, proof-techniques, pumping-lemma
---


# Question
Title: Grammatical characterization of deterministic context-free languages
Deterministic context-free languages are commonly defined using an *automaton* concept, the (restricted, deterministic) pushdown automaton. To some that is confusing, as the name *context-free* refers to a grammar type.

I seem to remember there exists a characterization of the DCF languages using grammars. In my recollection it used a complicated equivalence on non-terminals. Can anyone provide a pointer to that work?

# Answer
Wikipedia actually gives you the model and points to \[1\] for reference: LR grammars are equivalent to DPDA.

---

1. On the Translation of Languages from Left to Right by Donald Knuth (1965) \[free download\]
> 4 votes

# Answer
Just an additional note of possible use: the PLL(0) grammars == the strict deterministic grammars, perhaps an easier approach for both understanding and practical application. A nice description is in Parsing Techniques, 2nd Edition, pp354-357.
> 1 votes

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


title: Constructing right-linear grammar

text:
# Question
Title: Constructing right-linear grammar
Is the grammar

$\qquad S \to 1A0A \mid 0A \mid \varepsilon$

a right-linear grammar? $A$ is a nonterminal here, $0$ and $1$ are terminals.

I know $0A$ is right-linear but what about $1A0A$?

Trying to construct a right-linear grammar for language $10(0+1)^\*10$.

# Answer
> 4 votes
I'll give some hints as plain text, do try to have a go at solving the questions with this help before revealing the spoilers.

The first part you should be able to answer very easily - check the definition of a linear grammar, how many non-terminals can be on the right-hand side of the production?

> At most one, so this isn't a linear grammar, let alone right-linear.

For the second part, perhaps one way to approach it is to first build an NFA that recognises the same language that the grammar generates, then you can use the transitions of the NFA to generate the transitions of the grammar.

> $S\rightarrow 1A$
> $A\rightarrow 0B$
> $B\rightarrow 1B \\;|\\; 0B \\;|\\; C$
> $C \rightarrow 1D$
> $D\rightarrow 0$
> This grammar is certainly not the only one, but should look something like an NFA for the same language - the non-terminals are states, and $D$ is the accept state.

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


# Question
Title: Finding simpler equivalent regular expressions
I'm doing an exercise from my book that says:

> Let $r$ and $s$ be arbitrary regular expressions over the alphabet $\Sigma$. Find a simpler equivalent regular expression:
>
> a. $r(r^\*r + r^\*) + r^\*$
>
> b. $(r + \Lambda)^\*$
>
> c. $(r + s)^\*rs(r + s)^\* + s^\*r^\*$

The book doesn't cover how to simplify regular expressions, so I searched online and I presumed you would use the algebraic laws for regular expressions. I was able to use these laws to come up with something for part a. only:

a. $r(r^\*r + r^\*) + r^\*$

$r(r^+ + r^\*)+r^\*$

$r(r^+ + r^+ + \Lambda) + r^\*$

$r(r^++\Lambda)+r^\*$

$rr^+ + r\Lambda + r^\*$

$rr^+ + r + r^\*$

I don't know how to approach b. or c., because b. has $(r + \Lambda)^\*$ and c. has $(r+s)^\*$, and I couldn't find how to deal with these. Any hints?

# Answer
> 7 votes
A better approach would be to understand what words do these regular expressions represent. For example, what words are in $(r+\Lambda)^\*$? They look something like $r\_1r\_2 \Lambda r\_3 \Lambda = r\_1r\_2r\_3$, where $r\_1,r\_2,r\_3$ are generated by $r$. It seems that $\Lambda$ isn't making much of a difference. This should help you simplify $(r+\Lambda)^\*$. The same approach works for the other expressions (including the first one, which you haven't simplified completely).

---
Tags: regular-expressions
---


# Question
Title: Are there languages generated by linear grammar which aren't regular?
Are there languages generated by linear grammer which aren't regular?

# Answer
> 4 votes
Of course. Look at the first example on Wikipedia:

$\qquad S \to aSb \mid \varepsilon$

is linear and generates $\\{a^nb^n \mid n \in \mathbb{N}\\}$, a non-regular language.

If you mean left-linear, or right-linear, then no - they are equivalent to REG.

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


# Question
Title: Can P=PSPACE and PSPACE problems be formulated as $\Pi_1$ formula?
To say simply, can PSPACE problems be written as $\Pi\_1$ formula? Or how can these problems be written in terms of (first-order) arithmetic hierarchy?

edit:also currently, by what arithmetic hierarchy formula can P=PSPACE be written?

and what would be the consequence of being able to write P=PSPACE as $\Pi\_1$ formula?

# Answer
> 7 votes
You can get a $\Sigma\_2$ sentence for $\mathsf{P}=\mathsf{PSPACE}$, using the same technique as in the blog post, only replace $SAT$ by $QBF$. I doubt there is a known sentence of lower complexity.

# Answer
> 4 votes
$PSPACE \subset R \subset \text{co-}RE = \Pi\_1$. $PSPACE$ problems are decidable in finite time, since $PSPACE \subset EXP$. Languages in $R$ are decidable by a Turing machine, and $R=RE\cap\text{co-}RE$, and $\text{co-}RE$ is $\Pi\_1$. This implies that any language in $PSPACE$ is also in $\Pi\_1$, so the basic answer to your question is "yes."

If you're also asking about $P$, then the answer is also "yes" because $P \subseteq PSPACE$.

# Answer
> 3 votes
As already answered by sdcvvc, $\mathrm P=\mathrm{PSPACE}$ can be written as a $\Sigma^0\_2$-sentence. On the other hand, if it is equivalent to a $\Pi^0\_2$-sentence (let alone $\Pi^0\_1$), then this fact does not relativize, by the same argument as in https://mathoverflow.net/questions/57348. A combinatorial proof is given in https://cstheory.stackexchange.com/a/16644/6959.

---
Tags: complexity-theory, logic
---


# Question
Title: Why does bubble sort do $\Theta(n^2)$ comparisons on an $n$ element list?
I have a quick question on the bubble sort algorithm. Why does it perform $\Theta(n^2)$ comparisons on an $n$ element list?

I looked at the Wikipedia page and it does not seem to tell me. I know that because of its magnitude it takes a lot of work with large numbers.

# Answer
> 8 votes
Consider the worst case analysis: when the array is completely sorted, but from largest to smallest. In this case, bubble sort will make $n-i$ swaps in iteration $i$ (and in particular, there will be a swap in every iteration), and repeat that for $n-1$ times. This gives a total runtime of $(n-1)^2=\Theta(n^2)$.

Observe that even under some optimizations of the naive bubble sort, the runtime is still ${n\choose 2}=\theta(n^2)$.

# Answer
> 7 votes
I have to disagree slightly with what Shaull said, although it still comes out to the same big-theta run time. It is true that the first element in a reversely sorted list will have n-1 comparisons, but each suqsequent element will have one less. Leading to $\sum\_{i=o}^{n-1} i = \frac{n(n-1)}{2}$ number of comparisons, which still comes out to $\Theta(n^2)$ number of comparisons.

---
Tags: algorithms, algorithm-analysis, sorting
---


title: Why is MAX-2SAT not in P?

text:
# Question
Title: Why is MAX-2SAT not in P?
> Max-2-SAT is defined as follows. We are given a 2-CNF formula and a bound k, and asked to find an assignment to the variables that satisfies at least k of the clauses.

I can understand the trick used to prove 2-SAT is in P. You use get a contradiction by using unit propagation. But, I was wondering why does MAX 2-SAT escape this.

Also, I find it hard to believe this is NP-complete. Certainly, what is the problem that causes it to blow up.

Why wouldn't an algorithm like this work. Given a 2-SAT expression. Find it's length, which we can do in P. Need to check if there is at least k of the clauses.

So we just check $\binom n k$ posibilities and run like Horn algorithm on each sub expression of the n 2-SAT expression. Surely, where is the problem as we are just running a P algorithm a polynomial amount of time.

So I'm very confused. Sort of similar problem I have factorization and if that is in P or NP.

# Answer
Observe that the expression ${n\choose k}$ may be exponential in $n$ (e.g. if $k=n/2$).

Factorization is surely in NP. We don't know whether it is in P or not. This is a major open question. The fact that factorization is in BQP gives evidence that it might not be NP-complete (as other NP complete problems are not known to be in BQP)
> 6 votes

---
Tags: complexity-theory, np-complete, satisfiability
---


# Question
Title: applying CTL/LTL model-checking on some system
I apologies if my title is vague, I'm trying to apply CTL/LTL model-checking on some system written in java, however, I still don't understand how to reach a result using either of the approaches mentioned. Do I model my LTS/write specification and use a tool like SPIN to validate that or? I'm mainly looking for a point at a direction that will help me in making a start.

Again sorry but I made this thread after so much frustration searching for an explanation to my problem.

Thank you

# Answer
I'm pretty sure that you need your system to be designed in Promela, rather than Java. You then input the system in Promela, and the specification in LTL (or CTL) to SPIN, which outputs a C code for a model checker for the specific instance.
> 2 votes

---
Tags: concurrency, model-checking, computation-tree-logic, software-verification
---


# Question
Title: What is the complexity of this matrix transposition?
I'm working on some exercises regarding graph theory and complexity. Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically I just have to give an algorithm to transpose an $N \times N$ matrix.

My first thought was to loop through all rows and columns and simply swapping values in each of the $M\[i,j\]$ place, giving a complexity of $O(n^2)$. But I immediately realized there's no need to swap more than once, so I can skip a column every time e.g. when I've iterated over row $i$, there's no need to start iteration of the next row at column $i$, but rather at column $i + 1$.

This is all well and good, but how do I determine the complexity of this? When I think about a concrete example, for instance a 6x6 matrix, this leads to 6 + 5 + 4 + 3 + 2 + 1 swaps (disregarding the fact that position $\[i,i\]$ is always in the right position if you want to transpose a $N \times N$ matrix, so we could skip that as well). This looks a lot like the well-known arithmetic series which simplifies to $n^2$, which leads me to think this is also $O(n^2)$. There are actually $n^2/2$ swaps needed, but by convention the leading constants may be ignored, so this still leads to $O(n^2)$. Skipping the $i,i$ swaps leads to $n^2/2 - n$ swaps, which still is $O(n^2)$, but with less work still.

Some clarification would be awesome :)

# Answer
The sequence you (correctly) identified sums up to $\frac{n(n-1)}{2}=\theta(n^2)$, which gives the runtime you were looking for.

I'm not sure what you are referring to by "leading constants". Do you mean you can ignore e.g. $1+2+3$ ? sure, but that will reduce $6$ from the complexity, which is clearly meaningless. On the other hand, you cannot ignore $f(n)$ leading constants for any $f(n)=\omega(1)$, so there is really no point in ignoring them altogether.
> 7 votes

# Answer
You can also "transpose" a matrix in $O(1)$ time and space. Maintain a bit $t$ for your matrix $M$. Whenever $M$ is transposed, flip $t$. Now, consider accessing an entry in $M$. If $t$ is set to true, return $M\[j,i\]$ instead of $M\[i,j\]$. This trick is arguably cheating, but not always is the matrix actually needed to be transposed. This might work nicely depending the situation.
> 9 votes

---
Tags: graphs, time-complexity, algorithm-analysis, linear-algebra, adjacency-matrix
---


# Question
Title: Closure of regular Language - Transition Function : Sipser Proof
I was going through construction proofs for closure of regular languages under union, star and concatenation operation in the book: "Introduction to Theory of Computation" by Michael Sipser.

I have doubts regarding how he wrote the transition function.

When $Q \in F\_1$ and $a=\epsilon$ he wrote $\delta\_1(q,a) \cup \\{q\_2\\}$. I couldn't understand why its so. When the input is epsilon, the state moves to $q\_2$ and what is the need for writing that $\delta\_1(q,a)$

Also if that is so, the $A^\*$ example he wrote for the transition function $\\{q\_1\\}$ only when $q=q\_0$ and $a=\epsilon$

# Answer
> 2 votes
The idea is that whenever $A\_1$ reaches an accepting state, it "guesses" that this is a good place to split the word, and run the second part in $A\_2$. But maybe this guess is wrong? There are many ways to split a word, and you only need one such splitting to work.

As an example, consider the languages $L\_1=(a+b)^\*a$ and $L\_2=b(a+b)^\*$. Now consider what would happen in your suggestion with the word $aab$. After reading the first $a$, $A\_1$ will be in an accepting state, so it will move to the initial state of $A\_2$, and upon reading the second $a$, will move to a rejecting sink.

However, as Sipser suggests, $A\_1$ may continue using $\delta\_1$ for the second $a$ as well, and only then move to $A\_2$.

Same goes for the construction for Kleene star.

---
Tags: automata, proof-techniques, finite-automata, nondeterminism
---


# Question
Title: Proving non-confluency and adding an equation to make it confluent and terminating
I currently have a system that has `{f(a) = b, f(f(x)) = x}` (part of an exam question \- look at page 5 - exercise 1).

To start off with proving non-confluency, I am thinking along these lines:

```
f(f(x)) and f(a) can be unified by using {a -> f(x)}.

```

Then we can rewrite:

```
f(f(x)) = x                 [eq.1]
f(f(x)) = b                 [eq.2]

```

The above two cannot be reduced any further, and do not have any common ancestor or successor. Therefore the system is not confluent.

To make this confluent, we can add a third equation to the system:

```
x = b

```

This way, the equation will both be confluent and terminate. Another alternative would be:

```
f(x) = b

```

Is there anything I have missed? Or is this pretty much the gist of it?

# Answer
> 3 votes
I do not think $f(f(x))$ and $f(a)$ can be unified. You can not map constant $a$ to the term $f(x)$.

My example would be $f(f(a)) = f(b)$ while otherwise $f(f(a)) = a$.

It seems the equation $x=b$ maps all terms to $b$. That is too much. I would add $f(b) = a$. This leaves two classes of terms, those equivalent to $a = f(b) = f(f(a)) = \dots$ and those equivalent to $b = f(a) = f(f(b)) = \dots$

Here, $a=a$ and $b=b$ and never the twain shall meet ...

# Answer
> 4 votes
The notion you are looking for is that of **critical pair** (see the wikipedia entry for instance). The idea is to find the "most simple" term which allows *both* rewrite rules to be applied. In this case the rewrite rules are:

$$ f(f(x))\rightarrow x$$ $$ f(a) \rightarrow b$$

To find a critical pair, you look for the most general (in a precise sense) instance of the variables on the *left-hand side* which allow one term to be the (non-trivial) subterm of another. In this case, we can instantiate $x$ to $a$ and obtain

$$ a\leftarrow f(f(a)) \rightarrow f(b)$$

This is a *most general* instantiation: we can't apply both rules if $x$ isn't sent to $a$. The equations you gave imply $a = f(b)$. To obtain a confluent rewrite system, we therefore need to add one of two rules:

$$ a \rightarrow f(b)$$ or $$ f(b)\rightarrow a $$

Note that either rule will not make *more* terms equal, as the equality already holds! We can choose either rule to add to our system, but it is tempting to add the second one, as it seems more "computational". Now you have made your critical pair harmless: $f(f(a))$ rewrites to $a$ regardless of our choice of rule applications.

But we are not done! We have a *new* critical pair:

$$ b\leftarrow f(f(b))\rightarrow f(a)$$

However that critical pair is harmless, as both sides reduce to $b$.

Now every critical pair is harmless, and so we have verified the property of local confluence. This by itself is not enough to have confluence! However in your case, you have the additional property of **termination**: no term has an infinite rewrite sequence. This, in combination with local confluence, implies confluence, thanks to Newman's lemma.

Note that this whole approach (find critical pairs, add rewrite rules, check for termination, repeat) can be made systematic, to attempt turning any rewrite system into a terminating one; it is often called Knuth-Bendix completion.

---
Tags: logic, proof-techniques, semantics, term-rewriting
---


title: ML - Type Interface

text:
# Question
Title: ML - Type Interface
From my recitation class -

Can you please explain

* why does operator $"+"$ signature is $ int \rightarrow (int \rightarrow int)$ ?
* How does this graph is build ?
* And what is mean $t=u \rightarrow s$ ?

Thanks in advance .

# Answer
ML functions take a single argument. There are two common techniques to pass two arguments to a function.

* One is to create a pair (2-tuple) `p = (x, y)` and apply the function to the pair; the type of the function is then `('a * 'b) -> 'c`.
* The other approach is to make a function that takes one argument and returns a function that receives the second argument and does the work. This approach is what is done for `+` here and is called currying. The function then has the type `'a -> ('b -> 'c)`. Since this is common, the `->` operator on types is chosen to be right-associative, so `'a -> ('b -> 'c)` can be written `'a -> 'b -> 'c`.

---

The graph, and the derivation on the left, present a simple approach to ML type inference by unification. The first steps are with the atomic subexpressions: `2 : int`, `+ : int -> (int -> int)`, and so on. Next, building on, we have the subexpression `plus 2`, which is an application; the types of `+` and `2` must be unified with $p \to q$ and $p$ for some $(p,q)$, which leads to $p = \mathrm{int} \to \mathrm{int}$ and $q = \mathrm{int}$ and the type of `(plus 2)` is $\mathrm{int}$. The derivation on the left shows the type inference for $(\lambda x. ((+ \\: 2) \\: x))$ from the types of $(+ \\: 2)$ and $x$.

The graph represents the unification steps (with some trivial steps for atomic subexpressions omitted). Four variables $r$, $s$, $t$, $u$ are created to designate the type of each of the non-atomic subexpressions. The straight lines show the expression tree. The curvy line links the occurrence of the variable $x$ with its binding site.
> 3 votes

---
Tags: programming-languages, functional-programming, type-inference, type-checking
---


# Question
Title: Why can the state space of the 15 puzzle be divided into two separate parts?
I am trying to understand the proof here of why the state space in 15 puzzle is divided into two separate parts, but the explanation is complicated for me.

Could someone please explain it in simpler terms? I have been struggling with this for days :(

# Answer
Perhaps the simplest way to understand the proof is by the idea of a *conserved quantity* : find some quantity that can be derived from a configuration and show that every move preserves that quantity. A static version of the idea is found in the following old puzzle:

> Remove the northeast and southwest corner squares from a standard 8x8 checkerboard. Can the remaining 62 squares be tiled using 31 dominos?

Here, the parity principle is simple: each domino takes up exactly one black and one white square on a checkerboard, so any shape that can be tiled by the dominos has to have exactly as many white squares as black. Since the 62-square shape has 32 squares of one color and 30 squares of the other, there's no way of tiling it.

The conservation principle for the 15-puzzle is a bit more complicated, but it's fairly close to this: it's also a parity principle. Let's number the blank square '16' for the time being and imagine it being filled in; then we can talk about the state of the puzzle as a *permutation* of the numbers (1...16). Now, given an arbitrary permutation of the numbers (1...$n$), we can count how many pairs of numbers we have to swap to return all the numbers to their 'original place'. There are many different possible sets of swaps that can be made - for instance, if you have the permutation (3, 2, 1) you can get back to (1, 2, 3) by either swapping the first and third positions (3 with 1) or by swapping the first and second positions (3 with 2), then the second and third positions (3 with 1), then the first and second positions (1 with 2). (The minimum number of swaps that need to be made is called the number of *inversions* of the permutation, and it's an interesting quantity in its own right, but that's not important here). However you swap numbers around, though, the total number of swaps will either always be odd (like it is for (3, 2, 1)) or always be even; we call this number the *parity* of the permutation.

Now, going back to the fifteen puzzle: every move is to swap the blank square (the one we've labeled as '16') with some other square, one unit away from the blank square's current position. This means that a swap always comes with a move of one square - so if you consider the quantity 'total number of swaps I have done' + 'moves the 16 is away from its home square', then this quantity will always be even. In particular, when the 16 is back at its home square (0 moves away) then the overall number of swaps that's been performed must be even. This means that the *parity* of the permutation of the numbers (1..16) corresponding to our resulting position is always even. But now imagine the position of the original puzzle where the 14 and 15 have exchanged places; the 16 is at home but there's been only one 'swap' made. Since this is an odd number of swaps rather then an even number, it can't possibly be reachable from the base configuration.

There's one more minor catch: this shows that there are at *least* two categories that 15-puzzle positions can fall into, but it doesn't show that there are *only* two. For that, a slightly more complicated result is needed: namely, that any even permutation can be decomposed as a product of what are known as *3-cycles* (i.e. swaps $a\rightarrow b\rightarrow c\rightarrow a$). I won't try to prove this here, but the simplest proofs work algorithmically - similar to how bubble sort shows that every permutation can be generated by swapping only adjacent elements. With this result in hand, though, it's easy to get any even permutation: we can get an arbitrary 3-cycle by moving our three elements into positions 11, 12, and 15 on the puzzle (with the blank square in position 16, of course), and then moving the blank square Up, Left, Down, Right - you can convince yourself that this motion cycles the three elements. Once we've done this, we just *undo* the same motions that got the three elements into those positions, leaving the final positions of all the other elements unchanged from their starting positions. This way of getting an arbitrary 3-cycle, along with the theorem allowing any even permutation to be expressed in terms of 3 cycles, then gives a way of getting every reachable (i.e., corresponding to an even permutation) position.
> 8 votes

---
Tags: artificial-intelligence, search-algorithms
---


# Question
Title: Count unhappy numbers in a large interval
> An unhappy number is a number that is not happy, i.e., a number $n$ such that iterating this sum-of-squared-digits map starting with n never reaches the number 1.

For example, $23\rightarrow 2^2+3^2 = 13 \rightarrow 1^2 + 3^2 = 1$, so $23$ is a happy number. But, number $2$ is not and you can verify it.

The problem around my question (from 2010 acp icpc problem set) is to count unhappy numbers in an interval $\[\textrm{lo}, \textrm{hi}\]$. I'm looking for an algorithm that is practical for $\textrm{hi}$ up to $10^{18}$.

How can I write an algorithm for this problem, efficient and correct?

I know that the solution is with dynamic programming, but I don't know how can I get it.

My approach when I read the problem was use a backtracking to mark all numbers in the interval, like a dfs, and see that when you're processing a number and got the result, you should mark all numbers with form permutations of digits for the initial number. Then, I thought that a backtracking approach is faster. But this is not enough for contest, because the interval is $\[1, 10^{18}\]$ so, clearly dynamic programming is the way.

# Answer
I suggest you to start reading this Wikipedia page for an explanation, and then select from Rosetta code an implementation in one of the programming languages you know and to study it. Many algorithms are either based on caching or detecting the loop 4, 16, 37, 58, 89, 145, 42, 20, 4, ...

A dynamic programming solution, implemented in Haskell, is available here.

**EDIT**

The C source code available here uses the GNU GMP library to test for happiness of very large numbers. You can use it to test far beyond $10^{18}$, assuming you have enough memory. The code is for windows, but is easily portable to linux and Mac OS X.
> 2 votes

# Answer
Because sum of square of digits of 18 digit number is smaller than or equal to $18\times 9^2 = 1458$, it's enough to enumerate first $1458$ numbers and find list of happy numbers out of them (we say it $happy-list$), then for a given range $\[lo,hi\]$ check each number's square digit sum is in our happy list or not, so this is $O(hi-lo)$, because you can do preprocessing and save happy numbers below $1458$, then use them, but this is not good because when $lo=0, hi=10^{18}$ the $O(hi-lo)$ algorithm is not good for current PCs, so is better to find number of solution for below equation:

$x\_1^2+....x\_{18}^2 = y\_i \forall y\_i \in happy-list \text{ and } x\_j \>0$.

I don't know if is there any straight forward way to do this, but we know something like number of solution for $x\_1+....x\_{18} = y\_i \forall y\_i \in happy-list\text{ and } x\_j \>0$ is easy to find. I wrote this because I think this gives an idea to how to start to think about this problem, but if I found a way for above equation or with similar idea, I'll update my answer, but my first answer is too much faster than recursion like wiki's solution.
> 2 votes

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


# Question
Title: Circle Intersection with Sweep Line Algorithm
Unfortunately I am still not so strong in understanding Sweep Line Algorithm. All papers and textbooks on the topic are already read, however understanding is still far away. Just in order to make it clearer I try to solve as many exercises as I can. But, really interesting and important tasks are still a challenge for me.

The following exercise I found in lecture notes of Line Segment Intersection by omnipotent Jeff Erickson.

> **Exercise 2.** Describe and analyze a sweepline algorithm to determine, given $n$ circles in the plane, whether any two intersect, in $O(n \log n)$ time. Each circle is speciﬁed by its center and its radius, so the input consists of three arrays $X\[1.. n\], Y \[1.. n\]$, and $R\[1.. n\]$. Be careful to correctly implement the low-level primitives.

Let's try to make a complex thing easier. What do we know about intersection of circles? What analogue can be found with intersection of lines. Two lines might intersect if they adjacent, which property two circle should have in order to intersect? Let $d$ be the distance between the center of the circles, $r\_{0}$ and $r\_{1}$ centers of the circles. Consider few cases:

* Case 1: If $d \> r\_{0} + r\_{1}$ then there are no solutions, the circles are separate.
* Case 2: If $d \< |r\_{0} - r\_{1}|$ then there are no solutions because one circle is contained within the other.
* Case 3: If $d = 0$ and $r\_{0} = r\_{1}$ then the circles are coincident and there are an infinite number of solutions.

So, it looks like conditions of intersection are ready, of course it may be wrong conditions. Please correct if it's so.

**Algorithm.** Now we need to find something in common between two intersecting circles. With analogue to line intersection, we need to have insert condition and delete condition to event queue. Let's say event point are x coordinate of the first and the last points which vertical sweep line touches. On the first point we insert circle to *status* and check for intersection (3 cases for checking are mentioned above) with nearest circles, on the last point we delete circle from *status*.

It looks like is enough for sweep line algorithm. If there is something wrong, or may be there is something what should be done different, feel free to share your thoughts with us.

**Addendum**:

I insert a circle when vertical sweep line touches the circle for the first time, and remove a circle from the status when sweep line touches it for the last time. The check for intersection should be done for the nearest previous circle. If we added a circle to *status* and there was already another circle which we added before and it was still there, therefore the pervious circle was not "closed", so there might be an intersection.

# Answer
> 7 votes
You're definitely on the right track. The big question is: when you insert a circle, which other circles do you check for intersection? How do you perform this check?

In the line segment intersection case, the line segments at any given x coordinate are totally ordered. (You can list them from lowest to highest Y coordinate). Thus, you can maintain the line segments in a binary search tree, and when you add a new segment, you only need to find out where it belongs in the binary search tree, and check its neighbors for intersection events.

In the circles case, its not immediately clear which circles to check. If your answer is "all of them" then your algorithm needs some work.

Can you figure out a way to represent the circles so that they are totally ordered, like the line segments are?

> Try representing the circles as two half-circles. Each insert event is actually two events: insert top half, and insert bottom half.

# Answer
> 0 votes
I could think of this approach analogous to Bentley Ottmann sweep that runs in O((n+k)logn) time.

I could reduce the problem of circle intersection to line segment intersection. I will consider the vertical diameter parallel to Y-axis for each of the circles. The algorithm shall use a horizontal line that sweeps the plane from bottom to top.

Now we have Upper end point, lower end point for each of the circles. Also, we need to modify the Intersection predicate to say that two segments intersect if and only if the sweep line cuts through both the circles at a point.

Since the line intersection problem can be solved in O( (n+k) logn ) time, the same bound follows for circle intersection as well.

I am quite convinced that this would work but if you guys could point out any case that this will not handle in general, do let me know.

---
Tags: algorithms, computational-geometry
---