# Question
Title: Solving Subproblem in Logic (first-order, propositional, pddl)
## One sentence question

Is there any algorithm able to prove (solve) a logic problem (first-order, propositional, pddl) by finite induction?

## Background

I am researching Hierarchical planning solvers and I found the following problem. Let a problem climb a stairway. An agent is able to move up or down. For example, suppose the following "move up" action:

```
moveup(position):
    pre-condition: on(position)
    post-condition: ~on(position) ^ on(next(position)

```

Now, let a stairway be defined as:

```
stairway:
   next(first_step) = second_step
   next(second_step) = third_step
   ...
   next(nminusoneth_step) = nth_step

```

and, a start point from agent is on the first step:

```
on(first_step)

```

Now, I want to create a plan to bring the agent from the first step to last one. Of course, I can solve that in many different ways (brute force for example), but I know how to climb an one-step stairway (just move up) so, I am able to infer that all I need to climb an n-step stairway is just moving up (it is not necessary to decide each action individually). Is there already any algorithm for that (recognize a subproblem structure and infer actions by induction)?

# Answer
> 2 votes
In general, using mathematical induction to prove theorems automatically is quite difficult. First, note that this isn't really a problem of first-order vs second-order logic, since induction can easily be expressed as a *schema* in FOL, and generally be reduced to a finite set of axioms. It's more useful though to keep it as a schema, and add induction as a logical rule rather than a list of axioms.

This has been studied quite a bit, but success of general purpose automatic theorem provers is somewhat limitied in the presence of induction, for the following reasons:

* (Of course) the first order (quantifier free) theory with induction is undecidable. A good milestone of how undecidable a theory is is to measure how expressive the resulting theory is, and the theory with induction is essentially capable of expressing a large part of elementary mathematics quite easily. This is a pretty bad sign.
* Induction is *always* applicable: *any* goal which contains *some* occurrence of an inductive data type (like a list or a natural number) may be proven (indeed, may *need* to be proven) by induction. Clearly there needs to be a clever heuristic to decide when to apply induction. The general rule is: do everything but induction, and apply induction as an absolute last resort! Even with this heuristic, you need to know when to give up, which is again undecidable, but necessary if any kind of backtracking is to be performed.
* Sometimes the goal needs to be *generalized*. This is a distinctive phenomenon of induction, that sometimes the induction hypothesis is *too weak* to prove the conclusion, and as a result the whole goal needs to be *strengthened*, which is rather counter-intuitive (failure to prove a goal results in trying to prove a stronger one!). Finding and proving these strengthenings automatically is the subject of exciting current research in computer science (in the field of *loop invariant synthesis*).

Given all these difficulties, it's clear there's no general purpose algorithm for proving theorems by induction in full generality. However the problem itself is being actively studied, and I'll just leave you with this link to a workshop specifically addressing this problem.

---

As a footnote, your problem doesn't seem to be solvable with much else than standard "brute force" (or resolution), since the algorithm needs to verify that the last step is reachable by explicitly going through all the steps. Unless you have further knowledge (e.g. each step corresponds to a natural number), you need to verify that each step can be taken, and that there are no "breaks".

# Answer
> 0 votes
I didn't solve yet but I found important insights and pitfalls.

**Mathematical induction** is the Mathematical reasoning that allows generalization the one proposition over a whole *well-ordered* set following:

1. the proposition should applies over a base element, and
2. if the proposition applies over any element of the set then it should implies that to next element;

Mathematical induction is an Axiom of second-order logic. Therefore, it could not be apply directly in first-order logic. A possible solution is identify *well-ordered* sets over the belief base.

---
Tags: logic, induction
---


title: Parameterized Dominating Set

text:
# Question
Title: Parameterized Dominating Set
What is the best algorithm to compute p-dominating set?

The p-dominating set problem is a parameterized version of minimum dominating set in which the problem takes a parameter $k$ also as an input, and the problem is now whether there exist a dominating set of cardinality at most $k$.

I know the problem is W\[2\]-hard so there is no chance of getting a $f(k) n^c$ running time algorithm unless the parameterized hierarchy collapses.

# Answer
> 4 votes
Well, you can always solve it in XP time by trying all possible $k$-sets. In fact, it was shown by Pătraşcu and Williams \[1\] that there is no $O(n^{k-\varepsilon})$-time algorithm for $k$-dominating set for any $\varepsilon \> 0$, assuming SETH.

This is almost tight as for $k \geq 7$, the problem can be solved in $n^{k+o(1)}$ time (see \[1\]). As a special case, you can solve 2-dominating set in $O(n^\omega)$ time, where $\omega \< 2.376$ using matrix multiplication.

---

\[1\] Pătraşcu, Mihai, and Ryan Williams. "On the possibility of faster SAT algorithms." Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. 2010.

---
Tags: graphs, parameterized-complexity
---


# Question
Title: Vertex cover problem with 2-element vertices
Let $G = (W, E)$ be an undirected graph, where $W = \\{(v\_i,v\_j) \in V \times V : v\_i \> v\_j\\}$ and $E$ is a set of $2$-element subsets of $W$ such that, given two edges $e\_1 = (w\_1, w\_2)$ and $e\_2 = (w\_1, w\_3)$, $(w\_2, w\_3) \in E$ necessarily if there exists some $v$ belonging to $w\_1$, $w\_2$ and $w\_3$. (For example, if $((v\_1, v\_2), (v\_1, v\_3)) \in E$ and $((v\_1, v\_2), (v\_1, v\_4)) \in E$, then $((v\_1, v\_3), (v\_1, v\_4)) \in E$.)

In such a scenario, we want to remove the minimum number of vertices in $W$ to disconnect the graph, taking into consideration that whenever we remove a vertex $w = (v\_1, v\_2)$, the rest of the vertices containing $v\_1$ or $v\_2$ must be removed as well.

My question is whether this is actually the *vertex cover problem* in disguise or, somehow, the restrictions applied above make it easier or more difficult to solve it.

As an example, consider the following graph, where it's clear that removing $v\_2$, $v\_3$ or $v\_4$ leads to the disconnection of the majority of vertices in $W$.

# Answer
Assuming you want the resulting graph to be disjoint (contain only isolated vertices), then your problem is as hard as the vertex cover problem. There is a simple reduction.

Let $G^\*=(V^\*,E^\*)$ be an undirected graph, where $V^\* = \\{v\_1,v\_2,\dots,v\_n\\}$. Define $V = \\{v\_1,\dots,v\_{2n}\\}$, and define $E$ by creating edges $((v\_i,v\_{i+n}),(v\_j,v\_{j+n}))$ for each $i,j$ such that $(v\_i,v\_j) \in E^\*$. Note that this automatically satisfies all of your constraints, as there are no pair of edges $(w\_1,w\_2)$, $(w\_1,w\_3)$ in $E$ that share a common $v\_i$. Thus, given $G^\*$, we can define a new graph $G$ of your form.

Any way to remove vertices in $G$ corresponds immediately to a way to remove vertices in $G^\*$, and vice versa. Moreover, the minimum number of vertices you can remove from $G$ to leave every vertex isolated is equal to the minimum number of vertices you can remove from $G^\*$ to leave every vertex isolated. The latter is exactly the vertex cover problem. Therefore, we've shown a reduction from vertex cover to your problem: if we could solve your problem for $G$, we could solve vertex cover for $G^\*$.
> 6 votes

---
Tags: algorithms, graphs, optimization
---


title: Regular and Non-Regular Language

text:
# Question
Title: Regular and Non-Regular Language
My friends and I are taking a formal languages class and for one of our homework questions we have to prove if these languages are regular:

1) L = {apaqi : p and q are fixed integer values, i \>= 0}

2) L = {apbq : p and q are fixed integer values}

For (1), we know it is regular because we can make a DFA out of it, but what we are not sure how exactly the DFA should look like. Should it not be consist only of one state, say q0, and it acts as both the initial and final state, with a loop of "a" moves going through it? Our line of thought is because p and q could be any integers, so whatever p and q would be, we would always end up with a certain number of a's, but we are not sure we are 100% correct.

For number (2), we say it is not regular because p and q could be infinite, thus making the language automatically irregular.

We are still quite confused on which concepts are correct. This is still a very abstract concept for all of us and any guidance would be appreciated. Thank you!

# Answer
> 1 votes
Think of it this way. Fix $p$ and $q$ arbitrarily – for example, take $p = 4$ and $q = 5$. Then $$ \begin{align\*} L\_1 &= \\{ a^4 b^{5i} : i \geq 0 \\}, \\ L\_2 &= \\{ a^4 b^5 \\}. \end{align\*} $$ Now try to answer your question. The answer will be the same no matter what values you choose for $p$ and $q$.

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


title: Algorithm to find pronounciation rules

text:
# Question
Title: Algorithm to find pronounciation rules
Suppose that you have a large dictionary with spellings and pronounciations of foreign words, and you want to find a set of pronunciation rules. They should have the simplest form: a sequence of letters to a sequence of sounds.

For example, in French, *c* \[k\], *i* \[i\] and *ci* \[si\].

1. The rules may be long: *tion* \[sjɔ̃\] (instead of \[tjɔ̃\]).
2. They may be rare: *à* \[a\] is used only in a dozen of words.
3. They may be both: *aill* \[aj\] (as *a-ill*, instead of *ai-ll* \[ɛl\]).

Fortunately, such rules are rare enough: for the most part, the letters are pronounced by itself, even most of them in complicated rules. For examples, *cercle* \[sɛʀkl\] instead of \[kɛʀklɛ\]: the algorithm should notice the corresponding sounds in the middle of the word.

Maybe, there is a standard algorithm to extract candidates for such rules? I would like to have an explicit list of rules, rather than a method predicting pronunciation.

# Answer
> 2 votes
Broadly, I can see two possible approaches: machine learning, or data mining

## Machine learning

You could look into using machine learning to learn a transducer that transforms the input sequence (the letters in the word) to the output sequence (the pronunciation). This approach doesn't try to find an explicit set of rules; it just tries to find a method that is effective in practice at producing the right pronunciation.

You could try training a recurrent neural network (RNN), and/or a LSTM network. LSTM's have been effective at related tasks, and since you have a large training set, they might possibly be effective here. Bi-directional RNN's/LSTM's might be worth exploring.

## Data mining

Alternatively, you could use data mining techniques to try to find an explicit set of rules that seem to have good support among your dictionary.

This problem fits into the general area of sequence mining (also known as sequential pattern mining) and association rule learning. I think it might be fruitful to try applying one of the algorithms from that field, to your problem.

In your case, you could consider each possible substring of the word or pronunciation to be a possible item, and your goal is to find rules of the form $x \Rightarrow y$, where $x$ is a substring of the word and $y$ is a substring of the pronunciation. This is a special case of itemset mining, where your itemsets are restricted to have size 1. You could then adapt any standard itemset algorithm (e.g., Apriori, FP-growth) to this problem.

For instance, here is an adaptation of Apriori. You consider all possible rules of the form $x \Rightarrow y$, where $x$ and $y$ are length 1. For each, you compute their support or some probabilistic measure of the strength of the association (e.g., out of all words that contain $x$, what fraction contain $y$?). Discard all candidate rules for which this metric is below some threshold. Then, try all extensions of this rule by extending either $x$ or $y$ by one character to the left or right side of it; this gives you a bunch more candidates. For each such candidate, compute the metric and discard those that are below the threshold. Keep expanding your set of candidates until no new candidates can be identified. This is basically a form of "breadth-first search". Finally, at the end, prune your rules by eliminating rules with a containment relationship (e.g., if you have a rule $x \Rightarrow y$, then you might want to remove all other rules of the form $x' \Rightarrow y'$ where $x'$ is a substring of $x$ and $y'$ is a substring of $y$).

You could also consider similar tweaks to FP-growth.

However, it's not clear to me how well a data mining-based approach will work: while it does consider order to some extent, it doesn't take into account the position within the word, and it doesn't consider whether a set of rules fully covers all of the characters in the word, and it doesn't take into account rule overlap (e.g., $x\_1 \Rightarrow y\_1$ and $x\_2 \Rightarrow y\_2$ where $x\_1,x\_2$ overlap partially).

---
Tags: algorithms, machine-learning, data-mining, computational-linguistics
---


# Question
Title: Design a grammar for this context-free language
I am doing an exercise from Models Of Computation - Ch - 5, Q-1(r).

Design a grammar that generates this context-free language

$\\{ x\space\\$\space y^R \\,|\\, x, y \in\\{0, 1\\}^\* \text{ and } x \ne y\\}$

Any hint will be nice.

(**My try**: I can't seem to come up with a grammar. The pushdown automaton that can accept this language seems easy though. First push all of x into the stack, which can be identified on seeing the $. Keep matching y's characters one by one with top of stack character and pop until the first mismatch. If no mismatch is encountered and the stack is empty as well as y is exhausted, then reject. If a mismatch is encountered, *or* if the stack becomes empty before y is exhausted, *or* y is exhausted and stack is still not empty, then accept.)

# Answer
> 1 votes
Hint: Break this into four different cases:

1. Words of the form $x\\$y$ where $|x|\>|y|$.
2. Words of the form $x\\$y$ where $|x|\<|y|$.
3. Words of the form $\Sigma^\* 0 \Sigma^n \\$ \Sigma^n 1 \Sigma^\*$.
4. Words of the form $\Sigma^\* 1 \Sigma^n \\$ \Sigma^n 0 \Sigma^\*$.

# Answer
> 1 votes
Since I have been told to somehow prove that the grammar indeed generates the language describe, I am adding that in the form of an answer.

Breaking the language into 6 subsets (not mutually exclusive) and giving rules for generating each. The first two cases generate all those words such that $|x| \ne |y|$

* *Case 1:* $|x| \> |y|$

$\begin{align\*} X\_{Longer} &\to (0 \mid 1) \space X\_{Longer} \space (0 \mid 1) \\ X\_{Longer} &\to (0 \mid 1)^+ \space \\$ \end{align\*}$
* *Case 2:* $|x| \< |y|$

$\begin{align\*} Y\_{Longer} &\to (0 \mid 1) \space Y\_{Longer} \space (0 \mid 1) \\ Y\_{Longer} &\to \\$\space(0 \mid 1)^+ \end{align\*}$

The next 4 cases generate words where the first mismatch occurs at the $(|x| - n + 1)$-th character of string $x$ and $n$-th character of string $y$ for all $n \> 0$. (Note, $(|x| - n + 1)$-th character of string $x$ is the same as saying $n$-th character of $x^R$)

The rules have names of the form $M\_{c, l, r}$ where $c$ is the character which repeats consecutively $n$ times toward the front and back of the $\\$$ before the mismatch. $l$ and $r$ are the mismatching characters in $x$ and $y$ respectively.

* *Case 3:* Words of the form $(0\mid1)^\*\space 0 \space 1^n\space\\$ \space 1^n \space 1 \space (0\mid1)^\*, \forall n \geq 0$

$M\_{1, 0, 1} \to (0\mid1)^\*\space 0 \space O \space 1 \space (0\mid1)^\*$
* *Case 4:* Words of the form $(0\mid1)^\*\space 1 \space 1^n\space\\$ \space 1^n \space 0 \space (0\mid1)^\*, \forall n \geq 0$

$M\_{1, 1, 0} \to (0\mid1)^\*\space 1 \space O \space 0 \space (0\mid1)^\*$
* *Case 5:* Words of the form $(0\mid1)^\*\space 0 \space 0^n\space\\$ \space 0^n \space 1 \space (0\mid1)^\*, \forall n \geq 0$

$M\_{0, 0, 1} \to (0\mid1)^\*\space 0 \space Z \space 1 \space (0\mid1)^\*$
* *Case 6:* Words of the form $(0\mid1)^\*\space 1 \space 0^n\space\\$ \space 0^n \space 0 \space (0\mid1)^\*, \forall n \geq 0$

$M\_{0, 1, 0} \to (0\mid1)^\*\space 1 \space Z \space 0 \space (0\mid1)^\*$

And to complete, there's the $O$ and $Z$ rules

$\begin{align\*} O &\to 1\space O \space 1 \\ O &\to \\$ \\ Z &\to 0\space Z \space 0\\ Z &\to \\$ \end{align\*}$

So the starting non-terminal is:

$S \to X\_{Longer} \mid Y\_{Longer} \mid M\_{1, 0, 1} \mid M\_{1, 1, 0} \mid M\_{0, 1, 0} \mid M\_{0, 0, 1}$

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


# Question
Title: Can a DFA just have one state that is both the initial state and the final state?
so im trying to create a DFA for a language that has an infinite number of possible strings over the alphabet {a,b}.

can i not just have one state (initial and final state) that loops a,b to itself?

thanks

# Answer
> 2 votes
A DFA is defined as a tuple $\langle \Sigma,Q,\delta,q\_0,F \rangle$, with $\Sigma$ a finite alphabet, $Q$ a set of states, $\delta$ a transition function, $q\_0$ an initial state, and $F\subseteq Q$ a set of accepting states.

Take $Q=F=\\{q\_0\\}$ with $\delta(q\_0,\sigma)=q\_0$ for every $\sigma$. This DFA accepts every string, since it's run is always of the form $q\_0,q\_0,q\_0,...,q\_0$, and $q\_0\in F$.

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


title: Tile Problem : Dynamic Programming

text:
# Question
Title: Tile Problem : Dynamic Programming
Came across the following tile problem :

```
Given a “2 x n” board and tiles of size “2 x 1″, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.

```

Recurrence formula is as mentioned below :

```
count(n) = n if n = 1 or n = 2
count(n) = count(n-1) + count(n-2)

```

Explanation is as follows :

```
count(n-1) : If the first tile is placed vertically, then problem reduces to a grid of size "2 x (n-1)"
count(n-2) : If the first tile is placed horizontally, then problem reduces to a grid of size "2 x (n-2)", because we will need to place two tiles horizontally one above the other

```

But my doubt is, the above recurrence is fine if we always place the tiles at the left most side of grid. What if I place the first vertical tile at center of grid instead of the left most. Should not be covering all the permutation and combinations possible on basis of where we place the first tile?

# Answer
Your understanding of reducing the given problem to a subproblem is flawed. Say you have to place the tiles, if you start from the centre and keep on placing the tiles, finally the arrangement you have can also be obtained by placing tiles from the left hand side. You don't want to double count. So the recurrence relation you mentioned is correct.
> 4 votes

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


title: Why is ZPP = RP ∩ co-RP?

text:
# Question
Title: Why is ZPP = RP ∩ co-RP?
I am trying to prove the theorem that ZPP = RP $\\; \cap \\; co-RP$. If $L \in \\; \subseteq RP \\; \cap \\; co-RP$ then I can see that it belongs to $ZPP$. But I am unable to prove the reverse direction, as definitions of $RP$ and $co-RP$ don't include Turing machines whose *expected* running time is polynomial, but $ZPP$'s definition does. Am I missing something ? How should I proceed ?

# Answer
> 10 votes
The solution is given in the link provided by you in wikipedia article ZPP. See the section Intersection Definition in the link. You need to know about Markov's Inequality though.

Markov's inequality is $P\[ X \geq a\] \leq E\[X\]/a$ if $X \geq 0$. If we substitude $a = 2E\[X\]$ then we will have $P\[ X \geq 2 E\[X\]\] \leq 1/2$.

So, basically we run the algorithm that witnesses $L \in \textrm{ZPP}$ for at least double its expected running time. If it gives an answer, then we give that answer. If it doesn't give any answer before we stop it, we give NO answer. The probability of incorrect NO answer is $\leq 1/2$. This polynomial time algorithm proves $L \in \textrm{RP}$.

If we give answer YES on forced stoppage then that algorithm proves $L \in \textrm{co-RP}$. Thus $\textrm{ZPP} \subseteq \textrm{RP} \cap \textrm{co-RP}$.

For the sake of completeness, I also give the proof of $\textrm{RP} \cap \textrm{co-RP}\subseteq\textrm{ZPP}$.

Suppose we have a language $L \in \textrm{RP} \cap \textrm{co-RP}$. Then $L$ has a polynomial time algorithm $A$ that answers YES at least 1/2 times for $x \in L$ and a polynomial time algorithm $B$ that answers NO at least 1/2 times for $x \not\in L$. In one iteration we do the following: Given an input $x$ in $L$, we run $A$ on $x$. If it returns YES, the answer must be YES, so we return YES. Otherwise, we are in doubt so we run $B$ on the input. If it returns NO, the answer must be NO, so we return NO. If neither occurs, we repeat this iteration. We can show that the expected running time of this algorithm is still polynomial. Thus $\textrm{RP} \cap \textrm{co-RP}\subseteq\textrm{ZPP}$.

---
Tags: complexity-theory, time-complexity, probability-theory, randomized-algorithms, probabilistic-algorithms
---


# Question
Title: Are there improvements on Dana Angluin's algorithm for learning regular sets
In her 1987 seminal paper Dana Angluin presents a polynomial time algorithm for learning a DFA from membership queries and theory queries (counterexamples to a proposed DFA).

She shows that if you are trying to learn a minimal DFA with $n$ states, and your largest countexample is of length $m$, then you need to make $O(mn^2)$ membership-queries and at most $n - 1$ theory-queries.

Have there been significant improvements on the number of queries needed to learn a regular set?

---

### References and Related Questions

# Answer
In his answer on cstheory.SE, Lev Reyzin directed me to Robert Schapire's thesis that improves the bound to $O(n^2 + n\log m)$ membership queries in section 5.4.5. The number of counterexample queries remains unchanged. The algorithm Schapire uses differs in what it does after a counterexample query.

---

### Sketch of the improvement

At the highest level, Schapire forces $(S,E,T)$ from Angluin's algorithm to have the extra condition that for a closed $(S,E,T)$ and each $s\_1, s\_2 \in S$ if $s\_1 \neq s\_2$ then $row(s\_1) \neq row(s\_2)$. This guarantees that $|S| \leq n$ and also makes the *consistency* property of Angluin's algorithm trivial to satisfy. To ensure this, he has to handle the results of a counterexample differently.

Given a counterexample $z$, Angluin simply added $z$ and all its prefixes to $S$. Schapire does something more subtle by instead adding a single element $e$ to $E$. This new $e$ will make $(S,E,T)$ to be not *closed* in Angluin's sense and the update to get closure with introduce at least one new string to $S$ while keeping all rows distinct. The condition on $e$ is:

$$\exists s, s' \in S, a \in \Sigma \quad \text{s.t} \quad row(s) = row(s'a) \\; \text{and} \\; o(\delta(q\_0,se)) \neq o(\delta(q\_0,s'ae))$$

Where $o$ is the output function, $q\_0$ is the initial state, and $\delta$ the update rule of the true 'unknown' DFA. In otherwords, $e$ must serve as a witness to distinguish the future of $s$ from $s'a$.

To figure out this $e$ from $z$ we do a binary search to figure out a substring $r\_i$ such that $z = p\_ir\_i$ and $0 \leq |p\_i| = i \< |z|$ such that the behavior of our conjectured-machine differs based on one input character. In more detail, we let $s\_i$ be the string corresponding to the state reached in our conjectured machine by following $p\_i$. We use binary search (this is where the $\log m$ comes from) to find an $k$ such that $o(\delta(q\_0,s\_kr\_k)) \neq o(\delta(q\_0,s\_{k+1}r\_{k+1})$. In other words, $r\_{k+1}$ distinguishes two states that our conjectured machines finds equivalent and thus satisfies the condition on $e$, so we add it to $E$.
> 16 votes

# Answer
I do not know if my answer is still relevant. Recently it has been described the implementation of a new algorithm called Observation Pack or in some circumstances Discrimination Tree by Falk Howar. This algorithm is like L\* but use Rivest-Shapire or a other method(see Steffen and Isberner) for handle counterexample decomposition; and it uses a data structure, a discrimination tree (a binary tree) for make efficiently a "sift" namely the insertion of a A-transition (where A is each symbol of alphabet) of a new state found until there isn't closedness. This algorithm exists in two versions: OneGlobally and OneLocally according to whether the suffix founded in the decomposition is added to each component or not (the ratio behind the algorithm is that all prefixes in a component are equivalent to a short prefix and represent the same state in the target according to suffixes found at this time. Later with a new counterexample a new suffix is found that discriminates at least 2 prefixes of a same component. This cause a split of that component in two component). With OneLocally there are far fewer membership query but the number of equivalence query can increase drastically with big target DFA. Rather OneGlobally has a number of membership query always lower than L\* (but greater than OneLocally) and a similar number of equivalences queries than L\*

I know that exists another algorithm too: TTT algorithm that is better than Observation Pack too but I don't have a good knowledge of it.TTT algorithm should be the state of art
> 6 votes

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


title: Comparing rational numbers

text:
# Question
Title: Comparing rational numbers
Given $a,b,c,d \in \mathbb N$ and $b,d \notin \\{0\\}$,

$$ \begin{eqnarray\*} \frac a b \< \frac c d &\iff& ad \< cb \end{eqnarray\*} $$

My questions are:

Given $a,b,c,d$

1. Assuming we can decide $x \< y \in \mathbb Z$ in $\mathcal{O}(|x| +|y|)$, is there any way of deciding $ad\<cb$ without having to preform the multiplications (or divisions), $a\cdot d$ and $c \cdot b$. Or is there some sort of proof that there is no way.
2. Is there a faster method to compare rational numbers than multiplying out the denominators.

# Answer
> 7 votes
My current research:

## Initial attempt at some general rules

One can try to make some general rules for solving the rational comparison:

Assuming all positive $a,b,c,d$:

$$ a \< b \wedge c \ge d \Longrightarrow \frac a b \< \frac c d\\ $$ This basically means, if the left side is less than one, and the right side is at least one, the left side is less than the right side. In the same vein:

$$ a \ge b \wedge c \le d \Longrightarrow \frac a b \not\lt \frac c d\\ $$

Another rule:

$$ (b \> d) \wedge (a \le c) \Rightarrow \left\[\frac a b \< \frac c d\right\] $$ I think of this rule as logical, since the greater the denominator, the smaller the number, while the greater the numerator, the larger the number. Hence if the left side has a greater denominator *and* a smaller numerator, the left will be smaller.

From here on in, we will assume that $a\<c \wedge b \< d$, because otherwise we can either solve it with the rules above, or reverse the question to $\frac c d \overset ? \< \frac a b$, and we end up with this condition anyhow.

**Rules**: $$ \left. \\ \frac {(b-a)} b \< \frac {(d-c)} d \iff \left\[\frac a b \< \frac c d\right\] \right|\_{a\<c,b\<d} \\ $$ This rule basically states that you can always subtract the numerators from the denominators, and set the results as the numerators, to obtain an equivalent problem. I'll leave out the proof.

$$ \left. \\ \frac {a} b \< \frac {c-a} {d-b} \iff \left\[\frac a b \< \frac c d\right\] \right|\_{a\<c,b\<d} \\ $$

This rule allows you to subtract the left numerator and denominator from the right numerator and denominator for an equivalent problem.

And of course there is scaling:

$$ \left. \\ \frac {ak} {bk} \< \frac {c} {d} \iff \left\[\frac a b \< \frac c d\right\] \right|\_{a\<c,b\<d} \\ $$ You can use scaling to make the subtraction rules above more significant.

Using these rules you can play around with things, apply them repeatedly, in smart combinations, but there are cases where numbers are close, and pathological.

By applying the previous rules, you can reduce all these problems to: $$ \left. \frac a b \< \frac {ap+q} {bp'+q'} \iff \frac a b \< \frac {q} {q'} \right|\_{a\>q,b\>q'} $$

Sometimes you can solve this directly now, sometimes not. The pathological cases are usually in the form:

$$ \left. \frac a b \< \frac {c} {d} \right|\_{a\>c,b\>d,c\in \mathcal O(a), d \in \mathcal O(b)} $$

Then you flip it, and result in the same thing, just with one bit less. Each application of the rules + flip reduces it by a digit/bit. AFAICT, you cannot quickly solve it, unless you apply the rules $\mathcal O(n)$ times (once for each digit/bit) in the pathological case, negating their seeming advantage.

## Open problem??

I realized that this problem seems to be harder than some current open problems.

An even weaker problem is to determine:

$$ad \overset ? = bc$$

And yet weaker:

$$ad \overset ? = c$$

This is the open problem of *verifying multiplication*. It is weaker, because if you had a way to determine $ad \overset ? \< bc$, then you can easily determine $ad \overset ? = bc$, by testing using the algorithm twice, $ad \overset ? \< bc$, $bc \overset ? \< ad$. Iff either is true, you know that $ad \ne bc $.

Now, $ad \overset ? = c$ was an open problem, at least in 1986:

> The complexity of multiplication and division. Let us begin with the very simple equation ax = b. When considered over the integers, testing its solvability and finding a solution x is possible by integer division with remainder zero. For checking a given solution x, integer multiplication will suffice, but it is an interesting open problem whether there are faster methods of verification.
>
> ARNOLD SCHÖNHAGE in Equation Solving in Terms of Computational Complexity

Very interestingly, he also mentioned the question of *verifying matrix multiplication*:

> It is also an interesting question whether verification of matrix multiplication, i.e., checking whether AB = G for given C, could possibly be done faster.
>
> ARNOLD SCHÖNHAGE in Equation Solving in Terms of Computational Complexity

This has been since solved, and it is indeed possible to verify in $\mathcal O(n^2)$ time with a randomized algorithm (with $n\times n$ being the size of the input matrices, so it is basically linear-time in the size of the input). I wonder if it is possible to reduce integer multiplication to matrix multiplication, especially with their similarities, given Karatsuba integer multiplication's similarities to matrix multiplication algorithms that followed. Then perhaps in some way we can leverage the matrix multiplication verification algorithm for integer multiplication.

Anyway, since this is still, to my knowledge, an open problem, the stronger problem of $ad \overset ? \< cd$ is surely open. I am curious if solving the equality verification problem would have any bearing on the comparison inequality verification problem.

A slight variation of our problem would be if the fractions are guaranteed to be reduced to lowest terms; in this case it is easy to tell if $\frac a b \overset ? = \frac c d$. Can this have any bearing on comparison verification for reduced fractions?

An even subtler question, what if we had a way to test $ad \overset ? \< c$, would this extend to testing $ad \overset ? = c$? I don't see how you can use this "both ways" like we did for $ad \overset ? \< cd$.

Related:

* Approximate Recognition of Non-regular Languages by Finite Automata

They do some work on approximate multiplication, and randomized verification, which I do not fully understand.
* math.SE: How to Compare two multiplications without multiplying?
* Suppose we were allowed to preprocess $c$ as much as we wanted in polynomial time, can we solve $ab=c$ in linear time?
* Is there a linear-time nondetermistic integer multiplication algorithm? See http://compgroups.net/comp.theory/nondeterministic-linear-time-multiplication/1129399
> There are well-known algorithms for multiplying n-bit numbers with something like O(n log(n) log(log(n))) complexity. And we can't do better than O(n) because at least we have to look at the entire inputs. My question is: can we actually reach O(n) for a suitable class of "nondeterministic" algorithms?
>
> More precisely, is there an algorithm that can accept two n-bit binary numbers "a" and "b" and a 2n-bit number "c" and tell you in O(n) time whether "a * b = c"? If not, is there some other form of certificate C(a,b,c) such that an algorithm can use it to test the product in linear time? If not linear time, is the problem of testing the product at least asymptotically easier than computing it? Any known results along these lines would be welcome.
>
> John.
>
> ―johnh4717

# Answer
> 1 votes
Here's a *very partial attempt* at disproof. Suppose that we can make use only of a (constant number of ) additions and subtractions in our decider, as well as a constant number of ${mod}$ w.r.t predefined numbers. In other words, we can do a constant number of $mod\ 2$, $mod\ 3$, etc. in our decider. Then the only quantities we can compute are of the form $q = k\_1 a +k\_2 b+k\_3 c + k\_4 d = \sum k\_ia$ where the $k$'s are predefined constants. Note that $q$ can be computed in time $O(\sum|a|)$.

**Edited** This decider purports to determine a bit $B:B=1$ iff $ad\>bc$. Consider taking $a,b,c,d$ as points in $\mathbb{R}^4$. The bit $B$ is decided by its position wrt the surface $ad = bc$ which is a hyperboloid in 4 dimensions. If we have a point $(a,b,c,d)$ in the input space, the decider above can compute points within a bounded distance of this input point, i.e. those points $q: |q-a| = k\_1,$ etc. This defines a cuboid in 4 d space.

(How to make this more precise?) The distance from the cuboid to the surface is in general unbounded, and hence the surface can't be computed by the decider

# Answer
> 1 votes
Good question. Would you accept level of confidence?

Perhaps do approximate division. I.e.

To compute the bounding approximate quotients of a/b, right shift a by ceil(log\_2(b)) and also by floor(log\_2(b)). Then we know the accurate quotient is between these two values.

Then, depending on the relative sizes of the four integers, one may be able to rule out certain cases, and get 100% confidence.

One may repeat the procedure for radix other than 2, and by a succession of such operations increase the level of confidence, until a change of sign / tie-break is somehow observed?

That's my first-draft sketch of a method.

# Answer
> 1 votes
> is there any way of deciding ad \< cb without having to preform the \[expensive\] multiplications

Sure.

*Idea:* Compare the decimal expansion bit by bit.

The only nasty bit is that we have to exclude equality first because otherwise we may not terminate.
It is useful to first compare the integer parts because that is easy.

Consider this:

```
def less( (a,b), (c,d) ) = {
  // Compare integer parts first
  intA = a div b
  intC = c div d

  if intA < intB
    return True
  else if intA > intB
    return False
  else // intA == intB
    // Normalize to a number in [0,1]
    a = a mod b
    c = c mod d

    // Check for equality by reducing both
    // fractions to lowest terms
    (a,b) = lowestTerms(a,b)
    (c,d) = lowestTerms(c,d)

    if a == c and b == d
      return False
    else
      do
        // Compute next digits in decimal fraction
        a = 10 * a
        c = 10 * c

        intA = a div b
        intC = c div d

        // Remove integer part again
        a = a mod b
        c = c mod d
      while intA == intC

      return intA < intC
    end
  end
}

```

Note that the `do-while` loop has to terminate since the numbers are unequal. We do not know how long it runs, though; if the numbers are very close, it could be a while.

Clearly, there are no expensive multiplications; the only ones we need is to multiply the nominators by $10$. In particular, we have avoided computing $ad$ and $cb$ explicitly.

Is this fast? Probably not. There are lots of integer divisons, modulos and `gdc`s to compute, and we have a loop whose number of iterations is inversly proportional to the distance between the numbers we compare.

---

The helper method:

```
def lowestTerms(a,b) = {
  d = gcd(a,b)
  if d == 1
    return (a,b)
  else
    return lowestTerms(a div d, b div d)
  end
}

```

---
Tags: algorithms, integers
---


# Question
Title: Data structure choice for a query-update-delete problem
Given is an initial set of n keys. Each key k is of the form (p, q). Note that both p and q are positive.

At any given point, there are two possible actions:

1) Query-Delete: Given a value s as query, find all such keys in the set that have have the (globally) minimum p and satisfy (q \>= s), and delete these keys.

2) Insert: Add a new key k' = (u, v) to the set.

I was wondering what would be the best data structure to represent the above.

My first approach is to simply sort the original set in a linked list (or array) and return the appropriate tuples when queried, and if inserted, use linear search to find the position, but the worst-case insertion then becomes O(n), while query-deletion involves checking the first element, and has the complexity O(number of distinct q values).

A second approach is to use a red-black tree with the p values as its key, storing (p, q, r) in each node, where r is the biggest q value found at that level or below in the tree.

For example, given a set (10, 4), (20, 2), (30, 2), (40, 3) the tree looks like:

```
        (20, 2, 4)
       /          \
 (10, 4, 4)        (30, 2, 3)
                     \
                      (40, 3, 3)

```

where each node is of the form (p, q, r).

This approach has the benefit of being able to early exit during the query search if (r \< s) in the node. Insertion remains O(log n) like in red-black trees, but may face problems with sets of the form {(p, q1), (p, q2), ...}.

Could anyone please suggest modifications or propose a better approach? Thanks.

# Answer
Store your data structure in a red-black tree where the first component of a key (i.e. p in (p,q)) is the key and the values are red-black trees of the second parts of keys with identical first part.

So, for the set $\\{(a,b), (a,d), (d,b), (e,f), (e,g)\\}$, you would store a tree with three keys (a, d, and e). The value for the key a would be a red-black tree with b and d, the for the key d would be a red-black tree with b, and the value for the key e would be a red-black tree with f and g.

A red-black tree can be split in $O(\lg n)$ time, so query-delete would take $O(\lg n) + O(\lg n) = O(\lg n)$ time - $O(\lg n)$ for the tree lookup and $O(\lg n)$ for the split of the tree. This doesn't include the cost of deleting, deconstructing, finalizing, or disposing of the deleted elements.

insert would also be $O(\lg n)$.

Query-delete can be made $O(1 + \lg k)$, where $k$ is the size of the deleted set, by keeping a pointer to the smallest key in the big tree and searching from the ends of the little tree, rather than from the root.

Amortized, query-delete is $O(1)$: using the banker's method, simply put a single on each item in the little trees. Since returning $k$ items takes $O(1 + \lg k)$ time and returns $k$ coins, its amortized cost is now $O(1)$, while insert's is $O(1 + \lg n) = O(\lg n)$.
> 2 votes

# Answer
Use treaps. They store pairs of values and are heap-ordered w.r.t. one, and BST-ordered w.r.t. the other component.

They have expected logarithmic height if the $p$'s are uniformly distributed.

Query-delete comes down to traversing the tree recursively from the root, following along all edges in "direction" of $\geq s$ as long as the priority of the current node is equal to the one you saw in the root.
> 1 votes

# Answer
I would suggest C++ map with keys the first component and values map for the second component... you have logarithmic insert operation and you can erase in time linear in number of erased elements since you can access the element with the smallest first key by begin()... It's actually the interface of a red-black tree of red-black trees
> 0 votes

---
Tags: data-structures, heaps, dictionaries
---


# Question
Title: What exactly would stop me from registering a domain from my own nameserver?
Can I just make a nameserver and claim away? Are there implemented measures to stop this from happening?

# Answer
> 3 votes
Nothing stops you from setting up such a nameserver. However, this wouldn't be of any use to you, because no one is going to contact your nameserver to ask whether domainexample.com exists: they're only going to contact the official name server for .com.

It'd be like saying "can't I lie about the location of the White House if anyone asks me?" -- well, yes, I can, but if no one ever asks me that, then this isn't achieving much.

What prevents you from lying about .com? People aren't going to ask you; they are going to contact the root nameserver and ask that question. How do people know who the root nameservers are? The root nameservers are publicly known (specified in a RFC) and hardcoded in everyone's DNS software. So ultimately the recursion bottoms out.

That's why setting up your own nameserver won't help you: no one is ever going to ask your nameserver anything or have any trust in it, so its lies won't affect anyone.

---
Tags: computer-networks, security
---


title: "Minimal" intuitionistic type theory?

text:
# Question
Title: "Minimal" intuitionistic type theory?
I'm surprised that people keep adding new types in type theories but no one seems to mention a minimal theory (or I can't find it). I thought mathaticians love minimal stuff, don't they?

If I understand correctly, in a type theory with a impredicative `Prop`, λ-abstraction and Π-types suffice. By saying suffice I mean it could be used as intuitionistic logic. Other types can be defined as following:

$$ \bot \stackrel{def}{=} \Pi \alpha: Prop. \alpha \\ \neg A \stackrel{def}{=} A \to \bot \\ A \land B \stackrel{def}{=} \Pi C: Prop. (A \to B \to C) \to C \\ A \lor B \stackrel{def}{=} \Pi C: Prop. (A \to C) \to (B \to C) \to C \\ \exists\_{x: S}(P(x)) \stackrel{def}{=} \Pi \alpha: Prop. (\Pi x: S. P x \to \alpha) \to \alpha \\ $$

My first question is, do they (`λ`, `Π`) really suffice? My second question is, what do we need minimally if we don't have an impredicative `Prop`, such as in MLTT? In MLTT, Church/Scott/whatever encoding doesn't work.

Edit: related

# Answer
> 13 votes
To elaborate on gallais' clarifications, a type theory with impredicative Prop, and dependent types, can be seen as some subsystem of the calculus of constructions, typically close to Church's type theory. The relationship between Church's type theory and the CoC is not that simple, but has been explored, notably by Geuvers excellent article.

For most purposes, though, the systems can be seen as equivalent. Then indeed, you can get by with very little, in particular if you're not interested in classical logic, then the only thing you really need is an **axiom of infinity**: it's not provable in CoC that any types have more than 1 element! But with just an axiom expressing that some type is infinite, say a natural numbers type with the induction principle and the axiom $0\neq 1$, you can get pretty far: most of undergraduate mathematics can be formalized in this system (sort of, it's tough to do some things without the excluded middle).

Without impredicative Prop, you need a bit more work. As noted in the comments, an extensional system (a system with functional extensionality in the equality relation) can get by with just $\Sigma$ and $\Pi$-types, $\mathrm{Bool}$, the empty and unit types $\bot$ and $\top$, and W-types. In the intensional setting that's not possible: you need many more inductives. Note that to build useful W-types, you need to be able to build types by elimination over $\mathrm{Bool}$ like so:

$$ \mathrm{if}\ b\ \mathrm{then}\ \top\ \mathrm{else}\ \bot $$

To do meta-mathematics you'll probably need at least one universe (say, to build a model of Heyting Arithmetic).

All this seems like a lot, and it's tempting to look for a simpler system which doesn't have the crazy impredicativity of CoC, but is still relatively easy to write down in a few rules. One recent attempt to do so is the $\Pi\Sigma$ system described by Altenkirch *et al*. It's not entirely satisfying, since the positivity checking required for consistency isn't a part of the system "as is". The meta-theory still needs to be fleshed out as well.

A useful overview is the article Is ZF a hack? by Freek Wiedijk, which actually compares the hard numbers on all these systems (number of rules and axioms).

# Answer
> 12 votes
The problem with Church encodings is that you cannot obtain induction principles for your types meaning that they are pretty much useless when it comes to proving statements about them.

In terms of minimality of the system, one path mentioned in the comments is to use containers and (W / M)-types however they are rather extensional so that's not really convenient to work with in systems like Coq or Agda.

A more tractable approach is to use a polynomial functor defined as the extension of a Description rather than as the one of a container. The host theory only needs to be closed under $\Pi$, $\Sigma$ and $\mu$ and $\nu$ fixpoints (and equality for indexed polynomial functors). You get the same expressive power as with a (W / M)-type without the inconvenients: one can actually prove an induction principle without needing functional extensionality.

Nested fixpoints are more cumbersome but can be dealt with. I haven't written or seen a fully worked-out story about alternating $\mu$s and $\nu$s but it ought to exist.

---
Tags: type-theory, dependent-types
---


# Question
Title: How to give an upper bound on this bin packing problem?
In the bin packing with fragile objects (BPFO) problem one is given a set of objects $\\{1,\ldots,n\\}$ where each object $i$ has a weight $w\_i$ and a fragility $f\_i$ for all $i$ in the set $\\{1,\ldots,n\\}$. (We assum that $w\_i\le f\_i$.) Also, we have a set of bins of infinite capacity (each) in which we want to place the objects.

The objective is to assign the objects to the minimum number of bins such that the sum of the weights in each bin is at most the minimum fragility. That is, if we assign the set of objects $S$ to bin $B$ than we must have:

$$\sum\_{i\in S}w\_i\le\min\limits\_{i\in S}f\_i.\quad\quad\quad (1)$$

The BPFO problem is given in this paper. Let us denote the optimal value of BPFO by $OPT$.

I am trying to relax BPFO by modifying equation$~(1)$ as follows.

$$\sum\_{i\in S}w\_i\le f\_i,\forall i\in S$$

Let us denote the optimal value of the relaxed problem by $OPTR$.

Now, I would like to upper bound $OPT$ by $OPTR$. How can I achieve this?

It is clear that a solution to BPFO is a solution to the relaxed problem and then $OPT\ge OPTR$.

Is there a way to say that $OPT\le \alpha(n)OPTR$ where $\alpha(n)\ge 1$ ?

# Answer
> 3 votes
Your relaxation is same as original problem.

$$\sum\_{i\in S}w\_i\leq f\_j,\forall j\in S$$

is same condition as

$$\sum\_{i\in S}w\_i\leq\min\limits\_{j\in S}f\_j$$.

because

$$\min\limits\_{i\in S}f\_i \leq f\_j,\forall j\in S$$.

---
Tags: approximation, lower-bounds
---


# Question
Title: Problem in computational complexity (superior class)
> Say that a class $C\_1$ is superior to a class $C\_2$ if there is a machine $M\_1$ in class $C\_1$ such that for every machine $M\_2$ in class $C\_2$ and every large enough $n$, there is an input of size between $n$ and $n^2$ on which $M\_1$ and $M\_2$ answer differently.
>
> 1. Is **DTIME**($n^{1.1}$) superior to **DTIME**($n$)?
> 2. Is **NTIME**($n^{1.1}$) superior to **NTIME**($n$)?

This is an exercise from book Computational Complexity: A Modern Approach. But I have no idea to handle it. Does it have relationship with theorem that **DTIME**$(n)$ $\subsetneqq$ **DTIME**($n^{1.5}$)?

# Answer
> 2 votes
The proof of the time hierarchy theorems can be paraphrased like this. We want to show that $\mathsf{X} \subsetneq \mathsf{Y}$ for appropriate $\mathsf{X},\mathsf{Y}$. The idea is to construct a diagonalizing machine $M \in \mathsf{Y}$ (slight abuse of notation here) whose language is different from all languages in $\mathsf{X}$. On input $x$, the machine $M$ runs $x$ on $x$ up to some specified time bound, and then answers the opposite. If the simulation is efficient enough, $M \in \mathsf{Y}$.

Your question is very similar. Go over the proof of the time hierarchy theorems, and check whether the diagonalizing machines there fit your bill.

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


# Question
Title: Different between left-most and right-most derivation
I am a beginner started learning theoretical computer science. I just came through *context-free grammars*.

So my question is: what is the different between left-most and right-most derivation?

Because both of them gave me the same parse tree.

# Answer
Given a derivation tree for a word, you can "implement" it as a sequence of productions in many different ways. The *leftmost* derivation is the one in which you always expand the leftmost non-terminal. The *rightmost* derivation is the one in which you always expand the rightmost non-terminal.

For example, here are two parse trees borrowed from Wikipedia:

The leftmost derivation corresponding to the left parse tree is $$ A \to A + A \to a + A \to a + A - A \to a + a - A \to a + a - a $$ The rightmost derivation corresponding to the left parse tree is $$ A \to A + A \to A + A - A \to A + A - a \to A + a - a \to a + a - a $$ The leftmost derivation corresponding to the right parse tree is $$ A \to A - A \to A + A - A \to a + A - A \to a + a - A \to a + a - a $$ The rightmost derivation corresponding to the right parse tree is $$ A \to A - A \to A - a \to A + A - a \to A + a - a \to a + a - a $$
> 18 votes

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


# Question
Title: Articulation Vertex, significance and real world usage?
This question is not about any particular algorithm to look for *articulation vertices* (*cut vertices*) in a graph but rather seeking real world applications of algorithms involving such vertices.

I am going through Skienna's *The Algorithm Design Manual* and it gives an example of an articulation vertex in a telephone network as an approachable example.

Personally, I think there may be applications in networking where multipathing is implemented using more than one switches between the same set of connected hosts to provide tolerance against failure of one of the switches. But still, an algorithm to look for an articulation vertex is not directly applicable in this scenario.

Are there any real world examples of articulation vertices and how looking for them helps solving problems arising due to such vertices ?

EDIT:

Just adding a bit more food for thought. I think simulation based applications or maybe gaming could have some applications ?

For e.g. a game engine may generate some graph based entities *on the fly*, let's say a building which a player must go into in a FPS game. For testing the the *on the fly* part, it may be useful to look for parameters which may generate buildings(graphs) which are biconnected (or higher connected) for *easy or easier* settings where as graphs with articulation vertex can be considered to be *hard* settings. (Easy or hard here are relative terms and the semantics may be even reversed depending on the outcome of players' entering the graph)

# Answer
> 3 votes
First, yes, probably. One example is when we wish to split the graph into its sets of *biconnected components*.

Second, I think you misunderstand the purpose of the *exercise*. The goal is to teach you to think in terms of graph algorithms, not necessarily give you the solution for existing real world problems.

Most real world problems differ slightly from textbook exercises and examples. But the goal is to give you a toolbox so you can handle similar problems.

It is also important that you understand what an articulation point (or a cut vertex) is, as well as the similar concept for edges (*bridge*), so that you get a better understanding of graphs and graph connectivity. It is crucial to understand the concept of cut vertices and bridges before lifting the definitions to their more general versions on vertex- and edge-connectivity (separators and cuts).

---
Tags: graphs, graph-traversal
---


# Question
Title: Approximate a float using a minimal fraction
This sounds like it's probably a well-known problem, but I haven't been able to find references to it by searching.

Given a floating point value $x$ and an error range $\varepsilon$, how can I efficiently find a minimal positive integer $q$ such that $\left|x - \frac{p}{q}\right| \< \varepsilon$ for some integer $p$?

The approach that seems obvious is to iterate from $q = 1$ upward (skipping composite numbers), computing $p := round(x * q)$ and checking whether $\left|x - \frac{p}{q}\right| \< \varepsilon$. But I'm wondering if there's a smarter way.

# Answer
The partial convergents of the continued fraction of $x$ consists of all the best rational approximations of $x$; see Wikipedia, for example. A *best rational approximation* of $x$ is a rational number $p/q$ such that $\left|x-\frac{p}{q}\right| \leq \left|x-\frac{p'}{q'}\right|$ for all $q' \leq q$. Your $p/q$ is in particular a best rational approximation, so it would be one of the convergents.
> 4 votes

---
Tags: algorithms, floating-point, mathematical-programming, numerical-algorithms
---


# Question
Title: Point in Polygon Problem: Has anybody invoked the line integral?
Some twenty years prior I was given the task to solve the Point in Polygon problem for a piece of commercial software. I solved it invoking the ray casting algorithm. After a variety of enhancements the function worked well enough, but I felt there was a better way. I found inspiration in Gauss's Law. Charges and the electric field aside, it boils down to, in 2D, a (contour) line integral. In a plane, the integral $\int\_C d\theta = 2\pi$ if the point lies within the contour, and is zero if the point lies outside. With this in mind I reformulated the algorithm for arbitrary polygons:

```
double sum_theta = 0`
for( int i = 0 ; i < n_vtx ; i++ )
{
    int    j         = (i + 1) % n_vtx;
    XYPT   p_i       = ngon[i];
    XYPT   p_j       = ngon[j];
    XYPT   vector_i  = p_i - p_o;                 // vector from point o to vertex i
    XYPT   vector_j  = p_j - p_o;                 // vector from point o to vertex j
    double cp        = vector_i.cross( vector_j ) // cross product
    double dp        = vector_i.dot  ( vector_j ) // dot   product
           sum_theta+= Atan2( cp, dp );

}
if( sum > pi ) return INSIDE;
else           return OUTSIDE;

```

I'm not asking if this works. It does, rather well. (And I see no reason to replace it; I like its simplicity and elegance.) My question to this forum is largely of curiosity: Indeed, how much slower is this method than doing it by ray-casting (which can present *gotchas*) and intersection count; or by counting winding number (WN)? The application this services never has self-intersecting polygons (so, it seems, WN has no particular advantage) and the vertex count is never excessive (n\_max ~ 25).

Any thoughts?

# Answer
> 4 votes
Summing the angles around a point is equivalent to calculating the winding number around that point. It will give you a correct answer in the general case.

Going more in depth, I'll try to show that your proposed algorithm has many drawbacks.

# Algorithmic runtime

Algorithmically, your proposed algorithm must iterate over all $N$ points. Because of that, we can assume it runs in $\Theta(N)$ time.

In contrast, a ray casting algorithm checks against edges, of which there are $N$. The algorithm can be optimized using grids or quadtrees to reduce the amount of calculations needed. Since the ray might intersect all edges, that algorithm runs in $\mathcal{O}(N)$ time.

We can conclude that the ray casting algorithm will never perform worse than the angle sum.

# Gotchas

You mentioned the ray casting algorithm as having gotchas. I'll assume you refer to the problems occurring when the ray crosses a vertex or an edge directly. First, your proposed algorithm has the same problem. What if the point you choose is on a vertex or an edge?

The solution to the problem for both algorithms is to define strict rules. That is, from the start, decide (or parametrize the algorithm) so that points on edges or vertices of the polygon are either all included or all excluded.

As an aside, the solution for ray casting's problem of intersecting vertices and edges can be solved using a similar rule. When a vertex is on the ray, it must be considered to belong to one side of the ray (more here).

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


# Question
Title: Finding the lowest-weight negative cycle in a weighted digraph
Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the negative cycle in the graph whose weight is as small as possible?

I know that I can detect negative weight cycles using Bellman-Ford. Has this variation be studied before? Can you point me to a reference?

# Answer
Finding the least weight simple negative cycle is NP-hard even in the undirected case, as shown in this answer by reduction from Hamiltonicity. The reduction is very simple: make each edge have weight $-1$. There is a cycle of least weight at most $-n$ iff the graph is Hamiltonian.
> 4 votes

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


# Question
Title: How to avoid getting stuck on local optimum, for genetic algorithms
I'm programming a genetic algorithm using grammatical evolution. My problem is that I reach local optimal values (premature convergence) and when that happens, I don't know what to do. I'm thinking about increasing the mutation ratio (5% is it's default value), but I don't know how to decide when it is necessary.

The data I have on every generation is a bidimensional array whose first column is its fitness

```
adn[i][0] ← fitness
row → is the values of the Grammar
column ↓ Each indiviual result

```

If you need clarification, please ask and I'll be pleased of modifying. Note that this is not my mother language and sorry for the mistakes and for the inconvenience.

Answering a request, my operations are the following, and exactly in this order:

* I generate a random Population (A matrix with random numbers)
* I generate a matrix that contains the desired result. For doing this, i have implemented a couple functions that have aditionally a +-5% of variation, for example: fun(x)= (2\*cos(x) + sen(x) - 2X) * **(0,95+(a number oscillating between 0 and 0,1)**, the x contains every f(x) with sequentially from 0 to N (Being N the size of row), the y contains exactly the same (more results)
* Starts algorithm (generations beginning to change

The actions that make every generation are:

* Mutation: A random number of every cromosome can mutate on any gene → adn\[i\]\[random\] = random number (with a 5% of probability of this happening)
* Crossover: I cross every adn with other adn (80% is the chance of mutation for every pair), for the pairing I pick a random number and face adn\[i\] and adn\[(i+j) mod NumADNs\]
* Translate. I get a matrix that contains the values f(0 to N) making in one step transcription and translate aplying the grammar on the image

-fitness: I compare the values obtained with the expected ones and update the fitness.

-Elitism: After that, i choose the best 4 adn's and get it to the top, they will be selected

-Selection: Any non elitist adn will face a totally random adn, and if its fitness is lower (Lower is better) will prevail, being a possibilities of the worse one surviving

# Answer
> 11 votes
It looks like you're dealing with **premature convergence**.

In other words, your population fills itself with individuals that represent the suboptimal solution and/or individuals that are (too) close to said solution.

The basic framework of a genetic algorithm is as follows:

```
P <- Population of size N with N random individuals.
evaluate fitness of all individuals in P
while (stopping criteria not met) {
    C <- empty Child set of size M
    while (size of C is not M) {
        parent1 <- select an individual from P
        parent2 <- select an individual from P

        child1, child2 <- combine parent1 and parent2 somehow.
        child1, child2 <- mutate children by chance
        evaluate fitness of child1, child2
        C <- C + child1 + child2
    }
    P <- combine P and C. (P remains size N)
}
return individual with best fitness

```

Note that the (e.g.) the size of the population/children doesn't have to be constant *per se*. Or you might combine a variable number of parents into a variable amount of children (e.g. a crossover between 5 parents resulting in 7 children). But I would keep it simple, at first.

As you can see, the main operators in a genetic algorithm are, in order

* **Selection**: Select individuals from the population that will be combined. Examples: *tournament selection*, *proportionate selection*, *truncation selection*, ...
* **Crossover**: Combine selected individuals (parents) to new indidivuals (children). Examples: *one-point crossover*, *n-point crossover*, *uniform crossover*, *cut and splice*, ...
* **Mutation**: By chance, (don't) mutate an individual by changing the individual slightly.
* **Recombination**: Somehow insert the children into the set of parents. Examples: Add all children to the population, sort the thing by fitness and remove the worst individuals so your population is size N again; Sort your population and drop the worst M individuals and add all children; often the same techniques that are presented in the selection phase are used.

In your description, you're confusing multiple steps as if it were one (e.g. you skip the *selection* step but you incoorperate it in the *crossover* step). You also describe techniques as if it were a step of the algorithm (e.g. Elitism is a technique used in the *recombination* step to ensure that at least the best individuals don't die).

An example where premature convergence might/will occur is when you only *select* the best individuals as parents and only allow the best individuals survive (in the *recombination* step).

Some possible methods to resolve this:

* **Increase mutation rate**. However, a mutation is usually a very random process. You would need 'pure' luck to escape the suboptimal solution.
* **Redesign your genetic operations**. e.g. allow bad fitness individuals/offspring to survive the generation more frequently. It could be that you're currently selecting too much good individuals to survive. Don't let too much bad individuals survive though, or your algorithm will never converge to something good.
* (...)

The goal is to tweek your genetic operations in such a way that in each next generation, the average fitness of your population has (preferably) increased while maintaining a big enough fitness variation. This is not easy.

There are several other methods to avoid premature convergence if the above doesn't help you out. I strongly recommend experimenting with altering your genetic operations first before doing this, however. Search terms: *preselection*, *crowding*, *fitness sharing*, *incest prevention*, ...

# Answer
> 1 votes
If you increase mutation rate you can bounce from local optimum, search more possibilities but there is tradeoff - with higher mutation rate convergence rate will change, and with too high rate it will stop converging.
When results stop changin for some number of iterations - this is when you stop, so it is also the moment to start the new search.
I would propose to mix GA with SA to find global optimum.
Working hacky solution is to remember local optima and restart (mutate or reinitialize), but after it discarded attractor - drop mutation rate.

---
Tags: optimization, genetic-algorithms, evolutionary-computing
---


title: finding shortest negative cycle

text:
# Question
Title: finding shortest negative cycle
Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the shortest (uses the least number of edges) negative weight cycle in the graph?

I know that I can detect negative weight cycles using Bellman-Ford. Has this variation be studied before? Can you point me to a reference?

# Answer
You can use dynamic programming (in this case, known as the Floyd–Warshall algorithm) to calculate the least weight of a walk of length $\ell$ from $x$ to $y$, for all vertices $x,y$ and $\ell \geq 0$. The first $\ell$ (if any) such that this weight is negative is the length of the shortest negative cycle. (This breaks if there are bidirectional negative edges, unless you consider them as simple cycles.)
> 3 votes

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


# Question
Title: Upper bound on the covering radius of a code
Let $C$ be a $\[n,k\]$ linear code over $\mathbb{F}\_q$.

Suppose that $\rho$ is the covering radius .

I want to show that $\rho \leq n-k$.

Could you give me a hint how we could show this?

The covering radius is defined as follows:

$$\rho=\max\_{x \in \mathbb{F}\_q^n} d(x,C) \\ d(x,C)=\min\_{c \in C} d(x,c)$$

# Answer
You need to show that every vector is at distance at most $n-k$ from a codeword. The code is the collection of all vectors $x$ satisfying $Ax = 0$, where $A$ is an $(n-k) \times n$ matrix, which without loss of generality has the form $A = \begin{bmatrix} I\_{n-k} & B \end{bmatrix}$ (use Gaussian elimination, possibly permuting coordinates to avoid zero columns). Let $v$ be a completely arbitrary vector, and suppose that $Av = s$. Extend $s$ to a vector of length $n$ by adding zeroes at the end. Then $A(s + v) = 0$, i.e., $v + s$ is a codeword, which is at distance at most $|s| \leq n-k$ from $v$.
> 1 votes

---
Tags: coding-theory
---


# Question
Title: An NFA with no equivalent DFA with fewer than $2^n$ states: Example and Proof
I have been following the book *Introduction to Automata Theory, Languages, and Computation* by John E. Hopcroft and Jeffery D. Ullman.

I came across the following topic titled *Bad Case for Subset Construction (2.3.6)*. I cannot follow the example given over there, about NFA N that can accept strings with 1 at the $n^{th}$ position, and that the DFA formed from that NFA thereafter will have no equivalent with fewer than $2^n$ states.

> They argue that The DFA $D$ must be able to remember last n symbols it has read. Since any of the $2^n$ subsets of the last n symbols could be 1, if D had fewer than $2^n$ states, then there would be some state $q$ such that $D$ can be in state $q$ after reading two different sequences of n bits, say $a\_{1}a\_{2}...a\_{n}$, and $b\_{1}b\_2...b\_n$.

Here is an extract from the book itself:

I have been trying to comprehend the proof, including this line and the subsequent paragraph that follows, but I have not been able to.

Can someone please explain the approach ?

# Answer
> 5 votes
The proper way to do this proof is using Myhill–Nerode theory, which I will now explain. For a regular language $L$, say that $x,y$ are *inequivalent* if there exists a word $z$ such that $xz \in L$ and $yz \notin L$, or such that $xz \notin L$ and $yz \in L$. In every DFA accepting $L$, the state that is reached after reading $x$ is different from the state that is reached after reading $y$ (exercise). Hence, if we find a collection $x\_1,\ldots,x\_M$ of words such that $x\_i,x\_j$ are inequivalent for all $i \neq j$, then every DFA for $L$ must contain at least $M$ states (exercise).

For your language $L = \Sigma^\* 1 \Sigma^{n-1}$, you can take as your collection of words the set of all words of length $n$. If $x,y$ are two different words of length $n$ then $x\_i \neq y\_i$ for some $i$; say $x\_i = 0$ and $y\_i = 1$. Then $x 0^{i-1} \notin L$ (since the $n$th from last bit is $x\_i$ = 0), whereas $y 0^{i-1} \in L$ (since the $n$th from last bit is $y\_i$ = 0). This completes the proof.

# Answer
> 4 votes
The text is arguing as Yuval does; they're just hiding any mention of Myhill-Nerode. Here's an unpacking of their argument:

There are clearly $2^n$ possible length-$n$ input strings over $\\{0,1\\}$. Assume for the sake of argument that there is a DFA, $D$ that accepts the "$n$-th from the end is $1$" language and that $D$ has $m\<2^n$ states. We don't have enough states to assign a unique one to every possible length-$n$ input, so there must be some state $q$ where we wind up after reading two different strings $a\_1a\_2\dotsm a\_n$ and $b\_1b\_2\dotsm b\_n$.

Since $a\_1a\_2\dotsm a\_n\ne b\_1b\_2\dotsm b\_n$, they must differ in at least one place, say $a\_i\ne b\_i$. Suppose without loss of generality that $a\_i=1$ and $b\_i=0$.

If $i=1$, then since $1a\_2a\_3\dots a\_n$ has its $n$-th character from the last equal to $1$, state $q$ must be an accept state. But since $0b\_2b\_3\dots b\_n$ has its $n$-th character from the last not equal to $1$, state $q$ must be a non-accept state, a contradiction.

If $i=2$, we're in state $q$ after reading $a\_11a\_3\dotsm a\_n$ and also after reading $b\_10b\_3\dotsm b\_n$. Suppose that from state $q$ on input $0$ we pass to state $p$, then we'll be in state $p$ after reading $a\_11a\_3\dotsm a\_n0$ and also after reading $b\_10b\_3\dotsm b\_n0$. In the former case, $a\_11a\_3\dotsm a\_n0$ has its $n$-th character from the end equal to $1$ so $p$ must be an accept state, but $b\_10b\_3\dotsm b\_n0$ does not so $p$ must not be an accepting state, again a contradiction.

Continuing, it's easy to see that no matter where the two inputs differ, by appending $i-1$ zeros (or anything else) to the two strings we'll find ourselves in a state which must be both accepting and non-accepting, so our original assertion, that $D$ has fewer than $2^n$ states, must have been false, which is just what we wanted.

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


# Question
Title: Binary Search Tree Traversal output validity and unique BST construction
I had two specific type of questions involving Binary **Search** Tree (not simple Binary Tree) traversals :

1. Given x-order traversal output of BST, can we state if it is valid or invalid output?

(For example, this: `[3,2,1,4,6,7,8,5]` can be valid postorder traversal output, but this: `[4,1,3,2,6,7,8,5]` cannot be.)
2. Given x-order traversal output of BST, can we draw unique BST?

Put Pre, Post, In and Level in x. So there are actually 8 questions.

I didnt find any place discussing these all. But after a bit of thinking I realized that,

1. for all x-order traversal outputs, we can state whether it is valid or not.
2. for all x-order traversal outputs except the inorder, we can draw unique BST.

This is really confusing me. Especially in case of inorder. Logically, it seems that if we can construct unique BST for given x-order traversal output, then we can say that for that x-order traversal output, we should be able to tell whether the output is valid or not. But this does not seems to be correct, since in case of inorder traversal, we can tell if the given output is valid or not but we cannot construct the corresponding unique BST.

# Answer
> 2 votes
I believe you are correct. The hard part is convincing yourself why this is true, I guess.

The key to the riddle is the root. preorder, postorder and levelorder all have the root at first or last position. Once the root is known all elements smaller go in the left subtree and those larger go right. Thus reconstructing the tree from its order is a recursive process.

Inorder always yields the elements from small to large, so there the situation is completely different. There is no unique tree, and any tree that is built by adding the elements as a BST will do.

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


# Question
Title: How do you determine the inputs to a neural network?
I'm looking at this tutorial on neural networks. The data that is given from the UCI study includes various attributes, such as "mean x of on pixels", "total # on pixels" etc, which are taken as input to the neural network. However, it seems to me that this choice of input parameters is somewhat arbitrary, and, in this case, would only apply specifically to the black-and-white letter recognition problem, and maybe could be extended to some other image recognition problems.

As a result, my questions are:

1. How do you determine what inputs you should use for a neural network?
2. Are more inputs necessarily better?
3. Does it matter if inputs are linearly independent?
4. And, finally.. Could one build a neural network that could determine its own inputs for an arbitrary problem and raw data set?

# Answer
> 3 votes
> How do you determine what inputs you should use for a neural network?

Experimentation. Initially you use a priori knowledge and intuition to guess the features will be useful for classification or prediction or whatever it is your network is doing. Then you test the network and observe its error rate. Based on the results you make adjustments; add/discard features, regularize, add/discard layers, adjust the learning rate, and so on.

> Are more inputs necessarily better?

No. You're trying to find the features that matter to what you're trying classify/predict and discard unrelated features. Processing input/features that don't matter to the computation just wastes CPU time.

> Does it matter if inputs are linearly independent?

If inputs are linearly dependent then you are in effect introducing the same variable as multiple inputs. By doing so you've introduced a new problem for the network, finding the dependency so that the duplicated inputs are treated as a single input and a single new dimension in the data. For some dependencies, finding appropriate weights for the duplicate inputs is not possible.

> Could one build a neural network that could determine its own inputs for an arbitrary problem and raw data set?

This is essentially what neural networks that deal with raw data only must do. The hidden layers tease features out of the raw data and those features are gradually refined by the feedback that occurs during training. This is an approach you might use if you have no idea how to proceed given some classification problem. But usually you have some idea what features are both useful and difficult for the network to compute for itself, and you provide those features as additional input.

# Answer
> 0 votes
As far as I know:
0) If you provide different training set to similar problem it should work, but changing only this will probably result in bigish error rate.
1) in general case you cannot. The net with some structure was trained on some training data. If you have bunch of floating point values it might mean virtually anything. Inputs structure might hint that it was supposed to be applied to image. But in fact various nets with different purpose are not distingushable when they are trained. Moreover we do not exactly know in the most cases what net "knowledge" is, and reversing this problem or retreiving "actual knowledge" is open problem.
2) No. And to provide some insight - bigger inputs and longer training time results in overfitting, decreases speed (both of training and online work). It might be infeasible to train it from some point. There was experiment on several different sizes of input for ocr - success rate increased as long input was smaller than letters size, and dropped after that point. Not complete letters started to give false results.
3) Yes it does. Here we should be more specific, but taking small steps - linearly dependent data in e.g. Widrow-Hoff algorithm it will make problems - when there are not enough degrees of freedom the network cannot be trained with 0 error. So linearly independent data is preferable.
Also linearly dependent data provides less pieces of information. You can add some biased to salvage it, but how to choose them is arbitrary decision.
4) Since simpler problems are still open - no. Taking size of the network, structure and arbitrary data recognition I would not count on usable solutions anyway.

---
Tags: neural-networks
---


# Question
Title: Lower bound on the covering radius of a code
Let $C$ be a $\[n,k\]$ linear code over $\mathbb{F}\_q$.

Suppose that $\rho$ is the covering radius .

I want to show that $\rho \geq \frac{n-k}{1+ \log\_q{(n)}}$.

Could you give me a hint how we could show this?

# Answer
> 1 votes
The idea is to use a sphere packing argument, only for covering. Let $V\_q(\rho)$ be the volume of a Hamming ball of radius $\rho$. The Hamming balls around all codewords cover the entire space, so $V\_q(\rho) q^k \geq q^n$, or $V\_q(\rho) \geq q^{n-k}$. To deduce the bound, use an approximation for $V\_q(\rho)$.

---
Tags: coding-theory
---


# Question
Title: Undecidability of telling if a program returns true or false
Consider the problem of taking an input Turing machine and determining if the final cell is a $0$ or $1$ after computation halts. On cases where it writes something else or does not halt, you are allowed to give any answer (but you have to halt and give some answer on all inputs).

Is this problem undecidable? My gut says that it should be, but I can't find a reduction to the halting problem. Given a Turing machine that may or may not halt, we can set up the machine to finish with a $0$ in the case that it halts, but can't finish with anything in the non-halting case, so the oracle could just say $0$ in this case without having to figure out whether in fact the machine halts.

Note that a reduction in the other direction is simple; if you can solve the halting problem, then given a TM that either finishes with $0$ or $1$, we replace the $1$-writing step with an infinite loop to create a new TM. If the new TM halts, we say "it writes a $0$" and if it does not halt we say "it writes a $1$". This answer is guaranteed to be correct as long as the TM in fact halts with a $0$ or $1$, so we can solve the original problem.

# Answer
Assume you have a function like the one you described:

```
def haltify(f):
    # Never fails to halt.
    # If 'f' halts, returns f().
    # If 'f' doesn't halt, anything could be returned.
    ... magic ...

```

But then someone comes along and does this:

```
def evil():
    return not haltify(evil)

```

See the problem?

1. If `haltify(f)` is guaranteed to halt for all `f`, then `evil` is also guaranteed to halt because it just calls `haltify` on a specific `f` and inverts the output.
2. Since `evil` halts, `haltify(evil)` must evaluate to the same thing as `evil()`.
3. So `not haltify(evil)` simplifies to `not evil()` and that's what `evil()` returns.
4. That's a problem, because there's no `x` satisfying `x == not x`. Evil's result is contradictory.
5. Therefore one of the assumptions we used is wrong: either `haltify` isn't guaranteed to halt, or it isn't guaranteed to return `f()` when passed a halting `f`.

Bonus exercise: why doesn't the function `def good(): return haltify(good)` cause problems for haltify, despite apparently simplifying to the infinite loop `def good(): return good()`?
> 9 votes

# Answer
Suppose that $M$ is a machine solving this problem; I assume that $M$ accepts a Turing machine and an input, but you can arrange that it only accepts a Turing machine if you prefer. We construct a different machine $T$ that works as follows. On input $x$, it runs $M$ on machine $x$ and input $x$, records the output as $b$, and writes $1-b$ on the initial cell. Now run $T$ on itself to reach a contradiction.
> 7 votes

# Answer
Your reduction to the halting problem is streightforward logically. If your machine halts, it must halt in some time T based on a primitive construction of its input. If the halting problem is unsolvable, the construction must be lossy; therefore there exists a machine for which it guesses wrongly and does halt without being fully evaluated, and a long chain of XOR forces full evaluation to reach the right answer. Therefore there exists a machine for which it yields the wrong answer.

In fact any nontrivial problem that does not exclude non-halting machines as input reduces to the halting problem in this manner. Ref: https://en.wikipedia.org/wiki/Rice's\_theorem
> -3 votes

---
Tags: undecidability, decision-problem, halting-problem
---


title: Covering radius of code

text:
# Question
Title: Covering radius of code
Let $C$ be a $\[n, k\]$ linear code over $\mathbb{F}\_q$.

I want to calculate the covering radius of the Hamming codes.

I have thought the following:

Since the Hamming distance is $3$, the coverig radius will always be $3$.

Am I right?

# Answer
The Hamming codes are perfect codes. This means that balls of radius $(d-1)/2$ (where $d$ is the minimal distance) centered around the codewords partition the space. In particular, the covering radius is $(d-1)/2$.
> 1 votes

---
Tags: coding-theory
---


# Question
Title: Relation between covering radius and columns of parity check matrix
Let $C$ be a $\[n,k\]$ linear Code over $\mathbb{F}\_q$ .

I want to show that each vector of $\mathbb{F}\_q^{n-k} $ is written as a linear combination of $m$ columns of $H$ iff $\rho \leq m$.

I have thought the following:

$$ d(C)=\min \\{ d \in \mathbb{N} | \text{ there are d linearly dependent columns of H}\\} $$

So $H$ has $ d-1 $ linearly independent columns , so each vector of $\mathbb{F}\_q^n$ can be written as a linear combination of these columns.

But what can we say about the vectors of $ \mathbb{F}\_q^{n-k}$?

# Answer
Here is the idea. Suppose that $C$ has covering radius $\rho$. Pick a vector $s \in \mathbb{F}^{n-k}$. Since $H$ is full rank, there is a vector $x$ such that $Hx = s$. There is a vector $y \in C$ with $|x-y| \leq \rho$ (here $|\cdot|$ is Hamming distance). Then $H(x-y) = s$, and so $s$ is a sum of at most $\rho$ columns of $H$. The opposite direction is very similar.
> 2 votes

---
Tags: coding-theory
---


# Question
Title: How did each class of languages receive their name?
If we look at the Chomsky hierarchy, we see that there are four well-known classes of languages: regular languages, context-free languages, context-sensitive languages, and recursively enumerable languages. There's also the class of recursive languages (which fits in between CSL and RE), but Chomsky didn't include this class in his hierarchy for whatever reason.

How did each of these classes receive its name? For instance, what does "recursively enumerable" mean in the context of a Turing machine being able to construct a RE language? What is context, and what differentiates "freeness" from "sensitiveness"? I can imagine that a language is "regular" because it can be generated by a regular expression, but I'm not sure if this is the reason behind the name.

(And a bonus question just for the fun of it: why didn't Chomsky include recursive languages in his hierarchy?)

# Answer
**Regular Languages:**

There's some good discussion of this here: https://ell.stackexchange.com/questions/83917/how-did-regex-get-its-name

**Context-Free vs Context-Sensitive Grammars:**

For CFGs and CSGs, the "context" part is the idea that certain rules can be extended to apply based on relative positions of symbols rather than on single specific symbols.

Context-free grammars have substitutions that only allow you to replace single non-terminal characters at a time and does not consider the symbols around it. Since the context of where in a string the symbol occurs does not matter, we call the rule *context-free*.

Examples:

* $S \rightarrow foo$ is a context-free rule
* $aSb \rightarrow a foo b$ is *not* context-free due to it only contextually applying when $S$ is surrounded by both an $a$ on the left and $b$ on the right. It is instead, *context-sensitive*.

Context-sensitive grammars allow you to construct rules that operate on these situations where the relative locations of symbols matter. Since the rules can be specific respective to relative positions of terminal and non-terminal symbols, the rules are said to be *context-sensitive*.

**Recursively Enumerable:**

A set (language) is **recursive** if a Turing machine can tell you if a particular element is a member of that set or not in finite time. The name comes from a field called recursion theory, where recursion is a mathematically formal way to derive what computability is.

For example, the set of even binary numbers ($2\mathbb{Z}$) is a recursive set because I can take any number and test whether or not it is even in finite time on a Turing machine.

A set (language) is **recursively enumerable** if a Turing machine can enumerate over all the elements of that set. If an element you are testing for is in the set, you will eventually encounter it while enumerating through elements of the set. However, since the set can be infinitely large, you potentially will never be able to look at them all. If your element you are searching for is not actually in the set, you will neither be able to encounter it or know for certain that it is not in there.

Recursive languages are not part of the Chomsky hierarchy because the hierarchy is specific to grammars. It is not known if there is a natural grammar that captures recursive languages. See Decidable languages and unrestricted grammars?

Side Note: Typically we say that Turing machines *recognize* languages (not construct).
> 8 votes

---
Tags: formal-languages, terminology, history, chomsky-hierarchy
---


title: Can I use "XORing" in my thesis?

text:
# Question
Title: Can I use "XORing" in my thesis?
I'm currently writing my bachelor thesis and explain some algorithms where the XOR-operation is used.

Can I use "XORing" or "XORed" in my thesis or is this too informal?

For example: "xoring the plaintext with the stream cipher results in the cypher text" and "the plaintext is XORed with the stream cipher..."

Also what would be the correct way to write it? Completly lowercase or with an uppercase XOR?

Hope this is the right community to ask this question.

# Answer
Some useful guidelines for writing are:

* Who is my audience?
* Will my audience understand what I am writing?
* Will my usage of language be distracting or otherwise take attention away from the message I'm trying to make?

In this case, your audience is probably another computer scientist who has at least some knowledge of your area. Therefore, yes, I would expect that another computer scientist will understand your meaning if you write "XORing" or "XORed". Also, it's common enough that I don't think it will be distracting. Whether it's too information is perhaps a bit subjective, but I don't view it as too informal.

I've seen it both ways: "xoring" and "XORing". Personally, I find the all-caps jarring, so my eye prefers "xoring", but I think that is a matter of taste.

Note that "ciphertext" is normally spelled that as one word, and with an "i", not a "y". Right: "ciphertext". Wrong: "cyphertext", "cypher text", "cipher text".
> 5 votes

# Answer
People will know what you mean, but "XOR" is a noun, and verbing it into the word "XORing" is a little crass.

Usually authors will explain that bits are "combined using the exclusive-OR operation" and then speak of "combining", or something like that.
> -1 votes

---
Tags: xor
---


# Question
Title: How precise is the statement "STLC is the internal language of CCCs"?
I'm studying some basic category theory in the context of type theory and came across the statement "simply typed lambda calculus is the internal language of cartesian closed categories". However terms and substitutions in the internal language of CCCs are the same data type, unlike in (traditional) STLC. Speaking in Agda, we have

```
π¹ : ∀ {Γ σ} -> Γ × σ ⊢ Γ
π² : ∀ {Γ σ} -> Γ × σ ⊢ σ
_[_] : ∀ {Γ Δ σ} -> Γ ⊢ σ -> Δ ⊢ Γ -> Δ ⊢ σ

```

where `π¹` is supposed to be a substitution constructor and `π²` and `_[_]` are supposed to be term constructors.

This additional first-orderness allows to abstract over substitutions, so we can e.g. write (using de Bruijn indices)

```
I : ∀ {Γ σ} -> Γ ⊢ σ ⇒ σ
I = ƛ var 0

silly : ∀ {Γ Δ σ} -> Γ ⊢ Δ ⇒ σ ⇒ σ
silly = ƛ (I [ var 0 ])

```

I don't know what `silly` is, but it doesn't look like a regular lambda term to me.

So is the internal language of CCCs actually more expressive than STLC or am I misunderstanding something?

# Answer
> 5 votes
Cartesian closed categories correspond to the simply typed lambda calculus *with products*. Your `silly` function is just $\lambda x.\lambda y.y$. If you want something that directly corresponds to the simply typed lambda calculus without implying products check out this paper by Bart Jacobs: Simply Typed and Untyped Lambda Calculus Revisited.

Let's instantiate your `silly` term and spell out what it looks like in type theoretic notation.

First, we're using `_[_]` at type $(\sigma \vdash \tau \Rightarrow \tau) \to (\Gamma\times\sigma\vdash\sigma) \to (\Gamma\times\sigma\vdash\tau\Rightarrow\tau)$. As a rule and placing in the terms, we get: $$\frac{z : \sigma \vdash \lambda y:\tau.y : \tau\Rightarrow\tau \qquad \Gamma, x:\sigma\vdash x:\sigma}{\Gamma,x:\sigma\vdash (\lambda y:\tau.y)\[z\mapsto x\]:\tau\Rightarrow\tau}$$ where $M\[z\mapsto N\]$ means "substitute $N$ for $z$ in term $M$". Of course, substituting for a variable that doesn't occur does nothing. So, in type theory, the above is (often by definition of substitution) equivalent to just $\Gamma,x:\sigma\vdash(\lambda y:\tau.y):\tau\Rightarrow\tau$. (Closely relatedly, weakening is also often transparent in type theory.) We then lambda abstract to get `silly`.

As a potential further insight, structural rules like $(\lambda y:\tau.M)\[x\mapsto N\] \equiv (\lambda y:\tau.M\[x\mapsto N\])$ with $y$ not free in $N$ come from naturality. This particular case comes from naturality of currying (if you spell it out, you'll see how the "$y$ not free in $N$" part is handled).

However, in this case it was a bit of a fluke that this worked out. In general, the second argument to `_[_]` should be a substitution, i.e. an arrow from contexts to contexts. In this code, a context is effectively represented by a left nested tuple (ending in an empty tuple). So if the second argument to `_[_]` does not return a left nested tuple, then `_[_]` will not behave like substitution. For example, the expression `var 0 [ var 1 ]` does *not* correspond to $$x:\sigma, y:\sigma \vdash x\[x\mapsto y\] : \sigma$$ like we might think, but rather to $$x:\sigma\times\sigma, y:\sigma \vdash \mathtt{snd}(x) : \sigma$$ This second interpretation is an artifact of this particular implementation that was exposed by failing to meet the precondition of `_[_]`. We would get the intended behavior had we written something like `var 0 [pair unit (var 1)]`. It would be cleaner and closer to typical STLC syntax to have `_[_]` take a vector of arrows that get tupled together in a left nested manner.

That this confusion between types and contexts is so easy is particular to CCCs. Most categorical semantics have a strict distinction between types and contexts; they live in separate categories. This is true of the semantics in the above mentioned Bart Jacobs paper. However, this conflation of types and contexts in CCCs makes it possible to discuss the categorical semantics without needing to introduce notions like indexed categories or fibrations.

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


# Question
Title: Why are problems in P easy and other problems not
Problems in $P$ have polynomial time algorithms. Problems in e.g. $NP-complete$ are only solvable in "probably exponential time" (Shen Lin's PET).

Problems in $P$ are considered easy while others (most likely) are not.

What does easy mean? I've always thought of *hard* and *easy* this way:

Our computing power grows exponentially over time. A problem is called easy if we can solve exponentially more instances of it (in reasonable time) after each time unit. A problem is *hard* if we can only solve polynomialy more instances of it after each time unit.

I'm well aware of complexity analysis, the definitions and their meaning. I'm trying to propose a reasonable, intuitive and easy to understand explanation of *hard* and *easy*. Would the explaination above explain it correctly and would someone who never heard of the subject understand it?

# Answer
> 3 votes
Your definition of "easy" doesn't make much sense. What exactly does "solving more instances at each time unit" mean?

Usually our notion of hardness refers to our ability to "solve" one instance. More formally, let $T(n)$ be the amount of operations required (proportional to time) for inputs of size $n$, then by "hard" we usually mean that $T$ grows too fast.

As for why polynomial $T(n)$ is considered easy, see this question.

---
Tags: complexity-theory
---


# Question
Title: A regular expression for an automaton which accepts strings with no more than 3 consecutive zeros
This is the automaton I want to find the regular expression for:

As you see, states Q1 to Q4 are accepted and Q5 is a kind of trap. This automaton accepts strings that have no more than 3 consecutive zeros.
Can anybody help finding a regular expression for this?

Note : What I tried ...
I defined A:=(0+00+000)
So the automata accepts the strings which contain no consecutive A's. But I don't know how to find that kind of regular expression.

# Answer
> 0 votes
Hint: A string with no more than 3 consecutive zeroes has the general form $$0^{p\_1} 1 0^{p\_2} 1 0^{p\_3} 1 \ldots,$$ where $p\_i \leq 3$. Try expressing that structure as a regular expression.

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


# Question
Title: Does JPEG compression use a heuristic model similar to MP3?
I know that MP3 uses a compression heuristic that allows it to exclude storing frequency data outside a certain range due to the limits of human hearing.

Does JPEG employ some sort of non-linear quantization heuristic that accounts for the limitations of humans to perceive small differences in specific color bands or ranges?

Thank you in advance for any responses.

# Answer
There are several lossy aspects of the JPEG algorithm. The main one is *quantization of high-order Fourier coefficients*, and a more minor one is *downsampling the color components*.

JPEG compression of a black and white image (we deal with color images later on) is composed of four main steps:

1. Divide the image into $8 \times 8$ blocks.
2. Perform a two-dimensional Fourier transform on each block (specifically, apply the discrete cosine transform).
3. Quantize each of the Fourier coefficients.
4. Encode the Fourier coefficients using Huffman coding.

In addition, the *DC* component (the average of each block) is encoded differentially (with reference to the previous block). The lossy aspect here is the quantization, specified by a *quantization matrix*. Higher order coefficients are quantized more heavily, and the coefficients were originally chosen experimentally (though in principle they can be optimized for each image, since they are stored in the JPEG file). The *quality* parameter mainly affects the quantization matrix.

Color images are encoded by first moving into the YCbCr color space (similar to television's YPbPr), in which Y is the saturation components, and Cb and Cr are the color components. The latter two components are *downsampled* by a factor of 2 in the horizontal dimension (this is the most common choice, though others are possible), since the human visual system is less sensitive to this kind of data. Each of the color components is then encoded as a black and white image, using two different quantization matrix, one for the Y component, the other for the Cb and Cr components. The latter matrix quantizes more heavily.
> 2 votes

---
Tags: image-processing, data-compression
---


# Question
Title: How to come up the number of nodes on a given level in heaps?
CLRS asked it's readers to prove that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$ in any n-element heap as an exercise.
The principle of Mathematical Induction can be used to prove this as explained here.

My question is how one can come up with this formula at first place. Are there any key observations that lead us to this expression initially. And then proof by induction that this will hold true for all positive integer.

# Answer
You use the principle of scientific induction: you try a few examples and guess a good bound, and then try to prove it. Simultaneously, you try to construct counterexamples. Sometimes your failed attempts at proving a bound help you find a counterexample refuting it.

Often in research one of the hardest steps is to come up with the correct conjectures. This is a creative endeavor and there are no rules which guarantee success. Skill and experience help, but sometimes you just need to be lucky.
> 3 votes

---
Tags: algorithm-analysis, data-structures, proof-techniques, heaps
---


# Question
Title: Algorithm for graph with nodes grouped into sets
I have a weighted graph. The nodes of this graph are grouped into sets, and each node has only one corresponding set (no overlapping). Nodes in the same set do not have edges between them. An edge only connects nodes that are in different sets.

I want to select one node from each set, such that the total weight of the edges between these nodes is minimized. Between two sets, I will only be traversing one edge.

Only some sets are adjacent to each other, they are not all interconnected. But some sets do have multiple neighbours. When one set is adjacent to another, the nodes in these two sets form a complete bipartite graph.

Are there any algorithms to accomplish this? And is there a name for this type of graph?

# Answer
> 3 votes
The special case of zero-one weights is already NP-hard. In fact, even determining whether there is a choice such that the total weight is zero is NP-hard. See this question on cstheory.se. (You can arrange that all the weights are, say, $1$ or $2$, and then the condition that two connected parts are fully connected is satisfied.)

---
Tags: algorithms, graphs, optimization
---