title: Closed Walk in Planar Graphs

text:
# Question
Title: Closed Walk in Planar Graphs
Input: Planar graph $G$ and its embedding in sphere $\Pi$, edges $e, f \in E(G)$ and integer $k$.

Output: The set of closed walks in $G$ using $e$ and $f$ which contains $k$ faces of $G$. In other words the set of close walks in $G$ via $e$ and $f$ which each one partition $\Pi$ into two set of faces which one is of size $k$.

I'm wondering if this problem is solvable in poly-time!

# Answer
It's not, since there can be exponentially many such walks.

The $((2 \cdot n)+1)$ by $((2 \cdot n)+1)$ grid graph will have at least $2^n$ such paths for $k = (2\cdot n \cdot n)+(4 \cdot n)+1$, since paths can go along two sides of the grid, in from both ends of that, then connect both ends of *that* in a way which encloses exactly two squares of each of the $n$ non-overlapping 2-by-2 blocks on the diagonal between those ends.

However, there are at least 8 weaker versions of what you're asking about.

1. Enumerating them in poly(input\_size, number\_of\_such\_paths) time.
2. Enumerating them in poly(input\_size) $\cdot$ number\_of\_such\_paths time.
3. Enumerating them with polynomial delay.
4. Doing one of the previous three while using only poly(input\_size) space.
5. Computing number\_of\_such\_paths and a bijection from {0,1,2,3,...,number\_of\_such\_paths-1} to the set of such paths.
6. Doing the previous thing and computing the inverse of the bijection.

I don't know anything about whether or not any of those are doable in polynomial time.
> 2 votes

---
Tags: algorithms, graphs
---


title: How to use convex hull for this problem

text:
# Question
Title: How to use convex hull for this problem
Problem:

You are to collect a total of $N$ litres of red and $M$ litres of blue liquid. For doing job $i$ for time $t$, you get $a\_i t$ litres of red and $b\_i t$ litres of blue liquid. $t$ need not be an integer. At a time you can only do one job. You can choose some (or all) of the jobs and do it for your desired time. Given such $n$ jobs in the input and their respective $a\_i$ and $b\_i$ find the lowest total time in which you can get $N$ litres of red and $M$ litres of blue liquid.

How do I solve this problem using convex hull?

# Answer
Perhaps you want a hint first? Of course you start by considering all vectors $(a\_i,b\_i)$ first. The vector $(a\_i,b\_i)$ indicates the amounts you earn by working one hour on job $i$.

What is the meaning of any point on the line segment between points $(a\_i,b\_i)$ and $(a\_j,b\_j)$?

If any point $(a\_k,b\_k)$ is within the triangle $(0,0)$, $(a\_i,b\_i)$, $(a\_j,b\_j)$ why can you discard it?
> 4 votes

---
Tags: algorithms, optimization, convex-hull
---


# Question
Title: Duplicating the quotation marks in in the quotation-mark enclosed strings
There is such a grammar

```
string_literal ::= " { graphic_character } "

```

The double-quotes that you see must appear in the user program and curly braces mean "any number of graphic characters in the string". The characters are defined further

```
graphic_character ::= basic_graphic_character | lower_case_letter | other_special_character
basic_graphic_character ::=
upper_case_letter | digit | special_character | space_character

```

with special characters listed

> " # & ' () * + , - . / : ; \< = \> ? @ \[ \] _ \`

I have encountered a situation where I need the double quote to be the part of the string. This is admitted indeed: double quote is a first special character and it enters the basic graphic characters and, thus, graphic characters. So, I can legally put it into my string. But, this means that terminating quotation mark will be considered a part of the string also and parsing will fail. The language specification says that we need to double the quotation marks to produce a single qmark in the string. I do not get why this requirement it is not a part of the grammar. How should proper grammar had to look in this case?

# Answer
Just replace `"` in the list of possible characters with `"``"`.

That might have consequences for other grammar productions which use the same non-terminals, in which case you might need to separate `special_character` into `special_character_not_quote` and `"`.
> 3 votes

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


# Question
Title: What is a weighted or probabilistic automaton?
I'm developing a program that has some entities (things) that are "classified" according to "relevancy". Sort of like search engine (think PageRank).

Therefore, I'm looking to implement an automaton, which I think should handle "value hierarchies". What I mean is that each "next possible state" should have a value that determines how "relevant" it is relative to the state from which are to be moved to it.

Is this called a weighted automaton?
Or a probabilistic automaton?

---

This is what I want:

(From: http://engineering.flipboard.com/2014/10/summarization/)

To be able to have the states that can be "moved to" have different "relevancy values".

---

My application reminds of this:

(notice the "sub contexts" centered at the blue texts)

(From: http://shadow.cios.org:2222/www/vcceguide/images/full-screen/vcce-menunew-conceptanalysis-1c3b-tripleconceptnetwork-conceptmenusearch.png)

I think it's an automaton that (in my program) would be going through those "sub contexts" (moving from blue text to blue text, based on user input). But what kind of automaton?

# Answer
The setting you suggest is not clear enough to determine what kind of an automaton you are looking for.

A short explanation regarding the types of automata:

A weighted automaton is typically an automaton with a weight function on the edges (or states). Then, a run is assigned a weight according to the weight it traverses. There are many different semantics for the value of a run. These include the maximum/minimum weight, the sum, a discounted sum, an average, etc. Finally, nondeterminism is resolved with some semantics. Typically max/min.

The important thing is that a weighted automaton defines a function $f:\Sigma^\*\to \mathbb{R}$, instead of a Boolean language (which can be thought of as a function $g:\Sigma^\*\to \\{0,1\\}$).

Probabilistic automata can be thought of as a sort of weighted automata, but a distinction is usually made (mainly because weighted automata are often defined over a tropical semi-ring). In probabilistic automata, the "weights" (probabilities) are multiplied along a run, and the sum of the (accepting) runs is taken.

If you elaborate or demonstrate the scenario you are thinking of, perhaps I can modify the answer to suggest an appropriate model.
> 7 votes

---
Tags: automata, weighted-graphs
---


# Question
Title: Why not just use FSTs for combining syntactic and semantic analysis?
I've just found the finite state transducer.

Since the FST processes two tapes: one for input, one for output,

shouldn't it be possible to use FST to "pack together" some compiler stages, such as Syntactic Analysis and Semantic Analysis.

The FST could take in tokens and output semantically analysed code.

# Answer
> 3 votes
How useful this would be depends on the level of the Chomsky hierarchy at which the transducer operates:

* Regular languages:

A Finite State Automaton (FSA) is represented by its transitions (e.g. via a diagram or a list of triples) and the corresponding transducer can be seen as adding an output to each of the transitions.

Hence, the output is at the same 'granularity' as the input alphabet, which may not always be what's desired for associating semantics with syntax.

The issue is not so much with the \`redundant (epsilon) outputs' as the possible need to make semantic decisions at the level of *sequences of syntactic elements*, modeled in regular languages by a (necessarily fairly messy) nested transducer scheme.

* Context-free grammars

More usefully than for regular languages, it is possible to use syntax-directed translation which can be seen as a \`transducing' scheme associating a semantic output with a grammatical production.

---
Tags: automata, transducers
---


# Question
Title: Efficient algorithm to decide if a location is reachable
I am designing a game solver. I have a binary $m\*n$ Matrix, where $0$ stands for a free space, while $1$ stands for an occupied space. In the game we move a ball that we will call $x$. The ball can only move UP, DOWN, RIGHT or LEFT (no diagonal).

Imagine the following matrix:

$ 1 0 0\\ 0 1 0\\ x 0 1 $

We see that the ball is in the lower left corner -- which is "trapped". **What efficient algorithm can I use to decide if the ball is trapped, that is if there is no way to get to the other side (like the example given above)?**

Another example where the ball is *not* trapped:

$ 1 0 0\\ 1 0 0\\ x 0 1 $

I am using bits matrices, I would rather not use graphs if possible.

# Answer
> 6 votes
The problem you're trying to solve is *exactly* graph connectivity. You don't necessarily need to construct the graph explicitly but this is a graph problem.

By "you don't necessarily need to construct the graph explicitly", I mean that you don't necessarily need to create any new data structures. Every time your graph algorithm says "vertex", you can think "co-ordinates" and every time it says "neighbour" or "adjacent" or "edge", you can think of the squares above, below, to the left and to the right that contain 0.

# Answer
> 2 votes
From the comments on your post, being trapped means that you cannot reach every free space. You could run a simple **depth first search** (DFS) or **breadth first search** (BFS) on x. Each iteration, you would check your neighbors (Up, down, left, right) and check if it is a free space. Each time you visit a node, you could mark it as visited. Once your search has terminated, you could just check if some of the free nodes aren't visited. The worst case time complexity of this would be O(m\*n), as you would check every vertex.

**DFS**

In DFS, you search as deep as you can before returning. Common ways to implement a DFS include a recursive function or a stack. Every iteration, you perform your check to the neighbors and add it to the stack or call your function on the new node.

**BFS**

In BFS, you search each level. Implementing this is very similar to the non-recursive DFS, but instead of using a stack, you use a queue.

# Answer
> 1 votes
Following from David Richerby answer and your comment, you are right, for this particular problem it is possible to not have to run on every node. But there can be worst cases that force you to visit every node, for example:

0000000
0111111
0000000
1111110
0000000
$x$111111

An algorithm that will prevent visiting every node is to always choose the free space closest to the stopping space. The straight-line distance can be used, which is $\sqrt{(x2-x1)^2 + (y2-y1)^2}$ for two spaces $(x1,y1)$ and $(x2,y2)$. If there are more than one of them then any one is chosen. With this we have the example scenario below on the left:

**00**089 000000
**0**0670 011111
0450**0** 00000d
230**00** 101011
10**000** $x$0100d

However this algorithm will have an issue with the matrix above on the right. The d means a dead-end. To resolve this issue the algorithm will need to go back to where there was more than one free space, and choose the next non-visited free space closest to the stopping point. A stack can be used to keep track of the path taken, thereby allowing for going back. The travel complexity is O(2nm).

Each time a node is visited it is first checked for whether it was visited before. If the first time, then it is marked as visited and processed. The node (or space) can be marked with a 1 (so is a visited or occupied space). For an array storing the matrix, both marking and checking for if marked will take constant time O(1). For a graph with linked nodes, performance can be improved by using a self-balancing search tree such as the AVL tree. This will enable O(log(nm)) searches and insertions of nodes.

You only know it is a dead-end until you get there (the fun of playing Maze). Notice that the approach of a depth-first-search is used - as deep and close to the stopping point as possible. Performance can be improved if every node in the stack stores a pointer to the last node with a non-visited free space, so that it can directly be jumped onto on going back (violating the pain in playing Maze!)

---
Tags: algorithms, complexity-theory, search-problem
---


# Question
Title: Find a source-sink-path that touches a subset of edges
I have a directed graph that has a source node and a sink node and a subset of marked edges.

I need to find a path from source to sink that contains at least one marked edge and is cycle-free.

# Answer
> 5 votes
If the path did not have to be cycle free this would be easy: let $s$ and $t$ be the source/sink, take two copies of the graph, say $(V\_1, E\_1)$ and $(V\_2, E\_2)$, and for any marked edge $\\{v\_i, v\_j\\}$ in the original graph, add $\\{v\_{1i}, v\_{2j}\\}$ and $\\{v\_{2i}, v\_{1j} \\}$ to the new graphs (connecting them), then find a path from $s\_1$ to $t\_2$.

For the cycle-less case, the best I can think of is a solution using max flow: iterate over all marked edges $\\{u, v\\}$, add a supersource and supersink to the graph, add edges from the supersource to the original source and sink $s$ and $t$, and edges from $u$ and $v$ to the supersink. Then find two vertex disjoint paths from the supersource to the supersink (we consider two paths to be vertex disjoint if the only shared vertices are the supersource and supersink, there are at most two of these paths). If no two paths exist, you cannot use the edge $\\{u, v\\}$, otherwise you can reconstruct the full path using the flow you found.

Finding these vertex disjoint paths is not entirely trivial, you'll need to transform the graph a little (see e.g. here), but it will only increase the size of the graph linearly.

---
Tags: algorithms, graphs
---


# Question
Title: Usefulness of a linked list with a cycle
Is a singly-linked list that contains a cycle considered a corrupted data structure or is there some practical use for it?

(You could argue that a car without its front shield is not corrupted, if the owner intends for it to be like that, so lets understand the word "corrupted" in a sense of "damaged into state that it is useless".)

One of the possible ideas that I got is that it can represent some sort of a computation: the initial "non-cycled head" of the list can be viewed as the initialisation phase, whereas the "cycled tail" can serve as a never-ending computation. However, this reasoning is a bit Texas Sharp-shooter fallacy to me.

Any ideas?

# Answer
> 2 votes
In the case of circular linked list - this might be a buffer, neat structure to handle operations that must be consecutive or form a ring (like in parallel programming).

What if not the whole list is cycle?
This might be intended like conflict resolving, and thanks to cycle it will not go further.
It might be the case that every operation changes state so there is cycle, but it will eventually resolve.

If you write a turn-based game with general loop, there might be cycle if user can do something multiple times per turn. So here it is intended.

And totally not constructive - cycle came from bug, so it pushes application into infinite computation.

# Answer
> 0 votes
The Hamiltonian cycle problem asks for a cycle connecting all nodes. In this case the solution is a full circular linked list. However a modified version of the problem may ask that a particular connected subset must not form a cycle (so just a Hamiltonian path) while the others must. The solution will therefore be a linked list with a cycle.

I guess this can be useful in a graph problem where a particular subset of nodes form a connected path between the head node and the connected cycle of nodes. An example is to have the head node at the borders of city A, a path from city A to B through the desert, and connected nodes in city B.

```
                   5 6
     0 - 1 2 3 - 4     7
                   9 8
 city A  desert   city B

```

# Answer
> 0 votes
One particular example that I personally like and would like to share: cyclic linked lists can be useful when dealing with non-strict functional languages.

One can represent cyclic lists with recursive functions or recursive data structures and the latter can be more efficient performance-wise. A couple examples in Haskell:

(1) The $repeat$ function produces an infinite list consisting of $x$'s only: \[x, x, x, ...\].

```
repeat x = x:repeat x            -- recursive function representation
repeat x = xs  where xs = x:xs   -- recursive data structure representation

```

(2) The $iterate$ function returns an infinite list of repeated applications of $f$ to $x$: \[x, f x, f (f x), ...\].

```
iterate f x = x:iterate1 f (f x)            -- recursive function repr.
iterate f x = xs  where xs = x : map f xs   -- recursive data structure repr.

```

The performance gain can vary *significantly* for the above examples.

Examples are taken from the book "Thinking Functionally with Haskell" (2015) by Richard Bird (pp. 212 - 213).

---
Tags: data-structures, linked-lists, philosophy
---


title: Is this grammar LALR(1)

text:
# Question
Title: Is this grammar LALR(1)
I am working through creating a LALR(1) parser generator. I have the following grammar which I designed to highlight the epsilon for rule 3.

```
0. S' -> A
1. A -> a B b
2. B -> b
3. B ->

```

This recognizes `ab` and `aab`. It is my **assumption** that with one symbol of look-ahead, I would know whether to reduce using rule 3 or shift using rule 2. That is, when scanning `ab`, I need to reduce using rule 3 to get a `B` onto my stack. But when the input is `abb` I want to just shift the first `b`, then reduce it by rule 2.

As I work through creating a LALR(1) parsing table, I get the following:

```
 , $ , a , b , A , B
0,   , s2,   , g1,   ,
1, a ,   ,   ,   ,   ,
2,   ,   , s5,   , g3,
3,   ,   , s4,   ,   ,
4, r1,   ,   ,   ,   ,
5,   ,   , r2,   ,   ,

```

The issue is that there is an ambiguity on state \[2, b\] A 'reduce by 3' was rejected. Of course, this is why I chose the grammar.

I calculated first and follow as:

```
**************
* First sets *
**************
A { a } epsilon=false
B { b } epsilon=true
S' { a } epsilon=false

***************
* Follow sets *
***************
S' { $ }
    A { $ }
B { b }

```

Anyway, I have implemented this as best I know how and the ambiguity remains. Am I doing something wrong? Am I expecting too much from LALR(1)?

EDIT - one possible place where I am confused could be when 'lookahead' occurs. If the lookahead symbol is only used to make a decision on whether a reduction should occur, then to be successful we require enough information after we shift the first a. Basically, if we see two b's coming, we can infer our only chance of success is to shift the first one and then reduce it to B. If there is only one B, we'll need to reduce the epsilon to get a B onto the stack. Then we'll be set up to successfully reduce aBb. By this metric, this would be an LALR(2) grammar. Does this make sense (in the scope of LALR(k) parsers,) or am I just wrong?

# Answer
A simpler way to see that this grammar is not LALR(1) is to look at the LR(1) item sets:

1. $S' \rightarrow \bullet A,\enspace \\$$
$A \rightarrow \bullet aBb,\enspace \\$$
2. $S' \rightarrow A\bullet ,\enspace \\$$
3. $A \rightarrow a\bullet Bb,\enspace \\$$
$B \rightarrow \bullet b,\enspace b$
$B \rightarrow \bullet ,\enspace b$
4. $A \rightarrow aB\bullet b,\enspace \\$$
5. $B \rightarrow b\bullet ,\enspace b$
6. $A \rightarrow aBb\bullet ,\enspace \\$$

You can see that in state 3 the shift/reduce conflict remains, even in LR(1). This grammar is not LR(1), and thus not LALR(1).
> 3 votes

# Answer
You should first **change your Grammar** by replacing values of B and then create a parser

```
0. S' -> A
1. A -> a b | a b b

```

or

```
0. S' -> A
1. A -> a b | a B b
2. B -> b

```

For more, this may help
> 1 votes

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


# Question
Title: Proving a sorting operation in type system
I want to know how far a type system in a programming language can be beneficial. For example, I know that in a dependently typed programming language, we can create a `Vector` class incorporating size of the vector in the type signature. It is like a de-facto example. We can also write a function `append` using those signatures so that compiler proves resulting list's size will be the sum of the input lists.

Is there a way to encode, for example, in a sorting algorithm's type signature so that compiler guarantees resulting list to be a permutation of the input list? How this can be done, if it is possible?

# Answer
Yes, it is possible to express a precise type for a sorting routine, such that any function having that type must indeed sort the input list.

While there might be a more advanced and elegant solution, I'll sketch an elementary one, only.

We will use a Coq-like notation. We start by defining a predicate requiring that `f: nat -> nat` acts as a permutation on $0..n-1$:

```
Definition permutation (n: nat) (f: nat -> nat): Prop :=
  (* once restricted, its codomain is 0..n-1 *)
  (forall m, m < n -> f m < n) /\
  (* it is injective, hence surjective *)
  (forall m1 m2, m1 < n -> m2 < n -> f m1 = f m2 -> m1 = m2) .

```

A simple lemma can easily be proved.

```
Lemma lem1: forall n f, permutation n f -> m < n -> f m < n.
... (* from the def *)

```

We define what is the $m$th element of a list having length $n$. This function requires a proof `h` stating that $m\<n$ indeed holds.

```
Definition nth {A} {n} (l: list A n) m (h : m < n): A :=
... (* recursion over n *)

```

Given an ordering on `A`, we can express that a list is sorted:

```
Definition ordering (A: Type) :=
   { leq: A->A->bool |
     (* axioms for ordering *)
     (forall a, leq a a = true) /\
     (forall a b c, leq a b = true -> leq b c = true -> leq a c = true) /\
     (forall a b, leq a b = true -> leq b a = true -> a = b)
    } .

Definition sorted {A} {n} (o: ordering A) (l: list A n): Prop :=
...

```

Finally here's the type for a sorting algorithm:

```
Definition mysort (A: Type) (o: ordering A) (n: nat) (l: list A n):
   {s: list A n | sorted o s /\
                  exists f (p: permutation n f),
                  forall (m: nat) (h: m < n),
                     nth l m h = nth s (f m) (lem1 n f p h) } :=
... (* the sorting algorithm, and a certificate for its output *)

```

The output type states that the result list `s` is $n$ elements long, it is sorted, and that there's a permutation of $0..n-1$ that maps the elements in the input list `l` to the ones in the output list `s`. Note that we have to invoke the lemma above to prove $f(m) \< n$, which is required by `nth`.

Note however that it is the user, i.e. the programmer, which has to prove their sorting algorithm correct. The compiler will not simply verify that the sorting is correct: all it does is checking a provided proof. Indeed, the compiler can not do much more than that: semantic properties such as "this program is a sorting algorithm" are *undecidable* (by Rice theorem), so we can not hope to make the proving step fully automatic.

In the far, far future, we can still hope that automatic theorem provers get so smart that "most" practically used algorithms can be automatically proved correct. The Rice theorem only states that this can not be done in all cases. All we can hope for is a correct, widely applicable, but inherently incomplete system.

As a final note, it is sometimes forgotten that even simple type systems are *incomplete*! E.g. even in Java

```
int f(int x) {
   if (x+2 != 2+x)
      return "Houston, we have a problem!";
   return 42;
}

```

is semantically type safe (it always returns an integer), but the type checker will complain about the unreachable return.
> 13 votes

# Answer
Twan van Laarhoven has a nice fully worked out example in Agda of the "Correctness and runtime of mergesort, insertion sort and selection sort".

The comments are also interesting: in them, Bob Atkey's solution involving a deep embedding of Linear Logic is for instance mentioned.
> 7 votes

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


# Question
Title: Is it "valid" for semantic functions to query outside of the grammar in attribute grammars?
Is it valid (in the sense of formal grammars or formal language theory) to **refer to outside** of the grammar in **attribute grammars**?

What I mean is that since attribute grammars can contain *semantic functions* e.g.

> E1 → E2+T { E1.val := sum(E2.val, T.val) }

then could there (in the place of the sum function) be a function that does e.g. a SQL query?

---

Should add that this is technically feasible, but I want to know that if it's reasonable and in accord to the theory of attribute grammars and the practice of **semantic analysis**.

# Answer
The `sum` function of your example itself is already stepping out of the strict scope of the grammar. Or you'd have to to explicitly include all the machinery used in your attributed grammar into it, in which case nothing forbids adding (some formalization of) SQL and a database to it.
> 1 votes

---
Tags: terminology, formal-grammars, compilers, attribute-grammars, static-analysis
---


# Question
Title: Difference between $\mathsf{SIZE}(n^k)$ vs $\mathsf{P/poly}$ and $\mathsf{SIZE}(n)$ vs linear size circuit?
In the Wikipedia page on the Karp–Lipton theorem it is mentioned that $$\Sigma\_2\not\subseteq\mathsf{SIZE}(n^k)$$ (which is known) is not same as $$\Sigma\_2\not\subseteq\mathsf{P/Poly}$$ (which is open). I was of the opinion $\mathsf{P/Poly}$ referred to polynomial size circuits which seems same as $\mathsf{SIZE}(n^k)$. Why are these circuit complexity classes different? Could someone provide an illuminating example?

Does this mean that $\mathsf{NP}\subseteq\mathsf{P/Poly}$ is possible but $\mathsf{3}$-$\mathsf{SAT}\in\mathsf{SIZE}(n)$ is impossible?

For example in this paper it is shown $\mathsf{PP}$ has linear sized circuits with respect to an oracle but not even a quantum circuit of size $\mathsf{SIZE}(n^k)$. But at $k=1$ linear circuits coincide with $\mathsf{SIZE}(n)$. Correct?

# Answer
$\mathsf{P/Poly} = \bigcup\limits\_{k\in\mathbb{N}}\mathsf{SIZE}(n^k)$.

We don't know if every language in $\Sigma\_2$ has a polynomial size circuit, but we do know that we cannot have polynomial circuits of bounded degree,i.e. $\mathsf{SIZE}(n^k)$ for some $k\in \mathbb{N}$, for all languages in $\Sigma\_2$ (Kannan's theorem).
> 6 votes

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


# Question
Title: Is there a clear line between algorithmic problem and an algorithmic problem instance?
E.g. the algorithmic problem of sorting:
input: sequence of some objects;
output: reordering of sequences such that some relation works for each next element of a sequence.

Right? So what's the instance of a problem?

So instance could be:
input type: integers; relation in the output: $\geq$.

or instance is some specific input:
like $\\{1, 2, 3\\}$; plus some relation, e.g. $\geq$.

It looks like there is a problem, then like instance, and then kind of sub-instance.

Also, for example, sorting such that relation is $\ge$ vs $\le$ is it two different algorithmic problems? Or two different instances of the same algorithmic problem?

Also if input data is numbers vs input data is strings, is it two different algorithmic problems or two instance of the same algorithmic problem?

# Answer
> 2 votes
Yes, there is a clear distinction. A problem is a general computational task; an instance is an input to that task.

The confusion in your examples is because you need to make a decision about what the task is and, correspondingly, what the input is. For any fixed domain $D$ and fixed comparison relation $\sqsubseteq$ on that domain, sorting elements of $D$ according to $\sqsubseteq$ is a problem. The instances of this problem are sequences of elements of $D$. For example, the problem of sorting natural numbers according to $\leq$ is a problem, whose instances are sequences of natural numbers. The problem of sorting natural numbers according to $\geq$ is a different problem, though its instances are also sequences of natural numbers.

Alternatively, one could make the comparison operator a part of the input. Now, the problem is to sort elements of some fixed domain $D$ using the *given* comparison operator, and an instance consists of a sequence of elements of $D$ and a comparison operator. However, it's not clear how you'd specify the comparison operator, which is a binary relation on $D$, which could be an infinite amount of data. One option might be to have a list of allowed choices so, e.g., choice 1 means sort according to $\leq$, choice 2 means sort according to $\geq$, etc.

---
Tags: algorithms
---


# Question
Title: A non-mechanical way to get an infinite decidable subset of a Turing-recognizable language?
There's a famous theorem that every infinite Turing-recognizable language has an infinite decidable subset. The standard proof of this result works by constructing an enumerator for the Turing-recognizable language, then including the first enumerated string in the decidable language, then the first string that comes after it lexicographically, then the first string that comes after that lexicographically, etc. Since this set is enumerated by a Turing machine in lexicographically increasing order, it's decidable.

This construction works, but it doesn't seem to give a very "natural" example of an infinite decidable subset. In particular, the only way I can think of to describe the subset is to point at a specific enumerator for the language, define a recurrence relation from it, and then define the language from that recurrence relation.

Is there an alternative construction that produces an infinite decidable set from an infinite Turing-recognizable language that is less dependent on the particulars of how a specific enumerator runs?

# Answer
> 2 votes
Let $\Sigma$ be an alphabet, let $\mathcal{R}$ be the collection of all recognizable subsets (languages) of $\Sigma^{\*}$ and let $\mathcal{D}$ be the collection of all decidable subsets of $\Sigma^{\*}$.

Say that $n \in \mathbb{N}$ is a *code* for $L \in \mathcal{R}$ if the Turing machine encoded by the number $n$ (via some Gödel encoding of Turing machines) recognizes $L$. Let us write $L\_n$ for the set that is recognized by the $n$-th Turing machine.

Similarly, say that $n$ is a *code* of $D \in \mathcal{D}$ if the $n$-th Turing machine is the decider for $D$. If $n$ is the code of a decider (not every number is!) then we write $D\_n$ for the set it decides.

Consider the statement: *"For every infinite $L \in \mathcal{R}$ there is an infinite $D \in \mathcal{D}$ such that $D \subseteq L$."*

You are asking whether we can prove the statement by giving an effective procedure which assigns to every $L$ a corresponding $D$ in such a way that $D$ does not depend on the choice of the code of $L$. (Clearly, we can do this inefectively by an application of the axiom of choice.) More precisely, the question seems to be whether there a computable map $f$ such that

1. if $n$ codes an infinite $L \in \mathcal{R}$ then $f(n)$ codes an infinite $D \in \mathcal{D}$ such that $D \subseteq L$, and
2. if $L\_n = L\_m$ then $D\_{f(n)} = D\_{f(m)}$.

The answer is *no, there is no such map*: **you *must* appeal to a particular recognizer for $L$ and obtain a $D$ which depends on the recognizer.**

To prove that this is really so we appeal to Rice's theorem. Suppose we had such an $f$. There exists $n, m, a \in \mathbb{N}$ such that $a \in D\_n$ and $a \not \in D\_m$. The subset $S \subseteq \mathcal{R}$ defined by $$L \in S \iff \exists n \\,.\\, L = L\_n \land a \in D\_{f(n)}$$ is a non-trivial decidable subset of $\mathcal{R}$, which violates Rice's theorem.

# Answer
> 0 votes
Let us say we have a Turing recognizable language $L$ which is not decidable, let its recognizer be $R$. Say by some method you obtain a subset of $L$, $D$ which is decidable. As $D$ is decidable we can always construct a Turing machine $T$, which when given an input $w \in D$ prints the difference between the indices of $w$ and the next lexicologically larger string that belongs to $D$ ( indices are assigned to all strings in $\sum^{\*}$, when they are listed in lexicological order ). Now we build an enumerator $E$ for $L$. First $E$ prints the lexicological smallest string in $D$ ( let it be $w\_1 $ ). It then dovetails over strings that do not belong to $D$ using $R$. And when it has $T(w\_1)-1$ strings which halt when run on $R$ and are lexicologically larger than $w\_1$, it prints all the strings which have halted while dovetailing using $R$ till now ( some of them might be smaller than $w\_1$ ), followed by $w\_2$ ( the second string in $D$, by lexicological order ). $E$ repeats the process in a similar fashion indefinitely. It is clear that when we follow your approach using $E$ we get $D$. The only difference is instead of always taking the immediate next lexicologically larger string than the previous one, which $E$ prints, we have a computable function $T$ which tells how many lexicologically larger strings to skip before taking the next one to be a part of $D$.

---
Tags: computability, semi-decidability
---


title: Anatomy of a production rule

text:
# Question
Title: Anatomy of a production rule
Production is said to be of the form $u \to v$. I want to know if you distinguish $u$ from $v$ giving them some distinguishing names, like LHS/RHS or something alike.

# Answer
> 6 votes
$u$ can be called the 'head' (or left-hand side)

$v$ can be called the 'body' (or right-hand-side)

sources: source-1, source-2

# Answer
> 3 votes
Yes, I have found it in *Parsing techniques: A practical guide*

> For brevity we write ---\> instead of “may be replaced by”; since terminal and non-terminal symbols are now identified as technical objects we shall write them in a typewriter-like typeface. The part before the ---\> is called the **left-hand side**, the part after it the **right-hand side**.

---
Tags: terminology, formal-grammars
---


# Question
Title: Finding first/last intersection in a set of lines
I am given $n$ lines, in the form $y=ax+b$, where

1. there are no two lines with the same $a$
2. no three lines intersect in the same point
3. no vertical lines

I need to find in time $O(n\log n)$ an $x'$ such that for any $x\>x'$ there are no line intersections with that $x$ value.

For example consider the lines on the image above, the thick blue line is $x=0$, and the red line is $x=x'$.

Is that possible? Any hints or ideas on how to solve this?

# Answer
Notice that you want to maximize

$$x' = - {\frac{b\_j - b\_i}{a\_j - a\_i}}$$

over all possible pairs of indices $i,j$. If you interpret the lines as points in the plane, so that the line $y=ax+b$ corresponds to the point $(a,b)$, then the above expression corresponds exactly to the negative slope, so you want to look for the minimum slope that occurs between any two points in the set. You can prove that this slope always occurs between two points that are adjacent after sorting by $b$. Similarly, to minimize $x'$, it suffices to consider only points that are adjacent after sorting by $a$.

This yields a $O(n \lg n)$ time algorithm for your problem.

---

Also, here's a somewhat less efficient solution. It doesn't achieve $O(n \log n)$ runtime (the running time also depends on coordinate magnitude and required precision), but it may be what you're looking for.

Label the lines. Let $\mathrm{sortedPermutation}(x) = (\mathrm{label}\_1, \mathrm{label}\_2, ..., \mathrm{label}\_n)$ be a function of $x$ that returns the permutation of labels which corresponds to the sorted order of $y$ values at point $x$. Notice that $\mathrm{sortedPermutation}$ becomes constant after $x'$ (the lines never change order again). Let's call this final permutation $P\_{\mathrm{final}}$. We've never seen $P\_{\mathrm{final}}$ for any $x \< x'$. If we had, it means some lines swapped order more than once and, well, lines tend not to do that. $P\_{\mathrm{final}}$ is easy to compute in $O(n \log n)$ time.

You can now use $\mathrm{sortedPermutation}()$ to evaluate candidates for $x'$ and decide if they're too small or too big compared to the real value, and use binary search to find $x'$.
> 2 votes

---
Tags: computational-geometry
---


title: Analysing a context-free grammar

text:
# Question
Title: Analysing a context-free grammar
Let:

$$S \to AC \mid BC\\ A \to aAb \mid aA \mid a\\ B \to aBb \mid Bb \mid b\\ C \to Cc \mid c$$

I need to find if:

1. the word $aabbbcc $ is in the grammer, and if so to write a very left series, and the tree.
2. what is the languege that the grammer creates?
3. to tell if the grammer is ambiguous

---

**My try:**

1. Yes, $aabbbcc$ is in the grammer because $S\Longrightarrow BC\Longrightarrow aBbC \Longrightarrow aaBbbC\Longrightarrow aabbbC\Longrightarrow aabbbCc \Longrightarrow aabbbcc$
2. The laguage is $\mathscr{L}=\\{a^\*b^\*c^\*\\}$
3. I think that the grammer is not ambiguous because I didn't find a word $x\in \mathscr{L}$ such that there are two series to $x$

I'm not sure if my attempt is correct or not.

# Answer
The derivation is correct. The language is not (your answer allows the empty word to be part of the language for example). For the third question: did you exhaust every word in the language ? Is the language finite ?

Try again.
> 1 votes

# Answer
The derivation is indeed correct.

The language is not ambiguous, I've gone through a bunch of expressions myself trying to prove otherwise to no avail.

As for the language the grammar creates, I think that it is (a|b)(a\*|b\*)(c\*|c) and my reasons for this is that the grammar:

1.must, at least, include a combination of a, b, c, the empty word is not allowed.

2.must start with either the letter a OR the letter b
> 0 votes

---
Tags: formal-grammars
---


title: Ambiguity vs. context-sensitivity

text:
# Question
Title: Ambiguity vs. context-sensitivity
It is said that attributes supply some semantic information to the grammar. Meantime, the same attributes let you to resolve ambiguities. Text books agree that it is worth haveing a CF grammar which admits ambiguities because the ambiguities will go away anyway once you evaluate your AST with attributes anyway. For this reason it is useless to invent an intractable CS grammar for your language.

This strongly associates ambiguities with context sensitivity in my mind. However, there is an expert in the field who states brazen faced that context sensitivity is absolutely irrelevant to ambiguity but supplies no support to ground his statement. Can you untangle the conflicting opinions by some light?

---

I cannot refrain from asking the same question in the following form. My mind is highly influenced by this description the of grammar type comparison in "*Parsing Techniques: A Practical Guide*"

> Type n grammars are more powerful than Type n+1 grammars, for n = 0,1,2”, and one often reads statements like “A regular (Type 3) grammar is not powerful enough to match parentheses”. It means that more powerful grammars can define more complicated boundaries between correct and incorrect sentences. Some boundaries are so fine that they cannot be described by any grammar (that is, by any generative process). This idea has been depicted metaphorically in Figure 2.33, in which a rose is approximated by increasingly finer outlines. In this metaphor, the rose corresponds to the language (imagine the sentences of the language as molecules in the rose); the grammar serves to delineate its silhouette. A regular grammar only allows us straight horizontal and vertical line segments to describe the flower; the result is a coarse and mechanical-looking picture. A CF grammar would approximate the outline by straight lines at any angle and by circle segments. The result is stilted but recognizable. A CS grammar would present us with a smooth curve tightly enveloping the flower, but the curve is too smooth: it cannot follow all the sharp turns, and it deviates slightly at complicated points; still, a very realistic picture results. An unrestricted phrase structure grammar can represent the outline perfectly. The rose itself cannot be caught in a finite description; its essence remains forever out of our reach.

> A more prosaic and practical example can be found in the successive sets of Java programs that can be generated by the various grammar types:
>
> 1. The set of all lexically correct Java programs can be generated by a regular grammar. A Java program is lexically correct if there are no newlines inside strings, comments are terminated before end-of-file, all numerical constants have the right form, etc.
> 2. The set of all syntactically correct Java programs can be generated by a context free grammar. These programs conform to the (CF) grammar in the manual.
> 3. The set of all semantically correct Java programs can be generated by a CS grammar. These are the programs that pass through a Java compiler without error.
> 4. The set of all Java programs that would terminate in finite time when run with a given input can be generated by an unrestricted phrase structure grammar. Such a grammar would incorporate detailed descriptions of the Java lib and the Java run-time system.
> 5. The set of all Java programs that solve a given problem cannot be generated by a grammar (although the description of the set is finite).

I see that CF can generate the syntactically valid programs and you need CS grammar to accommodate the semantics of the language. This more complete grammar can resolve if `x(y)` is a call of a function or type conversion. It will also iron out the associativity ambiguity in `a+b+c` telling that difference between (a+b)+c and a+(b+c) is immaterial. For this reason I think that CF -\> CS also resolves ambiguities. Why telling that context sensitivity and ambiguity are orthogonal after that?

# Answer
This is plainly wrong. The set of all Java programs that always terminate is not recursively enumerable (essentially the halting problem), and so can't be generated by any grammar.

Ambiguous context free grammars are hard to parse efficiently, compiler writers prefer unambiguous grammars (or use tricks in the parser to bypass ambiguities). If the underlying grammar is ambiguous, chances are that the attributed grammar won't give a unique meaning either.

A context free grammar is called *ambiguous* if there is a string generated by the grammar with two different derivation trees. Context sensitive grammars don't have any similar description of the derivation that is independent of the order of productions applied, so ambiguity doesn't make sense for them.
> 2 votes

# Answer
First grammars describes languages. Formally context free, context sensitive and ambiguous qualify grammars and not languages (I've never seen ambiguous used to describe a language, I've seen context free and context sensitive used to describe languages with the meaning "there is at least one context free/sensitive grammar describing the language").

Ambiguous means that there are strings which may be analyzed in several ways. It is a term which may describe any kind of formal grammars able to describe the structure of valid string.

Context sensitive on the other hand is a term which, AFAIK, has a meaning only for generative grammars (those which are defined by a set of productions rules of the form $lhs \rightarrow rhs$). It means that all the rules of the grammar are context sensitive. And a rule in a generative grammar is context sensitive if only one symbol in the left hand side is replaced in the right hand side (for instance $A\\; B\\; C \rightarrow A\\; C$ and $A\\; B\\; C \rightarrow A\\; b\_1 \\; b\_2 \\;C$ are context sensitive, only $B$ is replaced $A\\; B\\; C \rightarrow D\\; E\\; F$ is not). Context free grammars BTW are context sensitive one where the left hand side has only one symbol.

It could be that the language you are interested in can only be described with ambiguous context free grammars and that there is a context sensitive one which is not ambiguous. That does not prevent that the concepts of ambiguous and context sensitive grammars are independent and that there are ambiguous context sensitive grammars (all the ambiguous context free one to start, and then some more).
> 1 votes

---
Tags: formal-grammars, ambiguity, context-sensitive, attribute-grammars
---


# Question
Title: All regular languages are context-free so why does the terminology not reflect that?
Since Regular languages $\subset$ Context-free languages, then Regular languages are Context-free languages?

Why is the terminology so different then?

To me these seem like a totally different class of languages, based on the terminology, even though they're "variations" of Context-free languages.

How about calling Regular languages Regular context-free languages?

# Answer
> 5 votes
Much of the terminology is due to historic accidents, cast in marble well before the relationship between the different sets of languages was considered, let alone known. Nobody is able to change it now, get over it.

Many labels in mathematics are mostly arbitrary, not unlike people's names. Yes, regularity would be nicer. No, it isn't a realistic option.

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


# Question
Title: How is heap memory allocated to a process?
I want to better understand how OS provides heap memory to a process. Here by heap memory I mean the memory allocated dynamically, say by call to `malloc`.

1. When a process is newly created, does OS reserve some heap memory for it?
2. If a process calls malloc, does OS associate a "Page" (from paging concept) with process and then return some portion from that page? And so do later calls to malloc try to provide memory from this page, and if not possible OS associates another page from RAM(or virtual memory)?

# Answer
Heap allocators typically call a system call to reserve a region of pages and then dole out chunks of that to `new`, `malloc`, and other higher-level calls. The system call on Unix used to be `brk` and `sbrk`, but implementations sometimes use `mmap` as well. I think windows uses `VirtualAlloc`, but it's not totally clear to me. A good resource for this is Wikipedia's page on C dynamic memory allocation.
> 7 votes

# Answer
Short answer, summarizing the other answers: It is done by the operating system. Simple (early) operating systems assigned fixed size areas for code, data, stack + heap (with the idea that the stack and heap grew towards each other). Early Unix systems had a space for the stack and an area for data, used also by the heap (which could be extended with the specialized `brk(2)` and `sbrk(2)` system calls). More modern systems use virtual memory, and aren't bound by limited, contiguous address spaces anymore. So the program can ask for extra addresses (usually via `mmap(2)` or similar) and the library handling the heap doles out parts of that as asked.

How exactly this all works depends on the programming language (different languages pose different requirements) and the facilities the underlying kernel offers.
> 5 votes

# Answer
To answer your question 1, the short answer is yes. The long answer is when an executable is linked, there are also fields in the executable header (For Unix and Unix-Like operating systems, it's ELF. Windows uses PE32/64 for 32-bit and 64-bit.) that determine the initial size of the static data area, the stack, and the heap.

For your question 2, the short answer is "it depends." Since most modern operating systems today use virtual memory, it is common to use Virtual Memory Addressing where each program is given its own separate memory space. The size of this memory space is either 2^32 on 32-bit systems or 2^64 on 64-bit systems. A good discussion on the layout of a running program on Linux can be found here. A request to the operating system will map in more pages to extend the range of valid addresses for the program to use. These new ranges are backed by physical RAM until they are swapped out to disk.

With that being said, there are program types that are fixed in size. For example, from the old MS-DOS era, there is something known as a .COM (COre iMage) file which is an executable, but it is allocated a fixed 64k-bytes. Although, with the nature of the machines back in the day, a COM file could access the entire memory map of the machine without consequence. Other machine types have different versions of this. Current Unix implementations however, supports the ELF executable type, and possibly others such as a.out. Executable script files which are equivalent to .BAT and .CMD files on Windows, use an interpreter which is an ELF binary.
> 3 votes

---
Tags: operating-systems, memory-management, memory-allocation
---


title: Help understaning LTL formulae

text:
# Question
Title: Help understaning LTL formulae
I am studying Software Engineering and I have different LTL formulas for which I have to determine if they are valid, unsatisfiable or neither.

Here are the formulas :

1. (\<\>\[\]p ∧ \<\>\[\]q) → \<\>\[\](p ∧ q)
2. (\[\]\<\>p ∧ \[\]\<\>q) → \[\]\<\>(p ∧ q)
3. (\[\]\<\>p) ∨ (\[\]\<\>¬p)
4. (\[\](p → \<\>q)) → (p → \<\>q)
5. (\[\]false) → (\<\>false)

I don't really understand these formulas and I don't know how to proceed. Should I build a Büchi Automaton ? What are the steps to solve this kind of question ?

# Answer
> 2 votes
You could build a Büchi automaton, but that might be harder than just understanding the formulas.

Let's consider the first formula: $$(\diamond\square p \wedge \diamond \square q)\to\diamond\square(p\wedge q)$$ In the left hand side of the "$\to$", consider the expression $\diamond\square p$, which reads "eventually always $p$". Thus, the entire left hand side of the "$\to$" says that eventuall $p$ will hold forever, and eventually $q$ will hold forever.

The right hand side says that both $p$ and $q$ will eventually hold forever.

This formula is valid, since if we wait long enough, then both $p$ will hold forever and $q$ will hold forever, meaning $p\wedge q$ will hold forever (eventually).

Try to work out the rest using similar considerations.

---
Tags: logic, formal-methods, linear-temporal-logic
---


title: How are HOGs calculated?

text:
# Question
Title: How are HOGs calculated?
Histograms of oriented gradients for human detection seems to be the paper from which all other papers cite when they use HOG features. However, this was the only description I could find in it:

> \[...\] In practice this is implemented by dividing the image window into small spatial regions (“cells”), for each cell accumulating a local 1-D histogram of gradient directions or edge orientations over the pixels of the cell. The combined histogram entries form the representation. For better invariance to illumination, shadowing, etc., it is also useful to contrast-normalize the local responses before using them. This can be done by accumulating a measure of local histogram “energy” over somewhat larger spatial regions (“blocks”) and using the results to normalize all of the cells in the block. We will refer to the normalized descriptor blocks as Histogram of Oriented Gradient (HOG) descriptors.

It is not clear to me how the HOG features are now calculated:

* How big are the cells? How is that size chosen?
* What is a 1-D histogram?
* What is a histogram of directions?

Suppose we have the following 5x5 patch of a grayscale image (I hope that is a normal size for a cell - if not, please just copy this block as often as necessary or give another example):

> 000 025 255 016 200
>
> 000 255 255 017 201
>
> 010 012 210 012 111
>
> 000 000 000 000 000
>
> 255 254 255 254 255

What would be the HOG features of it?

(Can you give a citable resource for the description?)

# Answer
> 2 votes
First, let's talk about what a histogram of directions is. You can think of the image as a 2D discrete function of x and y: I(x,y). You can take partial derivatives of this function: Ix and Iy. So at each pixel you have the gradient, which is the vector (Ix(x,y), Iy(x,y)). If you compute the magnitude of the gradient, and look at it as an image, you will see the edge map. If you compute the orientation of the gradient at each pixel, you get the edge orientation at that pixel. This is what you take a histogram of.

You divide the range of orientations into some number of bins (let's say 8). Then you look at a single cell. Inside the cell you compute the gradient of every pixel, take its orientation, and add it to the appropriate histogram bin. You can also weigh the contributions by the gradient magnitude, so that pixels with stronger edges contribute more to the histogram. Once you are done, the histogram encodes the distribution of edge orientations within the cell. Dividing the image into cells preserves some of the spatial layout of the edges.

The size of the cell is a parameter, which you can tune. Typically, it is set to 8x8. If the cell is too small, then you do not have enough pixels for a meaningful histogram. If the cell is too large, then you lose too much of the spatial information.

---
Tags: computer-vision, books, features
---


# Question
Title: When does one need an Earley parser or something else vs just a DFA?
If the language is implementable as mere DFA (i.e. it's a **regular language**), then why would one need a parsing algorithm such as Earley?

Regular languages are a subset of context-free languages, but what advantages would call for Earley over a DFA in the case of a regular language?

---

E.g. in this example: https://en.wikipedia.org/wiki/Earley\_parser#Example

Couldn't this be as well implemented simply as a DFA (or "DFA scanner")?

# Answer
The context free languages are a strict superset of the regular languages, meaning that all regular languages are context free and there's at least one context-free language that isn't regular. As a result, any algorithm that can parse arbitrary CFLs can be used to recognize regular languages.

In the example you linked, you are absolutely right that the grammar provided describes a regular language and in principle if you were just trying to build a recognizer for it you could just use a DFA. Using Earley's algorithm has a few advantages, though. One big one is that, since the language is described as a CFG, you can extract a parse tree from the Earley parser when a string is in the language, meaning that you can recover the structure of the formula. This isn't something that DFAs can do by themselves.

As for whether Earley parsers can handle all CFLs and whether they're just extensions of DFAs, yes, Earley parsers can handle any CFL, and in some sense, yes, they're kind of extensions of DFAs. Context-free languages have an associated class of automaton called a pushdown automaton that is essentially a finite automaton hooked up to a parsing stack. Many context-free parsing algorithms, including LR parsers and Earley parsers, are essentially pushdown automata whose states control the stack.
> 4 votes

---
Tags: automata, parsers
---


title: P is closed under power of integer

text:
# Question
Title: P is closed under power of integer
I'm new in this area of complexity and I'm trying to get into it by understanding basic proofs.

I want to prove that if $L\in P$, so $L^k\in P$, where $k$ is non-negative integer.

How to prove it in the "official" way?

# Answer
Here is the proof for NP. You generalize it to P.

Let $L$ be a language in NP. Thus there is a polytime non-deterministic Turing machine $T$ that accepts $x$ iff $x \in L$. Using $T$, we can construct a non-deterministic Turing machine that accepts $L^k$. On input $x$, the machine first guesses (non-deterministically) a partition $x=x\_1\ldots x\_k$, and then verifies that $x\_1,\ldots,x\_k \in L$ using $T$. It's not hard to check that this machine also runs in polynomial time.

When generalizing the argument to P we have to implement the partition guessing in a deterministic way – details left to you.
> 3 votes

---
Tags: complexity-theory, closure-properties, polynomial-time
---


# Question
Title: How to extract best illustrative sentences from documents for a given word?
I want to extract "best" sentences from the given (html) documents. Let me illustrate this with an example. I have a word "determine". Now I have hundreds of html files having paragraphs and sentences that contain this word. Out of those sentences, I want to collect and score only those that are capable of describing or illustrating the meaning of "determine". Lets go further, following are the sentences I have collected from the web (from google search for the word, vocabulary.com, merriam-webster.com, yourdictionary.com) for the word "determine":

1. It will be her mental attitude that determines her future.
2. Officials are working with state police to determine the cause of a deadly bus crash.
3. They are unable to accurately determine the ship's position at this time.
4. The program officers were determined to do better on that front.
5. And how did you determine that?

In my case, I would like my algorithm to filter out (4) and (5) since they seem to be incomplete sentences in the sense they won't be able to better "illustrate" the word "determine". I won't entertain (1) as well since this sentence is not stronger enough to help the reader visualize the use of the word "determine", if we assume the reader is reading the word for the first time. Now for the remaining sentences (2) and (3), I would like to rate them to find their "usefulness".

For sure this is NLP problem and requires extensive research work to achieve. But still I am new to this domain, and it would be extremely helpful if anyone could point me towards the related works. I believe this forum is the good one to put such queries related to computer science.

# Answer
> 1 votes
Luhn, H.P. (1958, April). The automatic creation of literature abstracts. IBM Journal of Research and Development, 2(2), 159-165.

* Describes the main elements of automatically creating literature abstracts. Significant sentences are candidates for inclusion into an abstract. The measure of sentence significance is based on significant words, and the proximity of significant words within sentences. Word significance is based on its frequency within the document; the word-frequency diagram depicts the set of words to consider as significant. Word significance also applies to the creation of indexes for search and retrieval.

Consider also the presentation I created when I took a graduate course: "Term Association and Thesaurus Construction"; you might find the references there useful too.

---
Tags: algorithms, natural-language-processing
---


# Question
Title: Which sort algorithm can I use as a metaphor for this learning philosophy?
### TL;DR

Which sort algorithm:

1. Works in multiple passes.
2. Performs less and less of the total work at each subsequent pass.
3. When visualized, makes it clear that the decreasing amount of work at each stage is the result of "reaping the benefits" of the work done in previous stages.

### The Long version

My nephew is having trouble with math at school and his teacher's methods don't seem to be doing him much good either, so I've begun to tutor him here and there and it's become clear that he has some gaps in his understanding which are hindering his progress. However, he resisting review of things he feels he is already familiar with because this feels like a waste of time to him, after all he "knows that already!". He's a bright kid but like so many children these days (and possibly since the dawn of mankind) he seems to want to rush ahead as quickly as possible, which hurts him in the long run.

There's ample pedagogical evidence that the mastery of a subject before progressing yields better results in the long run, but this can obviously feel like progress is much slower when you're just getting started. I've certainly felt that way and had to discipline myself to believe that deep understanding will beat mechanical routine in the long run (proficiency is important as well, of course).

So partly in an effort to make this case to him convincingly and perhaps mostly because I have a natural tendency to think about such things in algorithmic terms, I'm asking: which (if any) sorting algorithm(s) serve as a good illustration of this principle, that slow progress (more work?) in the initial stages makes subsequent steps easier (less work).

Quicksort's recursive nature isn't a good fit, and neither is merge sort. Insertion sort takes longer at each step (on average, about $k/2$ comparisons at stage $k+1$, I think) while bubble sort only does one comparison less at each pass.

I'm not concerned about $O(n^2)$ vs. $O(n\log n)$, sorting is an imperfect analogy for learning anyway. I'm just looking for a process I can visualize for him, that will set him thinking and that, hopefully, will give him a model to grab onto for use as a mental model for the process of learning (math), a model that places emphasis (and justifies the hard work involved in) on understanding of concepts instead of the memorization of procedures, even when it seems this gets you to the final answer more slowly.

The answer doesn't have to be a sorting algorithm actually, it just seems like the most natural place to look for such an example.

* Bonus points for providing an animation.

# Answer
> 2 votes
**Bubble Sort**

After each iteration the amount of elements to be compared reduces by one. Will serve a good analogy to working in passes and the amount of work decreases on each pass.

If there is no constraint for analogy the analogy to be from sorting only, then you can use **memoization** .

# Answer
> 0 votes
Perhaps insertion sort fits the bill (build up a stretch of sorted elements, insert the next one at it's proper position among them). A totally non-obvious technique doing as requested is Shell sort. Wikipedia's page on sorting might help finding something appropriate (or at least show that there are many different ways to solve that particular problem, which in itself is sobering to people looking for **the** solution).

# Answer
> 0 votes
I believe you have discounted quicksort too easily, because the usual way quicksort gets explained is through recursion.

Instead, explain quicksort as repeatedly 'splitting up' the array, until all the splits have size 1. And instead of doing usual recursion, keep a priority queue of the biggest subarray that we can split, breaking ties by splitting up the leftmost subarray. This may sound a lot more complicated, but this priority queue is not kept at all! Spotting the biggest subarray is instantly *visually* recognizable for a human.

Here is a visualization I made of quicksort running in this fashion:

Sadly it would be too much work for one answer to visualize the splits.

# Answer
> 0 votes
Maybe try bucket sort with large input to show that buckets are collecting similar numbers, and then it is trivial to take them. When we take introsort as example, it is more beneficial to show different steps.

---
Tags: algorithms, sorting
---


# Question
Title: Set Similarity - Calculate Jaccard index without quadratic complexity
I have a group of n sets for which I need to calculate a sort of "uniqueness" or "similarity" value. I've settled on the Jaccard index as a suitable metric. Unfortunately, the Jaccard index only operates on two sets at a time. In order to calculate the similarity between all $n$ sets, it will require in the order of $n^2$ Jaccard calculations.

(If it helps, $n$ is usually between 10 and 10000, and each set contains on average 500 elements. Also, in the end, I don't care how similar any two specific sets are - rather, I only care what the internal similarity of the whole group of sets is. (In other words, the mean (or at least a sufficiently accurate approximation of the mean) of all Jaccard indexes in the group))

Two questions:

1. Is there a way to still use the Jaccard index without the $n^2$ complexity?
2. Is there a better way to calculate set similarity/uniqueness across a group of sets than the way I've suggested above?

# Answer
An option would be to use the Signature Scheme of \[1\], **size-based filtering**: a scheme which uses size information to reduce the number of set pairs that need to be considered.

They also experiment with a weighted form; where weights are IDF-based.

\[1\] Arasu, Arvind, Venkatesh Ganti, and Raghav Kaushik. “Efficient Exact Set-similarity Joins.” In Proceedings of the 32nd International Conference on Very Large Data Bases, 918–929. VLDB ’06. VLDB Endowment, 2006
> 4 votes

# Answer
Another option would be to employ local sensitivity hashing wiki link. I've seen it being used in community similarity detection by Wu and Zou (*An incremental community detection method for social tagging systems using locality-sensitive hashing*, *Neural Networks* 58:14–28; ACM DL) which is basically detecting similarity between integer or string sets.
> 0 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: maximum distance in between points in taxicab metrics - inserting and deleting points
Let's define distance (taxicab metrics) between two points $(x\_1, y\_1)$ and $(x\_2, y\_2)$ as $$|x\_2-x\_1| + |y\_2-y\_1|$$

Initially, there are given empty set of points.
I think how to find maximum distance between two arbitrary points (among inserted points). Possible operations are:
1. Insert point
2. Delete point
3. Find maximum distance (taxicab metrics) between two points.

I can do it using AVL tree (augmenting). Then I can insert and delete point in $O(\log n)$, whereas find costs $O(n\log n)$ where $n$ is number of points.

However, I consider is it possible to speed up operation Find.
Any ideas ?

# Answer
> 2 votes
Yes, I think you can get $O(\log n)$ for $find()$ too.

First, figure out how to implement $find()$ in $O(n)$ time. Here are some ideas:

1. You can iterate over all possible choices for the first point $(x\_i, y\_i)$.
2. Now the problem is that depending on where the other points are situated in relation to $(x\_i, y\_i)$ the distance formula can take $4$ different forms. Each one of them entails different signs for the coordinates. We don't know where the maximum will come from, so let's iterate over all $4$ cases. Let's say the first case is $(x\_i, -y\_i)$. You'll have to match this with a $(-x\_j, y\_j)$, and you'll want to match it with one that has the maximum sum $-x\_j + y\_j$. Your first concern is how to obtain this best sum in $O(1)$. Your second concern is convincing yourself this solution is correct, because nowhere have we made sure that the best $(-x\_j, y\_j)$ actually has $x\_j \<= x\_i$ so that $|x\_i - x\_j| = x\_i - x\_j$. We're trying to maximize the result of each case, but we're taking all points into account for all $4$ cases, disregarding their position relative to the fixed point. Can you see why this actually works?

---
Tags: algorithms, optimization, computational-geometry, search-algorithms
---


# Question
Title: Unambiguous CFG that generates regular language according to Pumping Lemma?
The pumping lemma for regular languages states:

> Specifically, the pumping lemma says that for any regular language L there exists a constant p such that any word w in L with length at least p can be split into three substrings, w = xyz, where the middle portion y must not be empty, such that the words xz, xyz, xyyz, xyyyz, … constructed by repeating y an arbitrary number of times (including zero times) are still in L.

Now what's the unambigious CFG that produces this (recognizes strings of the form $xy^kz$)?

if $x=z=a$ and $y=b$, then

$X \rightarrow aX | Xa | bX | Xb | a | b$

is ambiguous.

# Answer
> 1 votes
For your first question, *do* check out the pumping lemma for regular languages. It is quite different from what you state.

For the second one, it is the set of strings of $a$ with exactly one $b$. Use:

$\begin{align} S &\rightarrow a S \mid b A \mid b \\ A &\rightarrow a A \mid a \end{align}$

Clearly non-ambiguous. Even a regular grammar.

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


title: Prime number CFG and Pumping Lemma

text:
# Question
Title: Prime number CFG and Pumping Lemma
So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the *pumping lemma*, so I was wondering if I might be able to get a comment on what I believe is a valid proof to this problem. From what I have seen online and in our review I don't think this is the customary answer to this problem so I want to know if I am applying the concepts behind the pumping lemma successfully. The problem is *not* a homework problem and can be found on my professor's previous exams here under the fourth problem of his exam given in Fall of 2011, which is...

> Let $L = \\{0^p \mid \text{\\(p\\) is a prime number}\\}$. Prove that $L$ is not context-free using the pumping lemma for context-free languages.

So here is my proof:

> Assume that the pumping length is $m$, where $m+1$ is a prime number. I shall also assume that there is a string $uvxyz = 0^{(m/2)}00^{m/2} \in L$. There are two possible positions that do not violate conditions 2 and 3 of the pumping lemma for context languages, being $|vy| \> 0$ and $|vxy| \leq m$. These are:
>
> 1. $u = 0^{(m/2)}, v = 0, x = 0^{m/2}$, pumping by one results in $0^{m/2}000^{m/2}$. Since m/2 + m/2 is m, which is one less than the prime number m+1, it is an even number. m+2 is also an even number and since $|0^{m/2}000^{m/2}| = m + 2$, this number of zeroes is also even and thus cannot be prime, resulting in a contradiction.
> 2. The other placement is to place the string on the symmetric opposite or $x = 0^{m/2}, y = 0, z = 0^{m/2}$. This results in the same contraction as in case 1.

The string cannot be placed in the center such that $v = 0^{m/2}, x = 0, y = 0^{m/2}$ as this would violate condition three or $|vxy| \leq m$, since $|vxy| = m + 1 \> m$.

So my question is essentially, is this a valid proof and if not what is wrong with it?

# Answer
> 9 votes
Your proof is incomplete, there are many cases you don't cover. You are not ruling out, for example, $u = 0^{m/2-3}$, $v=0$, $x=00$, $y=00$, $z=0^{m/2-2}$.

A good hint that your proof is wrong is that all you're using about prime numbers is that they're odd¹. Odd numbers do form a context-free language.

The pumping lemma gives you $uvxyz=0^p \in L$ and for all $n\in\mathbb{N}$, $uv^nxy^nz = 0^{p+(n-1)k} \in L$, with $k = |vy| \ge 1$. Now you need to prove that the numbers $\\{p + (n-1)k \mid n\in\mathbb{N}\\}$ cannot all be prime.

> Look at the values of $p + (n-1)k$ modulo $k+1$ when $n$ varies from $1$ to $k+1$. Since $k$ and $k+1$ are co-prime, one of them has to be $0$ modulo $k+1$, meaning that it is a multiple of $k+1$ (and not $k+1$ itself because it's larger), so it is not prime. Depending on your mathematics background, you may formulate this argument using the Chinese remainder theorem or any other equivalent theorem.

¹ <sub> And you didn't account for $2$ being prime, but that's ok, it's enough to consider sufficiently long words, because the status of a finite number of words doesn't affect the context-freedom of the language. </sub>

# Answer
> 4 votes
If $L$ is context-free, then by Parikh's theorem, the set $\\{p \mid \text{$p$ is a prime number}\\}$ is a finite union of arithmetic progressions. Therefore, there exists an infinite arithmetic progression $a, a+r, a+2r, \dotsm$ consisting only of prime numbers. In particular $a$ should be prime, but then $a + ar = a(r+1)$ is not prime. Contradiction.

# Answer
> 3 votes
If you know the result that any CFL over a 1-symbol alphabet is regular, then you just have to show that the language isn't regular, which is a trifle easier than showing that it's not a CFL.

# Answer
> 0 votes
Use the pumping lemma for context free languages, and argue by contradiction. Say the constant of the lemma is $n$, and let $p$ be a prime $p \ge n$. If the language is context free, the string $a^p$ can be written:

$a^p = u v x y z$

where $0 \< \lvert v y \rvert \< n$, such that for all $k \ge 0$ the string $x v^k x y^k z$ represents a prime. If we call $\lvert v y \rvert = l$, this means $p + (k - 1) l$ is a prime for all $k$. Pick $k = p + 1$, and you conclude that $p + p l = p (l + 1)$ is prime. But $l \ge 1$, so $l + 1 \ne 1$, a contradiction.

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


# Question
Title: Tools or techniques for studying the language a CFG produces?
When developing a CFG, I find that one can be confused about whether the grammar is correct, i.e. whether it recognizes only the required strings and not other strings.

But this can be hard to see?

Are there techniques and tools for "proof-reading", whether the grammar is correct and succinct enough?

# Answer
There is no general method for your problem. Indeed the problem whether a CFG accepts all strings is undecidable. However you can always try to find a formal proof.

Assume you want to prove that the grammar $G$ $$ S\to aSb \mid \varepsilon$$ generates the language $L= \\{a^nb^n \mid n\ge0\\}$. Then you have to show that (1) every string $a^kb^k\in L$ can be derived from $G$, and (2) every $w \in L(G)$ has the form $a^kb^k$.

Both statements are not difficult to prove. For example to show (1) you can argue as follows. If we apply the $S \to aSb$ rule $k$ times, then we get the string $a^kSb^k$. After substituting $S$ with $\varepsilon$ we obtain $a^kb^k$.
> 0 votes

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


# Question
Title: How to convert improper CFG to weakly equivalent one?
In wikipedia there's the definition for "Proper CFG".

> A context-free grammar is said to be proper, if it has
>
> $$\text{no unreachable symbols}: \forall N \in V: \exists \alpha,\beta \> \in (V\cup\Sigma)^\*: S \stackrel{\*}{\Rightarrow} \alpha{N}\beta$$ $$\text{no unproductive symbols}: \forall N \in V: \exists w \in \> \Sigma^\*: N \stackrel{\*}{\Rightarrow} w$$ $$\text{no ε-productions}: \> \neg\exists N \in V: (N, \varepsilon) \in R$$ $$\text{no cycles}: \> \neg\exists N \in V: N \stackrel{+}{\Rightarrow} N$$

https://en.wikipedia.org/wiki/Context-free\_grammar#Proper\_CFGs

It's also stated that non-proper CFGs can be transformed into "weakly equivalent" CFGs:

> In formal language theory, weak equivalence of two grammars means they generate the same set of strings, i.e. that the formal language they generate is the same.

https://en.wikipedia.org/wiki/Equivalence\_(formal\_languages)

but I cannot find the algorithm for doing this.

How is it done?

# Answer
> 1 votes
First of all, Wikipedia does supply a reference to a standard textbook. Second, since a proper grammar is one without unproductive symbols, to make a grammar proper all you have to do is erase all unproductive symbols and all productions involving them.

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


# Question
Title: Show that some context free languages must contain more that one non-terminal
Context free languages that has only one non-terminal is a proper subset of context free languages and they does not contains regular set. Since, CFL is more powerful than FSM and contains regular set, there must be some languages that requires more than one non-terminal. How can I show or proof this formally?

# Answer
Consider the language $L=\\{a^mb^{m+n}a^n\ |\ m,n\ge 1\\}$. From the assumption that there is a single-nonterminal CFG $G$ for $L$, we can derive constraints which eventually lead to a contradiction.

$G$ is given by the (singleton) set $\\{S\\}$ of nonterminals, set $\\{a,b\\}$ of terminals, and some number of rules $S\to w\_i$ for $w\_i\in\\{a,b,S\\}^\*$. There are some obvious conditions:

1. There must be some $i$ such that $w\_i$ contains $a$.
2. There must be some $j$ such that $w\_j$ contains $b$.
3. There must be some $k$ with $w\_k\in\\{a,b\\}^\*$.

Note that some of $i,j,k$ might coincide, but this does not matter. Now suppose that there is some $l$ such that $w\_l$ contains more than one $S$, i.e. $w\_l=xSySz$ for some $x,y,z$. Then $S\to xSySz\to xxSySzySz\to\dots\to xxw\_jyw\_izyw\_jz$ which contains a $b\dots a\dots b$ subsequence, i.e. we get a word outside $L$ (once any additional $S$ which might occur inside $x,y,z$ are replaced with $w\_k$).

So the rules in $G$ really can only be of the forms $S\to u\_iSv\_i$ or $S\to w\_i$ with $u\_i,v\_i,w\_i\in\\{a,b\\}^\*$. Since we can only use one of the latter form when building a word, and we may need arbitrarily many $b$, we get

1. For some $i$, either $u\_i$ or $v\_i$ contains a $b$. We will assume wlog that it is $v\_i$; the $u\_i$ case is symmetric.

Suppose that there is also a $j$ such that $v\_j$ contains $a$; then $S\to u\_iSv\_i\to u\_ju\_iSv\_iv\_j\to u\_iu\_ju\_iSv\_iv\_jv\_i$, which again contains a $b\dots a\dots b$ subsequence and takes us out of $L$. Therefore

2. $v\_i\in b^\*$ for all $i$.

But the words in $L$ all end with an $a$, so

3. $v\_i=\epsilon$ for all $i$.

But then $G$ is a regular grammar and cannot generate a non-regular language like $L$.
> 4 votes

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


title: Full Adder vs. Half Adder

text:
# Question
Title: Full Adder vs. Half Adder
I'm having some trouble figuring out where the "Carry in" value comes from in respects to a one bit full adder diagram. I understand the below half adder,

but my question is: is the the output of the bottom-most AND gate in the bottom diagram equal to the output "C" in the top diagram (Assuming A and B are constant throughout) - Is Cin from the bottom diagram equal to C in the top diagram?

# Answer
> 8 votes
The C's are not the same, but your statement about the AND gate is right.

Unfortunately, the people who drew your full-adder decided to save space instead of maximizing readability. This image does a better job of showing the relationship between half adders and full adders, even though the circuit is identical to the one above:

If they'd just put the wire splitting points inside the grey boxes showing the half-adders instead of outside, they'd be perfect.

Here's a block diagram you can use to see the exact relationship between a half-adder and an adder. It shows clearly something I find quite interesting about adders. The 'or' at the end looks like it could swallow a carry if both half adders were to emit a carry bit at the same time. It seems like we might need another half adder to resolve this, in a never ending chain. However, if you run the truth tables for the half-adder, you find that it is impossible for both half-adders to carry at the same time. Rejoice!

---
Tags: arithmetic, digital-circuits
---


# Question
Title: DFA: Why is the transition function not a set?
The DFA is a 5-tuple ($Q,\sum, \delta, q\_0, F$) where

-finite set of states ($Q$)
-finite set of symbols called the alphabet ($\sum$)
-a transition function ($\delta: Q \times \sum \rightarrow Q$)
-an initial or start state ($q\_0 \in Q$)
-a set of accept states ($F \subset Q$)

Since in practice (programmatic implementation) the transition "production" (that is, $\delta(q\_{from}, input) = q\_{to}$) cannot be the same for all in $Q\times \sum$ and $Q$, then why is it not defined as "a set of transitions".

# Answer
> 7 votes
A function *is* a set -- a set with additional structure. A function $f: X \to Y$ can be thought of as a subset of $X \times Y$, i.e., as a set $S$ of pairs $(x,y)$ such that $f(x)=y$. However, it's not just any old set. To qualify as a function, it has to have the additional property that $f(x)$ has a single value. Put another way, the set $S$ cannot contain two elements $(x,y)$, $(x,y')$ such that $y \ne y'$: a *function* is a set $S$ where that never happens.

The same applies here. The transition function *is* a set (a subset of $Q \times \Sigma \times Q$), but a set with some additional properties/restrictions that must hold for this to qualify as a DFA.

So, it's defined as a function to emphasize the additional requirement that for each state $q$ and each symbol $s$, there is a *single* state $q'$ that you go to, i.e., a *single* transition out of $q$ on symbol $s$.

If there were multiple possible states you could go to, from $q$ when receiving symbol $s$, then it wouldn't be a *deterministic* finite automaton -- it'd be a non-deterministic finite automaton.

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


# Question
Title: Hash table collisions: why use a linked list if we can use a hash set?
One way to deal with the problem of collisions for a hash table is to have a linked list for each bucket. But then the lookup time is no longer constant. Why not use a hash set instead of a linked list? The lookup time would then be constant. For example, in C++ the hash table could be defined as:

```
unordered_map<int, unordered_set<int>> m;

```

# Answer
> 8 votes
An hash set is an hash table. Using an hash set to handle collisions in an hash table is equivalent to using a bigger hash table, with an hashing function which is a combination of the hashing functions of both level.

In other words, you'd probably be better with a bigger initial table (for instance there is no risk of resonance between the two hash functions which could lead to an higher collision rate than expected at the second level).

# Answer
> 7 votes
> But then the lookup time is no longer constant

Not worst-case constant -- which it *never* is for (basic) hashtables -- but it is still average-case constant, provided the usual assumptions on input distribution and hashing function.

> Why not use a hash set instead of a linked list?

And how do you implement that one? You have created a circular definition.

> The lookup time would then be constant.

Nope, see above.

Your major confusion seems to be about what people mean when they say that hashtables have constant lookup time. Read here on how this is true and false.

# Answer
> 5 votes
You absolutely can do this. You just have to be careful with how you set things up.

There's a type of hash table called a dynamic perfect hash table that, with some modifications, is essentially what you're describing. It works by having a two-layer hash structure, where collisions in the top level are resolved by building a hash table for the second level that is guaranteed to have no collisions.

In order to get this to work, you need to have access not just to a single hash function, but to a family of different hash functions. There's two reasons for this: first, you need to ensure that if you get a collision in the top-level hash table, you don't then get the same collisions in the second-level hash table. Second, the second-level hash table needs to not have any collisions in it (after all, we're trying to resolve collisions via a second round of hashing!), so the hash table works by choosing new hash functions until it finds one with no collision.

This system gives guaranteed O(1) lookups - you need to do at most two hashes - with expected O(1)-time insertions and deletions.

In practice, this isn't used much because you need to have a family of hash functions available and in most programming languages objects just have a single hash function available to them.

# Answer
> 3 votes
It would be pointless to use a `HashSet`. If a number of objects land in the same bucket it is because they hash to the same value (`mod nBuckets` but likely the same actual value). What hash value would you use for the inner hash-set? You are in danger of forcing the inner `HashSet` to also collide.

# Answer
> 1 votes
There are hierarchical hash maps as you describe. However, there are some caveats.

First is that a hash map is only guaranteed constant time if you can limit the cost of a collision to constant time. If there are no collisions, then using a linked-list as the next layer never comes up, because you never need to deal with collisions at all. If you want to use a hash map for collision resolution rather than a linked list, we have to consider the case where there are collisions, so we have to either find a way to control the collisions in this new map, or accept worse runtime bounds.

Linked lists are fast and easy to manipulate and traverse. They require no spatial locality, so it is easy to pool the spare nodes for many linked lists and draw from that pool as needed. Compare that to resolving collisions with hash maps which require contiguous blocks of memory to be sized and managed. It'd be virtually impossible to manage these collision resolution maps without writing a malloc like function, which is one of the more expensive operations you can put into a high-speed structure like hash mapping!

Also, what are you hashing with anyway? If there is too much of a relationship between the hashing and binning procedures for the outer hash map and the inner hash map, collisions that cause us to need a collision resolution procedure are likely to collide again in the second layer, or the third layer. You may find that what looks optimal actually becomes very suboptimal in realistic situations.

In all, it tends to be easier and faster to maintain data using a linked list or a probing technique, monitor the depth of the lists, and perhaps re-hash if they get too non-ideal. The savings in memory management complexity far outweigh the behavior of using hash maps for collision resolution.

---
Tags: data-structures, hash-tables
---


# Question
Title: In NLP, does the lexer have to tag the tokens before the parser?
In NLP, does the lexer have to tag the tokens before the parser?

I.e. does the lexer have to classify the tokens to morphological categories before the parser?

I'm thinking yes, but is this also the only way to do the parsing?

# Answer
> 3 votes
Morphological tags can help the parser. On the other hand, the complete sentence structure, maybe even the paragraph context may help to finally disambiguate possible tags for a token. So there is no yes/no answer. Except, maybe, that tagging is, afaik, usually not attributed as work of the lexer, but rather a module of its own.

---
Tags: parsers, natural-language-processing
---


title: Who are the legislators of Paxos?

text:
# Question
Title: Who are the legislators of Paxos?
In the seminal distributed systems paper The Part Time Parliament (the Paxos protocol), Leslie Lamport names fictional legislators who are involved in the Paxon parliament protocol.

According to this writing, he notes that:

> I gave the Greek legislators the names of computer scientists working in the field, transliterated with Guibas's help into a bogus Greek dialect.

Does anyone have any information on the scientists that the legislators are named after? A list of the legislators in the paper and the corresponding computer scientists would be the ideal answer.

I think the first legislator mentioned in the paper, "Λινχ∂", is named after Nancy Lynch since it could be pronounced as "Linch". Also, "Λεωνίδας Γκίμπας" from the bibliography is Leo Guibas. I'm completely lost as to who the others are.

# Answer
This is an educated guess of the transliterated names I could find in the Paxos paper. Most of these are people mentioned in the paper's references.

* Λ˘ινχ∂: Lynch, N. - Legislator
* Φισ∂ερ: Fischer, M. J. - Legislator
* Tωυεγ: Toueg, S. - Legislator
* Ωκι: Oki, B. M. - Legislator
* ∆ωλεφ: Dolev, D. - Farmer
* Σκεεν: Skeen, M. D. - Merchant
* Στωκµε˘ιρ: Stockmeyer, L. - Legislator
* Στρωνγ: (Strong/Strang?) - Legislator
* ∆φωρκ: Dwork, C. - President
* ∆˘ικστρα: Dijkstra, E. W. - Cheese inspector
* Γωυδα: (Gouda) - Cheese inspector
* Φρανσεζ: Francez, N. - Wine taster
* Πνυeλ˘ι: Pnueli, A. - Wine taster
* Σ∂ν˘ιδερ: Schneider, F. B. - Citizen
* Γρεες: (Greece) - Citizen
* Λαµπσων: Lampson, B. - General
* Λισκωφ: Liskov, B. H. - Merchant
* Παρνας: Parnas, D. - Elder statesman
* Γρα˘ι: Gray, C. G. - Priest
* Λινσε˘ι: Lindsey, B. G. - Priest
> 7 votes

---
Tags: distributed-systems, history
---


# Question
Title: What are the advantages of online learning when training neural networks?
Stochastic gradient descent with a batch size of 1 is apparently used to learn from single examples as they arrive, but I don't understand why you would use such a small batch size instead of batching training inputs together.

# Answer
Batch learning and online learning both have their place. Generally speaking batch learning will train your neural network to a lower residual error level, because the online training can sometimes have one training undo the effect of another. However, online training has a few advantages:

* Online learning schemes learn "faster." In some cases, determining how many samples you need can be difficult, and sample gathering may be costly. Online learning lets you see the progress of your training as the number of samples increases, potentially saving on sample gathering costs once it reaches an acceptable error.
* Online learning schemes can be done during operation, which can be valuable.
* Online learning schemes are more effective for dealing with data sets that are not stationary. It is easier for the batch methods to come up with highly specialized solutions which work well for the test samples, but do not capture a general solution.
> 8 votes

# Answer
One reason you'd use online learning is that the samples (data points) only arrive one at a time. If you have all of the samples (data points) available at once, then batch learning is at least an option: but if the samples arrive in a continuous, streaming fashion, one at a time, and you need to make the best decision you can at each point in time given only the samples you've seen so far, then online learning becomes attractive, because it provides a way to update the neural network as each new sample arrives.

---

Online learning does not mean "only learning one weight at a time". Online learning is about learning from one sample at a time (one data point at a time), but you're still updating all the weights of the neural network.
> 0 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: Are parser combinators equivalent to scannerless parsing?
From what I can see, parser combinators are equivalent to scannerless parsing. I do not see this stated in implementations of scannerless parsing page, nor in the parsing combinators page, neither in the google generally. But, it seems they are. I didn't code the low-level rules separately or using different syntax than higher order ones.

Am I correct that parser combinators are simply scannerless parsing? Or is there a difference that I am overlooking?

# Answer
It may be that both are commonly used together (that's the kind of estimation which is very sensible to perspective effects), but they are in principle different.

Scannerless means that the parser is directly fed the stream of characters instead of getting tokens recognized by a scanner with white spaces and comments removed. You can use whatever kind of parsers you want to parse the characters.

Parser combinators is a way to build a parser for a complex language from parsers for simpler one. The stream of symbols on which the bottom parsers are working may be a stream of tokens recognized by a scanner or a stream of characters.

That said, it is possible to hold the point of view that a scanner is a parser combinators (combining regular expressions) and thus that parser combinators are always scannerless parsers (if you are using different tools for both, that seems a quite abstract point of view). But even then, it is possible to have scannerless parsers which are using other parsing techniques.
> 3 votes

---
Tags: terminology, parsers
---


# Question
Title: What does up arrow ($\uparrow$) mean in pseudocode?
I'm learning vantage point trees, and I met this while reading the paper *Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces* by Peter Yianilos (*Proceedings of SODA 1993*, SIAM, pages 311–321; PDF). The following pseudocode appears in Algorithm 1.

$$\begin{align\*} \hspace{2em}&\hspace{-2em} \textbf{function}\text{ Make\_vp\_tree(}S\text{)}\\ &\textbf{if }S=\emptyset\textbf{ then return }\emptyset\\ &\text{new(node);}\\ &\text{node}\\!\uparrow\\!\\!\text{.p} := \text{Select\_vp(}S\text{);}\\ &\text{node}\\!\uparrow\\!\\!\text{.mu} := \text{Median}\_{s\in S}\\, d(p,s);\\ &\dotsc \end{align\*}$$

`node` is a node of vp-tree, so I know what `node.p` means, but what do that up arrow means in this context?

# Answer
> 14 votes
The algorithms in the paper you link to are described in a notation quite similar to Pascal, a language that treats pointers in a very particular way. In Pascal, pointers are declared as references to values of specific types (a pointer to an integer can never refer to a boolean, for instance).

The upward arrow, in the example you reproduce, is a dereferencing operator. Clearly, `node` is a *pointer* to a value of a record type (not a record itself), of which `p` and `mu` are fields, so `node.p` has no meaning.

Check out this similar question for further clarification.

---
Tags: notation
---


title: On $SUBEXP$, $PP$ and $P/poly$

text:
# Question
Title: On $SUBEXP$, $PP$ and $P/poly$
Complexity zoo https://complexityzoo.uwaterloo.ca/Complexity\_Zoo:D#dtime states $DTIME(f(n))$ with $PP$ oracle is not in $P/Poly$ if $f(n)$ is superpolynomial.

We know $SUBEXP=\cap\_{\epsilon\>0}DTIME(2^{n^\epsilon})\not\subseteq DTIME(p(n))$ for any polynomial $p(n)$.

So do we have $SUBEXP^{PP}\not\subseteq P/Poly$? So can we say either $SUBEXP\not\subseteq P/Poly$ or ${PP}\not\subseteq P/Poly$ holds?

I am trying to understand if $C^O\not\subseteq D$ for classes $C,O,D$ then does it follow either $C\not\subseteq D$ or $O\not\subseteq D$?

In other words if we have two classes $C,O$ with $C\subseteq D$ and $O\subseteq D$ then does it mean $C^O\subseteq D$?

# Answer
> 2 votes
If $D$ is low for itself ($D^D = D$) then $C,O \subseteq D$ should imply $C^O \subseteq D$, though it might depend on the exact definition of the oracle model (for resource-restricted classes there are sometimes delicate issues there). In contrast, if $D$ isn't low for itself then taking $C=O=D$ we get a counterexample.

---
Tags: complexity-theory, oracle-machines
---


# Question
Title: Why is the distinction between linear and context-free grammars useful?
The linear grammar is a grammar that's either left, right or left and right linear.

The context-free grammar can contain any kind of productions of non-terminals and terminals.

All linear grammars are context-free grammars.

But what is useful about distinguishing linear and context-free separately?

# Answer
> 5 votes
Let $\cal F$ and $\cal G$ be two classes of grammars, or what ever language defining devices you want. We assume that $L({\cal F}) \subset L({\cal G})$, the languages defined by the first class are included in those of the second.

Why consider both ${\cal F}$ and $\cal G$?

The most obvious reason is that the "models" in $\cal F$ are usually easier to handle to those in $\cal G$. That means it is in general easier to understand, write and analyse grammars in $\cal F$ than those in $\cal G$. So whenever it is possible to work in the smaller class we might work there.

Sometimes we want to study and understand what makes a certain type of grammar hard to handle. We know that it is undecidable whether two context-free grammars generate the same word. For regular languages (given by right-linear grammars or finite automata) it is simple to construct the intersection and decide its emptiness. Now it is a matter of curiosity to know what happens in between: what about emptyness of intersection of linear languages?

Things are not always that straightforward. Deterministic pushdown automata are strictly less powerful than the general family (which generates context-free languages). They even allow a decidable equality test which is interesting for modellers. On the other hand, except for closure under complement, they have little closure properties.

# Answer
> 3 votes
In addition to reasons of curiosity and unveiling structure, there are practical benefits.

As concrete examples, linear grammars

1. are easier to prove correct,
2. are easier to parse for and
3. always have rational generating functions, obtained by algorithmically solving a linear equation system¹.

So it makes sense to identify if a context-free language can be represented in this fashion². We wouldn't know to look for that had we not studied linear languages/grammars on their own merit.

---

1. Which means it's "combinatorically tractable" in a certain sense.
2. Typical beginner's mistake: making the grammar too complicated

# Answer
> 1 votes
As @vonbrand pointed out, there are context-free languages that do not have any linear context-free grammars. According to this source, one concrete example is $\\{a^i b^i a^j b^j | i, j \in \mathbb{N} \\}$, which intuitively seems like a good candidate for a nonlinear language (you need to somehow glue together two different strings, each of which maintains some count, but linear grammars only let you build the front and back of the string in parallel. As a result, it's meaningful to distinguish between linear and context-free languages, since linear languages are a strict subset of the context-free languages.

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


# Question
Title: How should I show that a grammar is not LL(1) and convert grammar to LL(1)
I'm trying to find the ambiguity in this grammar so I can remove it and convert it to LL(1), however for the life of me, I can't find the ambiguity. Moreover, I think there is cycle between X and Y and I could not find a solution to solve this.

> 1) X --\>YX|$
>
> 2) Y --\> ε|A|let A in Y|let A in E end
>
> 3) A--\> x=E
>
> 4) E--\>(E)|E\*E|\*E|EE|x|ƛx.E\`

# Answer
`E → EE` is obviously ambiguous, as as `E → E*E`. How should `xxx` be parsed? Is it \[\[x x\] x\] or \[x \[x x\]\]?

`X` is only problematic if `Y` is nullable. If you remove the incorrect empty production for `Y`, you will also fix that issue.

---

To clarify, `Y → ε` is incorrect because it would allow `Y` to derive

```
let A in

```

which is not a complete statement (I mean, not a complete `Y` :) ). The production `Y → let A in Y` is sufficient to allow a statement to be preceded by any number of `let A in` clauses, without allowing it to be unterminated.
> 1 votes

---
Tags: formal-grammars, parsers, ll-k
---


# Question
Title: Problems whose decidability status is unknown but known to be less hard than the halting problem
Are there problems the decidability of which is unknown but it is known for certain that the problems are less hard than the halting problem.

# Answer
> 5 votes
Assuming that by "less hard" you mean "reducible to", then any problem that is known to be in $RE$ but not known to be in $R$ satisfies this condition.

For example, take the PCP problem with 4 tiles, whose decidability is open. It is an easy exercise to reduce the problem (or any other problem in RE) to HALT.

---
Tags: computability, reference-request, undecidability
---