# Question
Title: Reference request: Category theory as it applies to type systems
I keep hearing about how one must learn category theory to truly understand programming language theory. So far, I've learned a good deal of PL without ever stepping foot into the realm of categories. However, I figured it was time to take the leap to see what I had been missing.

Unfortunately, none of the sources I can find seem to make any connections to type systems or programming. They *say* it's an introduction to category theory for computer scientists, but then veer off into general abstract nonsense (I say this lovingly) without giving any practical examples or applications.

I guess my question is actually two-fold:

1. Is category theory essential for understanding the "deep concepts" in PL?
2. What's a source that explains category theory from the viewpoint of practical applications to type systems and programming?

So far, the furthest I've gotten is to a vague conception of functors (which don't seem to be related to functors in ML, as far as I can tell). I'm dreading the abstraction I'll need to keep in my head to understand monads from a category-theoretic view.

# Answer
Category theory is **not** necessary to understand programming languages, it's not even necessary to do advanced research on programming languages. Most programming language people don't know (much) category theory.

Category theoretical methods have been useful mostly in a small part of programming language research, namely in the analysis of functional programming, particularly, since Moggi's great discovery that some computational effects have monadic structure. In the 1990s, following Moggi's breakthrough, a lot research was done to extend categorical methods to other forms of programming languages. However, to the best of my knowledge categorical methods have not been found all that useful for OO, concurrent, parallel and distributed computation, timed computation or compilers. For this reason, people have mostly abandoned extending categorical methods.

Categorical approaches to typed programming work well in pure functions. Indeed some simple typing systems are categories. This is described in e.g.

There is now a lot of work on types for concurrent processes (e.g. session types) and none of that is categorical in nature as of Sept 2016.

That said, one can never know too much mathematics, and knowing category theory is useful. So it's a question of cost/benefit. If you like maths, if maybe you have a bit of background in algebra (e.g. what's the free group over a set, free ring etc) then learning category theory will be easy, and if you plan on doing work that is (inspired by) functional programming, knowing categories will be useful.

Finally, category theory is beautiful mathematics, and worth studying simply because it's so neat.

---

See Uday Reddy's contribution in this discussion for a different view.
> 15 votes

# Answer
Learning category theory is a huge time investment, and the question whether it is worth it is very valid. I still struggle with this too, and I already know why I should learn it. I wrote:

> I liked assembly language when I started to program, and set theory feels similar to assembly language. Category theory is one alternative to get around all the engrained prejudices about logic and model theory embedded into mainstream ZFC set theory.

The idea here is to use categories instead of sets or "unspecified bits" as a possible semantics for a given type theory or programming language. Why should one want to do this? Consider the duality between an action and an observation. Different observations (or at least their order in time) don't interfere with each other (outside of quantum mechanics), but this is not necessarily true for different actions. The engrained prejudices about logic embedded in set theory make it hard to model actions, compared to modeling observations.

---

I'm not convinced that there really is a perfect correspondence between category theory and type theory like claimed here:

> By a syntax-semantics duality one may view type theory as a formal syntactic language or calculus for category theory, and conversely one may think of category theory as providing semantics for type theory.

It is true that category theory can provide semantics for type theory (which can be really useful), but I doubt that type theory really provides a sufficiently powerful formal syntactic language to express all the calculations done in category theory.

---

In practice, the usefulness of category theory can arise by suggesting useful questions and analogies. But category theory can also suggest activities and questions which in the end turn out to be just a distraction (waste of time) from the really important issues. And you certainly can learn logic and type theory without caring about category theory.
> 6 votes

---
Tags: reference-request, programming-languages, type-theory, category-theory
---


# Question
Title: Relation between Type Assignment system (TA) and Hindley-Milner system
Recently I started my studies in type theory/type systems and Lambda Calculus.

I have already read about Simple Typed Lambda Calculus in Church and Curry style. The last one is also known as Type Assignment system (TA).

I'm thinking about the relations between TA and Hindley-Milner (HM), the system in languages like ML and Haskell.

The book Lambda-Calculus and Combinators: An Introduction (Hindley) says that TA is polymorphic (pag. 119). Is that the same sense of polymorphism in systems like HM and System-F?

TA is said to have the strong normalisation property, so is not turing complete. Languages that use HM system are turing complete, Haskell for example. So must be the case that HM system allows terms like the infinity loop $\Omega$ to receive a type. Is that correct or I'm missing something?

Any way, I would like to know the relation between TA and HM.

# Answer
System F and its subsystem HM have a type former for universal quantification:

$$ \tau \quad::=\quad \forall x.\tau \ |\ ... $$

which the system in Hindley/Seldin doesn't have. That is the key difference.

Now System F doesn't have decidable type-inference, and HM is a way of combining type-inference with reasonably expressive parametric polymorphism. HM achieves this by allowing only outermost universal quantification, i.e. all types are of the form

$$ \forall x\_1 \forall x\_2 ... \forall x\_n.\tau $$

where $\tau$ is quantifier free (and $n \geq 0$). HM gives a rule system that ensures that only programs that can be typed in this way are admissible. This is achieved by "let-polymorphism". The system in Hindley/Seldin doesn't do any of that. Later, in Chapter 13, Hindley/Seldin introduce pure type systems (PTS), of which System F is a special case. I'm not sure if HM can be expressed as a PTS.

---

The question of strong normalisation is orthogonal. System F and HM are strongly normalising, but that can easily be remedied by introducing fix-point combinators or similar. The paper Principal type-schemes for functional programs by L. Damas and R. Milner even states this: "*For example, recursion is omitted since it can be introduced by simply adding the polymorphic fixed-point operator ...*" The introduction of fixpoints, making the system Turing complete, poses no issues from the point of view of type inference.
> 9 votes

---
Tags: type-theory, type-checking, type-inference
---


title: Asymptotic growth of search algorithms

text:
# Question
Title: Asymptotic growth of search algorithms
I have 2 search algorithms and I have derived the following tight bound representations:

$$ nlog(n)+mlog(n) $$

$$ m∗n $$

Now i want to find a function $f(n)$ so that when $m$ is an element of tight bound $f(n)$, both algorithms have equal asymptotic run time.

Now I'm not sure if its just as simple as setting the two equations equal to each other and isolating 'm' or of it is more than tha

# Answer
> 1 votes
Your approach, for this problem at least, will work, but there are interesting things happening in the background. Simply setting the two terms equal and solving for $m$ will give you $$ m=\frac{n\log n}{n-\log n} $$ However, I doubt that you want to substitute this back into the two original expressions and try to find a $g(n)$ so that each of your original expressions is in $O(g(n))$. Let's try something else.

For no particular reason, let's try letting $m=\log n$. Then your two expressions become $$\begin{align} n\log n+m\log n&=n\log n+\log^2n \in O(n\log n)\text{, and}\\ n\\:m&=n\log n\in O(n\log n) \end{align}$$ Hooray! If $m=f(n)=\log n$ we get a common upper bound with $g(n)=n\log n$.

Let's do the same thing, now with $m=n$. The two expressions are now $$\begin{align} n\log n+m\log n&=n\log n+n\log n \in O(n\log n)\text{, and}\\ n\\:m&=n\\; n\in O(n^2) \end{align}$$ Drat. No common upper bound, but by transitivity, we have $n\log n+m\log n\in O(n^2)$ and so again, we find a common upper bound, namely the asymptoticly larger $g(n)=n^2$.

You can do this for all kinds of other $f(n)$, like $f(n)=\log\log n$ and even $f(n)=1$, both of which have common solutions $g(n)=n\log n$. In fact, it seems that we can do this for *any* $f$ whatsoever.

---
Tags: asymptotics, search-algorithms
---


title: A Dead-lock in an Operating System is

text:
# Question
Title: A Dead-lock in an Operating System is
A Dead-lock in an Operating System is

1. Desirable process
2. Undesirable process
3. Definite waiting process
4. All of the above

---

My attempt:

As "If a process is unable to change its state indefinitely because the resources requested by it are being used by another waiting process, then the system is said to be in a deadlock."

So, none option should be true. However, somewhere answer key is given option $(3)$.

> Can you explain it, please?

# Answer
> 3 votes
Your attempt "If a process is unable to change its state indefinitely because the resources requested by it are being used by another waiting process, then the system is said to be in a deadlock." is close, but not quite there.

A deadlock is a situation where one "process" (not a "process" as used in software development, but something more general) is waiting for a resource which will never become available because a second "process" is using the resource, *and* is waiting directly or indirectly for a resource that the first process is already using.

A situation where the second process doesn't stop using the resource just for the heck of it isn't a deadlock. A similar situation where the resource stops getting used, but everytime it stops being used some other process is quicker using it, is also not a deadlock (but an example of resource starvation, which is more general than deadlock).

---
Tags: operating-systems, process-scheduling, deadlocks
---


# Question
Title: What does $\mathbf{Q}^+$ mean in approximation texts?
Often, in a lot of texts concerning approximation algorithms I see the following notation (for example, here in page 19 of the PDF or the first page of the introduction):

> ... and a cost function on vertices $c:V\to \mathbf{Q}^+$ ...

Is this just the positive rationals? Or is this something else?

# Answer
> 5 votes
I'm going to say yes, positive rationals, because:

* That's what it means throughout math literature.
* That's a sensible domain for a cost function. It would possibly be a different algorithm problem if "negative" cost were legal. Furthermore real numbers introduce questions of representation and comparing them, so while mathematicians or economists often consider real numbers for quantity, computer scientists are more cautious.
* There is no front or back matter indicating otherwise.

---
Tags: algorithms, optimization, approximation, notation
---


# Question
Title: Comparison of Decision Trees: RTED vs MLE
I read two papers discussing how to compare between decision trees. One of them is RTED (that is specifically for trees and sub-case is decision trees) can be found here (RTED: A Robust Algorithm for the Tree Edit Distance)here:
and additional approach is COMBINING CLASSIFICATION TREES USING MLE by Shannon and Banks (Shannon, W. D., & Banks, D. (1999). Combining classification trees using MLE. Statistics in Medicine, 18(6), 727-740.). I would like to know if the MLE method is a sub case of RTED algorithm for comparison between decision trees? "Comparison between decision trees" I mean, given 2 decision trees we would like to compare the structure of them. It means by the location and the name of each node. The RTED transfers the trees into a Bracket Tree Format that contains the names of the tree nodes and compares between the 2 strings. The output is a number that is the Tree distance value (also know in literature Edit Distance). The question is if the algorithm described by Shannon and Banks (called MLE) is a specific case that is covered by RTED algorithm. If the final result of comparison between 2 decision trees will yield same result. If the answer is No, what are the cases in which the different algorithms will give different results?

# Answer
The main difference between MLE and RTED is that RTED can compare any kind of decision tree even non binary such as CHAID. In addition, each of them has different approach for scanning the tree. MLE is from top down and find all the possible paths while RTED can go in breadth way.
> 1 votes

---
Tags: algorithms, trees
---


# Question
Title: Master Theorem: How to find the value of b in this recurrence relation
The master theorem is used with recurrences of the form `T(n) = aT(n/b) + f(n)` where a \>=1 and b \> 1, in which case the value of b can be easily seen from the recurrence, however I have a recurrence of the form

```
T(n) = T((n/4)+3) + f(n)

```

How do I get the value of b in this case?

This question Particularly Tricky Recurrence Relation (Master's Theorem) is the only thing I found that has a similar case with T(n/4 +1) but gives no detail about how the b was calculated.

# Answer
> 3 votes
You can't use the Master theorem on that function $T$.

However, as Raphael suggests, you *could* consider the related function

$$T'(n) = T'(n/4) + f(n),$$

use the Master theorem to find a solution for $T'$, and then *check* whether that's a valid solution for $T$ too. No guarantees that it will be, but you could check.

In other words, you could use the *guess-and-check* strategy to solve the recurrence for $T$, where your "guess" comes from solving $T'$ using the Master theorem. See also Solving or approximating recurrence relations for sequences of numbers for an explanation of *guess-and-check* (also called *guess-and-prove*).

One caveat is that guess-and-check will probably require an explicit solution to $T$, with specific constants. In other words, it's usually not enough to guess that $T(n) = O(g(n))$; you will typically need to guess a specific constant $c$ such that $T(n) \le c \cdot g(n)$, one that will enable the proof to go through.

# Answer
> 2 votes
I don't think you can use master's theorem. However, there is a much more general version of that called Akra-Bazzi Method which can be used to solve this problem

# Answer
> 1 votes
What you can do is to use the master theorem to get lower and upper bounds separately, and then try to use other methods to prove a tight bound.

So, on one hand we have

$T(n) \leq T(n/3) + f(n)$

this is true because $T$ is an increasing function and $n/4 + 3 \leq n/3$ for $n$ big enough.

You will be using the master theorem with the following recurrence:

$T'(n) = T'(n/3) + f(n)$

and getting $T'(n) \in \Theta(g(n))$ for some $g$. So you will conclude $T(n) \in O(g(n))$

For the lower bound use $T(n) \geq T(n/4) + f(n)$.

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Can NFAs determinization be efficient given that the statespace is exponential?
I have recently learned about using powerset construction for conversion of NFA to DFA - however this only seems to be feasible when the number of states we are working with are 3 or less, as $2^k$ seems to grow unmanageable very quickly.

I have a problem with 6 states, meaning that if I were to use powerset construction, I would have 64 states. What is a more efficient way?

# Answer
> 6 votes
Let me mention a variant of the powerset construction. In this variant, we are going to construct only states reachable from the initial state. The way it works is as follows:

1. Create a list of states to-be-processed, and populate it initially with $\\{q\_0\\}$, where $q\_0$ is the initial state of the NFA.
2. While the to-be-processed list is non-empty, remove a state $S$, and compute all states reachable from $S$ by reading one character. Put any of these which hasn't been encountered yet in the to-be-processed list.

This variant (which I haven't quite specified in full) constructs the powerset automaton *restricted to states reachable from the (new) initial state*, and runs in time proportional to the resulting number of states (and the alphabet size).

The same construction, and indeed the vanilla powerset construction, also works for NFAs with several initial states. The only difference is that we start with the set $Q\_0$ of initial states (which is also going to be the initial state of the resulting DFA) rather than with $\\{q\_0\\}$.

# Answer
> 0 votes
In addition to the strategies pointed out in other answers , You can also adopt the method of directly constructing a DFA by determining the number of equivalence classes for your problem which is equal to the number of states in your minimized automaton. However this approach is suitable for problems having few partitions for the strings but produces the results quicker relative to other methods.

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


# Question
Title: I have a problem understanding a solution for number theory problem from SPOJ
Problem statement can be found here or down below.

The solution which I'm trying to understand can be found here or down below.

**Problem Statement**.

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

**Input**
The input begins with the number t of test cases in a single line (t\<=10). In each of the next t lines there are two numbers m and n (1 \<= m \<= n \<= 1000000000, n-m\<=100000) separated by a space.

**Output**
For every test case print all prime numbers p such that m \<= p \<= n, one number per line, test cases separated by an empty line.

**Example**
***Input***:
2
1 10
3 5

***Output***:
2
3
5
7

3
5
**Solution**

**Concept**:
The idea behind solution here is to generate all the prime numbers that could be factors of numbers up to the maximum endpoint 1 billion.
That square root happens to be around 32000.
Using this array, do a bounded Sieve of Eratosthenes only in the range requested.

```
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

int main() {
int primes[4000];
int numprimes = 0;

primes[numprimes++] = 2;
for (int i = 3; i <= 32000; i+=2) {
    bool isprime = true;
    int cap = sqrt(i)+1;
    for (int j = 0; j < numprimes; j++) {
        if (primes[j] >= cap) break;
        if (i % primes[j] == 0) {
            isprime = false;
            break;
        }
    }
    if (isprime) primes[numprimes++] = i;
}

int T,N,M;
scanf("%d",&T);

for (int t = 0; t < T; t++) {
    if (t) printf("\n");
    scanf("%d %d",&M,&N);
    if (M < 2) M = 2;

    int cap = sqrt(N) + 1;

    bool isprime[100001];
    memset(isprime,true,sizeof(isprime));

    for (int i = 0; i < numprimes; i++) {
        int p = primes[i];

        if(p >= cap) break;

        int start;

        if (p >= M) start = p*2;
        else start = M + ((p - M % p) % p);

        for (int j = start; j <= N; j += p) {
            isprime[j - M] = false;
        }
    }

    int start = (M % 2)?M:M+1;

    if (M == 2) {
        printf("2\n");
    }
    for (int i = start; i <= N; i+=2) {
        if (isprime[i-M]) printf("%d\n",i);
    }
}
return 0;
}

```

I know how Sieve of Eratosthenes works and I also ran this program using pen and paper.
It works fine but I 'm not able to understand why it works and how do I prove that this program and the algorithm used in it are right?
I spent hours but could not prove.
Any help would be appreciated.

# Answer
A number is prime if it has no non-trivial factors. In order to check whether a number $n$ is prime, it suffices to check that it has no factors in the range $2,\ldots,\sqrt{n}$. In order to find all primes in $\[a,b\]$, we go over all primes in $2,\ldots,\sqrt{b}$ (using a list prepared ahead of time), and for each such prime $p$, we mark off all multiples of $p$ in $\[a,b\]$. After going over all such primes, the unmarked numbers in $\[a,b\]$ are prime.

How do we mark off all multiples of $p$ in $\[a,b\]$? We mark off the first multiple $p \lceil a/p \rceil$ (computed in a funny way in the code), if it happens to fall inside the interval (but not if this multiple happens to be $p$ itself!), and then we mark off the remaining multiples, by jumping in steps of $p$ until we fall off the interval $\[a,b\]$.
> 0 votes

---
Tags: algorithms, primes
---


# Question
Title: Finding Regular expression for FSM with more than one final state
I am trying to find Regular expression for a FSM with more than one final state(in my case 2).

In this I am getting two different RE for state q4 and q5. So my question is If we get more than one different RE for one FSM with more than one final state, is it correct??

# Answer
> 4 votes
> If we get more than one different regular expression for the same finite state machine with more than one final state, is it correct?

Rather than push the buttons mechanically, you have to understand what you're doing. Your task is to find a regular expression equivalent to a given FSM. This means that the language accepted by your regular expression has to be the same as the language accepted by the given FSM.

For every state $\sigma$ in the FSM, you can computer a regular expression $r\_\sigma$ for the language $L\_\sigma$ of all words upon reading of which the FSM ends up at the state $\sigma$ (this definition is valid in the deterministic case; for non-deterministic automata, it has to be slightly modified). The language $L$ accepted by the FSM consists of all words upon reading of which the FSM ends up at an accepting state. Given this data, you should be able to come up with a regular expression for $L$ using the regular expressions $r\_\sigma$ for all accepting states — you just have to combine them in the correct way.

# Answer
> 1 votes
4 steps to convert FSM to RegEx:

1. Make sure no inward arrows in Initial state ($q0$), if there is then add a new state ($q00$) which goes to initial state ($q0$) on encountering $\epsilon$. Now treat this new state ($q00$) as your new initial state.
2. If there is an outward arrow from a final state (like $q5$ to $q6$) then add a new state ($fq5$). And make the final state ($q5$) point to this new state ($fq5$) on encountering $\epsilon$. Treat this new state ($fq5$) as the new final state.
3. If there are multiple final states (like $q5$ and $q4$) then add a new state ($q54$). And make all the final states to point to this new state ($q54$) on encountering $\epsilon$. Treat this new state ($q54$) as the only final state.
4. Now start eliminating states one by one and substitute a correct RegEx in their place\*. Goal is to reach with only 1 initial state and 1 final state, connected by the RegEx.

Now if you ask, can there be more than 1 RegEx for a FSM, then the answer is Yes. It depends on what order you eliminated the states.

Consider a NFA:

* $q00$ to $q0$ on $\epsilon$
* $q0$ to $q1$ on $b$
* $q1$ to $q0$ on $a$
* $q1$ to $q1$ on $c$ and
* $q1$ to $q2$ (final state) on $d$

Now if you remove $q0$ first you'll get different RegEx $\[b(ab)^\*(c+(ab)^\*)^\*d\]$ and if you eliminate $q1$ first you'll get a different RegEx $\[(bc^\*a)^\*bc^\*d\]$.

\*To eliminate states one by one

---
Tags: finite-automata
---


# Question
Title: String matching algorithm - check if a string matches a pattern
This looks like quite the challenge; given a pattern $P$ (of length $n$) and a string $S$ (of length $m$), how would you check whether the string matches the pattern? For instance:

* If $P$ = "xyx" and $S$ = "foobarfoo" then $S$ matches $P.$
* If $P$ = "acca" and $S$ = "carbuscarbus" then $S$ does not match $P.$

My thoughts so far: This looks like a *dynamic programming* problem. We can define a boolean

**$M(i, j)$ = True iff pattern $P\[i:n\]$ matches $S\[j:m\]$**

We then need $M(0, 0).$ **Note here that the substring notation is $P\[i:n\] = P\_iP\_{i+1}...P\_n$.**

I couldn't think of an efficient recurrence beyond this. It seems like I would have to introduce an extra mapping (from a substring of $P$ to a substring of $S$, indicating that the earlier "matches" the latter; for example in the first example, ("x", "foo") would be part of the mapping. You then replace "x" by "foo" in the substring of P). This would make it $O(2^n)$ or worse though.

If you don't see the intuitive meaning, here's a more rigorous definition: S matches P iff there exists a mapping $$T : P\[i:j\] \rightarrow S\[a:b\]$$ for $i, j \in \[1, 2 ...n\]$ and $a, b \in \[1, 2 ...m\]$, such that replacing $P\[i:j\]$ with $S\[a:b\]$ transforms P into S. For example, in the first case where $P$ = "xyx" and $S$ = "foobarfoo", $T$ is as follows:

* T('x') = 'foo'. {Here $i = 1, j = 1, a = 1, b = 3$}
* T('y') = 'bar'. {Here $i = 2, j = 2, a = 4, b = 6$}

Replacing all instances (in $P$) of 'x' with 'foo' and 'y' with 'bar', gives us 'foobarfoo' i.e. $S$.

Thus, $S$ matches $P.$

# Answer
> 5 votes
There are various algorithms for pattern matching in string.

## Exact String matching algorithms

1. Brute Force
2. Rabin Karp
3. Boyer-Moree
4. KMP
5. Aho Corasick etc.

## Approximate String Matching Algorithm

Approximate String matching is applied in text searching, pattern recognition and signal processing applications. For a text `T[1..n]` and pattern `P[1...m]`, we are supposed to find all the occurrences of pattern in the text whose **edit distance** to the pattern is at most `K`. The **edit distance** between two strings is defined as minimum number of character insertion, deletion and replacements needed to make them equal.

Approximate string matching problem is solved with the help of **dynamic programming**.

You can have a look through all these algorithms. These algorithms will take optimum complexity like **O(m),O(n+m)** (in case of KMP for example).

---
Tags: algorithms, dynamic-programming, strings, exact-string-matching
---


title: Mapping an address to a cache block

text:
# Question
Title: Mapping an address to a cache block
A cache with 64 blocks(block0 to block63) and each block of size 16 bytes (or 4 words). This is what I think of the address arrangement, if it is byte addressable.

block0 has addresses: 0, 64, 64\*2, 64\*3, ...., 64\*15

block1: 1, 64+1, 64\*2 + 1, 64\*3 + 1, .... 64\*15 + 1

block2:

**...**

**...**

**...**

**...**

block63: 63, 64\*1 + 63, 64\*2 + 63, 64\*3 + 63, ... 64\*15 + 63

But in the problem given in the figure, the addresses are suggested to be present in a serial order (see the last line saying "maps all addresses between 1200 and 1215") like:

block0: 0,1,2,3,4....15

block1: 16,17,... 31

block2:

**...**

**...**

**...**

**...**

block63: 1008, 1009,...1023

# Answer
A cache is a copy of a "chunk" of main memory of a given size that is held in a faster ram closer to the CPU.

In the example given each cache block holds a chunk that is 16 bytes in size and there are a total of 64 blocks available. When a CPU accesses an address if it's not already in cache, the data is copied from main memory into the cache in 16 byte chunks. When the cache load selects a cache block, it ignores the lower 4 bits of the address (for a 16 byte block) then it uses the next 6 bits of the address (for 64 locations) to determine which block to use and the remaining bits of the address are used as a TAG to keep track of the addresses currently cached. It fills the block with the 16 bytes starting at the accessed address with the lower 4 bits zeroed.

The math used in the explanation is based on the physical processes... Dividing by 16 ignores the lower 4 bits. Using the modulo of 64 on the result uses the next 6 bits as an index into the cache. The explanation didn't deal with tagging, but that wasn't really part of the question which was "Which cache block is it using?".

So consider the CPU accesses address 1205 (Using an address that doesn't start at the beginning of a cache block for a little more clarity.):

A 16 bit address 1205 in binary is 0000010010110101.

Ignoring the lower 4 bits, the memory's block address is 1001011

Since the cache is 64 blocks it uses the next 6 bits to select which cache block to use. In this case 001011 is used. This is block number 11.

The remaining bits, 000001, are used in a tag to indicate which memory block is in the cache.

The data is then loaded from the cache into the CPU using the lower 4 bits 0101 as an index (or the 6th byte of the block).

If a subsequent access is for address 1210, or binary 0000010010111010, the tag will match and the cache system won't have to access main memory for the data. It's already in cache and can be used quickly, the CPU just has to use the lower 4 bits of the address 1010 to load the 11th byte from the cache block...

If, however a future access is for address 9403, or binary 0010010010111011, this address also selects cache block 11 so the previous data is overwritten with 16 bytes of data from main memory beginning at 9392 (lower 4 bits zeroed), the new tag for the block is 001001, and the CPU loads the byte from 1011 in the cache block.
> 1 votes

---
Tags: operating-systems, cpu-cache
---


# Question
Title: Efficiently check if any vertex has a path to its partner vertex
So I have a directed graph that looks something like:

I'm trying to make an algorithm that can go through all the vertices and tell me whether we have any path from an upper case letter to its lowercase version, or a path from a lowercase letter to its upper case version. In the above example, we have a path from C to c. We also have a path from B to b, from a to A, from E to e, and from G to g. I'd like the algorithm to find at least one of these paths.

The algorithm can stop looking if it just finds one such case where this happens. Each vertex points to at most one different vertex, so the out-degree of every vertex is either zero or one. I'm trying to get this done efficiently (linear time) and can put whatever extra information in the vertices to do it. I've been attempting to use the DFS algorithm to do it because you can work with ancestry but I'm not sure if it works for specific vertex relationships efficiently.

I'm aware that DFS can use discovery time and finish time to find if a vertex is the ancestor of another, and that this is used for cycle detection. I'm basically wondering if there is an efficient way to check if a specific node (that isn't necessarily part of a cycle) is the ancestor of another specific node. Unless, of course, this is unnecessary and there is a better way to go about it.

# Answer
Observation: **Each weakly connected component can contain at most 1 cycle, and every vertex in such a cycle is reachable from every vertex in the weakly connected component.** That's because every vertex that participates in a cycle exhausts its single out-edge by connecting to the next vertex in the cycle, so the only other edges that can be incident on any vertex in this cycle must be in-edges from other vertices.

In more detail: Suppose to the contrary that a single component contains 2 cycles: Then either they are vertex-disjoint or not. In the former case, there must be an undirected path of edges (i.e., a path in the graph where edge orientation has been forgotten) connecting the two cycles. But the first and last edges in this undirected path must be "outwards" (i.e., the first must be an in-edge to the first cycle, and the last must be an in-edge to the second cycle), implying that some vertex on the path must have 2 out-edges, so this case cannot happen. In the latter case, let the two cycles be $C\_1$ and $C\_2$, and w.l.o.g. suppose $|C\_1| \geq |C\_2|$. Let $uv$ be an edge in $C\_1$ such that $u \in C\_1 \cap C\_2$ but $v \notin C\_2$. (Such an edge must exist if $C\_1 \neq C\_2$.) Then $u$ must have a successor $w \neq v$ in $C\_2$; but this immediately implies that $u$ has outdegree at least 2, so this cannot happen either.

## Algorithm phase 1: Detecting a cycle

So, starting at any vertex and successively traversing the single out-edge can only give one of two possible outcomes:

1. We reach a vertex with no out-edge. In this case, the component has no cycle.
2. We reach a vertex we have seen before. In this case, the component has a single cycle consisting of all vertices visited since the last time the final vertex was visited. In a $k$-vertex component, the cycle vertices can be identified in $O(k)$ time by numbering the vertices in visitation order and gathering them together in a subsequent pass.

To simplify notation I'll label the vertices with positive and negative integers, instead of upper- and lower-case letters. We will maintain a counter $c\_i$ for each pair of vertices $i, -i$: at the end of the algorithm, $c\_i = 2$ if and only if at least one of the vertices $i$ and $-i$ can reach the other by some path.

If a cycle was detected, we can start at any vertex in the cycle and continue following out-edges until we hit the first vertex again, incrementing $c\_{|i|}$ for each vertex $i$ encountered. Also, we (at least conceptually) create a new vertex $x$ to represent "the cycle", and as we proceed through each vertex $v$ in the cycle, we change every non-cycle edge $uv$ to $ux$. (Conceptually) delete the cycle vertices, and set $z = x$.

If no cycle was detected, set $z$ to the last vertex we found, say $i$, which by construction has no out-edge. Increment $c\_i$.

Observe that since any cycle has been deleted, the component is now a tree with all edges directed toward $z$.

## Algorithm phase 2: Reverse DFS

We now perform a DFS starting at $z$ and proceeding "against" the direction of each edge. During this traversal:

* Upon entering a vertex $i$: If $c\_{|i|} \< 2$, then increment it.
* Upon leaving a vertex $i$: If $c\_{|i|} = 1$, then decrement it.

This asymmetric increment/decrement scheme ensures that, whenever we discover a path from the root $z$ that contains both vertices in a pair, the discovery (which is recorded as a count of 2) "sticks", while OTOH whenever we discover that no path from the root $z$ through some vertex $i$ also contains $-i$, the discovery of $i$ is "forgotten" -- this has the important effect of *not* recording as matched any pair $i, -i$ that occur in the same component but such that neither is the ancestor of the other.

The above can all be implemented to take linear time in the number of edges within a component, so the overall time to process the graph is $O(|V|+|E|)$.
> 1 votes

# Answer
I would begin with a simple insight: Why plain dfs fail to solve this problem?, if you want to find a path from $A$ to $a$ then the dfs might fail because a node that belongs to the $A \to a$ path its already visited in the dfs search.

Then if we are looking for a path from $A$ to $a$ the problem we need to solve is that if we found a node $x$ that is already visited, how to know if $x$ actually leads to $a$ in a path we have explore before in the dfs search?

A DFS search forms DFS Spanning trees, roughly they are the trees that are formed as we tranverse the graph until we have no more options, it is at tree because we are marking nodes as visited so there are no cycles. It is important to understand that there may be *more than one* DFS spanning tree because is possible that certains node may not be reachable from all the nodes (taking a look at dfs spanning tree definitions will make clearer that point). Following that fact, we can say that every node will belong to exactly one DFS Spanning tree, so if we store all the DFS Spanning trees it will be *linear* in space, and transversing all will be *linear* in time (more on that next).

What we have so far is that we need to check if from $b$ we reach $a$, the way we do it is by looking at the DFS Spanning tree of $b$!, its trivial to see that the DFS Spanning tree where $b$ belongs its already computed at that moment because $b$ is already visited :) the trick is that we need to somehow store it as the dfs search is performed (its more a implementation detail).

We are almost there!, all reduces to this: how do we check that $a$ is a descendant of $b$ in its DFS Spanning tree?, well its trivial to do it in linear time but that would turn our algorithm quadratic (and the whole point of this question is to solve it in linear time), we can use the LCA (lowest common ancestor), if the LCA of $b$ and $a$ is $b$ then for sure $a$ is a descendant of $b$ in the tree!, compute LCA for two given nodes its linear but shockingly we can do it in log time and in constant time as well!, that is not a trivial task but is completely possible. Check this.

Another thing to keep in mind is that cycles are almost a problem in every stratagy, so you may consider to avoid them by computing strongly connected components first in linear time and then clustering the nodes in a single node.
> 0 votes

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


# Question
Title: How to use Pumping Lemma for $L = \{www | w∈\{0,1\}^*\}$
I'm trying to understand how to use a contradiction proof via the Pumping Lemma to prove a language is not regular. Everybody always uses examples like $\\{ 0^n1^n | n\>=0\\}$, where it can be broken up into two parts $xy$ and $z$ and where these parts are different. How can I apply it to a language consisting of the concatenation of 3 identical strings?

# Answer
Let's take the alphabets as **a** and **b** in-order to avoid confusion.

Suppose that **A1** is a regular language. Let p be the “pumping length” of the Pumping Lemma. Consider the string $s = a^pba^pba^pb$. Note that $s ∈ A1$ since $s = (a^pb)^3$, and $|s| = 3(p + 1) ≥ p$, so the Pumping Lemma will hold.

Thus, we can split the string $s$ into 3 parts $s = xyz$ satisfying the conditions.

i. $xy^iz ∈ A1$ for each $i ≥ 0$

ii. $|y| \> 0$,

iii.$ |xy| ≤ p.$

Since the first $p$ symbols of $s$ are all $a’s$, the third condition implies that $x$ and $y$ consist only of $a’s$. So $z$ will be the rest of the first set of $a’s$, followed by $ba^pba^pb$.

The second condition states that $|y| \> 0$, so $y$ has at least one $a$. More precisely, we can then say that

$x = a^j$ for some $j ≥ 0$,

$y = a^k$ for some $k ≥ 1$,

$z = a^mba^pba^pb$ for some $m ≥ 0$.

Since $a^pba^pba^pb = s = xyz = a^ja^ka^mba^pba^pb = a^{j+k+m} ba^pba^pb$, we must have that $j + k + m = p$. The first condition implies that $xy^2z ∈ A1$, but

$xy^2z = a^ja^ka^ka^mba^pba^pb$

$ = a^{p+k}ba^pba^pb$

since $j + k + m = p$. Hence, $xy^2z$ not an element of $A1$ because $k ≥ 1$, and we get a contradiction. Therefore, $A1$ is a nonregular language.
> 0 votes

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


title: How do i simplify this SOP expression?

text:
# Question
Title: How do i simplify this SOP expression?
Hi i have derived the following SoP (Sum of Products) expression , by analyzing the truth table of a 3 bit , binary to gray code converter. I ask for verification, because i feel as though this answer may not be correct or complete.

> X = a'bc' + a'bc + ab'c' + ab'c

which, using k-maps, was simplified to

> X = ab' + a'b

Is this correct ?

# Answer
> 2 votes
You can verify that the two expressions are equivalent by using some logical equivalences. Below I'm using 1 to represent true. $$\begin{align} a'bc'+a'bc + ab'c'+ab'c &= (a'bc'+a'bc) + (ab'c'+ab'c) &\text{associativity of } +\\ &= a'b(c'+c) + ab'(c'+c) &\text{distributivity, twice}\\ &= a'b(1) + ab'(1) &\text{inverse for }+\\ &= a'b + ab' &\text{identity for }\cdot \end{align}$$

# Answer
> 1 votes
K-map Simplification leads to the expression which you have arrived at . For checking the same you can create a truth table for your simplified expression and match the outputs with those of the initial expression. Or you could also use set operations on the given expression and reduce it .

The final expression also is ***a XOR B*** if it helps .

---
Tags: boolean-algebra, karnaugh-map
---


# Question
Title: Searching for efficient method to compute $a^n \bmod p$ for large numbers
I need an efficient algorithm with clear steps to compute $a^n \bmod p$ when $n$ is large enough and $p$ also. I'm looking for something equivalent to the built-in `PowerMod` function in Mathematica.

# Answer
> 2 votes
The algorithm you are looking for is quick modular exponentiation.

It is based on the exponentiation property of modulus operator :

A^B mod C = ( (A mod C)^B ) mod C

for example we need to calculate 4^8 mod 7 (let us assume for the time being 4^8 is a large number and cannot be computed by available machines.)

we can then write

=(4^ 4 * 4 ^ 4) mod 7

=(4^4 mod 7 * 4^4 mod 7 )mod 7

= (256 mod 7 * 256 mod 7) mod 7

= 2

This algorithm doesn't only work for powers of 2 it works generally . We just need to write the power in its binary representation .

example :

3^31 mod 4

can be written as

3^(16+8+4+2+1) mod 4

you can see once we apply the exponentiation property to same the computations will be quite efficient.

# Answer
> 1 votes
You can use the Square and Multiply method:

**Goal: Compute $y \equiv a^b \pmod{N}$**

**Step 1:** $\text{Initialize }\\ x \leftarrow a \\ t ~\leftarrow 1$.

**Step 2: Square and Multiply**

$\text{while } b \> 0: \\ \quad\quad \text{if } b \equiv 1 \pmod{2}: \\ \quad\quad\quad\quad t \leftarrow t \cdot x \pmod{N} \\ \quad\quad ~ x \leftarrow x^2 \pmod{N}\\ \quad\quad ~ b \leftarrow b \ \text{div} \ 2\\ \text{return } t $

---
Tags: reference-request, discrete-mathematics
---


title: Find the Unambiguous Grammar

text:
# Question
Title: Find the Unambiguous Grammar
Consider the following grammar: S-\>A.
A-\>A+A|B++.
B-\>y

Check whether grammar is Ambiguous or not? Also ,unambiguate the grammar.Now please tell me what will be the grammar after removing the ambiguity.

I have worked over here and i am able to draw two parse trees for the input string w=y+++y+++y++

# Answer
In general, disambiguating a grammar is more of an art than a science, especially since it's known that there is no possible algorithm that will correctly decide whether a given grammar is ambiguous. For simple grammars like yours, though, there are some techniques that will work.

First, let's simplify your grammar purely for ease of explanation, replacing it with $$ S\rightarrow A\quad A\rightarrow A+A\mid z $$ where the terminal $z$ will represent your "$y++$". This is ambiguous, since the string $z+z+z$ gives rise to two different parse trees \[*Hint 1*: do a leftmost derivation and a rightmost derivation of that expression and look at the resulting parse trees.\]

The problem here is that in a derivation with $\Rightarrow A+A+\dotsm+A\Rightarrow$, we'll have too many choices for which of the $A$ variables to replace, generally giving us different parse trees depending on what choice we make. We need to change the grammar so as to eliminate those possible choices.

The key here is that your grammar will generate all and only strings of the form $z+z+\dotsm +z$, with 1 or more $z$'s. Can you find another grammar that will generate these strings, so that the right side of any production contains only at most a single variable and perhaps some terminals? \[*Hint 2*: you can do this with a grammar having only one variable.\]
> 0 votes

# Answer
The grammar can be tested for ambiguity by drawing parse trees for a string in the language. If multiple parse trees exist for a given string the grammar is ambiguous.

For removing the ambiguity in the grammar you can introduce precedence in the production rules.

This looks like a homework though. Hope the answer helps you in solving the same.
> 0 votes

---
Tags: formal-grammars, compilers, ambiguity
---


# Question
Title: Feature detector that doesn't use corners
I'm trying to use computer vision to identify objects an image. I am currently using the SURF algorithm, but Harris and SURF both find virtually no points on our objects (a paper ball and a deodorant can) due to their simple features. If it does find points it finds one or two that aren't the same points it find in the new frame. SURF also finds a large amount of points on our floor due to the contrast of the black dots on the carpet. Here's a sample image:

Is there a feature detector that *doesn't* use corner detection/curvature?

# Answer
> 2 votes
If you have prior knowledge of the objects expected size you should ignore interest points of too small scale. I think these objects (thanks to round shape and contrast with the background) it should be an easy task for blob detection algorithms, you'd get one detected blob / item. Note that for SIFT or SURF the major orientation isn't well defined for blobs with rotational symmetry but it might be sufficient to assume fixed orientation (like on U-SURF).

---
Tags: computer-vision
---


title: Algebraic data types - unions

text:
# Question
Title: Algebraic data types - unions
Are there any programming languages where algebraic data types can be expressed not only by using intersection and disjoint union but also a standard set union (intersection + disjoint union)?

Do such types even make sense?

If so, could you provide practical example of use?

# Answer
> 5 votes
Yes, these type systems exist. They're generally referred to as "Set-theoretic Type Systems", and there's a good rundown of them here. They've been extended a lot, particularly with regards to subtyping and datasort-refinement types.

For a practical application of them, checkout their use in TypeScript.

Basically, union types correspond to untagged unions, and intersection types are a single value that matches two types. So we have rules that look like this:

* If $v : T\_1$, then $v : T\_1 \cup T\_2$ for any $T\_2$
* If $v : T\_1$ and $v : T\_2$, then $v : T\_1 \cap T\_2$

These are both commutative, so there's a symmetric union rule.

Note the difference between normal types: the unions here are untagged, and we have *very little* information when using a value of a union type, since we have no runtime way of determining which half of the union it is.

Likewise, a value matching an intersection type is not a pair, it's a single value that happens to typecheck against both of the types in the intersection.

Under this formulation, we can treat polymorphic and existential types as infinite intersections and unions:

* $\forall a \ldotp T$ is $\bigcap\_{S \in TYPE} \[S/a\]T$
* $\exists a \ldotp T$ is $\bigcup\_{S \in TYPE} \[S/a\]T$

That is, if a value typechecks against a polymorphic type, then it checks against any instance of that type. And if a value typechecks against an existential type, there must be some concrete type that it typechecks against.

As you might expect, introducing these usually makes type inference undecidable, though there is a lot of research going on in this area that I will not claim to be an expert in.

---
Tags: type-theory, type-checking
---


# Question
Title: Algorithm to find maximum number of floors you can check with N eggs and D maximum drops
Question: You are given access to a multistory building. You have N eggs and are allowed D maximum drops from their window.

Rules: If a egg is dropped from window of floor F and it breaks, it will break for all floors \> F.

If an egg is dropped from window of floor F and survives, it will survive for all floors \< F.

What is the maximum number of floors you can check in the worst-case?

E.g: With 1 egg and 5 drops, you can check at most 5 floors (1, 2, 3, 4, 5)

With 2 eggs and 5 drops, you can check at most 9 floors (2, 4, 6 ,8, 9)

EDIT: By "maximum floors you can check", I mean the highest floor for which you can guarantee that you know the outcome for all floors \<= to it. For. e.g in N = 1, D = 5 case, there is no algorithm that guarantees you will know the outcome at every floor \<= 6 in the worst case. This is because in the worst-case: drops from 6, 5, 4, 3, 2 break and you don't know what will happen at floor 1 since you have no more drops left.

My solution is as follows

```
findMaxFloors(N,D)
{
 nextFloor = 0

 while (D > 0)
 {
    nextFloor += MIN(N, D);
    D = D-1;
 }

 return nextFloor;
}

```

But the solution given on the forum is more complicated (using recursion) `maxFloors(N+1,D) = maxFloors(N, D-1) + 1 + maxFloors(N+1, D-1)`

I would appreciate any suggestions on the conditions under which my solution won't work.

# Answer
> 7 votes
First we'll clarify the problem a bit. We have $n$ eggs, which we can drop from any floor we want. We also have the constraint that we are allowed a **total** of $d$ drops of these eggs (rather than $d$ drops per egg). Obviously, when we drop an egg and it breaks, we can't drop it again. Let $f(n,d)$ be the maximum number $M$ such that with $n$ eggs and $d$ drops, we can completely describe the behavior of our experiment for floors $1,\dotsc,M$.

In other words, with $M=5$ the possible outcomes are \[YYYYY\] (the eggs break when dropped from all 5 floors), \[NYYYY\] (the egg survives a drop from floor 1 but no higher floor), and \[NNYYY\], \[NNNYY\], \[NNNNy\], and \[NNNNN\]. Obviously, in all possible descriptions, all the N's must come before all the possible Y's

With that out of the way, let's tackle the recursion $$ f(n,d)=f(n-1,d-1)+1+f(n,d-1) $$ Our plan of attack is to drop the first egg from floor $x$, yet to be determined. That egg either breaks or doesn't:

1. If it breaks, we know it will break when dropped from any higher floor as well, so we're left with $n-1$ eggs and $d-1$ more drops. In other words, we're looking at the lower floors and there will be $f(n-1,d-1)$ of them, namely floors $1, 2,\dotsc, f(n-1,d-1)$.
2. Since we've already settled the behavior at floor $x$, we need to have $x=f(n-1,d-1)+1$.
3. If it doesn't break, we know it won't break when dropped from a lower floor, so we still have $n$ eggs and $d-1$ drops remaining, which will mean that we can determine the behavior of the higher $f(n,d-1)$ floors. They will start at floor $x+1$ and will cover floors $x+1, \dotsc, x+f(n,d-1)=f(n-1,d-1)+1+f(n,d-1)$, exactly as the recursion stated.

For example, you correctly observed that $f(1,5)=5$ but your value for $f(2,5)$ was low. In fact, $f(2, d)=d(d+1)/2$, which is 15 in the case where $d=5$. Start with the first drop from floor 5, and you'll see that you can indeed determine the egg behavior at all of the first 15 floors.

---
Tags: algorithms, recursion
---


# Question
Title: Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min() Why?
I just found out by luck that

```
 Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min()

```

For example, Consider a sorted array, {1 43 65 97 98 99 101}

Abs(1-43-55-97-98-99-101)= 101-1

Does anyone know why?

Thanks in Advance.

# Answer
If you picture these as distances along a road, it should be very intuitive.

If (for example) you start at kilometer #7, then proceed through kilometers #45, #81, and #97, then the distances you travel are 45−7, then 81−45, then 97−81; and the total distance you travel is 97−7. Since the total distance is the sum of the individual distances, 97−7 = (45−7) + (81−45) + (97−81).

This only works for a sorted set, because otherwise you have backtracking, where you cover a certain distance and then "un-cover".
> 4 votes

---
Tags: arrays, mathematical-analysis, mathematical-programming
---


# Question
Title: Do the time and space complexities of a language depend on the Turing machine which is its recognizer?
From Ullman and Hopcroft's *Introduction to automata theory, languages, and computation*

> Consider the off-line Turing machine M of Fig. 12.1. M has a read-only input tape with endmarkers and k semi-infinite storage tapes. If for every input word of length n, M scans at most S(n) cells on any storage tape, then **M is said to be an S(n) space-bounded Turing machine**, or of space complexity S(n). **The language recognized by M** is also said to be of space complexity S(n).
>
> Consider the multitape TM M of Fig. 12.2. The TM has k two-way infinite tapes, one of which contains the input. All tapes, including the input tape, may be written upon. If for every input word of length n, M makes at most T{n) moves before halting, then **M is said to be a T{n) time-bounded Turing machine**, or of time complexity T(n). **The language recognized by M** is said to be of time complexity T(n).

If I am correct, a language can be the one recognized by several Turing machines.

Do the last sentences in the two paragraphs assume that for a language, all of its recognizer TMs have the same time complexity and the same space complexity?

* Is the assumption true?
* If the assumption is not true, do the sentences imply taking supremum of the complexities over all of the recognizer TMs of the language?

Thanks.

# Answer
Yes, you are correct. I applaud your careful reading.

This reading is most obvious if we view a TM as an algorithm (which they are). Clearly, for any computational problem, some algorithms are more efficient than others. Compare bubble sort to merge sort, for example.

But their definition is not *wrong*, just perhaps a little misleading. Any algorithm can provide a time-bound on a decision problem; but only one of them will be the *lowest* bound.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Is the following extension of finite state automata studied?
Consider a finite state machine as usual, but every transition, it can also update an integer counter by adding or subtracting a number. Say, a transition function of the form $\delta(q,a) = (p,k)$ moves to the new state $p$, and add $k$ to the counter, where $k \in \mathbb{Z}$ (so $k$ can be positive, negative, or zero).

A string is accepted if the final state and the counter value is in $F$, where $F$ is a finite set of pairs of states and counter values.

Is this model known? I could not find any reference of this particular extension.

# Answer
Assuming $k$ can be any integer, then this can be formalized as a *blind one-counter automaton*. Usually these automata accept on final state when its counter is zero, but we can easily model your acceptance type if you allow $\epsilon$ transitions (that do not consume input). If I am not mistaken, like with finite state automata, one can get rid of the $\epsilon$, but that is a non-trivial result.

There are several types of one-counter automata. In the most general form they are allowed to test whether the value of the counter equals zero. The languages they accept are a strict subset of the context-free languages.

The model you are probably looking for is called *blind*, it cannot test for zero, except as the final test for acceptance at the end of the computation.
> 11 votes

# Answer
This model is a variant of weighted automata, which are widely studied (although there are a lot of open questions about them). You can start here: Handbook of Weighted Automata.

Note that sometimes they are called "distance automata" (although this is becoming less common).
> 8 votes

---
Tags: finite-automata
---


# Question
Title: How do I interpret this formal languages definition?
Given the formal language

$L\_1 = \\{wcw | w\in \\{a,b\\}^+\\} $

Does this definition requires $w$ to be exactly the same before and after the terminal character $c$ or can it be different?

Example:

Are $aabca$ or $abca$ accepted words of $L\_1$, or only words like $aabcaab$ or $aca$?

# Answer
It's the same $w$. You can think of this language in a \`\`procedural'' way: it is formed by taking every word $w\in \\{a,b\\}^+$, and for each such word, adding to the language the word $wcw$.

Typically, sets (and languages in particular) are described as $\\{x: \text{condition on } x\\}$, which is pretty clear. However, it is sometimes more convenient to \`\`push'' the condition into the description of an element.

That is, you could describe the same language as: $$\\{x\in \Sigma^\*:\ \exists w\in \\{a,b\\}^+\wedge x=wcw\\}$$ Or even worse: $$\\{\sigma\_1\cdots \sigma\_n: \exists k\ge 1,\ n=2k+1\wedge \sigma\_1\cdots\sigma\_k=\sigma\_{k+2}\cdots\sigma\_{2k+1}\wedge \sigma\_{k+1}=c\wedge \forall 1\le i\le k,\ \sigma\_i\in \\{a,b\\}\\}$$

But obviously this is much more cumbersome than the original description.
> 4 votes

---
Tags: formal-languages
---


# Question
Title: What are the gap functions in the $AC$ hierarchy?
Hastad had in 1985 shown that PARITY(n) if it has to be evaluated by a depth$-d$ $AC^0$ circuit needs a size $\Theta(2^{n^{\frac{1}{d-1}}})$. But PARITY is in $NC^1$ and PARITY is also the negation of the MOD2 and hence this shows that the following inclusions are strict, $AC^0 \subset AC^0\[2\] \subset NC^1$.

* If I understand right then Razborov's 1987 result of exponential size lower bound for MAJORITY for $AC^0\[2\]$ or Smolensky's similar result in 1986 for MOD3 for $AC^0\[2\]$ do not in anyway strengthen the inclusion consequence of Hastad's result. Am I right?
* But do we know whether $AC^i$ vs $AC^{i+1}$ separation is strict or not? Like do we know of functions which are exponentially sized for $AC^i$ but can be computed by polynomial sized circuits for $AC^{i+1}$?

# Answer
Razborov-Smolensky prove that the classes $\mathrm{AC}^0\[p\]$ and $\mathrm{AC}^0\[q\]$ are incomparable when $p$ and $q$ are distinct primes, which also implies $$\mathrm{AC}^0\subsetneq\mathrm{AC}^0\[p\]\subsetneq\mathrm{ACC}$$ for prime $p$. That's about it: it is consistent with the present knowledge that uniform $\mathrm{AC}^0\[6\]$ coincides with all of the polynomial hierarchy PH, so no classes in between have been unconditionally separated (uniformly or nonuniformly).
> 3 votes

---
Tags: complexity-theory, computability, time-complexity, np-complete, circuits
---


title: What is induction-induction?

text:
# Question
Title: What is induction-induction?
What is *induction-induction*?

The resources I found are:

The first two references are too brief for me, and the latter two are too technical. Can anyone explain it in layman's term? It would be better if there's Agda code.

# Answer
**Supplemental 2016-10-03:** I mixed up induction-induction and induction-recursion (not the first time I did that!). My apologies for the mess. I updated the answer to cover both.

I find the explanations in the Forsberg & Setzer's paper A finite axiomatisation of inductive-inductive definitions illuminating.

### Induction-recursion

An inductive-recursive definition is one in which we define a type $A$ and a type family $B : A \to \mathsf{Type}$ simultaneously in a special way:

1. $A$ is defined as an inductive type.
2. $B$ is defined by recursion on $A$.
3. **Crucially,** the definition of $A$ may use $B$.

Without the third requirement, we could first define $A$ and then separately $B$.

Here is a baby example. Define $A$ inductively to have the following constructors:

* $a : A$
* $\ell : \big(\sum\_{x : A} B(x)\big) \to A$

The type family $B$ is defined by

* $B(a) = \mathtt{bool}$
* $B(\ell(x, f)) = \mathtt{nat}$.

So, what is in $A$? First of all we have an element $$a : A.$$ Because of that, there is a type $B(a)$ which is defined to be $\mathtt{bool}$. Therefore, we can form two new elements $$\ell(a, \mathtt{false})$$ and $$\ell(a, \mathtt{true})$$ in $A$. Now we have $B(\ell(a, \mathtt{false})) = B(\ell(a, \mathtt{true})) = \mathtt{nat}$, so we can also form for every $n : \mathtt{nat}$ the elements $$\ell(\ell(a, \mathtt{false}), n) : A$$ and $$\ell(\ell(a, \mathtt{true}), n) : A$$ We can keep going like this. The next stage will be that since $$B(\ell(\ell(a, \mathtt{true}), n)) = \mathtt{nat}$$ there is for every $m : \mathtt{nat}$ the element $$\ell(\ell(\ell(a, \mathtt{true}), n), m) : A$$ and the element $$\ell(\ell(\ell(a, \mathtt{false}), n), m) : A$$ We can keep going. A little bit of thinking reveals that $A$ is more or less two copies of lists of natural numbers, sharing a common empty list. I will leave it as an exercise to figure out why.

### Induction-induction

An inductive-inductive definition also defines a type $A$ and simultaneously a type family $B : A \to \mathsf{Type}$:

1. $A$ is defined inductively
2. $B$ is defined inductively, and it may refer to $A$
3. **Crucially,** $A$ may refer to $B$.

It is important to understand the difference between induction-recursion and induction-induction. In induction-recursion we define $B$ by providing equations of the form $$B(\mathsf{c}(\ldots)) = \cdots$$ where $\mathsf{c}(\ldots)$ is a constructor for $A$. In an inductive-inductive definition we define $B$ by providing constructors for forming the elements of $B$.

Let us reformulate our previous example as induction-induction. First we have the inductively given tpye $A$:

* $a : A$
* $\ell : \big(\sum\_{x : A} B(x)\big) \to A$

The type family $B$ is defined by the following constructors:

* $\mathsf{Tru} : B(a)$
* $\mathsf{Fal} : B(a)$
* if $x : A$ and $y : B(x)$ then $\mathsf{Zer} : B(\ell(x,y))$
* if $x : A$ and $y : B(x)$ and $z : B(\ell(x,y))$ then $\mathsf{Suc}(z) : B(\ell(x,y))$.

As you can see, we gave rules for generating the elements of $B$ which amount to saying that $B(a)$ is (isomoprhic to) the booleans, and $B(\ell(x,y))$ is (isomorphic to) the natural numbers.
> 18 votes

---
Tags: type-theory, induction, inductive-datatypes
---


# Question
Title: "Regular languages over a common alphabet are closed under union."
I just want to make sure I understand what this means. I am new to Formal Languages and this is my first week of courses.

Suppose we have two regular languages, $L\_1$ and $L\_2$, with a common alphabet.

The `union` of $L\_1, L\_2$ is $\\{x:x∈L\_1∨x∈L\_2\\}$

Does this mean that, for any string $s \in L\_1$, we also have $s \in L\_2$?

# Answer
I see two possible points of confusion in your question, and I will address them separately.

1. What is meant by the title of your post: ""Regular languages over a common alphabet are *closed under union*."
2. "The union of $L\_1,L\_2$ is $\\{x:x∈L\_1∨x∈L\_2\\}$ Does this mean that, for any string $s∈L\_1$, we also have $s∈L\_2$?"

## What is "Closure Under Union"?

Regular languages are a *class* of languages that exhibit the closure property with the union operation.

The *closure property* means that when an operation is applied to language(s) of a certain class the resulting language will also be of that class.

In this case the class of languages is the regular languages and the operation is union.

So all this means is that **the union of two regular languages is also a regular language.**

## What is the union of two languages?

Languages can be thought of as sets of strings, so the union operation works the same way as in typical Set Theory.

I would read $\\{x:x∈L\_1∨x∈L\_2\\}$ as "the set of strings such that the string is in $L\_1$ **or** the string is in $L\_2$."

This does **NOT** mean that for any string $s∈L\_1$, we also have $s∈L\_2$.

We only have that for any string $s$ in the union of languages $L\_1$ and $L\_2$, denoted $s \in (L\_1\cup L\_2$), that string $s$ is in either $L\_1$ **or** $L\_2$.
> 9 votes

---
Tags: regular-languages, sets, mathematical-foundations
---


# Question
Title: Ternary decision tree for the lower bound of comparison sort with 3-way comparisons
All the proofs I've seen about the Ω(nlgn) lower-bound for comparison sorts use binary decision tress like this (from CLRS textbook)

Now what if each comparison yields strictly 3 outcomes, i.e. `<`, `=`, `>`? (the input array is allowed to contain repeated elements)

The bound is probably still Ω(nlgn), but I'm not sure how one would draw the (not necessarily full) ternary decision tree (still with unique leaf nodes); this kind of tree is mentioned in the proof of the water jug problem.

# Answer
> 1 votes
The proof would be exactly the same, using a ternary tree (where each internal node has *three* children) instead of a binary tree. A ternary tree of depth $d$ has at most $O(3^d)$ notes, so a sorting tree would have to satisfy $n! = O(3^d)$, which implies that $d = \Omega(n\log n)$.

---
Tags: time-complexity, sorting, trees
---


# Question
Title: Do the Turing machines involved in Chruch-Turing thesis have to halt on all the inputs?
The following is Church-Turing Thesis from two books.

Is it correct that

* The first book seems to say that the Turing machines involved in the thesis may or may not halt on a given input,
* the second book says that the Turing machines involved in the thesis must halt on all the inputs?

Do the two books contradict each other? Why?

Thanks.

From Ullman and Hopcroft's *Introduction to Automata Theory, Language, and Computation* 1ed 1979

> Note that one TM may compute a function of one argument, a different function of two arguments, and so on. Also note that if TM M computes function f of k arguments, then f need not have a value for all different k-tuples of integers. ...
>
> In a sense,
>
> * **the partial recursive functions** are analogous to **the r.e. languages**, since they are computed by **Turing machines that may or may not halt on a given input**.
> * **The total recursive functions** correspond to **the recursive languages**, since they are computed by **TM's that always halt**.
>
> ...
>
> The assumption that **the intuitive notion of "computable function"** can be identified with **the class of partial recursive functions** is known as Church's hypothesis or **the Church-Turing thesis**.

From Lewis and Paradimitriou's *Elements of The Theory of Computation*

> However, we have also seen in the last chapter that not all Turing ma machines deserve to be called "algorithms:" We argued that Turing machines that semidecide languages, and thus reject by never halting, are not useful computational devices, whereas Turing machines that decide languages and compute functions (and therefore halt at all inputs) are. Our notion of an algorithm must exclude Turing machines that may not halt on some inputs.
>
> *We therefore propose to adopt **the Turing machine that halts on all inputs** as the precise formal notion corresponding to **the intuitive notion of an "algorithm"**.* Nothing will be considered an algorithm if it cannot be rendered as a Turing machine that is guaranteed to halt on all inputs, and all such machines will be rightfully called algorithms. This principle is known as **the Church-Turing thesis**.

# Answer
The Church-Turing thesis is an informal notion so it is not strange to see different authors taking slightly different positions.

To me, the second definition makes a bit more sense: CT tries to characterize "functions that are calculable in all cases", and for instance, we don't consider lets say, second order unification computable. The halting problem also falls in that category so I really wonder what do the authors mean.

Some interesting recent discussion about CT can be found in this thread: http://www.cs.nyu.edu/pipermail/fom/2016-August/020027.html
> 3 votes

---
Tags: computability
---


title: Find a Minimal Set of Combined Tuples

text:
# Question
Title: Find a Minimal Set of Combined Tuples
**Suppose I have a set of *n* ordered tuples, all of the same, fixed dimension**. The tuples' values are integers, with `#`s indicating an integer I don't care about. For example:

> { (1,2,5), (4,2,3), (1,2,#), (#,2,3) }

**Tuples can be combined so long as they don't disagree about anything**. For example, `(1,2,#)` and `(#,2,3)` can be combined into `(1,2,3)`. Therefore, we can simplify the above set by combining the last two elements:

> { (1,2,5), (4,2,3), (1,2,3) }

**The goal is to simplify the set as much as possible**. We can't simplify from here any more, but by simplifying in a different way, we could have done better by combining the 1st with the 3rd and the 2nd with the 4th (hence, this problem is not convex):

> { (1,2,5), (4,2,3) }

---

My question:

1. **Is this a well-known problem by a different name?** (E.g., give a reduction from some NP-complete problem, perhaps?) It's related to the set-cover problem, but somewhat different since elements can be combined and not everything need be chosen.
2. **What algorithms can I use to solve this, even approximately?** Speed is important; I solved a similar, simpler problem in expected O(n); equivalent performance would be ideal.

---

Call tuples containing at least one `#` "free tuples" (vs. "complete tuples"). **Observation: WLOG every tuple is free**: combining a free tuple with a complete tuple or a complete tuple with a complete tuple is never suboptimal, so we can preprocess all such combinations first, then remove all complete tuples--since by construction, nothing can combine with them.

# Answer
I am not aware of whether this problem has a name or not, but it can be shown that it is NP-complete by reduction from the maximum independent subset problem:

Given an undirected graph of $N$ vertices and $M$ edges, we can map the nodes to a set of $M$-tuples $\\{x\_1,...,x\_n\\}$ such that any two tuples are "compatible" if and only if the corresponding nodes do not share an edge:

* Given $i$-th undirected edge $\\{a,b\\}$ with $ a\leq b$ we set $x\_{a}\[i\]$ to 1 and $x\_{b}\[i\]$ to 2.
* Any element that remains unset by the previous rule is set to #.

Now:

* For each pair of nodes that share an edge, the corresponding tuples will not be compatible because they have different values in the position corresponding to the edge.
* For each pair of nodes that do not share an edge, for each position in the tuples at least one of them has # assigned in that position. Hence,they will be compatible.

By definition:

* An independent subset of the graph is such that it does not contain two nodes that share an edge.
* A compatible subset of tuples is such that it does not contain two tuples that are not compatible.

Hence a subset of nodes is independent if and only if the corresponding subset of tuples is compatible. Then, the size of the maximum independent set in the original graph is equal to the size of the maximum set of compatible tuples.
> 3 votes

# Answer
It seems to me this is the minimum set cover problem. https://en.wikipedia.org/wiki/Set\_cover\_problem

where the universe to cover is the union of the elements of each of the tuples. It is known to be NP-Complete so there aren't known algorithms to solve it in polynomial time.
> 0 votes

---
Tags: algorithms, approximation
---


# Question
Title: What is the simplest example of a prob whose complement does not have the same complexity?
Firstly it is my understanding that the complement of a problem is simply the "reverse" question. So the complement of "Is the sky blue?" would be "Is the sky not blue?". Is my understanding correct?

If so, how can a complement ever be more or less complex than the original problem? Please include the simplest example that you can think of.

# Answer
> 1 votes
The notion of "complex" depends entirely on your model of computation. For example, if you're using DFAs, then by just about every conceivable measure every problem has the same difficulty as its complement. On the other hand, if you're using PDAs as your model of computation, many languages can be recognized by a PDA even though their complements can't. For example, the language

> { ww | w ∈ {a, b}\* }

is not recognizable by any PDA, but its complement is.

In the land of **NP**, we don't know much about the relative difficulties of problems and their complements. It's an open problem whether the complements of any **NP**-complete problems are in **NP**.

Looking at decidability, a problem is decidable if and only if its complement is decidable. However, the same is not true of recognizability. The halting problem is recognizable, but its complement isn't.

---
Tags: complexity-theory
---


# Question
Title: Not sure how to interpret the question: how to find egg-breaking height
I have the below homework question as an assignment of my Computer Science Foundation class.

> Throwing eggs from a building. Suppose that you have an N story building, and plenty of eggs. Suppose also that an egg is broken if it's thrown off floor F or higher, and intact otherwise. First devise a strategy to determine the value of F such that the number of broken eggs is ~lg N when using ~lg N throws, then find a way to reduce the cost of ~2lg F when N is much larger than F.

I'm not entirely sure what the question is asking for. I believe, and what I attempted, is to provide an algorithm as a solution that has a runtime of log N.

From the description of the problem, I attempted to write a binary tree implementation. I'm not sure if this is correct. I'm not asking for an answer, but perhaps some guidance on what the problem is looking for.

# Answer
In this task, the resources that you care about are not running time, but rather the number of throws and the number of eggs broken (in the worst case). Here is an example. Suppose that $N = 2$. An optimal algorithm, which throws at most two eggs and breaks at most one egg, goes as follows:

1. Throw an egg from floor 1. If it breaks, the answer is $F=1$. Otherwise, continue.
2. Throw an egg from floor 2. If it breaks, the answer is $F=2$. Otherwise, the answer is $F=3$.

(If $F=3$ is not a possibility, then we need only one throw.)

In this way, we can determine $F$ using at most $\sim N$ throws and one broken egg. There is a way to improve the number of throws to only $\sim \log N$, at the cost of potentially breaking up to $\sim \log N$ eggs.
> 0 votes

---
Tags: algorithms, searching
---


# Question
Title: Examples for lower bounds proof except sorting
After i read this question here.

All non-trivial examples of lower bounds always mention sorting, but i do not find other non-trivial examples, which do not rely (partly) on the sorting proof.

What are other non-trivial examples?

# Answer
Here are some examples:

1. Finding an element in a sorted list takes time $\Omega(\log n)$ in the RAM model.
2. Implementing a disjoint sets data structure requires an amortized $\Omega(\alpha(n))$ operations in the cell probe model.
3. Determining whether the input string is a palindrome requires $\Omega(n^2)$ operations on a single tape Turing machine.

There are many others.
> 5 votes

---
Tags: complexity-theory, lower-bounds
---


# Question
Title: How to measure the degree of randomness in Disk I/Os?
Most disk-based system's performance heavily depends on its disk access patterns. So maximizing the sequential I/Os while avoiding the random I/Os is a typical goal in performance perspective. I am working on the same problem.

I have some difficulties in measuring the degree of randomness of Disk I/Os. I can measure the disk throughputs in MB/sec using the performance monitoring tools. However, MB/sec is a result of such and such possible causes including the disk access patterns. I want to directly measure how much random disk I/Os are occurring at a certain moment.

Is there any metric that is commonly used to represent the degree of randomness in Disk I/Os?

If there is, how can I measure those?

# Answer
I am not aware of any formal discrete metrics of spatial and/or temporal locality of reference. Maybe someone else can enlighten us on that.

Often I see metrics used that are relevant to the particular platform you're studying. So the metric is either 'L1 cache misses', 'branch mispredicts', 'hard drive head movement', etc. You can google how to measure those.

You can make ad-hoc models by saving the location of your read/writes and applying penalties if those locations (or 4K blocks around those locations) haven't seen I/O recently.
> 1 votes

---
Tags: performance
---


# Question
Title: Are partial recursive functions analogous to recursive languages or r.e. languages?
From Ullman and Hopcroft's *Introduction to Automata Theory, Language, and Computation* 1ed 1979:

1. > The assumption that **the intuitive notion of "computable function"** can be identified with **the class of partial recursive functions** is known as Church's hypothesis or **the Church-Turing thesis**.
2. > A problem **whose language is recursive** is said to be **decidable**. Otherwise, the problem is undecidable. That is, a problem is undecidable if there is no **algorithm** that takes as input an instance of the problem and determines whether the answer to that instance is "yes" or "no."
3. > Note that one TM may compute a function of one argument, a different function of two arguments, and so on. Also note that if TM M computes function f of k arguments, then f need not have a value for all different k-tuples of integers. ...
>
> In a sense,
>
> * **the partial recursive functions** are analogous to **the r.e. languages**, since they are computed by Turing machines that may or may not halt on a given input.
>     * **The total recursive functions** correspond to **the recursive languages**, since they are computed by TM's that always halt. ...

How do these go together?

1. From the following first two quotes

* The first quote says that computability can be identified with the class of partial recursive functions,
    * the second quote seems to say that computability can be identified with recursive languages.

    Note that the second quote says about decidability while here I uses computability, so I assume that computability and decidability are the same or consistent concepts, but is it true?

Do they imply that partial recursive functions and recursive languages are analogous to each other, as far as computability/decidability is concerned?
2. The third quote says that "in a sense",

* the partial recursive functions are analogous to the r.e. languages
    * The total recursive functions correspond to the recursive languages.

Does the third quote contradict the implication from the first two quotes as pointed out above in part 1?

In what "sense", does the third quote mean?

For my related confusion about the third quote, see Do the Turing machines involved in Chruch-Turing thesis have to halt on all the inputs?

# Answer
> 6 votes
Let me quote from the second edition of the same textbook, section 9.1 (sorry, I don't have the first one):

> Recall that a language L is recursively enumerable (abbreviated RE) if L = L(M) for some TM M. Also, we shall in Section 9.2 introduce "recursive" or "decidable" languages that are not only recursively enumerable, but are accepted by a TM that always halts, regardless of whether or not it accepts.

Therefore recursive languages are associated to total recursive functions, not partial.

Hope this answers both the questions.

EDIT: to answer the comment:

On the one hand, the reason lies on intuition: the Church-Turing thesis is about capturing the intuitive idea of "effective computability" or "things that we can *actually* compute". Imagine a program that, if *there is* a correct answer then it computes the answer, otherwise it never halts (i.e. it gives an answer only if *there is* an answer). Would you say that such a program computes the answer or not?

But on the other hand, if this intuitive picture doesn't convince you, consider the following (way more concrete): consider an effective enumeration $(\varphi\_i)\_{i\in\mathbb{N}}$ of all total recursive functions and consider the function $\varphi:=x\mapsto\varphi\_x(x)+1$. Now it is clear that you can compute $\varphi$: you can find the $x$-th function, you can compute it (as it is recursive) and you can sum 1 (as sum is recursive). But $\varphi$ cannot be total by a diagonal argument: if it were total than it would have its own index $i$, therefore

$$ \varphi(i) = \varphi\_i(i)+1 = \varphi(i) +1 $$

which is a contradiction. This problem vanishes if you consider instead partial functions.

# Answer
> 3 votes
A language $L$ is r.e. if and only if $L$ is the domain of some partial recursive function. That is, iff there's a program halting on $L$ and nowhere else.

A language $L$ is recursive if and only if it is the support of a total recursive function. The support of a function $f$ is the set of points where $f$ is nonzero, i.e. $\\{n\ |\ f(n)\neq 0 \\}$.

Alternatively, you can consider the characteristic and semi-characteristic functions of a set $L$, defined as follows:

$$ \chi\_L(x) = \begin{cases} 1 & \mbox{if $x \in L$}\\ 0 & \mbox{otherwise} \end{cases} \qquad \tilde{\chi}\_L(x) = \begin{cases} 1 & \mbox{if $x \in L$}\\ {\sf undefined} & \mbox{otherwise} \end{cases} $$ Then, we have that $L$ is recursive iff $\chi\_L(x)$ (which is total) is a recursive function. We also have that $L$ is r.e. iff $\tilde{\chi}\_L(x)$ (which is partial) is a recursive function.

# Answer
> 2 votes
To say that the notion of computable (number, function) is *intuitive* comes from the fact that it is not originally a mathematical concept - which is why your question belongs here, and not on math.se. Partial recursive functions define computability the same way a (formally stated) drawing method can be said to define what "circularity" is, within the context of an axiomatic geometrical theory.

There is no contradiction between the two first quotes, they just talk about different things. Things that are computable can be thought of as those that can be associated to a partial recursive definition, *a posteriori*. Logical predicates ("problems") that are decidable are those whose truth values can be obtained by a specific method, which has to be formally definable by a total recursive function, also *a posteriori*. They are called semi-decidable if the function is partial.

"In a sense" is there just to avoid conflating concepts that come from different domains but can be related in a strong way. Geometric shapes are not equations, but *in a sense* they can be strongly related.

---
Tags: computability, computation-models, mu-recursion
---


# Question
Title: Decidability of the language of all TMs whose languages reduce to a fixed decidable language
Given that $L\_1$ is decidable language. That means it has a TM ($M\_1$) decider. Now we consider a language, $L\_p$;

> $$L\_p = \left \\{ \langle M \rangle \mid L(M) \text{ is reducible to } L(M\_1) \right \\}$$

$L\_p$ consists of all the encodings of the Turing machines whose language is reducible to $L\_1$.

What can we say about $L\_p$, Or, $L\_p$ is decidable or undecidable ?

I understand if we assume to have a decider for $L\_p$ and using this as component if we can construct a TM which decides a problem $P$. If $P$ is already known as undecidable then we can conclude that out assumed decider for $L\_p$ does not exist.

How to come up with this reduction idea for $L\_p$ ?

# Answer
> 3 votes
Let $L\_1$ be a decidable language. Consider the class of Turing-recognizable languages

$$\mathcal{S} = \\{ L \mid L \mbox{ reduces to } L\_1 \\}$$

This class is non-trivial in the sense of Rice's theorem, as no recognizable but undecidable language can be an element of $\mathcal{S}$, and since we obviously have that $L\_1 \in \mathcal{S}$.

You can now apply Rice's theorem to get that $L\_p$ is undecidable.

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


title: What is Unique Coverage Problem?

text:
# Question
Title: What is Unique Coverage Problem?
I am trying to understand the problem statement and the approximation algorithm for the Unique Coverage Problem from these notes. I have refined the question based on the comments provided. Thanks to D.W for pointing out Exact Cover problem.

> Given a universe $U = \\{ e\_1, e\_2, \dots, e\_n\\}$ of n elements and given a collection $\mathcal{S} = \\{S\_1, S\_2, \dots, S\_m\\}$ of subsets of $U$ such that $\bigcup\limits\_{S{\_i}\in\mathcal{S}} S\_i$, is equal to $U$.
> **Exact cover** is a decisional problem of finding if there exists a sub-collection of subsets $\mathcal{S^{'}} \subseteq \mathcal{S}$, which can cover the Universe $U$ and each element $e \in U$ is contained exactly in one subset $s \in \mathcal{S^{'}}$.
> **Unique coverage problem** is to find a sub-collection $\mathcal{S}^{'} \subseteq \mathcal{S}$, such that, pairwise intersection of $s \in \mathcal{S^{'}} = \phi$ and cardinality of $\bigcup\limits\_{S{\_i}\in\mathcal{S}} S\_i$ is maximum.

My questions are,

1. Are the definitions written above correct?
2. Is the **Unique Cover Problem** a computational version of **Exact Cover**? (Exact cover requires universe $U$ to be completely covered, while Unique cover problem tries to maximize the cover of universe $U$).

From this video,I got the following example and answer for this example as 6, at duration 11:46.

> $U = \\{1,2,3,4,5,6,7,8\\}$
>
> $S\_1 = \\{1,2,5 \\}$; $S\_3 = \\{1,5,6,7\\}$
> $S\_2 = \\{1,3,8 \\}$; $S\_4 = \\{2,4,6,8\\}$

It is also mentioned in the video that the answer is 6 and its when unique cover is $\\{S\_3, S\_4\\}$, but $\\{S\_3 \cap S\_4\\} = \\{6\\} \neq \phi$.

3. Isn't the answer to above example should be either $S\_3$ or $S\_4$, whose cardinality is 4?

The algorithm given in the notes is as following:

> * Partition the elements into $\log n$ classes according to their degrees, i.e., the number of sets that cover the element. So class $i$ contains all the elements which are covered with at least $2^i$ and at most $2^{i+1}$ sets.
> * Let $i$ be the class of the maximum cardinality.
> * Choose any set with probability $\frac1{2^i}$

Applying the algorithm to above example, we get:

> $class\_1: \\{3,4,7\\}$; $class\_2: \\{2,5,6,8\\}$; $class\_3: \\{1\\}$

As cardinality of class 2 is maximum among others, we pick $i = 2$.

4. What does the algorithm mean to say,

> * Choose any set with probability $\frac1{2^i} = \frac1{4}$?
>     (the probability of what?)
5. Can anyone explain how this algorithm will give a $\mathcal{O}(log \text{ }n)$ approximation of optimal solution?

# Answer
Let's go over your questions one by one:

(1) Your definition of **Unique cover** is wrong. Given a set system $\mathcal{S}$, the goal is to find a subset $\mathcal{S}' \subseteq \mathcal{S}$ which uniquely covers the most elements. The subset $\mathcal{S}'$ *uniquely covers* an element $x$ if $x$ belongs to *exactly* one set in $\mathcal{S}'$.

(2) **Exact cover** is a decision problem, whereas **Unique cover** is an optimization problem. The decision version of **Unique cover** goes as follows:

> Given a set system and an integer $k$, is there a subset of the set system which uniquely covers at least $k$ elements?

**Exact cover** is a special case of the decision version of **Unique cover**.

(3) The sets $S\_3$ and $S\_4$ together cover $6$ elements once ($1,2,4,5,7,8$). Since $6 \> 4$, it is better to take both $S\_3$ and $S\_4$ rather than any of them individually.

(4) The probability is that of choosing any given set. I suggest you look for more material on probability theory and on randomized algorithms, and after that come back and see if it makes sense.

(5) This is explained very clearly in various lecture notes. There is no point repeating the explanation here. I suggest you learn probability theory and randomized algorithms from scratch, and then attempt to read the $O(\log n)$ analysis again. It might take a few weeks, but without catching up on the basics you have no chance of understanding anything which is even slightly advanced.
> 2 votes

---
Tags: algorithms, approximation, set-cover
---


title: Implementing Do keyword in a compiler

text:
# Question
Title: Implementing Do keyword in a compiler
I'm writting a compiler implementation for a language that you can see defined here. I having problems designing how the do keyword should be handled. You can find the code I'm referring to in here.

Let me delve a little bit into the problem. According to the documentation:

> The do keyword is used to call an expression (normally, a method call) just for its side-effect, and discards the result.

Now according to the list of possible expressions in the file I referred to before:

```
IntLit(value)
StringLit(value)
True()
False()
And(lhs, rhs)
Or(lhs, rhs)
Plus(lhs, rhs)
Minus(lhs, rhs)
Times(lhs, rhs)
Div(lhs, rhs)
LessThan(lhs, rhs)
Not(expr)
Equals(lhs, rhs)
ArrayRead(arr, index)
ArrayLength(arr)
MethodCall(obj, meth, args)
Variable(Identifier(name))
New(tpe)
This()
NewIntArray(size)

```

I want to figure out first in which cases should do act. Clearly, it should act with MethodCall as it provides a result but also with expressions that contain operators (And,Or,Plus,Minus,Times,Div,LessThan,Not,Equals,...). What would be the complete list of cases I should consider?

My second question is how can I implement Do behaviour for MethodCall, that is, not getting the result but getting the side effects.

# Answer
> 1 votes
The general idea is that `do ( expression )` is a statement that evaluates any expression and throws away the result.

A first attempt could be

```
  def evalExpr(e: ExprTree)(implicit ectx: EvaluationContext): Value =
    // ...

  def evalStatement(stmt: StatTree)(implicit ectx: EvaluationContext): Unit =
    stmt match {
      // ...
      case DoExpr(expr) =>
        evalExpr(expr)
    }
  }

```

but in this way, we return a `Value` and not a `Unit`, so the compiler raises a type error. We can fix that by using

```
      case DoExpr(expr) =>
        evalExpr(expr)
        ()  // the Unit value

```

---
Tags: programming-languages, compilers, syntax
---


# Question
Title: Complexity Theory - Why can't you use diagonalization to seperate classes A and B when an orcale O exists under which A=B?
In a recent lecture the professor stated that given two complexity classes A and B, and given the existance of an oracle O such that $$A^o=B^o$$ (As I understand, meaning that a problem in A with can be reduced to a problem in B with the oracle O), It can be shown that classes A and B can not be seperated using a diagonilization argument.

Unfortunately he did not explain much further... Can someone give the outline\thought process of the general proof (informally)? I think I understand why diagonalization fails in specific time hirearchy proof constructions (due to the existence of a cook reduction) but I can not see how to generlize this in a satisfactory way.

Thank you.

# Answer
In order to explain this, you need to understand what is meant by "diagonalization argument".

In this context, we mean a proof that only treats Turing machines as black boxes, i.e. only uses the fact that we can encode Turing machines as strings and treat them as inputs to other machines. This gives rise to the possibility of simulation, a machine $M$ can simulate some machine $M'$ without paying too much in space/time.

You can now observe that such proofs immediately generalize to the oracle model (encoding and simulation are possible), so if you could write such a proof for $A\neq B$, it would also work in the oracle model, showing $A^\mathcal{O}\neq B^{\mathcal{O}}$.

For further reading you could go to "Computational Complexity: A Modern Approach", by Arora & Barak. They have a section on limits of diagonalization.
> 3 votes

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


# Question
Title: Quantified Boolean Formula vs First-order logic
Is Quantified Boolean Formula (QBF) the same as First-order logic (FOL)?

# Answer
> 4 votes
Firstly, a quantified Boolean formula is a formula in quantified propositional logic (which consists of Boolean variables and quantifiers). A true quantified Boolean formula is a formula that can be made true (formulas have no free variables so they can be either true or false). Note that this term is also used for the true quantified Boolean formulas (TQBF) language which contains all true Boolean qualified formulas. Therefore, you probably had *a comparison of the respective logics* in mind, namely quantified propositional logic and first-order logic.

To make *a connection of quantified propositional logic and first-order logic*, let us consider predicate logic (that is more general, and includes first-order logic). When comparing propositional logic and predicate logic, a basic difference is that the latter includes a richer ontology: objects, functions and predicates on objects. (This allows more flexible and compact representation of knowledge, as expressing a binary predicate on a set of n terms might lead to n\*n terms in propositional logic.) Having this in mind, effectively, first-order logic and quantified propositional logic add quantification to propositional and predicate logic, respectively.

Consequently, from the perspective of the *comparison of the formal systems* represented by these two logics, one might consider *their expressiveness*. While quantified propositional logic is restricted to Boolean variables (that might hold either true or false), first-order logic does not have such restrictions. It can model different sets of objects (terms), together with predicates and functions on them (it is most widely used to express properties in wide range of mathematical theories). Therefore, strictly speaking, first-order logic is more expressive.

One important *distinction between these logics is in terms of decidability*. Namely, to check whether a formula in quantified propositional logic is true is decidable (the language TQBF is decidable; more specifically, it is PSPACE-complete). Unlike quantified propositional logic, first-order logic is undecidable if the language has at least one predicate of arity at least 2 (other than equality). This means that there is no decision procedure that determines whether arbitrary formulas are logically valid. (This can be shown by encoding the statement "the Turing machine T halts on empty input", which is known to be undecidable, in first-order logic.)

Note that formulas in quantified propositional logic can be *straightforwardly interpreted* in first-order logic. (This is explained in more details in this answer.)

---
Tags: logic, first-order-logic
---


# Question
Title: How to change the algorithm implication by changing the invariant?
I have this specification in GCL:

$\[Ctx C: n\geqslant 0\ \wedge\ b:\[0..n-1\]\ \text{of int}$

$\\{Q:\text{True}\\}$

$sum,i:=0,0;$

$\\{\text{Invariant}\ P: 0\leqslant i \leqslant n\ \wedge sum=\sum\_{j=0}^{i-1} b\[j\]\\}$

$\\{T:n-i\\}$

$do\ i\neq n \rightarrow\ sum, i:=sum+b\[i\],i+1;\ od$

$\\{R: sum=\sum\_{j=0}^{n-1} b\[j\]\\}$

$\]$

But then I have been requested to develop the same summation of the numbers located in $b$ but with the following invariant and dimension function ($T$):

$\\{\text{Invariant}\ P: 0\leqslant i \leqslant n\ \wedge sum=\sum\_{j=i}^{n-1} b\[j\]\\}$

and

$\\{T:i\\}$

But I don't how to proceed. What I firstly supposed is that the summation must be done in reverse order.

Some suggestion, ideas?

# Answer
> 2 votes
Well, the new invariant does not hold in the code you posted, so I guess you are asked to change the code accordingly.

> What I firstly supposed is that the summation must be done in reverse order.

That might be a wise choice. You could try something like this:

$$ \begin{array}{l} sum,i:=0,n; \\ \\{\text{Invariant}\ P: 0\leqslant i \leqslant n\ \wedge sum=\sum\_{j=i}^{n-1} b\[j\]\\} \\ \\{T:i\\} \\ do\ i\neq 0 \rightarrow\ sum, i:=sum+b\[i-1\],i-1;\ od \\ \\{R: sum=\sum\_{j=0}^{n-1} b\[j\]\\} \end{array} $$

I have not checked that this Hoare triple is valid, but it should be, possibly with some minor changes.

# Answer
> 2 votes
We wish to establish

```
R : sum = ∑ j : 0..n-1 • b[j]

```

using invariant

```
P : 0 ≤ i ≤ n ∧ sum = ∑ j : i..n-1 • b[j]

```

Well we clearly have `P ⇒ R` if we know `i = 0`, so let's use a loop with its negation as guard.

Now this loop will terminate if we reduce `i`, so let's place `i ≔ i -1` in the loop body while also attempting to maintain `P`; i.e., solve for `X` in `P ∧ i ≠ 0 ⇒ P [sum, i ≔ X , i - 1 ]`.

Indeed, let us assume `P` and `i ≠ 0` and solve for `X`:

```
  P [sum, i ≔ X , i - 1 ]
≡⟪ definition of P and substitution ⟫
  0 ≤ i - 1 ≤ n ∧ X = ∑ j : i-1..n-1 • b[j]
≡⟪ arithmetic ⟫
  1 ≤ i ≤ n + 1 ∧ X = ∑ j : i-1..n-1 • b[j]
≡⟪ Assumptions i ≠ 0 and P ensure 1 ≤ i ≤ n + 1 ⟫
  X = ∑ j : i-1..n-1 • b[j]
≡⟪ quantifiers: term split off rule ⟫
  X = b[i - 1] + ∑ j : i..n-1 • b[j]
≡⟪ assumption P yields sum = ∑ j : i..n-1 • b[j] ⟫
  X = b[i - 1] + sum

```

Hence, we have arrived at the appropriate loop-body by *mere calculation*: `sum, i ≔ b[i - 1] + sum, i - 1`.

Of course our loop will not begin if our variables are not initialized correctly, and indeed `P`, that is `0 ≤ i ≤ n ∧ sum = ∑ j : i..n-1 • b[j]` is easily truthified by setting `i ≔ 0`, since `0 ≤ n`, resulting in an empty sum and thus `sum ≔ 0`.

In summary, we have *calculated*

```
{ 0 ≤ n }
sum, i ≔ 0, n
{ Invaraint: 0 ≤ i ≤ n ∧ sum = ∑ j : i..n-1 • b[j]
  bound: i }
do i ≠ 0 → sum, i ≔ b[i - 1] + sum, i - 1 od
{ sum = ∑ j : 0..n-1 • b[j] }

```

---
Tags: algorithms, hoare-logic
---


# Question
Title: Does a language have a regular expression if and only if it is regular?
I know that if a language has a regular expression it is regular, is the other way also true?

# Answer
Yes, a language can be described as a (pure vanilla) regular expression if and only if it is regular. You can see the proof in any decent textbook on formal languages.
> 2 votes

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