title: augmenting AVL, intervals

text:
# Question
Title: augmenting AVL, intervals
Show how to augment dictionary of intervals (insert, delete, search) in order to make possible answer to following questions:

1. Check if given interval $\[a, b\]$ intersects with some interval in a dictionary
2. Check if given interval $\[a, b\]$ belongs to some interval $\[c,d\]$ in a dictionary (it means that $\[a,b\]\cap \[c,d\] = \[a,b\]$)
3. Check if given interval $\[a, b\]$ intersects with some interval $\[c,d\]$ in a dictionary, such that $\[c, d\]\cap \[a,b\] \neq \[a,b\]$ and $\[c,d\]\cap \[a,b\] \neq \[c,d\]$.
4. Check if is there in dictionary pair of intervals $\[a,b\];\[c,d\]$ such that $\[a,b\]\cap \[c,d\]\neq\emptyset$

Now, I say what I tried and why I am in stuck.
I use AVL tree. Key is left end of interval. Additional info in each node is maximum right end of intervals in subtree (of this node).
Moreover I include information about intersection in subtree (true or false) Then 1., 2., 4. are easy. However it is difficult to deal with 3.

Could you help me ? (don't throw out my thread, please)

**Edit**
dictionary = $\\{\[1,5\], \[2,7\], \[13,97\], \[213, 321\]\\}$
And now examples for 3. :
$\[3,5\]\to no$
$\[95,100\]\to yes$
$\[5,10\]\to yes$
$\[215, 321\]\to no$
$\[215, 322\]\to yes$
$\[4,6\]\to yes$
$\[2,7\]\to yes$
$\[2,5\]\to no$

# Answer
> 1 votes
Try to read this one: Interval Tree
I wouldn't store intersections.

When you augment tree you should place nodes in some order to avoid conflicts in searches. Try different scheme as in the link, there will be no need to choose which way to go during search.

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


# Question
Title: Are NP-complete sets formed from two other sets only if at least one is NP-hard?
This question is somewhat of a converse to a previous question on sets formed from set operations on NP-complete sets:

If the set resulting from the union, intersection, or Cartesian product of two decidable sets $L\_1$ and $L\_2$ is NP-complete, is at least one of $L\_1, L\_2$ necessarily NP-hard? I know that they cannot both be in P (assuming P != NP) since P is closed under these set operations. I also know that the conditions of "decidable" and "NP-hard" are necessary since if we consider any NP-complete set $L$ and another set $B$ outside of NP (whether just NP-hard or undecidable) then we can form two new NP-hard sets not in NP whose intersection is NP-complete. For example: $L\_1:= 01L \cup 11B$, and $L\_2:= 01L \cup 00B$. However, I don't know how to proceed after that.

I'm thinking that the case of union might not be true since we can take a NP-complete set $A$ and perform the construction in Ladner's Theorem to get a set $B \in$ NPI which is a subset of $A$. Then $B \cup (A \setminus B) = A$ is the original NP-complete set. However, I don't know if $A \setminus B$ is still in NPI or NP-hard. I don't even know where to start for the case of intersection and Cartesian product.

# Answer
The intersection of two non-NP-hard languages can be NP-hard. Example: The solutions of any 3SAT instance are the set intersection of the solutions of a HORN-3SAT instance and an ANTIHORN-3SAT instance. This is because a 3CNF clause must be either a Horn or anti-Horn clause and a 3SAT instance is the conjunction of such clauses. 3SAT is of course NP-complete; HORN-3SAT and ANTIHORN-3SAT are both in P.
> 1 votes

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


# Question
Title: Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$
I have recently encountered the following problem which I heard can be solved by using BIT (binary indexed trees) but I am not sure how:

Given an array $a\[1, 2, \ldots, n\]$ and $Q$ queries of the form $(L, R, i)$ $(L\leq i\leq R)$. For each query, you have to print the number of $j$ such that $L\leq j\leq R$ and $a\[j\] \leq a\[i\]$.

I tried coordinate compression and then sorting the queries by increasing order of $i$ (answering the queries offline), but the L, R part make things hard. I think we can convert the query $(L, R, i)$ into two parts $(1, R, i)$ and $(1, L-1, i)$ (and subtract them), but how to find the answer for that either?

Also note that this problem can be solved by Mo's algorithm, but I am looking for something like $O(q \log n)$ or $O (q \log^2 n)$ (maybe binary search on the answer and do some magic with bits?).

Thanks :)

# Answer
Here is a solution in time $O((Q+n)\log^2 n)$ and space $O(n\log n)$. For simplicity, assume that $n$ is a power of $2$, and that the array is zero-based.

A *dyadic interval* is an interval of the form $\[c \cdot 2^k,(c+1) \cdot 2^k)$ (that is, $c\cdot 2^k,\ldots,(c+1)\cdot 2^k-1$). For example, when $n = 8$ we have the following dyadic intervals: $$ \[0,8),\[0,4),\[4,8),\[0,2),\[2,4),\[4,6),\[6,8), \\ \[0,1),\[1,2),\[2,3),\[3,4),\[4,5),\[5,6),\[6,7),\[7,8). $$ Each interval of the form $\[0,x)$ is the disjoint union of at most $\log\_2 n$ slices. For example, for $n = 8$ we have (for $x \neq 1,2,4,8$): $$ \[0,3) = \[0,2) \cup \[2,3), \\ \[0,5) = \[0,4) \cup \[4,5), \\ \[0,6) = \[0,4) \cup \[4,6), \\ \[0,7) = \[0,4) \cup \[4,6) \cup \[6,7). $$

A *dyadic slice* of the array $a$ consists of the elements $a\[s\],\ldots,a\[t\]$ for some dyadic interval $s,\ldots,t$.

As preprocessing, we sort (separately) each dyadic slice of $a$. This takes time $O(n\log^2 n)$ and consumes space $O(n\log n)$ (since each index participates in $\log\_2 n$ slices).

As mentioned in the question, it is enough to handle the following type of query:

> Given $i,R$, count the number of indices $j \<R$ such that $a\[j\] \leq a\[i\]$.

Given $i,R$, we retrieve $a\[i\]$, and present $\[0,R)$ as a union of $O(\log n)$ dyadic intervals $I\_1,\ldots,I\_m$. Using binary search, for each $k$ we determine the number of indices $j \in I\_k$ such that $a\[j\] \leq a\[i\]$. This takes time $O(\log^2 n)$ (altogether). Summing these numbers, we arrive at the answer to the query.
> 2 votes

---
Tags: algorithms, binary-trees, binary-search
---


# Question
Title: Can someone explain this diagram about Slab Allocation?
I'm trying to understand how Slab Allocation works and why it is different or better than ordinary paging.

I found this diagram which I believe would be helpful if it had more explanation.

Some questions:

* What do the 3KB and 7KB items represent? Must they be related somehow? Why are they packaged that way?
* In the caches column, are the caches the grey boxes, or the white/blue boxes inside the grey boxes? Are the grey boxes a package of caches?
* Are the slabs just the blue boxes or is the whole "Physical Contiguous Pages" a slab?

I'd really appreciate some help. THanks!

# Answer
I can see why you're confused. The diagram is a bit confusing, and may actually be incorrect.

First off, let's think about why a kernel needs a memory allocator below the level of pages. This is probably already stuff that you mostly know, but I'll go through it for completeness.

Pages are the typical "unit" of memory operations. When a user-space application allocates memory, or memory-maps a file, or something like that, it typically gets a multiple of the machine page size. There are notable some exceptions; Windows uses 64k as the virtual memory allocation unit no matter what the page size of the CPU is. Nonetheless, let's think of it this way.

On a modern CPU, as far as user-space code is concerned, it has a flat address space. This is actually an illusion provided by the virtual memory system. The OS provides pages from anywhere in RAM (or possibly not in RAM at all, in the case of swapped memory or memory-mapped files) and maps them into a contiguous virtual address space.

The point of all this is that apart from a few special cases for the operating system itself (perhaps DMA buffers, maybe some special data structures set up at boot time, oh and the kernel image itself), the operating system kernel probably never has to manage any block of RAM bigger than a page. This simplifies things enormously, because it means that as far as pages go, every allocation and deallocation is the same size. It also effectively eliminates external fragmentation at the macro level.

However, kernels also need to implement some data structures of their own, and for that, they need a different kind of memory allocator. These data structures can usually be thought of as a collection of individual objects (e.g. an object may be a "thread" or a "mutex"). The size of these objects are typically far smaller than a page in size.

So, for example, an object which represents the security credentials of a process (think of the user id and group id in POSIX, say) might only be 16 bytes or so, whereas a "process" or "thread" might be up to 1kb in size. Clearly you don't want to use a whole page for these small records, so the idea is to implement an allocator on top of pages.

The lower-level allocation system has to satisfy many of the same issues as the page-level allocator: it has to be reasonably fast (including on multicore systems), you want to minimise fragmentation, and so on. But more importantly, it should be tunable and configurable depending on what kind of data structure you're storing.

Some data structures are inherently "cache-like". For example, many operating systems maintain a cache of path names to filesystem objects to avoid long chains of directory lookup (called the "name cache" or "namei cache" in Unix-speak). These objects are only needed for performance, not correctness, so you could (in theory) just forget a whole page full of entries if memory is tight and you need to free a page frame quickly.

Other data structures could be swapped to disk if memory is tight and you don't need them soon. But you don't want to do that with data structures which control swapping or the virtual memory system!

Some data structures can be moved around in memory with no penalty (e.g. if nobody refers to them with a pointer), so could "compact" themselves to avoid fragmentation if needed.

So the main idea of the slab allocator is that a page should only store data structures of the same "type". This ticks all the boxes: each object in a page is the same size, so there's no external fragmentation. Objects of the same "type" have the same performance requirements and the same semantics.

Incidentally, it's a similar story with allocation. For some types of object it's probably okay to wait if there's no memory immediately available to allocate that object. An object which represents an open file might be one example; opening a file is an expensive operation at the best of times, so waiting a little longer won't hurt that much.

For other types of object (e.g. an object which represents a real-time event that must happen a certain time from now), you really don't want to wait. So it makes sense for some types of object to over-allocate (say, have a few free pages in reserve) so that requests can be satisfied without waiting.

What you're basically doing is allowing each type of object to have its own allocator, which can be configured for the needs of that object. These per-object allocators are confusingly called "caches". You allocate one cache per type of object. (Yes, you'd typically implement a "cache of caches" as well.) Each cache only stores objects of the same type (e.g. only thread structures, or only address space structures).

Each cache, in turn, manages "slabs". A slab is a page frame which contains an array of objects of the same type. Slabs may be "full" (all objects in use), "empty" (no objects in use), or "partial" (some objects in use).

Partial slabs are probably the most interesting, since the slab allocator maintains a free list for every partial slab. (Full slabs and empty slabs need no free list.) Objects are allocated from partial slabs first (and probably from the "most full" partial slabs first) to try to avoid allocating pages that aren't needed.

The nice thing about slab allocation is that all of these allocation policy options (as well as the memory semantics) can be tuned for each kind of object. Some caches might retain a pool of empty slabs and some might not. Some might be able to be swapped to secondary storage and some might not.

Linux has has three different kinds of slab allocator, depending on whether or not you need compactness, cache-friendliness, or raw speed. There was a good presentation on this a couple of years ago which explains the tradeoffs well.

The Solaris slab allocator (see the paper for details) has a few more details to squeeze even more performance. For a start, in Solaris, everything is done with slab allocation, including page frame allocation. (This is Solaris' solution for allocating objects that are larger than half a page in size.) It manages smaller objects by nesting slab allocators in slab-allocated space.

Some objects in Solaris require complex and expensive construction and destruction (e.g. objects which have a kernel lock), and so they could be "partly free" (i.e. constructed but not allocated). Solaris also optimises free slab allocation by maintaining free lists on a per-CPU basis, ensuring that some operations are completely wait-free.

To support general-purpose allocation (e.g. for arrays whose size is not known at compile-time), most macrokernel-type operating systems also have caches which represent object *sizes* rather than object *types*. FreeBSD, for example, maintains caches for unknown objects whose sizes are powers of 2 bytes, from 4 to 256.

What I hope you can see is that slab allocation is a very flexible framework which can be tuned for the needs of different kinds of data. It doesn't compete with paging, but complements it (although in Solaris, page frames are allocated with slabs).

I hope this helps. Let me know if anything needs clarification.
> 23 votes

# Answer
The idea underneath the slab allocator is that the operating system needs specific but somewhat standard data structures (for example the process PCB, semaphores, file metadata etc) that suggest the memory usage that is necessary for them.

The slab allocator algorithm provides stocks of memory areas whose dimensions and initialization are optimized for these standard data structures. For example, as you can see from the picture, there can exist 3kb objects as well as of 7kb objects. However, we know that the kernel only allocates memory in multiples of the page size.

In order to avoid time and memory waste, the OS keeps in different caches pools of memory areas that can be rapidly allocated upon request, and the cache dimensions are different for every type of object and structure. However, the caches do not directly contain and manage these memory areas, and are not even guaranteed to reside in contiguous memory. They are instead divided in slabs, contiguous pages of memory, whose number is generally chosen to reduce memory fragmentation. It is in the slab that reside the different object instances, whether allocated or free. If a cache is full, new slab is allocated somewhere in the primary memory and it is added to the cache.

To sum up, the things you can see in the picture are examples of objects that the OS knows to be 3-7-whatever kB big. The kernel does not allocate a page memory specifically for them, since that would exponentially increase memory fragmentation, but "redirects" them to a cache (the grey box). In the cache there should be addresses that indicate physically contiguous areas of memory, the slabs (the white/blue sets of boxes) and the objects are finally allocated in an area of the slab (a part that is colored in blue, among free of full analogous memory areas of the same slab).
> 6 votes

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


# Question
Title: Arden's lemma applicability on context free grammars
The Arden's lemma states that there exists a solution to the equation between regular expressions r = sr + t, with r unknown, and it is s\*t.

I went through some other topics on the forum and I always saw it being applied, for example, on grammars that have productions like

S-\>AS|b

so that L(S) = L(A)L(S) + b and the solution is L(A)\*b.

However, on some student notes from a classmate I found this example:

S-\>ASA|A

A-\>aAa|Ab|e

and the Arden's rule is applied in this way without any further manipulation of the grammar:

L(S) = L(A)L(S)L(A) + L(A) and it concludes by saying that L(S) = L(A)\*

This seems wrong to me, but I want to check first whether there is some further hypothesis that can be applied here to make the statement valid. For example, I wonder if it is decidable (and of course valid) whether the productions S-\>ASA|A generate the same language of the productions S-\>AAS|A.

Can somebody please help me?

# Answer
First of all, let me mention that Arden's lemma applies not only to regular expressions but to any equation among languages of the form $r = sr+t$, where $r,s,t$ are arbitrary languages. The smallest solution to this equation (also known as the least fixed point) is always $r = s^\*t$. If $\epsilon \notin s$, then this is in fact the only solution. (Otherwise, $\Sigma^\*$ is also a solution.)

The language generated by the rule $S\to aSa|a$ is not $a^\*$ but rather $a(aa)^\*$: only odd powers are allowed. So it seems that the student notes contain a mistake, though in this particular case the calculation yields the correct conclusion since $\epsilon \in L(A)$.

On the other hand, $S\to aSa|a$ and $S\to aaS|a$ do generate the same language. More generally, if the only rules involving $S$ are $S \to ASA|A$, then replacing these rules by $S \to AAS|A$ or $S \to A|SAA$ result in the same language, $L(A)(L(A)^2)^\*$; and if $\epsilon \in L(A)$, we can further simplify this to $L(S) = L(A)^\*$.
> 3 votes

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


# Question
Title: How a human brain does computation after lexical analysis and parsing?
I've been trying to figure out the answer for this question.

> How exactly a human brain understands or computes the meaning of any sentence after doing the lexical analysis and parsing? What is the science behind this?

I've searched widely but couldn't read anything satisfactorily. I hope to get one here! Beside, It will be helpful if someone could also suggest me some resources where i can learn more about this. Thanks in advance!

# Answer
Adding a tiny bit I **know** there is flaw in the question to start with.
These are connected and "understanding" process starts with the first word. Interconnecting everything to provide one satisfactory answer is impossible.
If you are really interested in subject read history of H&M and Phineas Cage.
Then start with the core point of problem stated with simpler question "why people do not remember anything before they were 3 years old" approximatelly 3, but you will find out soon enough.
Then read about Cohort model.

Sorry but I do not have several days to spare right now.
And probably this is not ontopic here.
> 0 votes

---
Tags: artificial-intelligence, neural-networks, neural-computing
---


title: Edit distance between two strings

text:
# Question
Title: Edit distance between two strings
If X denotes the length of string s1 and Y denotes the length of the string s2, then the edit distance between s1 and s2 is never more than
`Min(X,Y)` or `Max(X,Y)`?
Please explain.

# Answer
It depends on the exact definition of edit distance:

Let, $s1=a$, $s2=bb$

The edit distance between $s1,s2$ is 3 if allowed *only* insertions and deletions; but it is 2 if allowed insertions, deletions and substitutions.

With substitutions, it is clear that the number of letters you need to change is at most the length of the longer string.
> 2 votes

---
Tags: edit-distance
---


title: Bytes and bits conversion?

text:
# Question
Title: Bytes and bits conversion?
It is claimed in my textbook that

> In a 32-bit system, The instruction LDR r4,\[r6\] lets you address a logical space of 4GB.

I know where the 4GB comes from, It is simply 2^32 / (1024 x 1024 x 1024).

However, My question is why is it bytes and not bits ?

Why when we raise 2^32, we should talk about bits and not bytes. And so 4GB doesn't make sense to me .

For me It would make sense if it is (2^32/8)/ (1024 x 1024 x 1024)

# Answer
That's because memory is usually byte-addressed. The address that you load from is an address of a byte in memory. Each address refers a different byte in memory. For a 32-bit address, there are $2^{32}$ different possibilities for the address, so $2^{32}$ different bytes that the address could refer to (and no overlap among these bytes). $2^{32}$ is equal to 4GB.

If we had a hypothetical machine where memory was bit-addressible, then it would indeed be 4Gb, i.e., 4 gigabits instead of 4 gigabytes -- but no one builds machines that way today.
> 1 votes

# Answer
One needs to distinguish the *address bus* and the *data bus*.

The width of the **address bus** determines how many locations (=words) the system can access. For instance, with 32-bit address bus, the system can access $2^{32}$ different addresses, that is, 4G words.

The width of the **data bus** determines how many bits each word consists. If the data width is 32 bits then each word is 32bits (4 bytes). There are architectures where word size is a byte, bit, or even 64bits.

Unless otherwise mentioned, it makes sense that a "32bit system" has an address bus and data bus of 32 bits. But one needs to check the specifics to be sure.
> 1 votes

---
Tags: computer-architecture, memory-access
---


# Question
Title: What is language of repeat(L) = {ww | w ∊ L}?
> What is language of repeat(L) = {ww | w ∊ L} ?

---

### My try:

I know it {ww | w ∊ (a,b)\*} is context sensitive language. Here , what is meant by "repeat(L)" ? Can you explain it ? It is not a homework question.

# Answer
$repeat(\cdot)$ is an operator on languages. It takes as an input a language $L$, and outputs a language defined by $\\{ xx \mid x \in L\\}$. That is, for any word $x\in L$ the string $xx$ will be in the output language $repeat(L)$.

A Few examples:

> $L=\\{ 0,00, 11\\}$ =\> $repeat(L) = \\{ 00,0000,1111\\}$
>
> $L=\\{ \\}$ =\> $repeat(L) = \\{ \\}$
>
> $L=\Sigma^\*=\\{\epsilon,0,1,00,01,10,11,...\\}$ =\> $repeat(L)= \\{\epsilon, 00,11,0000,0101,1010,1111,...\\}$
> 5 votes

---
Tags: regular-languages, regular-expressions, context-sensitive
---


# Question
Title: What's the error in the following proof of the halting problem decidability?
Let's encode every state and tape word (with position of Turing machine on it) with a single integer. Then the transition function can be represented as a total function from integers to themselves. Now let's apply any known algorithm for searching a cycle in the chain of pointers to that function and we've got it!

P.S. Sorry, it's late night question... The proof has to be complete nonsense :-)

# Answer
> 4 votes
A Turing machine may run forever without ever entering any kind of cycle. (Consider the machine which always just moves its head to the right.)

# Answer
> 0 votes
The Collatz conjecture is already given in the form of a total function from the integers to themselves. Both the task to decide whether there exists a cycle different from 1 -\> 4 -\> 2 -\> 1 and the task to decide whether there exists an infinite divergent trajectory are still open.

It is true that if there were a cycle, then a "slow theoretical" algorithm would be able to find it. On the other hand, the absence of a cycle (in general) cannot be verified by any algorithm. But Andrej Bauer is correct, possibility that there are infinite divergent trajectories is what prevents your proof to work in the intended way.

---
Tags: computability, halting-problem
---


# Question
Title: Data structure for optimal deduplication of common subsets
Consider a database with the following properties:

* It stores symbols (represented as 64-bit integers) and sets of symbols
* Sets may contain thousands of symbols, and there may be thousands of sets which are the same except for one or two added symbols
* Every set should have exactly one canonical representation (two identical sets must have identical representations in the database)

If several sets contain large common subsets, they should be highly compressible: it should be possible to represent the common subset as a set itself, and store a reference to it, similarly to most persistent data structures.

However, the requirement for a single canonical representation of a set complicates things. Inserting certain new elements may rearrange the entire data structure, removing shared subsets. What kind of data structure would allow for shared common subsets in the majority of cases? My first guess is a balanced binary tree, but I'm not sure if balancing is even necessary; all that's needed is for the same set of symbols to always result in the same tree.

# Answer
> 2 votes
What you're looking for here is the intersection of two classes of data structures:

* Persistent data structures, in which modifying a structure doesn't eliminate access to the old structure. This ensures that the shared parts don't have to be stored twice.
* Uniquely represented data structures, as required by your "one canonical representation" phrase.

Unfortunately, most persistent balanced tree data structures are not going to be uniquely represented. One that is uniquely represented is the sorted Braun tree, but they do not share a lot of structure, and two trees with $O(1)$ differences can have structures that are different in $\Omega(n)$ locations.

If you nest Braun trees within Braun trees, you can get this down to $O(\sqrt{n \log n})$.

However, since your symbols are 64-bit integers, you're in a good spot. You can use path-compressed tries, which have a unique representation. They use $\Theta(n)$ nodes to store a set of $n$ symbols, and adding or deleting a symbol to an existing set of symbols allows sharing almost all of the original structure: no more than $2 + \min(n,w)$ new nodes are created, where $w$ is the word width (64 for you).

---
Tags: data-structures, sets, data-compression
---


title: NP-hardness reductions

text:
# Question
Title: NP-hardness reductions
Suppose I have two generic problems $A\_{1}$ and $A\_{2}$: the instance of $A\_{i}$ is a graph $G$ and a number $t$, and the question is whether a certain parameter $P\_{i}(G)$ is at least $t$.

Suppose I want to reduce the NP-c problem $A\_{1}$ to $A\_{2}$. If I can show that $P\_{1}(G) \geq x$ if and only if $P\_{2}(G) \geq y$ for any $G$ with at least say $100$ vertices, do I have an admissible reduction?

# Answer
> 4 votes
If your problem is with the 100 vertices limitation, then you're in the clear. Consider the following reduction: given input $\left( G,t \right)$, if $G$ has under 100 vertices, exhaustively test all witnesses and check if $\left( G,t \right)\in A\_1$, this can be done since $A\_1\in NP$. Depending on whether or not $\left( G,t \right)\in A\_1$ output some constant word in/not in $A\_2$.

If G has more than 100 vertices, then your reduction outputs $\left(G,y\left(G,t\right)\right)$. Since you proved $\left( G,t \right)\in A\_1 \iff \left(G,y\left(G,t\right)\right)\in A\_2$ it's a reduction from $A\_1$ to $A\_2$. You will probably want (if you're dealing with polynomial time reductions) to show that $y\left(G,t\right)$ is computable in polynomial time.

The asymptotic behavior of the reduction's running time does not depend on how you treat small inputs (in this case, graphs with less than 100 vertices).

Edit: I should note that inputs can get arbitrarily large while keeping the graph small, by increasing $t$. However i assume that (as is with many natural graph problems e.g. clique, independent set) that if $t\ge f(|V\_G|)$ for some increasing function $f$, you can simply decide whether or not $(G,t)\in A\_1$.

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


# Question
Title: Can you recommend me book with problems?
I am searching for book about algorithms (excercises) with solutions. Can you recommend me one?

# Answer
I would suggest The Art of Computer Programming from Donald Knuth.

Next to the complex problems it describes, it offers various tasks on very different levels. It even scales their hardness between 10 (trivial task) and 50 (currently unsolved problems until now).
> 1 votes

---
Tags: books
---


# Question
Title: Equivalence of two context free grammars [for the given example]
I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck:

**G1:**

* S-\>e|aB|bA
* B-\>bS|aBB
* A-\>aS|bAA

**G2:**

* S-\>e|aSb|bSa|SS

I tried to apply Arden's rule in the first grammar, to variables A and B, but I think it might be bringing me to a loop since the productions are right-recursive. I'm not really good at manipulating grammars so I don't know how to proceed in the proof.

Also, the exercise has a second question:

Show that all the words generated by G1 have even length.

I thought that if I can demonstrate that G1=G2, it is easier to conclude the proof using G2, and in fact that is something I was able to do, but I miss the fundamental equivalence so as for now I only showed the property for G2...

# Answer
> 4 votes
Both grammars generate the language of words having an equal number of a's and b's. Here are some hints on how to prove that.

**Grammar $G\_1$:** Prove by induction on derivation length that

1. Every word generated by $S$ has an equal number of a's and b's.
2. Every word generated by $A$ has one more a's than b's.
3. Every word generated by $B$ has one more b's than a's.

This shows that every word generated by $G\_1$ has an equal number of a's and b's. For the other direction, prove by induction on word length that

1. Every word having an equal number of a's and b's can be generated by $S$.
2. Every word having one more a's than b's can be generated by $A$.
3. Every word having one more b's than a's can be generated by $B$.

This part is more complicated, though the different cases you have to consider follow closely the rules of the grammar.

**Grammar $G\_2$:** Easy induction on derivation length shows that every word generated by $S$ has an equal number of a's and b's. For the other direction, prove by induction on the length of the word that every word which has an equal number of a's and b's can be generated by $S$, as follows.

Given a word $w$, consider the walk generated by $w$ starting at the origin in which $a$ corresponds to a step up and to the right and $b$ corresponds to a step down and to the right. The walk ends on the X axis (since the number of a's and b's is equal). Let $x$ be the prefix of $w$ corresponding to the first time in which $w$ reaches the X axis (after the empty prefix), and write $w = xy$. If $y$ is empty then $x$ must start and end with different letters, so the one of the productions $S\to aSb|bSa$ can be used, and otherwise the production $S\to SS$ can be used.

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


title: What's wrong with this LL(1) grammar?

text:
# Question
Title: What's wrong with this LL(1) grammar?
I am trying to build a LL(1) parse table for the following grammar:

```
S -> L
L -> L : L
L -> id R
R -> ( L )
R -> ( )
R -> Epsilon

```

There are two problems here. First, the `L` rules are a left recursion and the `R` rules have `(` as the same prefix.

So I modified the Grammar to this one:

```
S -> L
L -> id R X
X -> : L X
X -> Epsilon
R -> ( P
R -> Epsilon
P -> L )
P -> )

```

I then checked the grammar with the JFLAP Tool and it says that my grammar is not LL(1). But I just don't see the problem.

Can somebody help me out here?

# Answer
Your original grammar is ambiguous:

```
L → L : L
L → id R

```

Suppose we have `id : id : id`. (For simplicity, I'm just letting `R` derive the empty string, but any valid derivation of the `R`s would end up with the same ambiguity.) That needs to be derived from `S → L → L<sub>1</sub> : L<sub>2</sub>`, but from there, either `L<sub>1</sub>` or `L<sub>2</sub>` can derive `L : L`. In effect, the two cases correspond to `:` associating to the left or associating to the right, but with longer sequences of `:`-separated `id R` clauses, the number of possible parses increases exponentially.

Your rewrite does not eliminate this ambiguity, it just makes it harder to see.

In short, you need to decide how `:` associates. It probably makes most sense for it to associate to the left, but an LL grammar really only handles right-association. (That's not a huge problem since you can reassociate the AST easily enough, but with an LR parser generator you wouldn't have to do any of this.) If we rewrite `L` as right-associative, we automatically eliminate the left-recursion problem:

```
S  → L
L  → L'
L  → L' : L
L' → id R

```

(Really, `L'` is not very useful in this case; it would have been almost as simple to write `L → id R | id R L`. But in either case, you end up needing to factor out the common prefix.)
> 3 votes

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


# Question
Title: Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ using a computer program?
Chapter 7 of The Haskell Road to Logic Math and Programming discusses induction and recursion.

Haskell is strongly typed and we can define the natural numbers

```
data Natural = Z | S Natural
deriving (Eq, Show)

```

and we can try to construct addition

```
plus m Z = m
plus m (S n) = S (plus m n)

```

Can we write a program that **proves** that addition is associative $(a+b)+c = a+(b+c)$?
Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$?

---

Is it possible to write a program (e.g. in Haskell) that proves the equivalence of two other programs?

> Model-checking a general purpose language is neigh impossible since models must be domain specific to be practical. Due to Gödel's Incompleteness Theorem, there simply is **no method for automatically finding proofs** in a sufficiently expressive logic.
>
> This means that you have to **write proofs yourself**, which raises the question of whether the effort is worth the time spent. Of course, the effort creates something very valuable, namely the assurance that your program is correct. The question is not whether this is a must-have, but whether the time spent is too great a cost. The thing about proofs is that while you may have an **"intuitive" understanding that your program is correct**, it is often very **difficult to formalize this understanding as a proof**.

---

This blog says associativity and other simple statements can be proven in Haskell using the Curry-Howard correspondence. Not entirely sure what that is.

https://jeltsch.wordpress.com/2012/04/30/dependently-typed-programming-and-theorem-proving-in-haskell/

```
assoc :: Nat nat1                                          ->
         Nat nat2                                          ->
         Nat nat3                                          ->
         (nat1 :+ nat2) :+ nat3 :== nat1 :+ (nat2 :+ nat3)
assoc Zero        nat2 nat3 = Refl
assoc (Succ nat1) nat2 nat3 = case assoc nat1 nat2 nat3 of
                                  Refl -> Refl

```

The program compiles and therefore the proof works.

---

## Apologia

I am an experience mathematicians, but I am new to how programmers and CS people think about proofs and theorem-proving. So please excuse me if I confuse one branch of math for the other.

# Answer
> 8 votes
In order with the explicit questions:

1. Yes
2. Yes
3. No

To answer the question I think you're attempting to ask, we can prove many things using type checking, but not everything. What does this have to do with programs? That's what the Curry-Howard correspondence tells us. The Curry-Howard correspondence is a relationship between logic and computational models. The informal version is "proofs and programs and programs are proofs". While the specifics are far too much to detail here, the rough idea is that a function (read program) that takes an input of type $A$ and produces an output of type $B$ is a proof that $A \rightarrow B$ (and yes the funtion type arrow maps to the logical implication arrow).

Why can't we do everything? The good old halting problem. Some things we just can't check. Even worse, in practice, we're often limited to things we already *know* we can check, i.e. programs that are of a subclass that we know always halt.

Just to give a more complicated example, I've written a proof/program for $1+\ldots n = \frac{n\cdot(n+1)}{2}$ in Coq. Coq is a bit different to Haskell, but the idea should be fairly apparent. In this case, Coq has the advantage that it's explicitly built for theorem proving, so we can get a "proof-like" version and a "program-like" version. The proof can only complete if all the types match correctly - i.e. if we can specify a way to get from the input type to the output type, in the normal type checking sense. To avoid using division, I've rephrased the lemma.

The proof-like version:

```
Fixpoint sum (n : nat) : nat :=
match n with
| 0 => 0
| S n' => n + sum n'
end.

Lemma sum_closed_form (n : nat) : 2 * sum n = n * (n + 1).
Proof.
  induction n.
  reflexivity.
  assert (Step: sum (S n) = S n + sum n).
    reflexivity.
  rewrite Step.
  rewrite mult_plus_distr_l.
  rewrite IHn.
  assert (Id : S n = n + 1).
    omega.
  rewrite Id.
  repeat rewrite mult_plus_distr_l.
  repeat rewrite mult_plus_distr_r.
  omega.
Qed.

```

So apart from the individual steps being black boxes, it's fairly clear that this looks a lot like a normal proof - it is in fact an induction, and all the mystery black boxes are in fact just *other* proofs that allow us to take some input type to another. One of the key steps in understanding how this works is to look closely at statement of the lemma: `Lemma sum_closed_form (n : nat) : 2 * sum n = n * (n + 1).`

Notice that it looks a bit like a function declaration, it takes a parameter of type `nat`, and produces an output of *type* `2 * sum n = n * (n + 1)`. That is in fact what it is, so in this form we can see the proof bit, and get an idea of the function bit - i.e. the proof is in fact a program. More explicitly, it is *this* program:

```
sum_closed_form =
fun n : nat =>
nat_ind (fun n0 : nat => 2 * sum n0 = n0 * (n0 + 1)) eq_refl
(fun (n0 : nat) (IHn : 2 * sum n0 = n0 * (n0 + 1)) =>
(fun Step : sum (S n0) = S n0 + sum n0 =>
eq_ind_r (fun n1 : nat => 2 * n1 = S n0 * (S n0 + 1))
(eq_ind_r (fun n1 : nat => n1 = S n0 * (S n0 + 1))
(eq_ind_r (fun n1 : nat => 2 * S n0 + n1 = S n0 * (S n0 + 1))
((fun Id : S n0 = n0 + 1 => eq_ind_r
(fun n1 : nat => 2 * n1 + n0 * (n0 + 1) = n1 * (n1 + 1))
(eq_ind_r (fun n1 : nat =>
n1 + n0 * (n0 + 1) = (n0 + 1) * (n0 + 1 + 1))
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + n1 = (n0 + 1) * (n0 + 1 + 1))
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n1)
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n1 + (n0 + 1) * 1)
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n1 + (n0 + 1) * 1 + (n0 + 1) * 1)
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n0 * n0 + 1 * n0 + n1 + n1)
(Decidable.dec_not_not
(2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n0 * n0 + 1 * n0 + (n0 * 1 + 1 * 1) +
(n0 * 1 + 1 * 1))
(dec_eq_nat (2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1))
(n0 * n0 + 1 * n0 + (n0 * 1 + 1 * 1) + (n0 * 1 + 1 * 1)))
(fun H : 2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) <> n0 * n0 + 1 * n0 +
(n0 * 1 + 1 * 1) + (n0 * 1 + 1 * 1) =>
(fun (P : Z -> Prop) (H0 : P (Z.of_nat 2 * Z.of_nat (sum n0))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul 2 (sum n0)))
(fun x : Z => x = Z.of_nat (n0 * (n0 + 1)) -> False)
((fun (P : Z -> Prop)
(H0 : P (Z.of_nat n0 * Z.of_nat (n0 + 1))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul n0 (n0 + 1)))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z = x -> False)
((fun (P : Z -> Prop) (H0 : P (Z.of_nat n0 + Z.of_nat 1)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add n0 1))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z =
(Z.of_nat n0 * x)%Z -> False)
(fun _ :  (2 * Z.of_nat (..))%Z =
(Z.of_nat n0 * (.. + 1))%Z =>
(fun  (P : Z -> Prop) (H0 : P (..)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add (..) (..)))
(fun x : Z => Z.of_nat (..) = x -> False)
((fun (P : ..) (H0 : ..) => eq_ind_r P H0 (..))
(fun x : Z => .. = ..%Z -> False)
(fun _ : .. => (..) (..) (..) (..)))
(inj_eq  (sum (S n0)) (S n0 + sum n0) Step))))
(inj_eq (2 * sum n0)
(n0 * (n0 + 1)) IHn)))
(mult_plus_distr_r n0 1 1))
(mult_plus_distr_r n0 1 n0))
(mult_plus_distr_l (n0 + 1) n0 1))
(mult_plus_distr_l (n0 + 1) (n0 + 1) 1))
(mult_plus_distr_l n0 n0 1))
(mult_plus_distr_l 2 n0 1)) Id)
(Decidable.dec_not_not (S n0 = n0 + 1)
(dec_eq_nat (S n0) (n0 + 1))
(fun H : S n0 <> n0 + 1 =>
(fun (P : Z -> Prop)
(H0 : P (Z.of_nat 2 * Z.of_nat (sum n0))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul 2 (sum n0)))
(fun x : Z => x = Z.of_nat (n0 * (n0 + 1)) -> False)
((fun (P : Z -> Prop)
(H0 : P (Z.of_nat n0 * Z.of_nat (n0 + 1))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul n0 (n0 + 1)))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z = x -> False)
((fun (P : Z -> Prop)
(H0 : P (Z.of_nat n0 + Z.of_nat 1)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add n0 1))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z = (Z.of_nat n0 * x)%Z -> False)
(fun _ : (2 * Z.of_nat (sum n0))%Z =
(Z.of_nat n0 * (Z.of_nat n0 + 1))%Z =>
(fun (P : Z -> Prop) (H0 : P (Z.of_nat (S n0) + Z.of_nat (sum n0))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add (S n0) (sum n0)))
(fun x : Z => Z.of_nat (sum (S n0)) = x -> False)
((fun (P : Z -> Prop) (H0 : P (Z.succ (Z.of_nat n0))) =>
eq_ind_r P H0 (Nat2Z.inj_succ n0))
(fun x : Z => Z.of_nat (sum (S n0)) = (x + Z.of_nat (sum n0))%Z -> False)
(fun _ : Z.of_nat (sum (S n0)) =
(Z.succ (Z.of_nat n0) + Z.of_nat (sum n0))%Z =>
(fun (P : Z -> Prop) (H0 : P (Z.succ (Z.of_nat n0))) =>
eq_ind_r P H0 (Nat2Z.inj_succ n0))
(fun x : Z => Zne x (Z.of_nat (n0 + 1)) -> False)
((fun (P : Z -> Prop) (H0 : P (Z.of_nat n0 + Z.of_nat 1)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add n0 1))
(fun x : Z => Zne (Z.succ (Z.of_nat n0)) x -> False)
(fun H0 : Zne (Z.succ (Z.of_nat n0))
(Z.of_nat n0 + 1) => ex_ind (fun (Zvar29 : Z)
(Omega75 : Z.of_nat n0 = Zvar29 /\ (0 <= Zvar29 * 1 + 0)%Z) =>
and_ind (fun (Omega66 : Z.of_nat n0 = Zvar29)
(_ : (0 <= Zvar29 * 1 + 0)%Z) =>
ex_ind (fun (Zvar30 : Z) (Omega74 : .. /\ ..%Z) =>
and_ind (.. => ..) Omega74) (intro_Z (sum (..)))) Omega75)
(intro_Z n0))) (inj_neq (S n0) (n0 + 1) H)))
(inj_eq (sum (S n0)) (S n0 + sum n0) Step))))
(inj_eq (2 * sum n0) (n0 * (n0 + 1)) IHn)))) IHn)
(mult_plus_distr_l 2 (S n0) (sum n0))) Step) eq_refl) n
: forall n : nat, 2 * sum n = n * (n + 1)

```

To give a shorter example, the associativity of addition can be proved like so:

```
Lemma add_assoc (n m p : nat) : n + (m + p) = (n + m) + p.
Proof.
  induction n.
  reflexivity.
  simpl. rewrite IHn.
  reflexivity.
Qed.

```

The associated function is:

```
add_assoc =
fun n m p : nat =>
nat_ind (fun n0 : nat => n0 + (m + p) = n0 + m + p) eq_refl
  (fun (n0 : nat) (IHn : n0 + (m + p) = n0 + m + p) =>
   eq_ind_r (fun n1 : nat => S n1 = S (n0 + m + p)) eq_refl IHn) n
     : forall n m p : nat, n + (m + p) = n + m + p

```

# Answer
> 2 votes
The sort of question you are asking falls under at least two possible topics. One is theorem proving and the other symbolic computation. Regarding the second topic, I highly recommend the book "A = B" by Petkovšek, Wilf and Zeilberger, which treats algorithms for symbolic computation. In there you can read about Gosper's summation algorithm which computes closed forms of hypergeometric sums.

The point is that, once the algorithms is implemented and the implementation is proved correct, then we know that the algorithm produces correct answers so running it amounts to producing a proof.

Also, in the case of finding closed forms of sums it is often easy to check that an answer is correct: to verify that $\sum\_i a\_i = S\_i$ verify that $S\_{i+1} - S\_i = a\_i$, often simple algebraic manipulations suffice.

---
Tags: type-theory, functional-programming, type-checking, proof-assistants
---


# Question
Title: Given two total Turing machines, is it undecidable problem to detect whether they give the same output on all inputs?
See title. And by all inputs I mean providing the functions with the same input and checking whether they give the same output for each case.

**EDIT**

If it can be reduced to Halting problem, then how?

**EDIT 2**

@Ariel's answer doesn't satisfy me since given the concrete machine $T$ and input $x$ he states that there exists a computable function that is equal to $1$ everywhere except $x$ and indicates whether $T$ terminates on $x$, on $x$. *Note: there is no algorithm for building such a function since it would answer the Halting problem immediately.* He proceeds with noting that if that function coincides (by required in the question decision algorithm) with the constant $1$ (as a function) then $T$ terminates on $x$. Otherwise - it does not. So, Halting problem solved, a contradiction. *Except there is no.* We didn't build an *algorithm* for building that function ($f\_{M\_x}$, if I understood correctly), so we didn't build an algorithm for deciding whether arbitrary $T$ terminates on given $x$. @Ariel, correct me, if I'm wrong...

**EDIT 3** @Ariel was correct!!! Since I did not mentioned that required decider algorithm must only accept not descriptions of computable functions but Turing machines implementing them, his answer was fully correct. Now the thing - I just require for seeked algorithm to process only pairs of always halting Turing machines and testing them for equality on every input. @Ariel, I'm really sorry :-(

**EDIT 4** And if somebody still wishes to answer this question, Rice's theorem for partial functions does not help, since I don't require the decider beeing searched for to be such over all partial function, only over total function, i.e. it may not halt on arbitrary not-always-halting Turing machine.

# Answer
The problem

> Do two *halting* Turing machines accept the same language (or compute the same "function")?

is undecidable.

Let $M$ be an arbitrary Turing machine. Let $M'$ be a Turing machine that on input $x$, simulates $M$ (on some predefined input) for $|x|$ steps and accepts if (and only if) $M$ halts within $|x|$ steps (or, if you want to go with a TM computing a function, returns $1$ if $M$ halts within $|x|$ steps and $0$ otherwise).

If $M$ doesn't halt then $M'$ accepts the empty language (or, computes the function $f(x)=0$). If $M$ does halt then the language $M'$ accepts is non-empty (or, the function is non-constant).

This gives a reduction from the Halting problem to the problem of detecting equality, since we just need to ask whether $M'$ is equal to the machine accepting the empty language (or, the machine computing the function $f(x)=0$).

This avoids all the issues of the function not being total or being unable to construct the function explicitly.
> 9 votes

# Answer
Representing computable functions as Turing machines, the language your interested in is $\left\\{ \left( \langle M\_1\rangle,\langle M\_2\rangle \right)| L(M\_1)=L(M\_2) \right\\}$. As everyone here mentioned it is undecidable. A simple example for a reduction from the halting problem would be $\left(\langle M \rangle,x\right)\rightarrow \left(\langle M\_x \rangle,\langle M\_{\Sigma^\*} \rangle \right)$, where $M\_x$ is the machine accepting all inputs different than $x$, and on $x$ simulates $M$, if $M$ halts $M\_x$ accepts. $M\_{\Sigma^\*}$ is a machine that accepts all inputs. It is easy to see why this is a reduction from the halting problem to your desired language.

As Giulia Frascaria mentioned, this problem might be decidable for weaker models (e.g. finite automata).

**Edit:** To avoid long discussion in the comments ill add it here. For any Turing machine $M$, it's characteristic function $f\_M(x)=1\iff x\in L(M)$ is total, If $M$ does not halt on $x$ then $x\notin L(M)$ and $f\_M(x)=0$. Why, in this case the function $f\_{M\_x}=1 \iff x\in L(M\_x)$ is computable? Look at two machines: they accept all inputs other then $x$, while one of them accepts $x$ and the other doesn't. Clearly one of these machines computes $f\_{M\_x}$, this argument isn't constructive, i didn't build the machine computing $f\_{M\_x}$, but iv'e shown it exists.

**Edit 2:** Think about what would a valid reduction between the halting problem and the problem you stated should look. Given a pair $\left(\langle M \rangle,x\right)$ i need to describe two total computable functions that agree on all inputs iff $M$ halts on $x$. By describe, i mean i should only have a way to encode them (do not confuse with the term computing or anything else). I have described $f\_{M\_x}$ in terms of $M$ and $x$. It is a well defined total function. Specifically, it outputs $1$ on all inputs other than $x$, and on $x$ outputs 1 iff $M$ halts on $x$. I did not say the machine $M\_x$ computes it, i simply encoded(described) it using $M$ and $x$. Then i claimed that the function $f\_{M\_x}$ is also computable. So given a pair $\left(\langle M \rangle,x\right)$ i was able to output a pair of functions (and by outputing a function, i do not mean outputing the machine computing it, only outputing some description of that function) which agree on all inputs iff $M$ halts on $x$.
> 4 votes

# Answer
I would say that **in general** it is undecidable: in fact, this problem can be reduced to the Halting problem, which states that it is not decidable whether a given turing machine (read "function") terminates on an input x.

This does not mean that you can't find a solution to specific given problems. For example, if it is possible to write these two functions as finite state automata, it is then decidable whether they generate the same language (or output).
> 2 votes

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


# Question
Title: Are there automatic transformation of grammar algorithms?
From time to time you can write a grammar that creates shift/reduce conflict (for example) but after reading the grammar you notice that if you rewrite the productions the conflict will go away, despite the fact that the rewritten grammar is obviously equivalent and accepts exactly the same language.

Are there some automatic transformations of the grammar to avoid conflict? Something (just an analogy) as left recursion elimination in LL parsers?

For example, here is a trivial example of two grammars:

```
...
deco_symbol -> anon_symbol | named_symbol;
...

```

and

```
...
symbol -> anon_symbol | named_symbol;
deco_symbol -> symbol;
...

```

For LR(1) parser such indirection can be crucial and second form can introduce conflicts (it did in real life).

Since I asked this question I wrote automatic removal of identity production and it helped, so this would be the first type of transformation I know it is helpful. Now I am testing wrapper production removal and empty productions as well.

# Answer
If you are willing to implement an **lr(k)** algorithm then yes, there are transformations that you should do in order to obtain a correct parser: first of all, you have to build an augmented grammar adding production **S'-\>S**, making S' the new axiom. This is actually not always necessary, but it allows you have a standardized procedure for all the productions so let's pretend it is for now. After that, you should also eliminate useless symbols from the grammar with the apposite algorithm.

If you execute lr(k) parsing under these hypothesis for the grammar, you should not have conflicts.

----- EDIT ----- I hope this will be of some help :)

An lr(k) parser builds a parsing table over a given grammar G. These parsers are able to recognize words generated from grammars which are deterministic context free and in lr(k) form. If a conflict occurs, then the language generated by the given grammar cannot be parsed using that table and **the grammar is not a lr(k)** grammar.

However, one can show that a language L is deterministic context free iff there exists k \>= 1 such that L is generated by an lr(k) grammar.

I might be wrong but what I concluded from these notions is that if the grammar is lr(k) no conflicts should occur, and one of the definitions of a lr(k) grammar is:

The definition of lr(k) grammars states that the axiom must not occurr on the right hand side of any production, and should this is not be respected one needs contruct the augmented grammar first, using S' as new axiom and adding the only production S'-\>S. For further definitions of lr(k) grammars or a clarification of what I wrote, I advise to read *The Theory of Parsing, Translation and Compiling* (around page 370), since I fear I don't have the preparation to answer all questions.
> -2 votes

---
Tags: parsers, lr-k
---


# Question
Title: Turning a simple polygon with holes into exterior-bounded only
I am converting cartographic objects, which have an exterior boundary (simple polygon) and zero or more interior boundaries (also simple), into a less sophisticated format that specifies exterior boundary only. To overcome this restriction, I plan to “cut through the body of the shape” — joining a pair of nodes of exterior and interior boundary (see figure, left), thus creating a zero-width way into the shape's former interior space that will then technically become exterior (see figure, right).

So the question is: **which nodes to join?** (Not that it's *unacceptable* to create new nodes in suitable locations, but *undesirable*.) An obvious and ideal choice would be the two nodes most close to each other; moreover, I suppose that those would automatically constitute a valid solution — i. e. the new segments won't intersect any existing one. Consequently, the question becomes: **how to find the closest node pair?**

Googling on this topic yields many results for similar questions which vary in degree of “similarity”, complexity of understanding the algorithm and computational complexity. But most importantly, as far as I noticed, they vary in applicability to input data, — that is, some are designed for convex polygons only, others fail on “overlapping” polygons (I suppose that includes my case, too). So I decided to ask: **which algorithms are optimal or at least suitable for my particular task?**

# Answer
> 4 votes
The closest vertices between the inner and outer polygons do *not* necessarily produce a valid solution as shown in the following figure:

You just need to find a pair of vertices between the inner and outer polygons whose corresponding edge does not intersect either polygon. Search for vertices $u$ and $v$ from the inner and outer polygons such that the edge $(u,v)$ does *not* cross any other edge (some care needs to be taken that you don't slip between two edges as shown on the right above -- choosing the closer vertex avoids this problem).

A straight forward approach would scan all such $u,$ $v,$ and all edges resulting in $O(n^3)$ time in the worst case -- in practice you'll find a solution fairly quickly. This can be sped up by placing all the vertices in a BSP tree whose half-spaces are defined by the polygon edges -- then you only considering vertices $v$ in the same half-space as $u.$

# Answer
> 2 votes
For two sets there is an $O(n \log n)$ (where $n$ is the total number of points) algorithm found by Godfried T. TOUSSAINT and Binay K. BHATTACHARYA in Optimal algorithms for computing the distance between two finite planar sets.

They prove that the edge you are looking for is in the minimum spanning tree and there is algorithms to compute this tree in $O(n \log n)$ in the plane. Then you just have to explore the tree in linear time to find the edge.

It seems to me that this algorithm can be generalized when you have $k$ interiors boundaries : all the $k$ edges you are looking for ($k$ because it's a tree beetween $k+1$ nodes : the exterior and the $k$ interiors) are in the minimum spanning tree. The proof is almost the same that for 2. Thus the running time is still $O(n \log n)$ in worst case.

Since neither your polygons are convex nor their coordinates are integers (?), I think you can't have a better result.

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


# Question
Title: How to construct a grammar that generates language L?
I'm in a Formal languages class and have a grammar quiz coming up. I'm assuming something like this will appear.

Consider the alphabet $\Sigma$ = {a, b, c}. Construct a grammar that generates the language $L = \\{bab^nabc^na^p \mid n ≥ 0, p ≥ 1\\}$. Assume that the start variable is $S$.

# Answer
One possible grammar is: $G = (N, \Sigma, P, S)$, where

$N = \\{S,U,V\\}$

$\Sigma = \\{a,b,c\\}$

$P = \\{ S \to baUV, U \to ab|bUc, V \to a|aV \\}$

The key observation here is breaking $bab^nabc^na^p$ into 3 parts, $ba$, $b^nabc^n$, and $a^p$, one fixed, one growing bidirectionally, and one simple repeatition. Express the growing patterns first, then merge them along with the fixed parts.
> 2 votes

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


# Question
Title: Maximum bipartite matching when some nodes must be matched
Consider the problem of finding a maximum cardinality bipartite matching under the additional condition that some set $S$ of nodes (all lying on the same side of the bipartition) must be matched.

Can this problem be reduced to (ordinary) bipartite matching? Bipartite matching can be solved in $O(m \sqrt{n})$ by Hopcroft Karp or $O(n^{\omega})$ where $\omega$ is the exponent of matrix multiplication due to a recent result, or $\widetilde{O}(m^{10/7})$ in terms of the number of edges m. Do these running times carry over to this problem? I think Hopcroft-Karp can produce the same running time with some modifications, but am not sure about the others; so I'm wondering if a simple reduction to matching exists -- this would allow one to bypass an analysis of the above papers.

# Answer
Assume the maximum matching problem is $U-V$ matching, and $S\subset U$.

1. Find maximum $S-V$ matching. If the result equals $|S|$, then it is a feasible matching in original $U-V$ matching problem. Othewise, no matching meets the requirement.
2. Using the feasible matching got in previous step as basis, improve it by augmentation, thus computing maximum $U-V$ matching.

Since an augmenting path never turns a matched vertex into unmatched vertex, the maximum matching found by above algorithm meets the requirement.

Using Hopcroft Karp algorithm, the complexity is $O(m\sqrt{n})$.

I don't know if the $O(n^{\omega})$ or $\tilde{O}(m^{10/7})$ algorithm works. But basically any maximum matching algorithm that based on augmentation works. And for those unit capacity network flow algorithms, it also works as long as it accepts an initial feasible flow and arguments along it, taking the lower capacity bound into account. (ie. never augment back through edges $s \to x (x\in S)$)
> 2 votes

# Answer
It can be done in $\widetilde{O}(m^{10/7})$ time, by reducing to network flow.

As a warmup, suppose we know the max matching you're seeking has size $k$. Then let's build a flow graph by adding three nodes to your original graph: we'll add a source node $s$, a second node $s'$, and a sink node $t$. Then, we'll add some edges with unit capacity: $k-|S|$ parallel edges $s \to s'$, an edge $s \to v$ for each node $v \in S$, an edge $s' \to w$ for each node $w$ on the left-hand side such that $w\notin S$, and an edge $x\to t$ for each node $x$ on the right-hand side. Now find the maximum flow in this graph. This will give you the matching you want: your matching corresponds to a legal flow of capacity $k$, and any legal flow of capacity $k$ corresponds to a matching of size $k$ that matches every vertex in $S$ (since the only way to get $k$ flow out of $s$ is to saturate every edge out of $s$, and in particular to send one unit of flow to each vertex in $S$; that flow has to go somewhere, so that means every vertex of $S$ is matched).

So, if we knew $k$, this would find the matching you want. Also, the running time would be $\widetilde{O}(m^{10/7})$, as Madry's algorithm can compute maximum flows in that running time.

Of course, in real life we don't know $k$ a priori. However, we can use binary search to find it. This increases the running time by a $\lg(n)$ factor, which is absorbed in the $\widetilde{O}$ running time; the total running time remains $\widetilde{O}(m^{10/7})$.

I realize this doesn't answer whether $O(m \sqrt{n})$ or $O(n^\omega)$ is attainable. It seems possible that the same considerations which lead to a $O(m \sqrt{n})$ time for computing maximum flows in bipartite matching instances might also lead to a $O(m \sqrt{n})$ time for the kind of graph I outlined above, but I don't know whether this is indeed the case or not.
> 0 votes

---
Tags: algorithms, graphs, bipartite-matching
---


# Question
Title: augmenting bst - is there exist pair (a,b) of numbers such that |b-a| = d?
How to check if exist pair $(a,b)$ of numbers in BST such that $|a-b| = d$, where $d$ is given.
Example:
contain of tree: $1, 4, 5, 3, 8, 45, 532$
$d=5$,
answer: $yes$, there is pair $(5,8)$
$d=52$
answer: $no$.

I can solve it when number are in array - then I sort them, and in linear time I can find that pair. Neverthelress I can't idea how to augment BST in this task.
Can you give me a hint ?

# Answer
> 2 votes
By "in linear time I can find that pair" I assume you are using two-pointer technique, that using 2 pointers to traversal the array, trying to reduce the gap to the target by advancing one of the pointer.

An in-order traversal of BST outputs all values in order in linear time. So you can apply your linear-time algorithm similarly on BST, only the pointers advancing to the in-order next node.

---
Tags: binary-trees
---


# Question
Title: Prove or disprove that $NL$ is closed under polynomial many-one reductions
> If $B \in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A \in NL$.
> Prove that the above claim is correct, incorrect, or equivalent to an open question.

Trying to solve this, I was pretty sure that the statement is either incorrect, or at least equivalent to an open question. My reasoning was that the statement is correct if the reduction is promised to be a **log-space reduction** (uses only $log \ n$ space). Removing this demand seems to be too much, but I wasn't able to prove this.

I was then told that this statement is equivalent to the open question $NL = P$. I thought of this, and tried proving that if the statement is correct, then one can define a Karp reduction from any $L \in P$ to a language in $NL$, therefore proving $L \in NL$ and $P \subseteq NL$. However I couldn't find such a reduction. The only reduction I could think of that could help would be to transform the operations of a deterministic polynomial Turing machine $M\_L$ to a configurations graph (a directed graph with an edge $(u,v)$ iff there exist two consecutive configurations $u, v$ in $M\_L$. However, this reduction would take exponential $2^{p(n)}$ time, and not polynomial.

Any contribution would be appreciated.

# Answer
> 4 votes
Let's prove the two directions separately. Suppose first that $\mathsf{NL}=\mathsf{P}$. In order to prove the statement, suppose that $B \in \mathsf{NL}$ and that there is a polytime many-one reduction from $A$ to $B$. Since $\mathsf{P}$ is closed under polytime many-one reductions and $B \in \mathsf{NL} = \mathsf{P}$, clearly $A \in \mathsf{P} = \mathsf{NL}$, proving the statement.

Suppose next that the statement is correct. Let $B$ be any non-trivial language in $\mathsf{NL}$ (for example, $B = \\{\epsilon\\}$), and let $A \in \mathsf{P}$ be arbitrary. Since $A \in \mathsf{P}$ there is a polytime function $f$ computing it. We can easily modify $f$ to a polytime reduction from $A$ to $B$ by fixing some YES instance and NO instance in $B$ (here we need that $B$ be non-trivial). The statement implies that $A \in \mathsf{NL}$. Since $A$ was arbitrary, we deduce that $\mathsf{P} \subseteq \mathsf{NL}$ and so $\mathsf{NL} = \mathsf{P}$.

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


# Question
Title: Finding the k-th smallest rational number efficiently
Consider the following set:

$S := \left\\{\frac{a}{b} \colon a \in \\{1,\ldots,A\\}, b \in \\{1,\ldots,B\\} \right\\}$

$S$ is the set of all rational numbers that can be represented by two integers $a$ and $b$ that are bounded by $A \geq 1$ and $B \geq 1$. For the sake of simplicity, we can also think of $S$ as a multiset such that the number of elements in $S$ is given by $A \cdot B$.

Do you see any possibility how to find the $k$-th smallest number in $S$ in time $\mathcal{O}(\log (A \cdot B))$ ?

Clearly, the smallest number if given by $\frac{1}{B}$ and, as long as $B \geq 2$, the second smallest number is given by $\frac{1}{B-1}$. But then things are getting interesting...

# Answer
It is perhaps more natural to consider the *set* $S$. Let us further consider the case $A = B = n$ and the set $S \cap \[0,1\] = \mathcal{F}\_n$, the $n$th Farey sequence; if we know $|\mathcal{F}\_n|$ and can solve the problem for $\mathcal{F}\_n$ then we can also solve it for the entire $S$. The set $\mathcal{F}\_n$ has size $\Theta(n^2)$.

The fastest algorithm known for finding order statistics (i.e., the $k$th smallest element) in $\mathcal{F}\_n$, due to Patrășcu and Pawlewicz, runs in time $\tilde{O}(n^{2/3})$. This is much slower than the complexity you're interested in, $O(\log n)$.

It is possible that considering the multiset instead of the set makes the problem easier.
> 3 votes

# Answer
I don't see how to achieve what you want for arbitrary $k$. However, for small $k$, it is possible to solve this problem efficiently. In particular, it's possible to find the $k$th smallest element in $O(k \log k)$ time.

Use a priority queue (min-heap). Initially, insert $1/B$ into the priority queue. Then, do the following $k$ times:

* Remove the smallest element from the priority queue, say $a/b$. Output $a/b$, and then insert both $(a+1)/b$ and $1/(b-1)$ into the priority queue (assuming they're in $S$).

This does at most $2k$ insertions into the priority queue and $k$ delete-mins; also, the size of the priority queue is $O(k)$, so the total running time is $O(k \log k)$. This answer treats $S$ as a set rather than as a multiset.
> 2 votes

---
Tags: efficiency, number-theory, finite-sets
---


title: compilers and their inheritance

text:
# Question
Title: compilers and their inheritance
If compilers have an inheritance of compilers(for example, a compiler needs to be compiled by another compiler, and that compiler needs to be compiled by another compiler, and so on) then if there is an inefficiency in one of the compilers up the line of inheritance(like the compiler's compiler's compiler's compiler), would the current compiler inherit that inefficiency?

# Answer
> 5 votes
The inefficiency in compiler would make the next compiler work slower, but the result of work will be the same. So in next compiler you wouldn't even know about that inefficiency.

# Answer
> 2 votes
No, because compiler runtime is irrelevant to quality of produced code.
It would not propagate.

It will only once slow down compiling time in flawed compiler, there is no possibility of making next compiler slower (it will be essentially the same one).

Let me give you example:
By analogy you have one recipe, chain of writters and one cook.
Writters are passing recipe one to another and their responsibility is to change words according to given dictionary.
None of then is making mistakes. But you can switch one of writters with slower writing one.
The cook gets the same recipe always, the only difference is time, and delay is caused by this inefficient writter (not by successor).

You should read this thread: C compiler, there are some awesome answers related to your question.

# Answer
> 2 votes
A chain of compilers, as you describe in your question can be illustrated by the T-diagram notation. This is usually used to illustrate the mechanisms of bootstrapping a compiler compiling itself. It is also used to explain a cross compiler, and porting a compiler.

The notation is also valuable in explaining how optimisation improvements can be incorporated into a compiler and how bug fixes propagate in those compilers.

Early in the development of such compilers, such as a Pascal compiler in Pascal, or a **C** compiler in **C** the question of how one could fix a bug in the compiler that caused incorrect code to be generated. In that case, surely, the compiler itself would then be faulty. How could such a faulty program be used to remove a fault in itself!

Similarly, if an optimisation is added to the generated code how can we ensure that compiler itself utilises that optimisation. These questions are exactly the same as what you asked about: the inheritance of inefficiency. The inheritance of efficiency and the inheritance of faults are the very same question.

The technique is illustrated below; to ensure that the improvement is properly incorporated (or the inefficiency removed) the binary and source for the compilers can be compared. They must be bit-for-bit identical. I have used this method myself to ensure that no faults are passed on, often by performing this process in a loop, re-generating the compiler. If it does not change it demonstrates that inefficiencies are not being propagated.

```
   .--------------------------.          .--------------------------.
   |        Compiler 1        |          |      Compiler 3          |
   | Language -------> M-code |          | Language -------> M-code |
   |                          |          |                          |
   `-------.          .--------------------------.          .-------'
           |          |       Compiler 2         |          |
           | Language | Language  ------> M-code |  M-code  |
           |          |                          |          |
           `------------------.          .------------------'
                              |          |                ^
                              |  M-code  |    should be   |
                              |          |<-- identical --'
                              `----------'

Figure 3.4  A self-compiling compiler must be self-consistent

```

(Diagram Source)

# Answer
> 0 votes
Today nobody would do this, but the very first C compiler compiled a limited subset of C, and was written in its own dialect of C. Then this compiler was translated into assembly language by hand, and the result was then used to compile its own code. The result was then used to compile itself again, the result should be the same as the first round (as a correctness check).

Once you have a capable compiler, you can write a more complete compiler (or one for a different language, or one which generates better code, or...) by using this first compiler to compile them.

---
Tags: compilers
---


# Question
Title: Can we prove mathematical induction statements in Lisp?
My previous question Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ using a computer program? has a problem that it tries to cover too much ground. Here is a related question motivated by the comments.

In Lisp and certain other languages code and data are put on equal footing. **Lisp** is certainly strong enough to define abstractions, lazy evaluation and define types. I wonder if it is strong enough to prove simple statements about itself.

Important here... **I only intend to prove specific theorems**. It is quite clear we can't prove all theorems using any programming language.

Let's try: $1 + 2 + 3 + 4 + \dots + n = \frac{n(n+1)}{2}$. Then we statement:

$$ P(1): 1 = \frac{1(1+1)}{2} \text{ and }P(n):1 + 2 + 3 + 4 + \dots + n = \tfrac{n(n+1)}{2} $$

We need to show that $\boxed{P(n) \to P(n+1)}$ this type of statement seems simple enough that we could try to verify it within Lisp itself. I could be wrong.

This couldn't be so hard. We have two functions:

* $F\_1(n) = 1 + 2 + 3 + \dots + n$ and $F\_2(n) = \frac{n(n+1)}{2}$
* In both cases there is some type of recursion $F(n+1) = (n+1) + F(n)$
* Then we could show the implication $F\_1(n) = F\_2(n) \to F\_1(n+1) = F\_2(n+1)$

The induction step should be expressible as a recursion. If the program itself can't prove induction statements, perhaps it can just summarize them in some kind of way.

---

In Haskell, the strong type means that once it compiles you have proven the types agree. This may not be as strong as proving other types of theorems.

I am not an expert in proof-checkers so excuse me if I get the basic concepts wrong.

# Answer
> 6 votes
Let me try to clarify a point that seems to be confusing you: you seem to be conflating 2 related, but different concepts.

* The first is the concept of a **proof system**, which allows you to **specify and prove** theorems about mathematics or computer science. Dependent types are *one* elegant way to do this, where the types are the specification language and the proofs are identified with programs, but this is **not the only way to build a proof system!** Isabelle allows you to specify and prove properties about programs, and is *not* based on dependent types or the Curry-Howard isomorphism/approach. The crucial takeaway is that these systems require the user to supply the proof.
* The second is the notion of **automatic theorem proof systems** (or provers) which take a specification language and **automatically attempt to divine a proof**. This means that ATP systems are *in particular* proof systems, where the user input for proofs is just a click on the "prove" button (actually most ATP systems allow and require a lot more input from the user). This state of affairs is of course quite desirable in theory, as it greatly relieves the burden for the user, and most proof systems integrate *some* capabilities of ATP.

With these clarifications in mind, my first answer is that **Lisp is neither a proof system nor an ATP system**. It is a programming language. As such, it cannot be said to prove *anything* as is. The Lisp language is untyped, so it doesn't even make sense to ask if its type system can be seen as a specification language.

My second answer is that **Haskell is neither a proof system nor an ATP system**. This seems to contradict the answer given to you here, but the point is that the Haskell type system **closely reassembles a dependently typed proof system**, to the extent that "specification-like" types can be given and "proof-like" programs can be written. One important limitation is that **Haskell is not consistent when viewed as a logic**. In particular, $1+1 = 3$ can easily be "proven" in a variety of different ways. Actual proof systems like Agda and Coq, however, can be used to specify and prove things about programs, which themselves can be *extracted* to Haskell programs.

All this being said, there is a very notable ATP system that *can* specify and automatically prove things about (a small subset of) Lisp programs **including your example**: the ACL2 system. Hey, they even have your example in these slides! (They don't give the solution though).

---
Tags: functional-programming, induction, proof-assistants, lisp
---


title: Loops at low level

text:
# Question
Title: Loops at low level
When programming with high level languages like Python or Matlab, it is always better to model the problem such as the solution is some kind of vector or matrix multiplication, to avoid loops. But this vector multiplication will itself take each elements from both arrays and multiply them so basically there must be some loops at some level. Is that the case or is there special methods at assembler level that make multiplications of memory blocks with no loops?

# Answer
When you are using vectorized operations in a high-level language such as Matlab or python, you are not avoiding loops, but rather pushing them from the high-level language (Matlab or python) to a low-level language (C or fortran) which can execute these loops much faster. Loops in Matlab or python are slow for several reasons, the main ones being that these languages are interpreted, that typing is dynamic, and that even basic data types involve a lot of overhead.

Some old supercomputers had a vectorized architecture (for example Crays), but this is no longer the case. Nowadays there are small-scale vectorized instructions which operate on a small number of data points at once (as mentioned in EvilJS's answer), though their use could be rather specialized.

Loop unrolling, mentioned by EvilJS, can be used to cut down the number of conditional jumps, which slow down the execution of the code. The body of the loop is repeated a small number of times, thus reducing the frequency of conditional jumps at the expense of code size (which could be important due to the existence of code caches). Such tricks are better left to the implementors of standard libraries.
> 6 votes

# Answer
Underneath there are normal loops, or vectorized instructions (SIMD instructions where possible).
It is not possible to avoid loops at all - you can unwind them if you know number of iterations in advance, otherwise basically you cannot get rid of them.
For example in Matlab if you want to check yourself - after exporting to C there are normal loops, and for those functions that are not exported - they are using some reduction methods to speed up (which should work, but for some reason Matlab is very slow).

As Yuval Filmus correctly stated, loop unwinding is degrading performance, it was only for educational purpose of avoiding loops, never optimise like this (your compiler probably does better job, or you should exhaustively test the code in case you know better).

Also there are some optimisations under the hood, for example taking some matrix features or some kinds of decompositions, so it is hard to tell what is used at the moment.
So if you try to implement straightforward method it may differ from these languages.

Normal loops should use register to loop counter, sometimes they don't.

Side note, you should use Matlab compiler, this speed ups a lot.
> 3 votes

# Answer
Consider the following simple python3 script:

```
import numpy as np
import numpy.random as npr
import timeit

# Naive implementation of inner product
def inner_product(vec1, vec2) :
    dot = 0
    for ii in range(N) :
        dot += vec1[ii]*vec2[ii]
    return dot

N = 10000
v1 = npr.rand(N)
v2 = npr.rand(N)

# Print v1 dot v2, computed three different ways. There are others.
print (inner_product(v1, v2))
print (sum(v1*v2))
print (np.inner(v1, v2))

# Time those three approaches.
setup="from __main__ import loop_inner_product,v1,v2"
print(timeit.timeit('inner_product(v1, v2)', setup=setup, number=100))

setup="from __main__ import v1,v2"
print(timeit.timeit('sum(v1*v2)', setup=setup, number=100))

setup="from __main__ import np,v1,v2"
print(timeit.timeit('np.inner(v1, v2)', setup=setup, number=100))

```

The first three print statements print the same value; after all they are computing the same thing (to within numerical precision). However, the results of the next three print statements are very, very different.

On my computer,

* `sum(v1*v2)` is three to four times faster than is `inner_product(v1,v2)`.
That's not bad, but it's not that good either.
* `np.inner_product(v1,v2)` is almost 1000 times faster than is `inner_product(v1,v2)`.
Now that's an improvement.

There are a number of things that make `inner_product` so very slow. One of them is the loop itself. Each iteration calls a generator function that creates a new python object that contains the integer. All of those objects need to be garbage collected. Another issue is the indexing. This involves a call to the `numpy.array.__getitem__` function. This function is rather complex; there are lots and lots of ways to slice and dice a numpy array. Compare that to the C equivalent:

```
for (int ii=0, size=v1.size; ii < size; ii++) {
    sum += v1[ii]*v2[ii];
}

```

Here, no new objects are being constantly created and destroyed. No functions are being called over and over again to increment the iterator or to access an element of the array. An optimizing compiler will most likely keep the index, the size, and the sum in registers.

Whenever you find yourself writing a loop in a language such as python or matlab, you should rethink what you're doing. If you rewrite it without a loop and the speedup is only a factor of three or four, you should rethink what you're doing. There's probably a library function implemented in C, C++, or Fortran that does exactly what you want, and that might well result in a speedup of a factor of 1000.
> 3 votes

# Answer
Wrong. You should write your solution (with or without loops) to be as *clear* and *natural* as possible. If it is a bunch of nested loops, so be it. This makes your program/script easier to write, easier to check it is correct, and easier to modify later on when the need arises.

If **after getting it right** you see that it is too slow, *then* you can start worrying about rewriting those parts you *measure* to take up most of the running time for speed. This is a judgement call, your time is much, much more valuable than the computer's.
> 2 votes

---
Tags: loops
---


# Question
Title: Search problem when the effects of actions are not deterministic
The standard search problem studied in AI contains:

* An initial state $A$;
* A final (goal) state $Z$;
* A set of actions that can change the state; each action takes as input a certain state and returns another state.
* A solution to such a problem is a sequence of actions starting at $A$ and ending at $Z$.

I am interested in the following variant:

* Each action can return one of several states; it is not known which state will be returned.
* A solution is a tree in which each path from the root ends at $Z$.

For example: Suppose we start at state $A$ and do the action "ABRA". This action can return state $D$ or state $E$. In state $D$ we can do the action "DAMA" which returns state $Z$; in state $E$ we can do the action "EAGL" which can return either state $Z$ or state $Y$. In state $Y$ we can do the action "YADA" which returns state $Z$.

The motivation here is automatic construction of algorithms. Every solution is an *algorithm* for reaching from $A$ to $Z$. For example, the above solution can be read as the following algorithm:

```
Begin (state=A)
   ABRA
   If D then
      DAMA
      End (state=Z)
   Else If E then
      EAGL
      if Z then
         End (state=Z)
      Else  (state=Y)
         YADA
         End (state=Z)
      End If
   End If
End

```

MY QUESTIONS:

* What are good references that deal with this kind of search problem?
* Are there any usable solvers for solving such problems (similar to e.g. planners or solvers for usual search problems)?

# Answer
> 2 votes
One helpful way to think of this is as a two-party game. When it is Alice's turn, she chooses an action; then, Bob chooses among the possible states that the action could return, and the system transitions to that state. We start at the start state $A$. Alice wins if she eventually reaches the goal state $Z$. Bob is trying to prevent Alice from ever reaching $Z$.

With this viewpoint in mind, there's a straightforward algorithm to determine whether Alice has a strategy to win this game. Let $S$ denote the set of all possible states. If $R \subseteq S$ is a set of states, define $f(R)$ to be the set of states $s$ such that there exists an action $a$ so that every state $t$ that could be returned by action $a$ (applied to $s$) satisfies $t \in R$. Also let $R\_0 = \\{Z\\}$. Now compute the following sequence:

$$\begin{align\*} R\_1 &= R\_0 \cup f(R\_0)\\ R\_2 &= R\_1 \cup f(R\_1)\\ R\_3 &= R\_2 \cup f(R\_2)\\ &\vdots \end{align\*}$$

Iterate until you reach a fixpoint, i.e., $R\_{i+1}=R\_i$. Then $R\_i$ is the set of states that can reach $Z$: for every $s \in R\_i$, there exists a strategy that Alice can use to ensure she will reach the goal state $Z$. So, we can simply check whether $A$ is in $R\_i$ or not.

You can make the running time of this algorithm linear, by a simple trick. Store the set $R\_i$ explicitly in memory. Also, you maintain a separate data structure for "the fringe": the set of states that can reach $R\_i$ in a single step. For each state $s$ in the fringe and each action $a$ available on $s$, you maintain a counter that counts how many of the possible results of applying $a$ to $s$ will take you to the current set $R\_i$. On each iteration, you can compute $R\_{i+1}$ and update all of the counters. Each counter only decreases; it never increases. Also, a state $s$ is in $f(R\_i)$ just when one of the actions available on $s$ has a counter that has decreased to zero, so computing $f(R\_i)$ is just a matter of scanning the fringe and finding the counters that have hit zero; then you compute $R\_{i+1}$, update the fringe, and update the affected counters. The running time of this algorithm is linear in the size of "the graph", i.e., in the number of states plus the number of transitions (triples of state $s$, action $a$ available on $s$, and state $t$ that could be returned by this action).

However, this straightforward algorithm is not very memory-efficient: it requires explicitly storing a large set of states. Also it requires enumerating the statespace, or a large part of the statespace. Therefore, it might be sufficient for small systems, but for large systems it might not be attractive.

For larger systems, you might want to consult the model checking literature to see if there are better solutions.

For example, I suspect you might want to look at Alternating-time Temporal Logic (ATL), in the model checking literature. It deals with search problems for two-party games. I think I recall that there are model-checking algorithms for solving problems associated with these kinds of two-party games, but I'm not certain about that.

(Incidentally: another way to think about your problem is that the possible results from each action correspond to non-deterministic choices, and there is an adversary (Bob) who is resolving all non-determinism in the worst possible way.)

---
Tags: reference-request, search-algorithms, heuristics
---


# Question
Title: Combining Production Rules using Reinforcement Learning
Production systems have been used to solve puzzles such as the Tower of Hanoi for years with hard-coded production rules. However, has there been any research in using reinforcement learning to combine basic production rules into more complex ones with the goal of solving a puzzle?

Note that I've asked a similar question on Cogsci.SE, but with a greater cognitive perspective. In my opinion, the two perspectives are different enough to merit semi-cross-posting.

# Answer
this writeup by Kenan Deen solves the Tower of Hanoi problem with reinforcement learning and Markoff decision processes.

there is some other research on using genetic programming in "solving" (successfully playing) video games. these approaches do find "subroutines" that can be regarded as subgoals. for example, in playing pacman, an algorithm might have a subroutine/ subgoal that eats ghosts if they are blue, otherwise, run away from them. the sample algorithms are sometimes encoded as LISP-like trees. see eg
> 1 votes

---
Tags: reference-request, artificial-intelligence, reinforcement-learning
---


title: Proving the Bubblesort actually sorts

text:
# Question
Title: Proving the Bubblesort actually sorts
Say $A'$ is the output of $\mathrm{Bubblesort}(A)$ on an array of length $N$. To prove that Bubblesort works, we have to prove that it always terminates and that $$A'\[0\]\leq A'\[1\] \leq \dots \leq A'\[N-1\].$$ Is there anything else that needs to be proven to show that Bubblesort actually sorts?

(I have found this question in a textbook about algorithms.)

# Answer
> 9 votes
Here is an algorithm which satisfies your conditions:

```
for i in 0,...,n-1:
   A'[i] = 0

```

Clearly your conditions are lacking.

---

Correction of a sorting program, like any other program, is a combination of two condition: *termination* and *partial correction*. *Termination* just states that if the preconditions are satisfied then the program always terminates (in your course the phrase used is evidently "outputs after finite time", but *halts* or *terminates* is shorter). *Partial correctness* means that if the preconditions are satisfied and the program halts, then the postconditions are satisfied. What is left here is to come up with preconditions and postconditions. Since you're not working within a formal model, it is not clear how exactly to state the precondition, but it's probably something like that:

**Precondition:** The input $A$ is an array of length $N \geq 1$ of numbers.

(More generally, it is an array of some linearly ordered set, but we can think of "numbers" (whatever that means) as an important special case.)

Stating the postcondition is harder. It is *not* enough to ask that the output be sorted, as my example above shows. The semantics are subtler. Here is one way of stating the postcondition:

**Postcondition:** (1) The output array $A'$ is an array of length $N$ of numbers.

(2) The output array $A'$ is nondecreasing, i.e., $A'\[0\] \leq \dots \leq A'\[n-1\]$.

(3) The multisets $\\{A\[0\],\ldots,A\[n-1\]\\}$ and $\\{A'\[0\],\ldots,A'\[n-1\]\\}$ are equal, i.e., for each number $x$, the number of elements in $A$ equal to $x$ is the same as the number of elements in $A'$ equal to $x$.

The way that you prove postcondition (3) for bubble sort (and, more generally, for comparison sorts) is by showing that the *swapping* operation preserves the multiset of elements (the fast implementation of quicksort might need more care). So it might seem that you can replace (3) with the following postcondition:

(3') The array $A'$ is obtained from $A$ by a sequence of swaps.

There are two problems with this postcondition. First, it is not semantic — it doesn't describe what sorting accomplishes, only how sorting is done. Second, it is too restrictive. There are sorting algorithms which use operations beyond swapping. A particularly useful example is *counting sort*. Suppose the sorted numbers come from a very small domain, say $\\{0,\dots,m-1\\}$. We compute a *histogram* of the input array (using an integer array of length $m$), and then go over the histogram, producing a sorted version of the input.

# Answer
> 0 votes
Apart from the given terminating condition the only condition required is to prove that A' contains all the elements of A , just that they have been permutated

---
Tags: algorithms, sorting, arrays
---


# Question
Title: Difference between regular expression and grammar in automata
I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to differentiate between regular expressions and grammar of a language( I have not been taught the grammar for regular expressions).

I understand that grammar helps us to generate the valid strings in a language, but then this is what the rules for defining a regular expressions state. So where does the difference lie? I asked my professor and he said that regex are the most basic strings in a language and grammar is the set of rules for any language, which are of higher order than regex. Can someone provide some more in-depth information?

# Answer
Regular expressions, regular grammars and finite automata are simply three different formalisms for the same thing. There are algorithms to convert from any of them to any other.

The basic reason that we have all three is that they were created independently, with the first set of equivalences (there are several other formalisms as well) proven by Kleene (this result, or part thereof is called Kleene's Theorem).

So in that context, depending on which way round you want to run the models, they all recognise or generate strings of a regular language, and mathematically, there is, in that sense, no difference.

Of course sometimes one model is easier to use than another for a particular task, due to the details of the formalism. Furthermore the way they work in a human's head is often a little different, finite automata "feel" like computers, regular expressions "feel" like you're constructing a string out of smaller substrings and regular grammars "feel" like a more traditional grammatical derivation or classification of a sentence in a language (unsurprisingly when you look at the history).

So to compare the two, let's define them:

***Regular Expressions***

So regular expressions are recursively defined as follows:

1. $\emptyset$ is a regular expression
2. $\varepsilon$ is a regular expression
3. $a$ is a regular expression for every $a \in \Sigma$
4. if $A$ and $B$ are regular expressions then
    * $A\cdot B$ is a regular expression (concatentation)
    * $A \mid B$ is a regular expression (alternation)
    * $A^{\ast}$ is a regular expression (Kleene star)

Along with some semantics (i.e. how we interpret the operators to get a string), we get a way of generating strings from a regular language.

***Regular Grammars***

Regular grammars consist of a four tuple $(N,\Sigma, P, S \in N)$ where $N$ is the set of non-terminals, $\Sigma$ is the set of terminals, $S$ is the start non-terminal and $P$ is the set of productions which tell us how to change the start symbol, step by step, into a string in $\Sigma^{\ast}$. $P$ can have its productions drawn from one of two types (not both though):

*Right Linear Grammars*

For non-terminals $B$, $C$, terminal $a$ and the empty string $\varepsilon$, all rules are of the form:

1. $B \rightarrow a$
2. $B \rightarrow aC$
3. $B \rightarrow \varepsilon$

*Left Linear Grammars*

Left linear grammars are the same, but rule #2 is $B \rightarrow Ca$.

***Things to Ponder***

So looking at these definitions and playing with them, we can see that regular expressions look like matching rules, or ways of dealing with strings a bit at a time.

Grammars seem to "label" sections of the string, and group labels under new labels to validate the string (i.e. if we can get from $S$ to the string, or vice versa, we're happy).

However these are really doing the same fundamental thing, and how you view the metaphor of their function is really up to you.
> 25 votes

---
Tags: automata, formal-grammars, regular-expressions
---


# Question
Title: How to determine how many dots are in a resource in a resource allocation graph?
I understand most concepts regard a resource allocation graph but I see that some resources have more dots (not sure what they are actually referred to) in them than others such as the example below, R1 and R3 have one dot, R2 has two dots and R4 has three dots. I cannot find anything online that explains this so I would just like to know, how would you determine how many dots should be in a resource when drawing the graph?

# Answer
> 2 votes
The dots represent the number of clients a resource can serve simultaneously. So, in the example in the question, resources $R\_1$ and $R\_3$ can only serve one client at a time, $R\_2$ can serve two and $R\_4$ can serve up to three clients at the same time.

---
Tags: resource-allocation
---


# Question
Title: Algorithm for Filling Regions with Small Gaps
I am looking for an algorithm that fills a region with one color, but the edge of the region is not completely closed (i.e. one or more gaps are being left). The result is like the use of the Paint Bucket Tool with Gap Size option in Adobe Flash. We can assume that the input of the algorithm has to specify the largest size (straight line distance) of the gap.

My straightforward idea is (1) to fill the gaps in the edges (as shown in this webpage), and then (2) use the flood fill algorithm to perform the filling on a closed region. I have done (2) by using a recursive algorithm, but how should (1) be done?

Any alternative idea are also welcomed. Thanks!

# Answer
> 2 votes
This is clossing operator implemented as dilate-then-erode filter and then it is FloodFill.
Dilate filter is adding pixels that would became new hull.
Erode filter is cutting out pixels that are at the hull.
Here is try me link: Demo of operators
One thing that could be improved in this technique are gaps after filter.
You can get rid of it by applying dilation on color region.

This is one kind of solving, another would be to go along the edge and find pattern edge-gap-edge with given radius.
There are also caveats - if edge is not in single color, then operators must include that information or get binary representation (with binary data, e.g. 0 means empty, 1 means edge).
Clossing operator is easy to implement but slower than contour tracing.
You could trace edge by FloodFill starting from edge region, using BFS and going into counting mode after boundary is crossed, to check within gap radius.

---
Tags: algorithms, computer-vision
---