# Question
Title: Finding maximal factorization of regular languages
Let language $\mathcal{L} \subseteq \Sigma^\*$ be regular.

A factorization of $\mathcal{L}$ is a maximal pair $(X,Y)$ of sets of words with

* $X \cdot Y \subseteq \mathcal{L}$
* $X \neq \emptyset \neq Y$,

where $X \cdot Y = \\{xy$ | $x \in X, y \in Y\\}$.

$(X,Y)$ is maximal if for each pair $(X',Y') \neq (X,Y)$ with $X'\cdot Y' \subseteq \mathcal{L} $ either $X \not \subseteq X'$ or $Y \not \subseteq Y'$.

Is there a simple procedure to find out which pairs are maximal?

Example:

Let $\mathcal{L} = \Sigma^∗ab \Sigma^∗$. The set $F = \\{u, v, w\\}$ is computed:

* $u =(\Sigma^∗, \Sigma^∗ab\Sigma^∗)$
* $v = (\Sigma^∗a\Sigma^∗, \Sigma^∗b\Sigma^∗)$
* $w = (\Sigma^∗ab\Sigma^∗, \Sigma^∗) $

where $\Sigma = \\{a,b\\}$.

Another example:

$\Sigma = \\{a, b\\}$ and $\mathcal{L} = \Sigma^\*a\Sigma$ Factorization set $F = \\{q, r, s, t\\}$ with

* $q = (\Sigma^\*, \mathcal{L})$
* $r = (\Sigma^\*a, \Sigma + \mathcal{L})$
* $s = (\Sigma^\*aa, \epsilon + \Sigma + \mathcal{L})$
* $t = (\mathcal{L}, \epsilon + \mathcal{L}) $

# Answer
As suggested in the comments to the question, I will try to give an (unfortunately partial) answer to the question, at least to the extent that I have understood the problem myself (this implies that you may well find mistakes, and if you find a way to more briefly or clearly explain one of the below points, feel free to edit the answer accordingly):

First, one should note that we do not actually have to compute the universal automaton of a language if we want to compute the factorizations of a language.

From the paper mentioned in my comment¹, there is a 1-1 correspondence between left and right factors of a regular language, that is, given a left factor of the language, the corresponding right factor is uniquely determined and vice versa. More precisely, we have the following:

Let $(X,Y)$ be a factorization of $L$. Then $$Y = \bigcap\_{x \in X}x^{-1}L, X = \bigcap\_{y \in Y}Ly^{-1},$$ that is, any left factor is an intersection of right quotients, and any right factor is an intersection of left quotients. Conversely, any intersection of left quotients of $L$ is a right factor of $L$, and any intersection of right quotients of $L$ is a left factor of $L$.

Note that for a regular language, there is only a finite set of left and right quotients, and thus or problem reduces to computing the left and right quotients of a language, and then to compute their $\cap$-stable closure, that is, a minimal superset of the quotients that is closed under intersection. These are then precisely the right factors and left factors, and then it is usually easy to see which pairs are subsets of $L$.

## Example

In order to illustrate the above points, consider the first example in the question (of which I also think that it is incorrect in the paper):

Let $L = \Sigma^\ast ab \Sigma^\ast$. Now, the left quotients of $L$ are the sets $x^{-1}L$ for $x\in \Sigma^\ast$, that is, those words $u$ in $\Sigma^\ast$ that can be prefixed with $x$, i.e. $xu \in L$. When is $y^{-1}L=x^{-1}L$ for distinct $x,y$? This is the case if and only if $x$ and $y$ can be augmented to words in $L$ with precisely the same suffixes. This means, to put it into more familiar terms, they are Nerode-equivalent, and the suffixes that are needed to append to words in a Nerode class are precisely the respective left quotients.

For $L$, we see that our Nerode-equivalence classes are

* $N\_1$, the set of words not containing $ab$ as a factor and ending with $a$,
* $N\_2$, the set of words ending with $b$ and not containing $ab$ as a factor, and
* $N\_3$, the set of words containing $ab$ as a factor, that is, $N\_3 = L$

They can be augmented with the following sets (that is, these are the left quotients of the words in the respective classes):

* $S\_1 = x^{-1}L$ for $x$ in $N\_1$ consists of all words in $L$ (any word can be augmented with a word containing $ab$ as a factor and thus becomes a word in $L$) and $b\Sigma^\ast$, that is $S\_1 = L \cup b\Sigma^\ast$
* $S\_2 = x^{-1}L$ for $x$ in $N\_2$ is the language itself, that is, $S\_2 = L$ and
* $S\_3 = x^{-1}L$ for $x$ in $N\_3$ is obviously $\Sigma^\ast$. That is, we have found three right factors of $L$. As $S\_2\subset S\_1\subset S\_3$, their $\cap$-stable closure is trivially ${S\_1,S\_2,S\_3}$, and those are then precisely the right factors.

Hence, our factorization set $\mathcal{F}\_L$ is of the form $(P\_1,S\_1),(P\_2,S\_2),(P\_3,S\_3)$.

Now, for the left factors $P\_i$, we use the equations of the beginning of this answer:

$$ P\_i = \bigcap\_{x\in S\_i} Lx^{-1} $$.

For $P\_1$, this yields $L \cup \Sigma^\ast a$, for $P\_2$ we get $\Sigma^\ast$ and for $P\_3$, we obtain $L$. You can see this by inspection (the most popular excuse for being too lazy to state a formal proof) or by explicitly computing the right quotients (which is fairly analogous, although not completely, to computing the left quotients). Our factorizations are thus given by $\mathcal{F}\_L = {u,v,w}$ where

* $u = (P\_1,S\_1) = (\Sigma^\ast ab \Sigma^\ast \cup \Sigma^\ast a, \Sigma^\ast ab \Sigma^\ast \cup b\Sigma^\ast)$
* $v = (P\_2, S\_2) = (\Sigma^\ast, \Sigma^\ast ab \Sigma^\ast)$ and
* $w = (P\_3, S\_3) = (\Sigma^\ast ab \Sigma^\ast, \Sigma^\ast)$

## Summary

To summarize (as you were asking for a simple procedure):

* For computing the factorizations of a language $L$, first compute the left quotients of $L$.
* You can do so, in the language of the paper, by constructing a minimal DFA $A$ for $L$ and then for each state $q$ in $A$ (corresponding, as a Nerode-equivalence class, to a left quotient) compute the future of $q$ in $A$, thus obtaining one left quotient of the language for each state.
* The collection of left quotients obtained in this way yields, in general, a subset $S\_R$ of the right factors.
* Compute then the $\cap$-stable closure of $S\_R$, which can be done in practice by forming the intersection of any subset of $S\_R$ and adding any subset obtained in this way to $S\_R$.
* The set $S\_R$ together with all the intersections from the previous step is then the set of right factors of $L$.
* In order to obtain the left factors, we can compute the right quotients of $L$.
* These are sets of the form $Ly^{-1}$, for $y\in \Sigma^\ast$. Now, these are again only finitely many, and for $x\neq y$, we have $Ly^{-1} = Lx^{-1}$ if and only if for all $u\in \Sigma^\ast$, $ux \in L \Leftrightarrow uy \in L$, that is they can be prefixed to words in the language with precisely the same set of strings.
* To compute $Lx^{-1}$, consider those states $q$ in $A$ such that $x$ is contained in the future of $q$. The union of the pasts of those states constitute one right quotient. Find all these quotients.
* You know you are done when you have found as many left factors as you have right factors.
* Find those pairs of left and right factors $X,Y$ such that $X\cdot Y \subseteq L$. This is $\mathcal{F}\_L$.

---

1. The Universal Automaton by Lombardy and Sakarovitch (in Texts in Logic and Games, Vol 2: Logic and Automata: History and Perspectives, 2007)
> 8 votes

---
Tags: algorithms, regular-languages, optimization
---


# Question
Title: Little's law and average time on a system with a switch
We have a switch with $2$ lines of input and $2$ output. Each line is $10 Mbps$. The size of packets is fixed and is $1KB$. The $1^{st}$ line of input is active (transferring packets) $40\\%$ of the time, while the $2{nd}$ line is active $70\\%$ of the time. $\frac{1}{4}$ of **packets of input $1$** (with arrival) directed to buffer of output line $1$, while the $\frac{3}{4}$ directed to buffer of output line $2$. Respectively $\frac{1}{2}$ of **packets of input $2$** go to buffer 1 and $\frac{1}{2}$ to buffer $2$. Buffers $1$ and $2$ are monitored and we know that tha average number of packets in buffer $1$ is $3$ packets and in buffer $2$ is $4.5$ packets.There is also an external measurement system that measures the total time of packet input $1$ to the switch.Based on these measurements calculated the average time of packets of input $1$ in the system for those that are directed to output $1$ is $5mse$c and to output $2$ is $7msec$ . Find the average residence time of packets of input line $2$ that are directed to buffer $1$ and the average time in the system (for the same packets)

note: the residence time of one packet on switch, is the time spent on buffer plus the transmission time from the output line

Consider these cases: 1) consider packets sit in the buffer until they are done being transmitted 2) assume the transmitter works on one packet at a time and removes the packet from the buffer while it is working on it

# Answer
> 1 votes
My best guess is that the intention of the problem is that packets sit in the buffer until they are done being transmitted. So when the problem says that $N\_1 = 3$ this includes the packet being transmitted in addition to those waiting in the buffer.

Two applications of Little's Law should get you the answer without needing to figure out any details about the transmitter.

Spoiler! (Mouse over the region below to see my answer.)

> The throughput on input line 1 is $.4 \times \frac{10\mathrm{Mb}}{s}\times \frac{1\mathrm{packet}}{\mathrm{KB}}\times\frac{1\mathrm{B}}{8\mathrm{b}} = .5\mathrm{Kpackets}/\mathrm{s}$. $\frac{1}{4}$th of that is directed to buffer 1, so $.125\mathrm{Kpackets/s}$. The throughput on input line 2 is $.875\mathrm{Kpacket}/\mathrm{s}$. Half of that is directed to buffer 1, so $.4375\mathrm{Kpacket/s}$. The problem says that $R\_{11}$, the measured average time of a packet from input 1 to output 1 is 5ms. The throughput of those packets is 125p/sec, so by Little's Law the number of packets from input 1 inside buffer 1 averages 0.625. So 3-0.625=2.375 packets in buffer 1 must come from input 2. The throughput of input 2 packets in buffer 1 is 437.5p/s. By Little's Law the response time for input 2 packets in buffer 1 is 5.43ms.

If it really is supposed to be the case that packets leave the buffer while they are being transmitted, then you can apply Little's Law at any level of the hierarchy. You can apply it to the entire switch, to one of the outputs (the buffer + the transmitter), to just one of the buffers, or to one of the transmitters. When applied to the transmitter you would use the variety of Little's Law that is sometimes called the "utilization law" \[Lazowska, Zahorjan, Graham and Sevcik; *Quantitative System Performance*, 1984\].

Output 1 is providing $562.5\mathrm{packets/s}$, which is a utilization of $0.45$. So by the utilization law $0.45 = 562.5\mathrm{packets/s}\times S\_{\mathrm{transmit}}$, so $S\_{\mathrm{transmit}} = 0.8\mathrm{ms}$. Thus the time in the buffer for packets from input 1 is $4.2\mathrm{ms}$ rather than $5\mathrm{ms}$ and the rest of the calculation proceeds similarly to above. (Apply Little's Law twice.)

Another way to look at it, which provides the same answer, is that the utilization of the transmitter is the average number of packets in the transmitter. So the average number of packets in the output 1 buffer and transmitter combined is $3+0.45=3.45$. Then you apply Little's Law twice and you can confirm that you get exactly the same result as you get when assuming that each packet from input 1 takes $4.2\mathrm{ms}$ in the buffer and $0.8\mathrm{ms}$ in the transmitter.

---
Tags: probability-theory, computer-networks
---


title: lambda calculus as a type theory

text:
# Question
Title: lambda calculus as a type theory
From the Introduction section of Homotopy Type Theory book:

> Type theory was originally invented by Bertrand Russell ... It was later developed as a rigorous formal system in its own right(under tha name "$\lambda$-calculus").

Can anyone explain me this sentence? I'm having trouble seeing $\lambda$-calculus as a type system.

(also in the same paragraph, $\lambda$-calculus called as "Church's type system")

# Answer
In the very next paragraph of that book (see HoTT, p. 2) they give an informal characterization of what qualifies a language system (or logic) as a type system, namely that: *in it all terms are typed*.

By "Church's type system" they're referring to the **simply typed lambda calculus** (introduced in 1940).

> In 1930s, in particular while preparing his negative solution to the decision problem, Church had introduced a system of **untyped lambda calculus**. This, of course, was *not* a type theory.

The 1940 system, however, is a type theory, because in it all terms are typed (see, for example (T&S), Section 1.2 for how exactly this is done). By "lambda-calculus as a type system" they're referring to this second, simply typed version of lambda calculus.

(T&S) Troelstra, A.S. & Schwichtenberg, H. *Basic Proof Theory*, 1996.
> 9 votes

---
Tags: lambda-calculus, type-theory
---


# Question
Title: Determine if two grammars for the same language are ambiguous
I'm reading the book: *Formal Syntax and Semantics of Programming Languages*. I don't understand this exercise:

> Consider the following two grammars, each of which generates strings of correctly balanced parentheses and brackets. Determine if either or both is ambiguous. The Greek letter ε represents an empty string.
>
> ```
> <string> ::= <string> <string> | ( <string> ) | [ <string> ] | ε
> <string> ::= ( <string> ) <string> | [ <string> ] <string> | ε
>
> ```

# Answer
> 1 votes
Consider this a hint. As I write in my comment, what is the syntax tree of `()()()`? Does the first two pairs belong to the leftmost of the `<string><string>`-part, or does the two latter pairs belong to the rightmost?

$$ \left( \overbrace{ \overbrace{ () }^\text{string} \quad \overbrace{ () }^\text{string}}^\text{string} \quad \overbrace{ () }^\text{string} \right) \text{ vs } \left( \overbrace{ () }^\text{string}\quad \overbrace{ \overbrace{ () }^\text{string}\quad \overbrace{ () }^\text{string}}^\text{string} \right) $$

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


title: Joining two red-black trees

text:
# Question
Title: Joining two red-black trees
I have

1. two red-black trees $T\_1$ of black height $H\_1$ and $T\_2$ of black height $H\_2$
2. such that all the nodes $N$ belonging to $T\_1$ are less than (in value) all the nodes $N$ of $T\_2$
3. and a key $K$ such that $K$ is greater than all the nodes of $T\_1$ and less than all the nodes of $T\_2$.

I wanted to devise an algorithm to combine $T\_1$, $K$ and $T\_2$ into a single red-black tree $T$.

I could delete each element from either $T\_1$ or $T\_2$ and put it in other tree. But that will give me an algorithm of time-complexity $2^{H\_1}$ or $2^{H\_2}$ (depending on the tree from which I have deleted the elements from). I would like to have an algorithm which is $O(\max(H\_1,H\_2))$.

> Definitions :
> Black-height is the number of black-colored nodes in its path to the root.
>
> Red-Black tree : A binary search tree, where each node is coloured either red or black and
>
> * The root is black All NULL nodes are black
> * If a node is red, then both its children are black
> * For each node, all paths from that node to descendant NULL nodes have the same number of black nodes.

# Answer
> 1 votes
Your question surprisingly has an answer on stackoverflow, no doubt dating before this site. The question gives an algorithm of time complexity $O(\max(H\_1,H\_2))$, and claims that it can be improved to $O(\min(H\_1,H\_2))$.

By the way, oftentimes $O(H\_1 + H\_2)$ is used for $O(\max(H\_1,H\_2))$.

# Answer
> 1 votes
I think the trick to join in $O(\min(H\_1,H\_2)$ is to do operations like finding height in parallel and stop after doing it for the smaller one. Note that like many other common data structures, any subtrees of a RB-tree is already an RB-tree. We only need to fix the part above the modification.

It is instructive to try to do this first for simple BST. Given two BSTs with heights $h\_1$ and $h\_2$ and a key between their keys, merge them into one BST with the height $\max(h\_1,h\_2) + O(1)$ in time $O(\min(h\_1,h\_2))$.

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


title: Chaitin's elegant programs

text:
# Question
Title: Chaitin's elegant programs
I need help to understand Chaitin's elegant program proof. An elegant program is the shortest program that produces a given output.

Here is the proof:

> Construct a program $B$ that takes as input a number $N$ and enumerates all possible programs $P\_k$ longer than $N$. $B$ runs the elegance tester $\mathrm{ET}$ on each enumerated program $P\_k$ in turn until it finds some $P\_k$ which $\mathrm{ET}$ claims is elegant. $B$ then runs that $P\_k$, thus producing the same output as that $P\_k$.
>
> **Lemma:** B must produce some output.
>
> **Proof:** There are an infinite number of elegant programs, as noted earlier. So if $\mathrm{ET}$ works as assumed, $B$ must eventually find one of those elegant programs whereupon it will produce that program's output. Now run $B$ with $N$ set to $|B| + 1$ (See note 1). (This is the "threshold size" mentioned in the theorem.) $B$ now will produce the same output as some program $P\_k$ which $\mathrm{ET}$ claimed was elegant. But $P\_k$ is longer than $B$, so $P\_k$ cannot be elegant because $B$, which is shorter, produced the same output. Therefore, $\mathrm{ET}$ was wrong when it claimed $P\_k$ was elegant. QED.

My question is: The proof begins with a program $B$ that is a program "that takes as input a number $N$ and enumerates all possible programs $P\_k$ longer than $N$" But because of the halting problem such a program is not possible, so the proof starts dead? There is something I'm not understanding here.

# Answer
> 4 votes
The algorithm $B$ is described in a mildly sloppy way. You can look at it as a two-step process:

1. Find suitable $P\_k$.
2. Run $P\_k$.

Now, step 1 can be done one program at a time since the set of all programs is recursively enumerable and we assume that a recursive (and total) elegance tester $\mathrm{ET}$ exists. Note that we use $\mathrm{ET}$ as an oracle.

So, the algorithm is this:

```
def B(N,x)
  E = program_enumerator

  do
    P = E.next
    if ( length(P) <= N )
      continue
  while ( !ET(P) )

  return P(x)
end

```

Why is this a proof? We call the underlying technique proof by contradiction. Here is what happens:

* *Assume* that a general, total elegance checker $\mathrm{ET}$ exists.
* *Under this assumption*, construct a (computable!) program $B$ that is equivalent to a program $P$ so that $B$ is smaller than $P$ but $\mathrm{ET}$ says that $P$ is elegant (i.e. smallest).
* Since this is a contradiction, the assumption has to be false; that is, such an elegance checker can not exist.

# Answer
> 1 votes
I assume the description of the algorithm comes from http://www.flownet.com/gat/chaitin.html or a similar text. In particular it explains that both input and code are counted in the size of a program.

One reason why the Halting problem is irrelevant here is that program B does not execute program Pk (in which case indeed we could have programs Pk that do not stop), but only runs ET on the string representation of program Pk.

By definition program ET is a program that always stops after some time. After finishing it returns a program Pk that is elegant. This program Pk therefore produces an output after a finite time so we can safely execute program Pk.

So in a nutshell, neither ET nor B can tell you for any arbitrary program if that programs halts or not.

---
Tags: computability, program-optimization
---


# Question
Title: Representing grammar for list/dictionary with optional end separator as LL(1)
Considering a grammar that includes a dictionary or list with an optional terminal separator - e.g.:

$$ \begin{align} obj \to & dict \\ &\mid OTHER \\ dict \to & \\{ \quad \\} \\ & \mid \\{ \quad pairs \quad \\} \\ pairs \to & pair \quad ,? \\ & \mid pair \quad , \quad pairs \\ pair \to & PAIR \end{align} $$

My understanding is that the above is **not** an LL(1) grammar because there are productions with FIRST() sets crossing over.

But what if we convert it to the following:

$$ \begin{align} obj \to & dict \\ &\mid OTHER \\ dict \to & \\{ \quad dictrest \\ dictrest \to & \\} \\ & \mid pair \quad pairseq \quad ,? \quad \\} \\ pairseq \to & \varepsilon \\ & \mid , \quad pair \quad pairseq \\ pair \to & PAIR \end{align} $$

Is this latter version LL(1)?

# Answer
You grammar can be boiled down by removing some chain rules to this:

$\qquad\begin{align} obj &\to \\{\ dict \mid OTHER \\ dict &\to\ \\} \mid PAIR\ pairs\ ,\ \\} \mid PAIR\ pairs\ \\} \\ pairs &\to\ ,\ PAIR\ pairs \mid \varepsilon \end{align}$

Note that I expanded the $?$ which, as far as I know, is not EBNF. This introduces one source of ambiguity LL(1) can not get rid of. The version with $?$, i.e.

$\qquad\begin{align} obj &\to \\{\ dict \mid OTHER \\ dict &\to\ \\} \mid PAIR\ pairs\ ,?\ \\} \\ pairs &\to\ ,\ PAIR\ pairs \mid \varepsilon \end{align}$

has a similar problem: while deriving $dict$ and you see $PAIR\ ,$, which alternative of $pairs$ do you choose? Impossible to decide.

Note that your basic problem is that you create a sequence of stuff from the left without knowing what the last element is going to be. Formally, you have the right-linear grammar

$\qquad A \to abA \mid ab \mid a$

which generates $(ab)^\*a(b\mid\varepsilon)$, surrounded by

$\qquad S \to \\{\ A\ \\}$.

Selecting the very last rule is indeed problematic -- because you threw away the real end marker, the closing brace! Move that one to $A$, get rid of the ambiguity with $a$ and you are good!

> $\qquad\begin{align} S &\to \\{\ A \\ A &\to aB \mid\ \\} \\ B &\to bA \mid \ \\}\end{align}$
> 1 votes

---
Tags: formal-grammars, parsers
---


title: Getting started with Data Mining

text:
# Question
Title: Getting started with Data Mining
This is the first time that I'm looking in depth into the topic, although I've always been curious. Could someone let me know about online resources (courses, tutorials, etc) and books that cover the basics of the topic? I'd like to explore both the theoretical part and the more practical part of Data Mining.

# Answer
> 1 votes
You can start with Data Mining: Concepts and Techniques.

To see data mining algorithms in practice you can use Weka.

# Answer
> 0 votes

---
Tags: reference-request, data-mining
---


# Question
Title: Data structure for maintaining large space-efficient filtered array
How does one implement a space efficient data structure that satisfies the requirements below?

1. You have a large array
2. You have a filter which tells you which elements in that large array are to be deleted
3. Lookup of i'th element in the array should be constant time
4. The space formerly occupied by deleted elements in the array should be available for further use.

I've explored approaches ranging from bloom filters to trees, but they violate one requirement or the other.

EDIT: Further clarification.

Space-efficient: Any space not used by elements of the array that have not been deleted by the filter, which we can term extra space or space for book-keeping, should be $O(1)$. We can probably relax this to allow any solution that gets close to $O(1)$ extra space. $O(n)$ extra space is undesirable.

Array in the context of this problem is an array-like collection where you can get the $i$th element in constant time. You lookup by index here.

I suspect amortized performance bounds should be fine.

The filter takes each element of collection and returns 0/1 corresponding to delete/no delete.

# Answer
> 2 votes
There is a simple and clean solution that satisfies all of your requirements.

To delete elements, you scan the set of array indices (from 1 to $n$), querying the filter on each and deleting each element that is to be deleted, compacting the array as you go (to shift everything after the deleted element forward one slot). The deletion operation can be implemented in $\Theta(n)$ time, with a single linear scan. This satisfies all of your requirements. (Note that you did not specify any restriction on the running time of the deletion operation.) In particular, it is space-efficient: it does not require *any* extra space (it has 0 space overhead, since after deletion, all of the space that's not in use for storing undeleted array elements is immediately available for other use). Looking up the $i$th element of the array takes constant time, thanks to the compaction: you just index into the $i$th element of the compacted array.

If for some reason this solution is not acceptable to you, then you need to re-think the requirements more thoroughly and edit the question to pose the exact set of requirements more carefully.

Given the problem as you've stated it, I don't think it will be possible to do better than this trivial solution. You can't do better than $\Theta(1)$ time for lookup. You can't do better than 0 space overhead. And I don't think you can do better than $\Theta(n)$ time for deletion, given how you specified the interface to deletion (which works by specifying a filter that is an oracle that, on input $i$, tells you whether index $i$ should be deleted or not). Even just figuring out which elements of the collection to delete requires querying the filter on all $n$ possible indices, which takes $\Theta(n)$ time. So, I don't think you can do any better than $\Theta(n)$ time for the deletion operation -- and in particular, I don't think you can do any better than the above scheme, at least not with this specification of how the filter is provided.

# Answer
> -1 votes
> Lookup of i'th element in the array should be constant time

The only thing I could think of is a hashtable

> The space formerly occupied by deleted elements in the array should be available for further use.

This could be achieved easily by having an array of pointers or a queue of pointers that way whenever you decide to create a new item, you can choose to pop from the queue or array. When you delete/don't need the object in the array, you enqueue it. If the queue or array is empty, then you create a new object.

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


# Question
Title: Scheduling algorithm to minimize maximum deadline overshoot in pre-emptive scheduler
Suppose there are $n$ tasks, which need to be scheduled by a *pre-emptive* scheduler. Each task $T\_i$ has a deadline $d\_i$ and a total processing time $t\_i$ associated with it. Now, all $n$ tasks are given a priory to the scheduler. The scheduler can run a task for 1 unit of time in one go. After each unit of time, it can schedule any process (including the current one) for the next 1 unit of time.

The goal of the scheduler is to *minimize* the *maximum* overshoot of its deadline by any process. For example, for tasks $T\_1: (2, 2)$, $T\_2: (1, 1)$ and $T\_3: (4, 3)$ are the 3 tasks with their respective $(d\_i, t\_i)$, then a schedule of $T\_2, T\_1, T\_3, T\_1, T\_3, T\_3$ gives a maximum overshoot of 2. No other schedule can reduce the maximum overshoot.

My solution is to use "Earliest Deadline First Scheduling", with tie-breaks based on most time/work remaining. Further ties are broken arbitrarily. Basically, after each unit of time, the task with the earliest deadline is scheduled first. Any ties are decided on which task has the most work remaining. Further ties are broken arbitrarily. This seems to work on a few small hand-constructed cases. But I could not prove or disprove it.

To make the question more than a yes/no question, I would really appreciate it if someone could prove if this is correct, or provide a correct and efficient (sub-quadratic time) algorithm for this. This is not homework. It was presented to me by someone, and I suspect it might be a popular interview question or a question on a programming forum.

# Answer
> 4 votes
The problem *minimizing maximal lateness* is discussed in the algorithm book by Kleinberg and Tardos under *greedy algorithms*. The solution is like yours, ordering the tasks by their deadline. Indeed the length of the tasks is not relevant.

The main ingredient of the proof is that any optimal solution $O$ can be transformed into this greedy one $G$ by swapping two adjacent tasks that do not agree on the greedy ordering.

Assume we have two tasks $(t\_i,d\_i)$ and $(t\_j,d\_j)$ with $d\_i\le d\_j$ and $O$ has scheduled task $j$ just before $i$, while the greedy algorithm wants it the other way. Assume task $i$ starts at time $t$ in $O$. The lateness in $O$ is the maximum $m$ of $t+t\_j-d\_j$ and $t+t\_j+t\_i-d\_i$.

After swapping we have the maximum of $t+t\_i-d\_i$ and $t+t\_i+t\_j-d\_j$. This cannot be worse then the performance of $O$ since both these two numbers are at most $t+t\_i+t\_j-d\_i \le m$ (using $d\_i\le d\_j$). As $O$ is optimal, so must the swapped version, but it looks more like $G$.

This is not the complete proof. E.g., we have to show that always such a pair $i,j$ can be found, to iterate and obtain $G$ from $O$ by swapping. Also we have to consider 'negative values', when actually $i$ or $j$ meet their deadline, and $m=0$.

# Answer
> 0 votes
Here is a simple proof that the additional criteria that job need not be completed in one go is actually not necessary:

suppose the input is a sequence of tasks $\\{(d\_i, m\_i)\\}$, where $d\_i$ is the deadline of task $i$ and $m\_i$ is the duration of task $i$, for $i$ = 1, 2, ...,$n$. We can transform the input into another instance, where each task $i$ is replaced by $m\_i$ "subtasks" $(d\_i, 1)$. The optimal solution for the original problem cannot be better than the optimal solution for the transformed problem, as schedule of the original $n$ tasks is also a valid schedule of the transformed problem; on the other hand, if we run the algorithm in the book of Kleinberg and Tardos on the transformed problem (which would produce the optimum schedule for the transformed input), it would naturally put all subtasks consecutively as they have the same deadlines, which in turn is a valid schedule for the original input.

---
Tags: algorithms, optimization, scheduling
---


# Question
Title: Prove Context Free languages not closed under difference?
Given two context-free languages $L\_1$ and $L\_2$, the language given by the difference of the two languages, $L\_1 - L\_2$, is (in general) not context-free. Is it possible to prove this without using pumping lemma?

# Answer
> 8 votes
Hendrik Jan gives a nice complete answer. If you're looking for a more abbreviated proof, without mention of Turing machines, you can prove it fairly easily, starting with the assumption that $CFL$ is not closed under complementation.

We know that there exists $L\in CFL$ such $\overline{L} \not \in CFL$, that is, its complement is not context free. But $\Sigma^\* \setminus L = \overline{L}$. Since $\Sigma^\*$ and $L$ are both context free, this shows $CFL$ is not closed under difference.

# Answer
> 6 votes
Yes I believe it is possible to prove such a non-closure property without pumping a specific example language.

As noted in the comments, complement $\Sigma^\* - L$ is a special form of difference. It turns out that complementation is an extremely powerful tool used with context-free languages. One can show that *computation histories of Turing machines* can be specied as complements of context-free languages. This seems to originated from J. Hartmanis, "Context-free languages and Turing machine computations", Proceedings of Symposia in Applied Mathematics, Vol. 19, AMS, 1967, 42-51.

A computation history (for a fixed TM $M$) is a string of the form $x\\$C\_0\\$C\_1\\$\dots\\$C\_n$ where $x$ is an input string, $C\_0$ is the initial configuration of $M$ on $x$, meaning a string of the form $q\_0x$ where $q\_0$ is the initial state, $C\_n$ is a final configuration (with a final state) and each pair of consecutive $C\_{i-1}\\$C\_i$ represents a single step of TM $M$.

The language of those strings is the complement of a context-free language.

What is CFL would be closed under complement? Then the context-free languages would be equal to the languages accepted by Turing Machines: the languages of valid computations would be context-free, and from this we can find their prefixes or the accepted inputs of the TM. I do think that is a contradiction without the pumping lemma. We know there are more TM accepted languages than CF languages by complexity or decidability arguments.

---
Tags: context-free, closure-properties
---


# Question
Title: When does the nearest neighbor heuristic fail for the Traveling Salesperson?
Can you provide an example of NN algorithm failure on the Euclidean traveling salesman problem?

I was trying to construct a specific example of this for my friends and was failing.

# Answer
Consider a ladder

```
a----b----c
|    |    |
d----e----f

```

Say length of `a-b` is $2$ and length of `a-d` is $1$. The optimal route is `a-b-c-f-e-d-a`, $10$ units long. Starting at `a`, NN would produce `a-d-e-b-c-f-a` which is $7 + \sqrt{17} \> 11$ units long.

There is actually a four node example, a rhombus

```
  A
 /|\
B-+-C
 \|/
  D

```

Say length of `B-C` is $10$, length of `A-D` is $24$ and thus length of `A-B` is $13$. The optimal route is `A-B-D-C-A`, $52$ units long. NN would produce the path `A-B-C-D-A`, $60$ units long.
> 8 votes

# Answer
The following answer is to give an intuition of how a situation can look that fails. Karolis Juodelė's answer is much better than this, but I find the following example to give a nice intuition.

Let's say that we look for shortest TSP path, and not cycle, with predefined starting vertex, consider the graph below with X being the starting vertex, one dash means distance one, and two edges means distance two:

O--X-O-O-O-O

Going left immediately, and then all the way to the right gives a cost of 8, whereas going NN, i.e., right first, gives cost 9.
> 5 votes

---
Tags: algorithms, heuristics, traveling-salesman
---


# Question
Title: Differences between basic, complex and terminological facts in a Knowledge Base using First-Order Logic
I've been reading the excellent book Knowledge Representation and Reasoning by Ronald Brachman and Hector Levesque.

In the beginning of Section 3.2 "Vocabulary" of Chapter 3 "Expressing Knowledge" they state:

> In creating a KB (Knowledge Base) it is a good idea to start with the set of domain-dependent predicates and functions that provide the basis for the facts about the KB's domain.

In the same section these facts are separated in three categories:

* Basic facts
* Complex facts
* Terminological facts

After reading the entire chapter I could not entirely understand the differences between these types of facts.

Can someone help me to understand the differences in these concepts?

# Answer
In §3.2 they distinguish between the following four grammatical categories, with some examples:

```
Predicates: Woman, Rich, Beautiful, Bankrupt
Relations: LivesAt, HadAnAffairWith, Loves
Functions: fatherOf, bestFriendOf, ceoOf
Individual constants: maryJones, johnQSmith, tomsHouse

```

In the background they have first-order logic with identity, which means they allow for quantification only over *individual* variables. Within this machinery, in §§ 3.3–5 they introduce the three types of facts.

> **Basic facts** are the *atomic sentences* and their *negations*.

The *atomic sentences* are those sentences which are made of:

1. a \[predicate\] + an \[individual\]. E.g.: Woman(maryJones)
2. an n-ary \[relation\] + n \[individual\]s. E.g.: Loves(maryJones, tomsHouse)
3. an \[individual\] + "=" + an \[individual\]. E.g.: maryJones = marySmith

Note that *functions* applied to individual constants also denote individuals (e.g., fatherOf(maryJones) is some individual), that's why clauses (1–3) include the word 'individual' rather than 'individual constant' so as to allow also for functional expressions denoting individuals. The *negations* of atomic sentences are defined as follows: a sentence ¬S is a negation of an atomic sentence iff S is an atomic sentence.

> **Complex facts** are the *basic facts* closed under boolean *connectives* and *quantifiers*.

That's just a fancy way of saying that: (i) basic facts are complex facts, and (ii) if φ and ψ are complex facts, then ¬φ, (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), and ∀xφ are also complex facts. They give the following example of a complex fact on p. 34: ∀y\[Rich(y) ∧ Man(y) → Loves(y, jane)\] (every rich man loves Jane).

Beware that on p. 36 they list sentences like "jane ¬= john" among complex facts, suggesting that they're *not* basic facts. But they are. I suspect that's why you've been having hard time seeing the difference between the types. By the definition of basic facts (see above), sentences like "jane ¬= john" are considered basic, because they're the *negations* of *atomic sentences* such as "jane = john".

> **Terminological facts** are *complex facts* taken to be axiomatically or definitionally true.

A better term for them would be "definitional facts" or "meaning postulates" (as Rudolf Carnap calls them). Consider the predicate Man. If someone is a man, we know, without having to see this person, that he is not a woman; it's definitionally true! We capture that logical relationship between predicates Man and Woman with the terminological fact: ∀x\[Man(x) → ¬Woman(x)\]. That is only one example of a terminological fact; more can be found on pages 36–7. They're pretty straightforward to understand.

Hope this helps clarify the distinction.
> 7 votes

---
Tags: terminology, logic, knowledge-representation, first-order-logic, reasoning
---


# Question
Title: Results on the languages recognized by undirected DFAs
For my Bachelor's thesis, I consider the class of languages recognized by symmetrical DFAs, that is, deterministic (complete) finite automata satisfying the following condition:

Let $A$ be a complete DFA over the alphabet $\Sigma$. If, for every $a\in \Sigma$ and every transition $u \stackrel{a}{\longrightarrow}v$ in $A$, there is a transition $v \stackrel{a}{\longrightarrow}u$ in $A$, we call $A$ a *symmetrical* DFA (*SDFA*). If $A$ is not complete, we call it a *partial* SDFA. We can regard an SDFA as an undirected, labeled graph in a natural way.

I could find an algebraic characterization of the class of languages recognized by (complete as well as partial) SDFAs and deduce some closure properties. However, neither me nor my supervisor are aware of previous results concerning this particular class of regular languages (barring results like Reingold's $\mathsf{SL = L}$ which might seem related).

Motivated by a comment that J.-E. Pin passed on a related question I asked, my question is now:

> Are there results concerning these automata?

# Answer
I can only give a partial answer. Let $\mathcal{S}$ be the class of all regular languages recognized by a complete SDFA. Then $\mathcal{S}$ is a subclass of the class $\mathcal{G}$ of group languages. A *group language* is a language whose syntactic monoid is a finite group , or equivalently, recognized by a finite permutation automaton (each letter induces a permutation on the set of states). The inclusion $\mathcal{S} \subset \mathcal{G}$ is strict. However, the following result holds, showing that $\mathcal{S}$ is a kind of generator for $\mathcal{G}$:

For every group language $L \subseteq A^\*$, there is an alphabet $B$, a monoid morphism $f: A^\* \to B^\*$ and a language $K \subseteq B^\*$ in $\mathcal{S}$ such that $L = f^{-1}(K)$.

**Proof**. Let $\mathcal{A} = (\\{1, ..., n\\}, A, \cdot, 1, F)$ be a permutation automaton recognizing $L$. It is a well-known fact that the group of all permutations on $\\{1, ..., n\\}$ is generated by the set $B$ of its *transpositions* (a transposition permutes two states and fixes all the other states). By construction, the automaton $\mathcal{B} = (\\{1, ..., n\\}, B, \cdot, 1, F)$ is a SDFA and hence recognizes a language $K$ of $\mathcal{S}$. Now, for each letter $a \in A$, there is a word $u\_a \in B^\*$ which defines in $\mathcal{B}$ the same permutation as $a$ in $\mathcal{A}$. Let $f: A^\* \to B^\*$ be the morphism defined by $f(a) = u\_a$ for each letter $a \in A$. It should now be clear that $f^{-1}(K) = L$.

The class $\mathcal{PS}$ of languages recognized by a partial SDFA is of course larger than $\mathcal{S}$, but does not exhaust the class of all regular languages. Actually, one can show that if $L$ is in $\mathcal{PS}$, then the syntactic monoid of $L$ is an inverse monoid and in particular, its idempotents commute. This latter property is shared by the slightly larger class of *reversible automata*. See

J.-É. Pin, On the languages accepted by finite reversible automata, in 14th ICALP, Berlin, (1987), 237-249, LNCS **267**, Springer Verlag
> 4 votes

---
Tags: formal-languages, reference-request, regular-languages, finite-automata
---


# Question
Title: Alternative proof for the undecidability of $A_{TM}$
The proof of the undecidability of $A\_{TM}$ in Michael Sipser's textbook`*` contains the definition of a Turing Machine, which accepts the encoding of a TM, if this TM doesn't accept its own encoding, and rejects it, if it does. If this TM is run on its own encoding, there is problem: it should accept if it doesn't accept and vice versa.

My problem with this proof is that it strongly resembles Russel's paradox. This paradox arises if we define a set, which contains all sets that are not members of themselves. If we ask whether this set contains itself, there is problem: it should contain itself if it doesn't contain itself and vice versa.

Russels's paradox has been eliminated from axiomatic set theory: in ZFC, it follows from the axioms that such a property doesn't define a valid set. Interestingly enough, in the theory of computation, a similar property defines a valid TM.

That's why I don't like the proof in Sipser's book. I'd like to emphasize that I know that this proof is perfectly valid, but I'd like to know if there is another proof which follows a different chain of thought, and doesn't define such a TM.

---

`*`Sipser, M.: Introduction to the Theory of Computation (2nd ed.), 2006, page 179. On this page, Sipser uses the term *halting problem* for the language $A\_{TM}$. The proper name for this language is *acceptance problem*, see the footnote on page 188.

# Answer
So your problem is that we construct a Turing machine that works on Turing machines. In that case, we show that the particular Turing machine we imagine can not exist, and that is indeed the case for most interesting such machines.

However, it is clear that for example the problem

> Given a Turing machine (encoding), decide whether the machine has a final state.

is decidable. Similar *syntactic* properties are also decidable.

Therefore, there *are* Turing machines that work on Turing machines, and therefore themselves. How is that possible?

One (intuitive, certainly not rigorous) argument is that such machines work on *encodings* of Turing machines that are available independently of the machines "themselves" (by a recursive enumerator). In particular, in order to answer a question about itself a given machine will not have to encode itself, it will rather work on its own encoding provided from the outside *without ever knowing* it does.

In particular, there is no "infinite wrapping": a Turing machine encoding (our input) is a finite string, even if it defines an infinite set. Note how this is different from self-referential sets (easier to see for $\\{A \mid A \in A\\}$): if a set is infinite, it can't "refer" to itself in a finite way.

That said, any infinite set (of Turing machines) that *is* decidable has a finite representation *as Turing machine* (by virtue of its decider) and vice versa. That is, non-computability is equivalent to a set (of Turing machine encodings) not having a Turing machine (encoding), so I think there is a vague parallel to Russel's paradox after all.
> 5 votes

# Answer
There is no paradox. We have made an assumption, namely that the halting problem is solved by some Turing machine, and using it reached a paradox. Hence our assumption must be wrong. In the same way, Russell's paradox is a proof that the collection of all sets not containing themselves is a proper class.

In both cases, the paradox is solved by concluding that some object cannot exist. In the case of Russell's paradox, we can give a description of the object - properties it satisfies - but it doesn't exist as a set. In the same way, the halting problem is definable, but there is no Turing machine that accepts it.

In recursion theory we can breathe life into it by making it an oracle, and consider the implications. Similarly, in set theory we can consider *relativized* versions of Russell's set (relativized to some set "sub-universe"), though due to the axiom of regularity the result isn't interesting.
> 5 votes

---
Tags: terminology, computability, turing-machines, halting-problem
---


# Question
Title: Undecidability of a restricted version of the acceptance problem
It's known that the following language, the so-called acceptance problem is undecidable:

$A\_{TM} = \\{\langle M,w\rangle\\,\vert\\,M\text{ is a TM which accepts }w\\}$

The proof is by contradiction: Assume there is a TM $H$ which decides $A\_{TM}$. Let $D$ be another TM. Given the code of a TM $M$, $\langle M\rangle$ as input, $D$ simulates $H$ on $\langle M,\langle M\rangle\rangle$, and accepts, if $H$ rejects this input and rejects, if $H$ accepts it. That is, $D$ accepts $\langle M\rangle$ if $M$ rejects its own code, and vice versa. Running $D$ on its own code, $\langle D\rangle$, leads to contradiction.

---

Let's restrict $A\_{TM}$ by excluding all input strings which encode a TM:

$E = \\{w\\,\vert\\,w\text{ is a structurally valid encoding of a TM}\\}$ $A'\_{TM} = \\{\langle M,w\rangle\\,\vert\\,M\text{ is a TM which accepts }w\text{ and }w\not\in E\\}$

I'd like to know whether $A'\_{TM}$ is also undecidable.

I tried to prove it the above way: Assume there is a TM $H'$ which decides $A'\_{TM}$. Let $D'$ be another TM. Given the code of a TM $M$, $\langle M\rangle$ as input, $D'$ simulates $H'$ on $\langle M,\langle M\rangle\rangle$, and accepts, if $H'$ rejects this input and rejects, if $H'$ accepts it. The problem is that running $D'$ on its own code, $\langle D'\rangle$, doesn't necessarily lead to contradiction. I mean since $\langle D',\langle D'\rangle\rangle$ is not a member of $A'\_{TM}$, we don't know what $H'$ will do with it.

---

**Note: An encoding of TMs, and TMs along with an input string**

Let $M = (Q, \Sigma, \Gamma, \delta, q\_{i}, q\_{a}, q\_{r})$ be a TM, where

* $Q$ is the set of states,
* $\Sigma = \\{0, 1\\}$ is the input alphabet,
* $\Gamma$ is the tape alphabet ($\Sigma\subset\Gamma$),
* $\delta: (Q-\\{q\_a, q\_r\\})\times\Gamma\rightarrow Q\times\Gamma\times\\{L,R,S\\}$ is the transition function,
* $L$, $R$ and $S$ denote the respective head movements, "left", "right" and "stay", and
* $q\_i$, $q\_a$ and $q\_r$ are the initial, accepting and rejecting state, respectively.

Let's assign a unique positive integer to each element of $Q$, and do the same in case of $\Sigma$, $\Gamma$ and $\\{L,R,S\\}$. Now every transition rule $\delta(p, a) = (q, b, m)$ can be encoded as $\langle p\rangle 1\langle a\rangle 1\langle q\rangle 1\langle b\rangle 1 \langle m\rangle$, where $\langle x\rangle$ denotes a sequence of $0$'s, with length being equal to the positive integer assigned to $x$. The encoding of $M$, denoted by $\langle M\rangle$, can be created by concatenating its transition rules, separated by $11$'s. The combined encoding of $M$, and an input string, $w\in\Sigma^\*$, denoted by $\langle M,w\rangle$ is $\langle M\rangle111w$.

# Answer
The complication forbidding the input from being an encoding of a Turing machine is easy to overcome. All you need to do is tweak $D$ a bit, so that instead of accepting an encoding $\langle M \rangle$ of a Turing machine, it accepts some other input which can be *decoded* into an encoding of a Turing machine, while at the same time *not* being an encoding of a Turing machine itself.
> 3 votes

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


# Question
Title: Relation between Russellian type theory and type systems
I recently realized that there is some sort of relation between Russellian type theory and type systems, as found e.g. in Haskell. Actually, some of the notation for types in Haskell seems to have precursors in type theory. But, IMHO, Russell motivation in 1908 was to avoid Russell's paradox, and I am not sure how that is related to type systems in computer science.

Is Russell's paradox in one form or another something that we would have to worry about, for example, if we didn't have a good type system in a given language?

# Answer
\`\`Type theory" in the sense of programming languages and in the sense of Russell are closely related. In fact, the modern field of dependent type theory aims to provide a constructive foundations for mathematics. Unlike set theory, most research in type theory based math is done in proof assistants like Coq, NuPRL, or Agda. As such, proofs done in these systems are not only "formalizable" but actually fully formal and machine checked. Using tactics and other proof automation techniques we try to make proving with these systems "high level" and thus resemble informal mathematics, but because everything is checked we have much better guarantees on correctness.

See here

Types in ordinary programming languages tend to be more limited, but the meta theory is the same.

Something similar to Russell's paradox is a major issue in dependent type theory. In particular, having

```
Type : Type

```

usually leads to contradiction. Coq and similar work by nesting universes

```
Type_0 : Type_1

```

but in Coq by default these numbers are implicit as they normally don't matter for the programmer.

In some systems (Agda, Idris), the type in type rule is enabled via a compile flag. It makes the logics inconsistent, but often makes exploratory programming/proving easier.

Even in more mainstream languages, Russell's paradox occasionally shows up. For example, in Haskell, an encoding of Russell's paradox combining impredicativity and open type case is possible, allowing one to build divergent terms with out recursion even at the type level. Haskell is \`\`inconsistent" (when interpret as a logic in the usual way) since it supports both type and value level recursion, not to mention exceptions. None the less, this result is rather interesting.
> 9 votes

# Answer
You're right about Russell's motivation. His paradox plagues all theories of sets that admit unrestricted comprehension axioms to the effect that: any propositional function determines a set, namely that of all those entities that satisfy the function. Among theories of or based on sets that did have that flaw were Cantor's naive set theory and Frege's system of *Grundgesetze* (specifically: axiom 5).

Since types are considered to be special kinds of sets, if care is not taken, a similar paradox can creep into a type system.That being said, I'm not aware of any type systems that have suffered such a fate. I can only recall Church's early attempts at formulating lambda calculus in the 30s, which turned out to be inconsistent (Kleene-Rosser Paradox), but that one was neither due to types nor was related to Russell's paradox.

*Update*: See Philip's response for an actual answer to your question.
> 3 votes

# Answer
Since you mention Python the question is not purely type-theoretic. So I try to give a broader perspective on types. Types are different things to different people. I've collected at least 5 distinct (but related) notions of types:

1. Type systems are logical systems and set theories.
2. A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to prove or ensure that no type errors can occur.
3. Type is a classification identifying one of various types of data, such as real-valued, integer or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of that type can be stored
4. Abstract data types allow for data abstraction in high level languages. ADTs are often implemented as modules: the module's interface declares procedures that correspond to the ADT operations. This information hiding strategy allows the implementation of the module to be changed without disturbing the client programs.
5. Programming language implementations use types of values to choose the storage the values need and algorithms for operations on the values.

The quotes are from Wikipedia, but I can provide better references should a need arise.

Types-1 arose from Russel's work, but today they are not merely protect from paradoxes: the typed language of homotopy type theory is a new way to encode mathematics in a formal, machine-understandable language, and a new way for humans to understand foundations of mathematics. (The "old" way is encoding using an axiomatic set theory).

Types 2-5 arose in programming from several different needs: to avoid bugs, to classify data software designers and programmers work with, to design large systems and to implement programming languages efficiently respectively.

Type systems in C/C++, Ada, Java, Python did not arose out of Russel's work or a desire to avoid bugs. They arose out of needs to describe different kinds of data out there (e.g. "last name is a character string and not a number"), modularize software design and to choose low-level representations for data optimally. These languages have no types-1 or types-2. Java ensures relative safety from bugs not by means of proving program correctness using type system, but by a careful design of language (no pointer arithmetic) and runtime system (virtual machine, bytecode verification). Type system in Java is neither a logical system nor a set theory.

However, type system in Agda programming language is a modern variant of Russel's type system (based on later work or Per Martin-Lof and other mathematicians). The type system in Agda is designed to express mathematical properties of program and proofs of those properties, it is a logical system and a set theory.

There are no black-white distinction here: many languages fit in between. For example, type system of Haskell language has roots in Russel's work, can be viewed as a simplifed Agda's system, but from mathematical standpoint, it's inconsistent (self-contradictory) if viewed as a logical system or a set theory.

However, as a theoretical vehicle to protect Haskell programs from bugs, it works pretty well. You even can use types to encode certain properties and their proofs, but not all properties can be encoded, and the programmer can still violate the proved properties if he uses discouraged dirty hacks.

Type system of Scala is even further from Russel's work and Agda's perfect proof language, but still has roots in Russel's work.

As for proving properties of industrial languages whose type systems were not designed for that, there are many approaches and systems.

For interesting but different approaches, see Coq and Microsoft Boogie research project. Coq relies on type theory to generate imperative programs from Coq programs. Boogie relies on annotation of imperative programs with properties and proving those properties with Z3 theorem prover using a completely different approach than Coq.
> 3 votes

---
Tags: programming-languages, type-theory
---


# Question
Title: Definition of deterministic pushdown automaton
Wikipedia Pushdown automaton (as of aug 16, 2013) states:

> In general, pushdown automata may have several computations on a given input string, some of which may be halting in accepting configurations. If only one computation exists for all accepted strings, the result is a deterministic pushdown automaton (DPDA)

My professor gave this as an example that we shouldn't trust Wikipedia but rather consult a textbook. Is he right?

# Answer
> 6 votes
Yes, this is an example of an informal explanation that is not quite true.

A PDA is deterministic if (at any moment) it can make at most one legal computational step. This is a *local* property, a condition on a single step, and not on a computation.

The statement "*If only one computation exists for all accepted strings*" is a *global* property, a statement on all computations on a given string.

Let me give an example where the two concepts differ. The language of all (even length) palindromes over $\\{a,b\\}$ is context-free. It is accepted by a PDA in the obvious way. Start copying the input to the stack, guess the middle, then check whether the rest of the input matches the first part read (in reverse), finally accept on the empty stack. This automaton has only one accepting computation on each palindrome, but certainly is not deterministic.

But here I have argued that "only one *accepting* computation" is not the correct statement, where Wikipedia does only insist on a single computation (without the condition of acceptance). So is Wikipedia right after all? Unfortunately, no. The problem is in the $\varepsilon$-transitions. It is quite legal for a deterministic PDA to have the possibility of making several $\varepsilon$-moves before and after acceptance, it may even loop. That means many accepting computations on a fine deterministic PDA. It is also the reason that some proofs on PDA need just some extra care.

You may now edit Wikipedia to correct this mistake!

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


title: How can I define this syntax?

text:
# Question
Title: How can I define this syntax?
I wanted to define syntax for a graph path considering it may branch out anywhere.

For instance, I have a path going from `a` to `e` following `b, c, d`: `a, b, c, d, e`.

Let's consider it (may) branches from b now: `a, b, (x | y), d, e` which actually means three different paths:

1) `a, b, d, e`

2) `a, b, x, d, e`

3) `a, b, y, d, e`

So, each parenthesis actually means "the path might either go through any of the nodes defined in the parenthesis connecting the node just before parenthesis and right after parenthesis or through none of the nodes defined in the parenthesis".

With more inner parenthesis, a single string line may generate even more paths. For instance: `a, b, (x | (z | t) | y), d, e` which means these five paths:

1) `a, b, d, e`

2) `a, b, x, d, e`

3) `a, b, y, d, e`

4) `a, b, z, d, e`

5) `a, b, t, d, e`

6) `a, b, z, y, d, e`

7) `a, b, t, y, d, e`

8) `a, b, x, z, d, e`

9) `a, b, x, t, d, e`

So, how can I define this syntax mathematically?

# Answer
> 4 votes
You are mixing two things here: syntax and semantics.

First, syntax. What is the language of strings $L\_P \subseteq \Sigma^\*$ with $\Sigma = \\{\mathtt{a}, \dots, \mathtt{z}, \mathtt{)}, \mathtt{(}, \mathtt{,}\\}$ that describe a set of paths as you specify them? You can specify $L\_P$ by the formal grammar

$\qquad\begin{align} S &\to T\mathtt{,} S \mid \mathtt{(}S\mathtt{)}S \mid T \\ T &\to \[\mathtt{a}\dots\mathtt{z}\] \end{align}$

Note that the key feature is *recursion* for the parts inside parentheses. Depending on the parsing algorithm you want to employ, you may have to refactor this grammar.

Next, which set of paths does a given string $p \in L\_p$ describe? Note that this is *independent* of the syntax; we could define anything we want as the meaning of $p$. Your specification is quite precise, and can be described by these by recursive functions:

$\qquad\begin{align} \varphi(t) &= \\{t\\} \quad, t \in \[\mathtt{a}\dots\mathtt{z}\], \\ \varphi(t\mathtt{,}w) &= \varphi(t) \cdot \varphi(w) \quad, t \in \[\mathtt{a}\dots\mathtt{z}\], w \in \Sigma^\*, \\ \varphi((v)w) &= (\psi(v), \\{\varepsilon\\}) \cdot \varphi(w) \quad, v, w \in \Sigma^\* \\ \end{align}$

and

$\qquad\begin{align} &\psi(t) = \\{t\\} \quad, \mathtt{t} \in \[\mathtt{a}\dots\mathtt{z}\], \\ &\psi(t\mathtt{,}w) = \psi(t) \cup \psi(w) \quad, t \in \[\mathtt{a}\dots\mathtt{z}\], w \in \[\mathtt{a}\dots\mathtt{z},\mathtt{,}\]^\*, \\ &\psi(v\_0(w\_1)v\_1(w\_2) \dots v\_{k-1}(w\_k)v\_k) = \\ &\phantom{=}\bigcup\_{i \in \[0..k\]} (\psi(w\_1), \\{\varepsilon\\}) \cdot \dots \cdot (\psi(w\_{i}), \\{\varepsilon\\}) \cdot \psi(v\_i) \cdot (\psi(w\_{i+1}), \\{\varepsilon\\}) \cdot \dots \cdot (\psi(w\_k), \\{\varepsilon\\}) \quad, v\_i \in \[\mathtt{a}\dots\mathtt{z},\mathtt{,}\]^\*, w\_i \in L\_P. \\ \end{align}$

Note how $\varphi(p) \subseteq \[\mathtt{a}\dots\mathtt{z}\]^\*$ is the set of paths described by $p$.

**Warning:** Your syntax has the troublesome feature that a comma-separated list of path elements has different meaning outside and inside of parenteses (resulting in *two* functions for the semantics). In combination with your semantics, that means e.g. that you can not describe the set of paths $\\{ad, abcd\\}$.

**Warning:** Your semantics have the troublesome feature that any list of atoms in parentheses may produce at most one atom (selection), but if one element of the list is another list we suddenly get more (selection + concatenation). In other words, the semantic of $\mathtt{,}$ inside of parentheses changes *depending on context*. This is what makes the semantics so horrible. But then, maybe that is how it has to be: you seem to want it that way.

---
Tags: formal-languages, parsing
---


title: Showing a language is in co-NPC

text:
# Question
Title: Showing a language is in co-NPC
I need to prove that this language is in co-NPC: $\\{ \langle M,x,1^n \rangle \mid M $ is a TM and for all $c \in \Sigma^\*$ , $M$ accepts in $ $$n$ steps when given $(x,c)$ as input $\\}$.

I tried to do so by showing that the complement is in NPC, that is $\\{ \langle M,x,1^n \rangle \mid M $ is a TM and there exists $c \in \Sigma^\*$ , s.t $M$ doesn't accepts in $n$ steps when given $(x,c)$ as input $\\}$.

I can prove that it's in NP by giving a polynomial non-deterministic algorithm, but I get stuck in the reduction part and don't know from which language in NPC to do a polynomial reduction and how. Does anybody know how do deal with such reduction?

# Answer
Hint: While it's certainly possible to choose a concrete language and show a reduction from it, in this case it's actually easier to show a reduction from every language in NP.

As a starting point, recall that a language $L$ is in NP iff there exists a *polynomial-time verifier* for it.

Let $L$ be a language in NP, and let $M$ be a polynomial verifier for it, and let $f(n)\in O(n^k)$ be the runtime of the verifier. Observe that for every word $x$ we have that $x\in L$ iff there exists a witness $y$ such that $M$ accepts $(x,y)$ within $f(|x|)$ steps.

This looks a lot like your language, see if you can complete the proof from here.
> 4 votes

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


# Question
Title: When testing n items, how to cover all t-subsets by as few s-subsets as possible?
This problem arose from software testing. The problem is a bit difficult to explain. I will first give an example, then try to generalize the problem.

There are 10 items to be tested, say A to J, and a testing tool that can test 3 items at the same time. Order of items in the testing tool does not matter. Of course, for exhaustive testing, we need $^{10}C\_{3}$ combinations of items.

The problem is more complex. There is an additional condition that once a pair of items has been tested together, than the same pair does not need to be tested again.

For example, once we executed the following three tests:

A B C

A D E

B D F

we do not have to execute:

A B D

because the pair A,B was covered by the first test case, A,D was covered by the second, and B,D was covered by the third.

So the problem is, what is the minimum number of test cases that we need to ensure that all pairs are tested?

To generalize, if we have n items, s can be tested at the same time, and we need to ensure that all possible t tuples are tested (such that s \> t), what is the minimum number of test cases that we need in terms of n, s and t?

And finally, what would be a good algorithm to generate the required test cases?

# Answer
> 12 votes
The block designs you want (for testing 3 things at a time, and covering all pairs) are called Steiner triple systems. There exists a Steiner triple system with $\frac{1}{3} {n \choose 2}$ triples whenever $n \equiv 1 \mathrm{\ or\ } 3$ mod $6$, and algorithms are known to construct these. See, for example, this MathOverflow question (with a link to working Sage code!). For other $n$, you could round up to the next $n' \equiv 1 \mathrm{\ or\ } 3$ mod $6$, and use a modification of this triple system for $n'$ to cover all pairs for $n$.

If you want the best construction for other $n$, the number of triples required is the *covering number* $C(n,3,2)$, and is given by this entry in the on-line encyclopedia of integer sequences. This links to the La Jolla Covering Repository which has a repository of good coverings. The online encyclopedia of integer sequences gives a conjectured formula for $C(n,3,2)$; if this formula holds, intuitively that means there should probably be good algorithmic ways of constructing these coverings, but since the formula is conjectured, it is clear that nobody currently knows them.

For high covering numbers, good coverings are harder to find than for $C(n,3,2)$, and the repository will give better solutions than any known efficient algorithms.

# Answer
> 6 votes
Form the undirected graph $G$ where each vertex is a pair of items, and where there is an edge between two vertices if they share an item in common. In other words, $G=(V,E)$ where $V=\\{\\{a,b\\} : a,b \in \text{Items} \land a\ne b\\}$ and $E=\\{(s,t) : s,t \in V \land |s\cap t|=1\\}$. The graph has ${n \choose 2}$ vertices, and every vertex has $2n-4$ edges incident on it.

Then one approach would be to find a maximum matching in $G$. Edmonds' algorithm can be used to find such a maximum matching in polynomial time. If you're lucky, this will give you a perfect matching, and then you're good. Each edge $(\\{A,B\\},\\{B,C\\}) \in E$ in the matching corresponds to a test case $A B C$. Since every vertex is incident with one edge in the perfect matching, you have covered all pairs, using ${n \choose 2}/2$ test cases, which is within a $1.5$ factor of optimal. If you don't get a perfect matching, add a few more test cases as needed to achieve full coverage.

# Answer
> 5 votes
In the case of $s=3$ and $t=2$ you need to perform at least ${n \choose 2}/3$ tests, since there are ${n \choose 2}$ pairs and every test covers 3 pairs. That means that you can do the trivial thing and perform ${n \choose 2}$ tests, and be only a factor of 3 worse than the optimum.

If you are actually programming this, then a way to optimize this could be by first picking some number tests at random, and then do the brute force on the pairs not covered by the test so far.

---

For general $s$ and $t$, there is a lower bound of ${n \choose t}/{s \choose t}$ tests. For an upper bound I'm claiming that is is enough to make $C \cdot \frac{{n \choose t}}{s \choose t}\cdot {\log({n \choose t})} \leq O(t \cdot (\frac{n-t}{s-t})^t \log(n))$ tests.

Let's see what happens we we choose the tests uniformly at random.If you pick an $s$-tuple $S \subseteq \[n\]$ at random, then for a fixed $t$-tuple $X \subseteq \[n\]$, we have $\Pr\[X \subset S\] = \frac{{n-t \choose s-t}}{{n \choose s}}$. Therefore, if we pick $C \cdot {n \choose t} \cdot {\log({n \choose t})}$ tests at random, then $$\Pr\[X \text{ does not belong to any of them}\] = \left(1 - \frac{{n-t \choose s-t}}{{n \choose s}}\right)^{C \cdot {n \choose t} \cdot {\log({n \choose t})}} \leq \exp \left(-C \frac{{n-t \choose s-t}{n \choose t}}{{n \choose s}{s \choose t}} \cdot \log({n \choose t})\right) = \exp(-C \log{n \choose t})\leq 1/{n \choose t}.$$

Therefore, by the union bound, after $O(t \cdot (\frac{n-t}{s-t})^t \log(n))$ random tests all $t$-tuples will be covered.

---
Tags: algorithms, combinatorics, software-testing
---


title: Mealy machines to model ciphers

text:
# Question
Title: Mealy machines to model ciphers
Similar questions have occurred quite a number of times (1) (2) (3), but I have, say, a specific instance of one. I'm aware of a bunch of applications of finite automata, but would you provide an academic exposition of applications of finite state machines (like, e.g., Mealy machines) in cryptography and ciphers? There is a mention about things like that in Wikipedia article on Mealy machines (subsection “Applications”). So the links to some academic texts play up on this are very appreciated. Alternatively would you share your thoughts on how to furnish this topic (FSM in cryptography) for students?

# Answer
Consider the coding $a \to 0$, $b \to 1010$, $c \to 100$, $d \to 1011$, $r \to 11$.$\ \ $ I let you guess what represents $010101101000101101010110$ in this coding, but this can be easily computed by a sequential machine, as illustrated here, slides 9-10.

What is the theory behind this? A subset $P$ of $A^+$ is a *prefix code* if no element of $P$ is a proper prefix of another element in $P$. For instance, the sets $\\{0, 1010, 100, 1011, 11\\}$, $0^\*1$ and $\\{0^n1^n \mid n \> 0\\}$ are prefix codes, with $A = \\{0, 1\\}$. Prefix codes are conveniently represented by the leaves of a tree. In particular, variable-length Huffman codes, the UTF-8 code and the Morse code are of this type.

Now if $B$ is another alphabet and $f:B \to P$ is an injective function, then $f$ extends uniquely to an injective monod morphism (coding) from $B^\*$ to $A^\*$. Further, if $P$ is a finite subset of $A^+$, the decoding function $f^{-1}$ can be computed by a sequential machine. This machine is essentially the minimal automaton of $P^\*$, equipped with appropriate outputs (see the example).

Variable-length codes (whose prefix codes are a special case of) form the topic a rather advanced theory. The main reference is:
J. Berstel, D. Perrin, C. Reutenauer, Codes and automata. Encyclopedia of Mathematics and its Applications 129. Cambridge: Cambridge University Press (2010). ISBN 978-0-521-88831-8.
> 3 votes

---
Tags: reference-request, automata, finite-automata, cryptography
---


# Question
Title: What is a good algorithm for generating random DFAs?
I am generating random DFAs to test a DFA reduction algorithm on them.

The algorithm that I'm using right now is as follows: for each state $q$, for each symbol in the alphabet $c$, add $\delta (q, c)$ to some random state. Each state has the same probability of becoming a final state.

Is this a good method of generating unbiased DFAs? Also, this algorithm doesn't generate a trim DFA (a DFA with no obsolete states) so I'm wondering if there is a better way of generating random DFAs that can somehow ensure that it is trim?

# Answer
> 6 votes
Check out \[1\] and the discussion in Section 4, Random Automata Generation. The paper benchmarks different DFA minimization algorithms. A uniform random generator is used that produces canonical string representations of complete DFAs with $n$ states and $k$ symbols. They also discuss other methods.

---

\[1\] Almeida, M., Moreira, N., & Reis, R. (2007). On the performance of automata minimization algorithms. Logic and Theory of Algorithms, 3.

# Answer
> 4 votes
There are algorithms to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz.

But, it is also mentionned in the above paper that almost all DFAs are already minimal. Non minimal DFAs are like prime numbers ... there are just few of them. And if you use this algorithm to test minimization algorithm it will be like if you were testing an algorithm on prime number with a simple random number generator. In order to have more non minimal DFAs, you may alter the algorithm by adding a sink state, and redirect an important percentage of the transitions to this sink state.

But from my point of view, if you want to test the speediness of your implementation, check it against what you want to use it for: with random word sets or random REGEX, create a NFA or a DFA, and then minimize the resulting DFA.

# Answer
> 4 votes
You should look at Cyril Nicaud's homepage. In particular, the following references are relevant to your question:

F. Bassino, J. David and C. Nicaud, Enumeration and random generation of possibly incomplete deterministic automata, *Pure Mathematics and Applications* **19** (2-3) (2009) 1-16.

F. Bassino and C. Nicaud. Enumeration and Random Generation of Accessible Automata. *Theor. Comp. Sc.*. **381** (2007) 86-104.

# Answer
> 2 votes
one natural strategy is to regard the DFA as a graph and then there are many "natural" and highly studied random distributions of graphs, the simplest is probably Erdos-Renyi. in that case you treat all states of the DFA as nodes of the graph and some fixed percent of all possible edges (DFA transitions) are chosen. more sophisticated distributions that are studied much in the more recent era are small world graphs. for the strategy you mention in your question you are apparently choosing the special case $p=1/n$ where $n$ is the number of nodes in the graph. however your strategy, nor Erdos-Renyi, does not guarantee that all the states in the DFA are connected \[a natural constraint to add\].

---
Tags: algorithms, finite-automata, randomness, pseudo-random-generators, random-graphs
---


# Question
Title: Is the language that accepts strings concatenated with their reverse regular?
If the set of regular languages is closed under the concatenation operation and is also closed under the reverse operation ($x^R$ is the reverse of $x$) then is the language generated by $$\\{ww^R|w\in\Sigma^\*\\}$$ for some input alphabet $\Sigma$, also regular? If not, why not?

I've been trying to find a proof for this using the pumping lemma, but it seems that selecting any substring towards the middle of the string being pumped could also be of the form $\\{ww^R|w\in\Sigma^\*\\}$, causing the original string to remain in its original form.

Here's a try:

$\textbf{Theorem:}$ The language, $A$, generated by $\\{ww^R|w\in\Sigma^\*\\}$ is not regular.

$\textbf{Proof:}$ Assume $A$ is regular (We will use the Pumping Lemma for Regular Languages to show a contradiction). Let the input string $s$ be $ww^R$ and let $p = |w|$.

When splitting $s$ into substrings $x, y, z$ such that $s=xyz$ we see that $xy$ must be a substring of $w$ by the third condition of the Pumping Lemma ($|xy|\le p$).

By the first condition of the Pumping Lemma, we see that all strings of the form $xy^iz$ must be in $A$ for all $i \ge 0$. Taking $i$ to be zero, we obtain the string $xw^R$. $|x| \< |w^R|$ so $xy^0z \notin A$.

QED? What if $xw^R$ can still be split so that for some substring $k$, $kk^R = xw^R$?

I think I may be overthinking this but it's really bugging me.

# Answer
> 4 votes
You're over-thinking it on the $xw^R=ww^R$ thing, that's a red herring. But you're not over-thinking it by looking for a contradiction, you're looking in the wrong place.

First, your proof that the language is irregular is correct. You're aiming to show a contradiction. All you need is one counterexample; just one! And you found it already. This may seem paradoxical, but your understanding of how to operate on languages is a little off. As you noted, regular languages are closed under reversal:

$L^R = \\{w^R|w\in L\\}$

They are also closed under concatenation:

$L\circ L^R = \\{wv|w\in L, v\in L^R\\}$

But, you see, that's a little different from $L\_{mirrored} = \\{ww^R|w\in L\\}$. Look:

$L = \\{$ `cat, dog`$\\}$

$L^R = \\{$ `tac, god`$\\}$

$L\circ L^R = \\{$ `cattac, catgod, dogtac, doggod`$\\}$

$L\_{mirrored} = \\{$ `cattac, doggod`$\\}$

There's your contradiction! You must have thought those last two were the same, when they're not. Rather,

$L\_{mirrored} \subseteq L\circ L^R$

And the subset of a regular language is not necessarily regular.

edit: I removed a large chunk of this answer, so the comments below will probably be confusing...

# Answer
> 3 votes
Here is a short solution. Let $L = \\{ uu^r \mid u \in A^\*\\}$. If $A$ is empty or contains only one letter, then $L$ is regular. Suppose now that $A$ contains at least two letters, say $a$ and $b$. Using the pumping lemma, it is easy to see that the language $L \cap a^\*bba^\* = \\{a^nbba^n \mid n \geqslant 0 \\}$ is not regular. Therefore $L$ is not regular, since the intersection of two regular languages is regular.

# Answer
> 2 votes
Hint: Find a word $w$ so that for every proper substring $x$ of $w$, $xw^R$ is not of the form $zz^R$. As mentioned by Pål, you will only be able to find $w$ if the alphabet contains at least two letters. Also, naturally $w$ must depend on the pumping length $p$ (since your argument relies on $|w| \geq p$).

Not every word $w$ works, so your proof isn't complete. You have identified this problem yourself. Every step in a proof needs to be justifiable, otherwise it's not a proof. If there is a step you're not sure about, then it's not a proof.

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


# Question
Title: Is there a formal name for this graph operation?
I'm writing a small function to alter a graph in a certain way and was wondering if there is a formal name for the operation. The operation takes two distinct edges, injects a new node between the existing nodes of each edge and then adds an edge between the two new nodes. For example:

```
add new nodes a and b to the graph
let edge1 = (x,y), let edge2 = (u,v)

delete edge (x,y)
create edges (x,a), (a,y)

delete edge(u,v)
create edges(u,b), (b,v)

create edge (a,b)

```

# Answer
Your attempt is like subdivision. Actually you used two subdivision and finally you add extra edge between center of subdivision nodes.
> 2 votes

# Answer
No. No, there is not. You can come up with one if you'd like.
> 0 votes

---
Tags: graphs, terminology, combinatorics
---


# Question
Title: How many recursive calls are made by this gcd function?
In the following function, let $n \geq m$.

```
int gcd(n,m)
{
 if (n % m == 0) return m;
 n = n % m;
 return gcd(m, n);
}

```

How many recursive calls are made by this function?

* $\Theta (\log\_2 n)$
* $\Omega (n)$
* $\Theta (\log\_2(\log\_2 n))$
* $\Theta ( \sqrt{n} )$

I think the answer is $\Theta (\log\_2(\log\_2n))$, but my book is saying $\Theta (\log\_2 n)$.

My reasoning is as follows. Here we are not dividing the number. If there was a division then it would be $\log n$. But here operation is $\bmod$. So we will get a very small number after the first call. So it must be $\log \log n$. Am I thinking correctly?

# Answer
> 6 votes
Hint: on input $F\_{n+1},F\_n$, *gcd* makes a recursive call with inputs $F\_n,F\_{n-1}$. Now use the asymptotic formula $F\_n = \phi^n + \Theta(1)$, where $\phi = (1+\sqrt{5})/2 \> 1$.

Also, while we're at it, $\Theta(\log\_2 n) = \Theta(\log n)$, and similarly $O(\log\_2 n) = O(\log n)$ (and the same fore $\log\log n$); try to figure out why (here the base of $\log n$ can be arbitrary, but for definiteness you can choose base $e$).

# Answer
> 1 votes
First thing, drop the $2$ !! Here's the reason.. asymptotics don't really care much for the constants in the bases... $$ log\_an = \frac{log\_bn}{log\_ba}$$ Now $log\_ba$ is a just another constant, so you can drop it..

---

**Now**, about your question, the most important thing to notice here is the recursion...

* If you stare at the algorithm for sometime, you will see that the remainder is 'cut' into half in every 2 steps.
* And since it cannot go less than 1, there can be atmost $2.\[log\_2 n\]$ steps/recursions.
* Each step/recursion requires constant time, $\theta(1)$
* so this can be atmost $2.\[log\_2 n\].\theta(1)$ time
* and that's $\theta(log$ $ n)$

that was fun, right? :)

now, 'see' that our proof is fundamentally based on the observation that *the remainder halves in every two steps* make sure you prove that, (hint: i did my proofs with 'proof by cases method' and 'contradiction method')

---
Tags: algorithms, algorithm-analysis, arithmetic
---


# Question
Title: What is the reason of inaccuracy of operations on float numbers?
I wonder why in JavaScript

```
0.1 + 0.2  // return 0.30000000000000004

4%0.1 // return 0.09999999999999978

```

http://jsbin.com/oHISAfU/1/edit (Example)

In C the math.h library fmod function

```
printf("%f", fmod(4.0,0.1));  // print 0.100000

```

http://ideone.com/RG5Wyv (Example)

And in Spotlight (search feature in the Mac OS X ~ I already submit bug report) that support math operation

```
4%0.1 = 0.1

```

# Answer
It's because 0.1 = 1 / 10 = 1 / (2 × 5) cannot be represented exactly in binary floating point. This happens in C too:

```
 printf("%.20f", fmod(4.0,0.1));

```

prints `0.09999999999999978351`.

Specifically, the only numbers that binary floating point can represent exactly are dyadic fractions of the form *a* / 2*b*, where *a* and *b* are integers. Even more specifically, for IEEE single precision floating point numbers, *a* must be between -224 and 224 and *b* must, in effect, be between -151 and 104. (Or at least approximately so; there are some tricky special cases like denormalized numbers.) For double precision floats, the ranges are wider, but even so, a fraction like 1 / 10 cannot be represented exactly, because the denominator is not a power of two.
> 15 votes

# Answer
Ilmari Karonen gets it right in the other answer. But it gets even worse than that: arithmetic operations involving floating-point numbers don't necessarily behave the same as operators we're used to from mathematics. For instance, we're used to addition being associative, so that $a + (b + c) = (a + b) + c$. This doesn't generally hold using floating-point numbers, and for a given format it's not hard to come up with counterexamples. Not exactly relevant to the question you asked, except to illustrate that you should never assume floating point calculations are going to be exact.
> 8 votes

---
Tags: floating-point
---


title: Category theory (not) for Programming?

text:
# Question
Title: Category theory (not) for Programming?
After learning Haskell and other not so pure FP languages I decided to read about Category theory. After gaining good understanding of Category theory I started thinking about how the concepts of category theory can be used to think about **designing programs** but no matter how hard I tried it seems this is not the way to go.

After spending many unsuccessful attempts to relate category theory to **designing programs** I came to the conclusion that:

* Category theory is useful when **designing a programming language**.
* Category theory is not something that you use when **designing programs** (even when using a language which was designed based on category principles). For example: When programming in Haskell you will use types, types constructor, functions, higher order functions etc to design your program, not category theory concepts.

In summary we have below layer system (order is low to high):

**Category theory -\> Programming language -\> Program**

At a particular layer you use the concepts of the **immediate underlying layer**.

Is this understanding correct? If not and you believe that in **designing programs** we can directly use category theory concepts, please refer some articles or blog posts where it is being demonstrated.

NOTE: By **designing programs** I mean designing programs based on different concepts, like concurrency, parallelism, reactive, message passing etc.

# Answer
Well, that of course depends on what sort of program you are trying to design.

If you are designing an accounting program for your aunt's chocolate shop, I very much doubt category theory will be of much use.

But there are of course situations in which category theory is enormously useful in design of programs (by which I also mean data structures, libraries, and so on). Such situations occur mostly when the programs involved are of a mathematical nature.

If you want to write programs that compute with exact real numbers and other structures occurring in mathematical analysis, the first question you need to answer is what it means to *correctly* implement a complicated mathematical object (such as a differentiable function, a manifold, etc.). Here it helps very much to know some category theory and logic, because they give you a systematic way of translating definitions of mathematical structures to specifications and implementations of corresponding data structures. The buzzword you should look for is *realizability theory*. But this is just one example.

The best way to see how category theory comes in handy is to look at programs written by people who know a lot of category theory (and mathematics in general). An obvious example of this is Martín Escardó and his impossible functionals, for instance:

> M. Escardó and P. Oliva: What Sequential Games, the Tychonoff Theorem and the Double-Negation Shift have in Common, Mathematically Structured Functional Programming 2010, ACM Press. (with companion Haskell and Agda files)

You may complain that this is not just category theory but also logic and topology. Such complaints would be severely misguided. The best category theory is always mixed with other things.

Lastly, I would advise against drawing grand conclusions about nature of things based on a bit of self-assigned reading.
> 14 votes

# Answer
People used to use CT to describe data types.

1. The data type was defined by a particular category whose objects are finite sequences of (specification language) types, and whose arrows were projections or else compositions of the data type operations. For example, the object is the domain and is the codomain of the push operation of stacks. This gives you syntax, but you still don't have a notion of semantics.
2. An algebra, which is to say, an instance of the type, is a functor from the theory to Ens, the category of (small) sets. (We use "small" to avoid Russell's paradox, but it doesn't mostly matter.)
3. It turns out that closure properties of the categories correspond to families of logical theories. For example, if the theory category is closed under products, the data type can be axiomatized by equations. If the theory category is closed by taking pullbacks, then the data type can be axiomatized by Horn sentences.

I'm not completely sure anybody pays attention to this any more. I would think that this, and the links there, would explain it in more detail.
> 7 votes

---
Tags: functional-programming, category-theory
---


# Question
Title: Document definition in information retrieval
Is there common formal definition of **Document** in information retrieval field? In many researches authors don't define the term **Document**(maybe because it is evident for them). Wikipedia says "text file, document (computer science) a computer file that contains text" but it doesn't seem as common formal definition.

Do you know the common formal definition of **Document**, or, if not, do you know any researches where that term was defined?

# Answer
For a formal definition of *document* in the Information Retrieval context, you can look at IR glossaries.

A common definition is:

> **Document**: Specific unit of retrieval (usually text). It can be a web page, an article, a book, a section or chapter.

(see for example the Glossary of the book Modern Information Retrieval by Ricardo Baeza-Yates and Berthier Ribeiro-Neto)
> 3 votes

---
Tags: terminology, data-mining, information-retrieval
---


# Question
Title: Searching a value in a "piecewise" ordered array
If we have an array $A$ of length $N$, which is partitioned into $\sqrt{N}$ adjacent subarrays $A(i)$, each of which is monotonically ordered from $\min(i)$ to $\max(i)$ (it is known what places have those bounds in A for each subarray), with the following conditions:

```
min(i) < min(i+1),
max(i) < max(i+1),
min(i+1) < max(i),
If subarrays A(i) and A(i+1) both have the j-th element, then A(i,j) < A(i+1,j),
The number of elements in subarray A(i) is strictly increasing with i

```

Would it be possible to search an element in the array $A$, in time $O((\log N)^k)$, for a positive $k$? If yes how?

If not, what kind of minimal additional conditions would allow that?

Edit. The subarrays are not necessarily of equal length. They are strictly increasing. The above stated conditions are always guaranteed.

What I have tried so far is to binary search them separately, but that is obviously going to be very inefficient.

\[Note that this question has obviously nothing to do with the search of the min of max value in the array. And I am not interested in sorting the array. Just the mere search.\]

# Answer
> 1 votes
It should be possible to do this with $O(\sqrt{N})$ comparisons, saving an $O(\log N)$ factor over the straightforward "binary search each subarray".

The last condition, that the lengths of the subarrays strictly increases, makes things messy. The analysis of $M$ subarrays, each of length $M$, is easier and it should be straightforward to extend the method to increasing-length subarrays. Note that $\log M = O(\log N)$.

Also complicating things are the strict inequalities; it is easier to work with non-strict inequalities (which are also more general).

Finally, the conditions ensure that in subarray $A(i)$, the first element $A(i,1)$ is the minimum value and the last element $A(i,M)$ is the maximum value, so there is no need to deal with these elements explicitly. This yields the simplified problem

1. there are $M$ subarrays of equal length $M$, and
2. for all $i,j$

* \[monotonicity across subarrays\] $A(i,j) \le A(i+1,j)$,
    * \[adjacent subarrays overlap\] $A(i+1,1) \le A(i,M)$, and
    * \[monotonicity within subarrays\] $A(i,j) \le A(i,j+1)$.

If there is $u$ such that $A(u,1) \le n \< A(u+1,1)$, then only the first $u$ subarrays need to be considered, and similarly for $v$ such that $A(v-1,M) \< n \le A(v,M)$ focuses attention on the last $v$ subarrays; together their intersection defines a set of subarrays that must contain $n$. The rest of the subarrays can be ignored. This preprocessing can be done in $O(\log N)$ steps.

Then $A(i,1) \le n \le A(i,M)$ is guaranteed for each remaining $i$ in the range $M-v+1$ to $u$, otherwise $n$ is not in the array. For the remainder, suppose that the preprocessing did nothing, so $u=v=M$ (this is the worst case). Run binary search on the middle subarray $w=\lfloor M/2\rfloor$; this determines that $A(w,j) \< n \< A(w,j+1)$; (if equality holds then $n$ has been found).

By monotonicity across subarrays, $A(i,j) \le A(w,j) \< n$ for all $i \le w$ and similarly $n \< A(w,j+1) \le A(i,j+1)$ for all $i \ge w$.

Now we need to recursively search about half of the remaining elements, considering the two rectangular blocks $A(1,j+1)..A(w-1,M)$ and $A(w+1,1)..A(M,j)$ in turn. There are $M$ calls to check a block, but successive calls receive exponentially smaller blocks to work with. Amortising the work across calls, the total work is $O(\sqrt{N})$ steps as each leaf of the search tree only does a constant amount of work. More precisely this relates to solving the recurrence $f(n) = 2f(n/4) + \log n$ for which $f(n) \in O(\sqrt{n})$.

So overall, $O(\sqrt{N})$ steps suffice.

Note that the overlap of adjacent subarrays may be of use when extending to increasing-length subarrays, or in improving the algorithm, but isn't used here.

As far as I can tell, $\Omega(\sqrt{N})$ is also a lower bound. A handwaving argument is that in the worst case, when all the values are close except for a single missing value, that value could be hidden in any of the rows and each row must be examined at least once.

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


# Question
Title: To what factor can I compress information from binary to Quinary
I am trying to think if we can have an injective mapping $\mathcal{f}$, say something like $\Sigma\_{bool}= \\{0,1\\}^\* $ to $\Sigma\_{5} = \\{0,1,2,3,4\\}^\* $ such that $|x| \leq 2.|\mathcal{f}(x)|$

The motivation here is simple, consider I have a word $110110110110110110110$, so i can compress and represent that as $(110)^7$ or $110,111$ so what can i do if i am allowed to use symbols from $\Sigma\_5$?

I hope my question made sense :)

# Answer
> 4 votes
Here is a simple way to get the inequality $|f(x)| \leqslant {1 \over 2}(|x| + 3)$. Just encode words by blocks of length $2$ using the coding $00 \to 0$, $01 \to 1$, $10 \to 2$ and $11 \to 3$ and add the suffix $40$ or $41$ for the last letter if the length of the word is odd. For instance, $f(11011000) = 3120$, $f(11011000\mathbf{0}) = 3120\mathbf{40}$ and $f(11011000\mathbf{1}) = 3120\mathbf{41}$.

One can improve this inequality to $$ (\*) \qquad|f(x)| \leqslant \biggl\lceil{1 \over \log\_2 5}|x| + C\biggr\rceil $$ where $\log\_2 5 \approx 2.3219\cdots$ and $c = \frac{3}{\log\_2 5}-1 \approx 0.2920\cdots$. Indeed, the number of words of length $\leqslant n$ in $\Sigma^\*$ is $\frac{|\Sigma|^{n+1}-1}{|\Sigma|-1}$. Therefore, there is an injection from $\Sigma\_2^{\leqslant n}$ to $\Sigma\_5^{\leqslant m}$ if and only if $$ 2^{n+1} - 1 \leqslant \frac{1}{4}(5^{m+1} - 1) $$ which gives $4(2^{n+1} -1) \leqslant 5^{m+1} - 1$, or equivalently, $2^{n+3} \leqslant 5^{m+1} + 3$. This inequality is already satisfied if $2^{n+3} \leqslant 5^{m+1}$, that is, if $n+3 \leqslant (m+1)\log\_2 5$. In particular, if you choose $m = \lceil {1 \over \log\_2 5}n + C\rceil$, one can build an injection $f$ from $\Sigma\_2^\*$ to $\Sigma\_5^\*$ satisfying $(\*)$ as follows. Recall that the *shortlex* (or *radix*) order is the order $\leqslant$ on $\Sigma^\*$ defined by $u \leqslant v$ if and only if $|u| \< |v|$ or $|u| = |v|$ and $u \leqslant\_{lex} v$. That is, words are first ordered by length and words of equal length are ordered according to the lexicographic order. The shorlex order is a total order on $\Sigma\_k^\*$ and hence each word $u$ has a rank $r\_k(u)$ in this order. For instance, for $k = 2$ you get $r\_2(\varepsilon) = 0$, $r\_2(0) = 1$, $r\_2(1) = 2$, $r\_2(00) = 3$, $r\_2(01) = 4$, $r\_2(10) = 5$, $r\_2(11) = 6$, $r\_2(000) = 7$, etc. For $k = 5$, you have $r\_5(\varepsilon) = 0$, $r\_5(0) = 1$, $r\_5(1) = 2$, $r\_5(2) = 3$, $r\_5(3) = 4$, $r\_5(4) = 5$, $r\_5(00) = 6$, $r\_5(01) = 7$, etc. Given $u \in \Sigma\_2^\*$, you now define $f(u)$ has the unique word $v \in \Sigma\_5^\*$ such that $r\_5(v) = r\_2(u)$ or, if you prefer, $f(u) = r\_5^{-1}(r\_2(u))$. This $f$ will satisfy $(\*)$ but is of course more difficult to compute than the first coding.

---
Tags: formal-languages, data-compression
---


# Question
Title: Worst-case time algorithm?...which one is faster?
Imagine that an algorithm A runs in worst-case time $f(n)$ and that algorithm B runs in worst-case time $g(n)$. Answer either yes, no, or can’t tell and could you explain me why?

Is A more faster than B, for all $n\>n\_0$ if $g(h)=Ω(f(n)\log n)$?

Is A more faster than B, for all $n\>n\_0$ if $g(n)=O(f(n)\log n)$?

Is A more faster than B, for all $n\>n\_0$ if $g(n)=Θ(f(n)\log n)$?

# Answer
If $g(n) = \Omega(f(n)\log n)$ then for large $n$, $g(n) \geq Cf(n)\log n$ (for some $C \> 0$, and so algorithm $B$ takes more time than algorithm $A$ (in the worst case). In other words, algorithm $A$ is faster.

If $g(n) = O(f(n)\log n)$ then all we know is that for large $n$, $g(n) \leq Cf(n)\log n$; it could be that also $g(n) = \Omega(f(n)\log n)$, in which case algorithm $A$ is faster; or it could be that $g(n)$ is constant while $f(n) = n$ (for example), in which case algorithm $B$ is faster; and there are other possibilities.

If $g(n) = \Theta(f(n)\log n)$ then in particular $g(n) = \Omega(f(n)\log n)$, and so we revert to the first case.
> 2 votes

# Answer
I think that the first statement holds true in all cases; as from the definition of $\Omega$ we can say that $g(n)$ is not dominated by $f(n)\log n$ so we can say that $f(n)$ is faster than $g(n)$ since it must hold true for all $n\>n\_0$. Hence A is faster than B if $g(n)=\Omega(f(n)\log n)$.
> 1 votes

---
Tags: algorithms, algorithm-analysis, time-complexity
---


title: Bayesian Network - Inference

text:
# Question
Title: Bayesian Network - Inference
I have the following Bayesian Network and need help with answering the following query.

**EDITED:**

Here are my solutions to questions a and b:

**a)**

```
P(A,B,C,D,E) = P(A) * P(B) * P(C | A, B) * P(D | E) * P(E | C)

```

**b)**

```
P(a, ¬b, c ¬d, e) = P(a) * P(¬b) * P(c | a, b) * P(¬d | ¬b) * P(e | c)

= 0.02 * 0.99 * 0.5 * 0.99 * 0.88 = 0.0086

```

**c)**

P(e | a, c, ¬b)

This is my attempt:

```
a ×  ∑ P(a, ¬b, c, D = d, e) =
     d

 a × ∑  { P(a) * P(¬b) * P(c | a, b) * P(d) * P(e | c) + P(a) * P(¬b) * P(c | a,b)    *P(¬d)
     d                                                                  + P(e | c) }

```

Note that a is the alpha constant and that a = 1/ P(a,¬b, c)

The problem I have is that I don't know how to compute the constant a that the sum is multiplied by. I would appreciate help because I'm preparing for an exam and have no solutions available to this old exam question.

# Answer
> 3 votes
You're on the right path. Here's my suggestion. First, apply the definition of conditional probability:

$$ \Pr\[e|a,c,\neg b\] = {\Pr\[e,a,c,\neg b\] \over \Pr\[a,c,\neg b\]}. $$

So, your job is to compute both $\Pr\[e,a,c,\neg b\]$ and $\Pr\[a,c,\neg b\]$. I suggest that you do each of them separately.

To compute $\Pr\[a,\neg b,c,e\]$, it is helpful to notice that

$$ \Pr\[a,\neg b,c,e\] = \Pr\[a,\neg b,c,d,e\] + \Pr\[a,\neg b,c,\neg d,e\]. $$

So, if you can compute terms on the right-hand side, then just add them up and you've got $\Pr\[a,\neg b,c,e\]$. You've already computed $\Pr\[a,\neg b,c,\neg d,e\]$ in part (b). So, just use the same method to compute $\Pr\[a,\neg b,c,d,e\]$, and you're golden.

Another way to express the last relation above is to write

$$ \Pr\[a,\neg b,c,e\] = \sum\_d \Pr\[a,\neg b,c,D=d,e\]. $$

If you think about it, that's exactly the same equation as what I wrote, just using $\sum$ instead of $+$. You can think about whichever one is easier for you to think about.

Anyway, now you've got $\Pr\[e,a,c,\neg b\]$. All that remains is to compute $\Pr\[a,c,\neg b\]$. You can do that using exactly the same methods. I'll let you fill in the details: it is a good exercise. Finally, plug into the first equation at the top of my answer, and you're done.

# Answer
> 2 votes
$$ \Pr\[e|a,c,\neg b\] = {\Pr\[e,a,c,\neg b\] \over \Pr\[a,c,\neg b\]} $$

$$ \Pr\[e,a,c,\neg b\] = \sum\_{d} Pr\[a,\neg b,c, D = d, e\] = Pr\[a, \neg b, c, d, e\] + Pr\[a, \neg b, c, \neg d, e\] = $$

$$ = P(a) * P(\neg b) * P(c | a,\neg b) * P(d | \neg b) * P(e|c) + $$

$$ P(a) * P(\neg b) * P(c | a,\neg b) * P(\neg d | \neg b) * P(e|c) = $$

$$ ..... = 0.0148 $$

$$ \Pr\[a, \neg b, c\] = P\[a, \neg b, c, D, E\] = \sum\_{d} \sum\_{e} P\[a, \neg b, c, D= d, E = e\] = $$

$$ P\[a, \neg b, c, d, e\] + P\[a, \neg b, c, d, \neg e\] + P\[a, \neg b, c, \neg d, e\] + P\[a, \neg b, c, \neg d, \neg e\] = $$

$$ = / ........ / = C $$

Now we have that:

$$ \Pr\[e|a,c,\neg b\] = {\Pr\[e,a,c,\neg b\] \over \Pr\[a,c,\neg b\]} = 0.0148 / C $$

---
Tags: probability-theory
---