# Question
Title: the convention for declaring arrays in pseudocode
I have a very simple question. What is the right standard convention to use for declaring arrays?

I understand that for a simple declaration of a variable as an integer, this is the convention:

```
DECLARE myVar : INTEGER

```

What about for an integer array of 10 elements?

```
DECLARE myVar : ARRAY[1,10] of INT

```

or

```
DECLARE myVar[1,10] : ARRAY of INT

```

or something else?

# Answer
> 9 votes
Pseudocode is not a formal language. Declare your arrays however you want, as long as it's obvious what you mean. Including the full limits (as you have in both your array examples) is good, since it means the reader isn't worrying about whether you start your indices at 0 or 1.

# Answer
> 4 votes
There are no conventions in pseudocode. You can use whatever convention you want, as long as you think that the reader can understand what you mean. If you're not sure that your convention is transparent enough, explain it.

There is no reason to use a programming-language-like convention like you give. How about:

```
$myVar$ is an integer.
$myArray$ is an array of 10 integers.

```

In the second case, you can explain that your arrays are always 1-based.

---
Tags: arrays
---


# Question
Title: Transitions needed for dividing two fixed integers
Let $Q$ be the set of states of the Turing Machine, $\Sigma$ be the alphabet, and $\\{L,R,S\\}$ be the left shift, right shift, and stay respectively.

A transition is an element of $Q \times \Sigma \times Q \times \Sigma \times \\{L,R,S\\}$ which can be read as current state, current symbol, next state, next symbol, movement direction.

For a Turing Machine I'm looking to understand how many transitions, or states since they are linearly related, are needed so that when I give integer $i \ge 0$ on the tape it outputs the $i^\text{th}$ digit after the decimal point(zero indexed) of $\frac{p}{q}$ for which $p$,$q$ are coprime. Assume it is in base $c$ and you only have the characters $0,1,\dots,c-1$ and blank. I imagine this is possible to do in $O(c\log q)$ states, but my best attempts(outlined below) only give me $O(cq)$. An example where $c=2$ and $\frac{p}{q}=\frac{1}{3}$ would be I want a binary Turing machine such that when given $10$ on the tape would output the $3^\text{rd}$ digit after the decimal point of $\frac{1}{3}$ which is $0$ and when given $110111$ would output the $56^\text{th}$ digit which is $1$.

Here is my way of doing it. For the purpose of this $\text{nt}(c,q)$ is the length of the non-terminating portion length of $\frac{p}{q}$ in base $c$, this is easily verified to be the same for all coprime $p$,$q$. Also define $\text{per}(c,q)$ as the length of the periodic portion of $\frac{p}{q}$ in base $c$

My basic idea was you check if it is less than $\text{nt}(c,q)$ and if so output that digit and halt, this takes $O(c\\,\text{nt}(c,q))$ transitions. If it's not smaller subtract out $\text{nt}(c,q)$ which takes $O(c\lfloor \log \text{nt}(c,q) \rfloor)$ transitions. Then test for what the result is modulo $\text{per}(c,q)$ and output the appropriate digit. This takes $O(c\\,\text{per}(c,q))$ transitions. Now remember that the worst case of $\text{per}(c,q)+\text{nt}(c,q)$ is $q-1$. Therefore the final transition complexity is $O(cq)$

A second idea I had was Newton's algorithm which I think would take $O(c\log q)$ transitions. The basic idea would be to output $p$,$q$,$.1$ to the tape in base $c$, convert to unary which takes $O(c)$ transitions then do multiplication and subtraction in unary which takes $O(1)$ transitions. Would this work?

# Answer
> 1 votes
Using a Turing machine compiler I wrote I devised a program to do this in $O(c\log(q))$ transitions assuming $0 \le p \< q$. More precisely it does it in $2 \lfloor \log\_2(q) \rfloor +\lfloor \log\_2(p) \rfloor + C$ states for some value $C$. I'm sure the value I found(~$409$) wasn't optimal.

The actual program itself is too long to include here(totaling $3584+18\lfloor\log\_2(q)\rfloor + 9\lfloor \log\_2(p) \rfloor$ lines) Here is the program in my pseudo language for approximating 5/9, it can be compiled with the program found here. The syntax for the language is also found there.

```
xn=1,4
while i decr {
    xnH=xn
    a=xnH
    a=a,0
    t=0,1
    while xnH decr {
        p=9,4
        while p decr {
            incr(a)
        }
        incr(t)
    }
    two=a
    two=two,2
    two=two,0
    first(two)
    while a decr {
        decr(two)
    }
    xnH=xn
    b=two
    b=b,0
    while xnH pop {
        b=b,1
        xn=xn,1
        incr(t)
    }
    pop(b)
    xn=xn,1
    while xn decr {
        p=two
        while p decr {
            incr(b)
        }
        incr(t)
    }
    xn=b
    incr(t)
}
xnH=xn
xnH=xnH,0
while xn decr {
    p=5,3
    while p decr {
        incr(xnH)
    }
    incr(p)
}
incr(xn)

```

`xnH` holds the final value(the whole thing is assumed to be after the decimal point). It shouldn't be too hard to extract out a single digit from it(in $O(1)$ states). Also as a note even for small values of `i` this program takes quite a long time to execute.

---
Tags: algorithm-analysis, turing-machines
---


# Question
Title: Are there BBP formulas for all computable numbers?
A BBP algorithm is a formula with the following form where $b \in \mathbb Z$, $b \ge 2$, and $p(k)$ and $q(k)$ are polynomials in $k$ $$\sum\_{k=0}^{\infty}\frac{1}{b^k}\frac{p(k)}{q(k)}$$ There are known BBP formulas for many computable numbers and it is easy to prove that any number with a BBP formula is computable.

Obviously all rationals have BBP formulas, let $n$ equal the length of the period in base $b$ and let $q(k)=1$ and $p(k) = \lfloor b^n\frac{p}{q}\rfloor$

I don't believe that there is a general form like that for all computable reals, i.e. you cannot given a definition of an irrational $\alpha$ derive $b$,$p(k)$,$q(k)$, but is it true that one exists for all computable numbers?

# Answer
You can easily use diagonalization to construct a computable real which is not of this form. Fix some enumeration of all triplets $(b,p,q)$. I will describe a process that generates binary digits of a real number.

The process goes over all triplets $(b,p,q)$ in the fixed order. Suppose that it's time to handle $(b\_i,p\_i,q\_i)$, and that currently we have generated the digits $\beta\_1 \dots \beta\_n$. The process evaluates the corresponding sum $S(b,p,q)$ to such a precision that the first $n+1$ binary digits can be gleaned for it. It outputs $\beta\_{n+1}$ so as not to equal to $S(b,p,q)$.

The argument as stated is not 100% correct, and I'm leaving it to the reader to discover where I cheated and to fix the proof.
> 3 votes

---
Tags: computability
---


title: Is Deciding Decidability Decidable?

text:
# Question
Title: Is Deciding Decidability Decidable?
I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem.

# Answer
**Major edit of my original:**

A naive reading of your question seems to be, let $P$ be the problem

> $P=$ Given a language, $L$, is it decidable?

Then you ask

> Is $P$ decidable?

As D.W. and David have noted, the answer is, "yes it is", though we don't know which of the two trivial deciders is the right one. In order to frame your problem so that it's not quite so trivial, I'd suggest this. First, let's restrict things slightly by considering only those languages $L(M)$ which are the languages accepted by some TM $M$. The reason for doing this is that if a language is not accepted by any TM, then it's not r.e. (recognizable) and so can't be recursive (decidable). Then we can recast $P$ as

> $P'=$ Given a description, $\langle M\rangle$ of a TM, $M$ is $L(M)$ decidable?

Now $P'$ is a language of TM descriptions, rather than a language of languages as $P$ seemed to be (under a generous interpretation), and it's now perfectly reasonable to ask whether the language $P'$ is decidable. Under this reading, the language $$ \\{\langle M\rangle\mid M \text{ is a TM and $L(M)$ is decidable}\\} $$ consisting of TM descriptions is not decidable. This is an easy consequence of Rice's Theorem. So now we have two answers: my "no" and D.W.'s "yes", depending on the interpretation.
> 10 votes

# Answer
As we have seen in the different answers, part of the answer is in formulating the right problem.

In 1985 Joost Engelfriet wrote "The non-computability of computability" (Bulletin of the EATCS number 26, june 1985, pages 36-39) as an answer to a question posed by a clever student. Unfortunately, the BEATCS was at that time paper-only and the article left no electronic traces.

The author assumes we have a (logical) formalism $\Psi$ with the usual boolean operators and variables. Its precise definition is not important. A formula $F(m,n)$ specifies a function $f:\Bbb N \to \Bbb N$ iff (for all $m,n\in \Bbb N$) $f(m)=n$ $\Leftrightarrow$ $F(\underline m,\underline n)$ is true, where $\underline m$ is the numeral representing the number $m$.

I quote:

> **Theorem 1**. Let $\Phi$ be a formalism in which both a computable and a non-computable function $\Bbb N \to \Bbb N$ can be specified. Then there is no algorithm that for an arbitrary specifiable function $f$ (given by a formula that specifies it) decides whether $f$ is computable.

The fun part is in the following observation made in the paper:

> Note that this theorem applies in particular to formalisms $\Phi$ in which *all* computable functions can be specified (a natural condition for such a formalism), because then also a non-computable function can be specified.
> 9 votes

# Answer
Yes. It's always decidable.

For any problem P, let Q be the problem of determining whether P is decidable or not. I claim that Q is decidable. Here's why. Tautologically, either P is decidable, or it isn't. So, one of the two programs is correct: (1) `print "yup P is decidable"` or (2) `print "nope P is not decidable"`. It might be non-trivial to figure out which of those two programs is correct, one of them is correct, so a decider for Q surely *exists*. Therefore, the problem Q is decidable.

This is reminiscent of the following classic question: Is it decidable to tell whether Collatz's Conjecture is true? The answer is yes. This might look odd, as no one knows whether Collatz's Conjecture is true (that's a famous open problem). However, what we do know is that Collatz's Conjecture is either true or it's not. In the former case, the program `print "yup it's true"` is a decider. In the latter case, the program `print "nope it's not true"` is a decider. We don't know which one is a valid decider, but this is enough to prove that a valid decider exists. Therefore, the problem is decidable.
> 4 votes

---
Tags: computability, undecidability, decision-problem
---


# Question
Title: Is there any relation between Global minimum cut problem and Maximal independent set?
I have simple undirected graph. I want to determine a size of `minimum vertex cover`, a size of `maximal independent set` and a size of a `global minimum cut`.

A minimum vertex cover is complementary to a maximum independent set. So, I can find one of this this and get both of them.

Is there any relation with global minimum cut? Or I have to find this size independent from other?

# Answer
Minimum cut can be computed efficiently (you haven't explained what *global minimum cut* is, but presumably it reduces to minimum $s$-$t$ cut). Minimum vertex cover (probably) cannot. So any connection would be rather indirect. Minimum cut is related to another quantity, maximum flow, which is defined more generally for weighted directed graphs. Both quantities are equal due to the fundamental max-flow min-cut theorem (sometimes known as the min-cut max-flow theorem).
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: comparison in speed between the processor and the hard disk
I'm reading through William Stalling's operating system intrnals and design principles book. Talking about interrupts, it gives the following examples when comparing the speed of a processor and a hard disk:

> To give a specific example, consider a PC that operates at 1 GHz, which would allow roughly 10^9 instructions per second. A typical hard disk has a rotational speed of 7200 revolutions per minute for a half-track rotation time of 4 ms, which is 4 million times slower than the processor.

My question is how was the result calculated? How did we know that the hard disk is 4 million times slower?

# Answer
This is to some extent a comparison between apples and oranges. The assumption is that the basic operation on a CPU takes 1 ns (since the clock frequency is 1 GHz), whereas a basic operation on the hard disk takes 4 ms. The quoted factor is just 4 ms / 1 ns = 4×106.
> 1 votes

---
Tags: computer-architecture, operating-systems, comparison
---


# Question
Title: Why is NP not trivially equal to Co-NP? (a.k.a. what does Co-NP mean exactly?)
I've been trying to wrap my head around Co-NP, and how it's different to NP, but I am having some trouble.

Co-NP is defined by Wikipedia as this: "A decision problem $\mathcal{X}$ is a member of **co-NP** if and only if its complement $\overline{\mathcal{X}}$ is in the complexity class **NP**."

When it was explained to me in class, and after reading about it, my understanding is that if a problem $\mathcal{X}$ is defined to be the answer to $x \in L$ for some $x$ and some language $L$, and $\overline{\mathcal{X}}$ is defined to be $x \notin L$ for the same $x, L$.

Am I right? If I am, how is it different to find the answer to $\mathcal{X}$ and $\overline{\mathcal{X}}$? Knowing that $\mathcal{X}$ results to true or false would tell you that $\overline{\mathcal{X}}$ results to the opposite, wouldn't it?

Edit: I believe this question to be different enough to "Why can't we flip the answer of a NDTM efficiently?" to have merit, as the discussion is being held in a different language and approach.

# Answer
**The Definitions**

This comes from the one-sidedness of the definition $NP$, that (we think) is inherent to the class.

One definition of $NP$ is the set of languages $L$ such that there is some for every $x \in L$, there exists a certificate $c$ polynomial-sized relative to $x$, and an algorithm to check if $c$ is a valid certificate that runs in polynomial time.

This definition says absolutely nothing about strings $y \not \in L$. If a word is in our language, there's some certificate. But there might not be certificates for each string not in the language.

So, if we have a magic guessing machine (aka non-determinism, the $N$ of $NP$), we can magically guess a certificate for any $x$ that is in $L$, but to show that $y$ is not in $L$, we have to iterate through all potential certificates and show that none of them are valid.

**Example**

This is probably made more clear with an example. Let's suppose we have some problem where we have two sets $A$ and $B$, and we want to test if $A \subseteq B$. Let's assume all members of $A$ and $B$ are polynomially sized, and there's a polynomial check to test if any given member is in $A$ or $B$, but there's potentially exponentially many elements in both $A$ and $B$.

This problem is in $co-NP$. Why? Because there's an easy certificate for the "no" case. If $A \not \subseteq B$, then we can just say "Look, I know it's not a subset, since I found this element in $A$ that's not in $B$".

But, to show that there is a subset, we have to go through all elements and show that none of them are in $A$ but not in $B$. So this problem is easy to certify in the no case, but hard in the yes-case.

**Implications**

Why does this matter? In practice, it tells us the direction that is easy to guess, the direction where heuristics or local search help us the most, and the direction that has the potential to be fast.

For example, consider the travelling salesman problem. Say we want a path shorter than $k$. We can use a bunch of heuristics to try to find the shortest path through all cities. If it finds one of length less than $k$, then we know the solution to the decision problem: a tour of length $k$ or less exists. If it doesn't find one, we have no extra information. There could have been some path that our heuristics missed.

$NP$ problems are ones where the "yes" instances give us this certainty, a "for-sure yes" answer. We search, and if we find one solution/certificate, we know the answer is yes. But to say no, we need to look at all certificates.

$Co-NP$ is where we are searching for a certificate that says "for-sure no", where a yes is only found by looking at all potential certificates and seeing none work.
> 9 votes

---
Tags: complexity-theory, complexity-classes, np, co-np
---


# Question
Title: Doubts about infinite language decided by a turing machine
Assume you have an infinite language $L$ over alphabet $\Sigma=\\{a,b\\}$ For example, $L=\\{ax \mid x \in \Sigma^\*\\}$

Can a Turing Machine, $M$ decide this language?

(Generalizing, are all the recursive languages finite?)

In my opinion, it can, since I can enumerate all the strings and say if they are in the language or not. However, enumerating all the strings will take infinite amount of time, so I will never end up enumerating them.

Can someone clarify this doubt?

# Answer
> 5 votes
Some infinite languages are decidable, some are not. The algorithm that you give, however, doesn't work, for two reasons:

1. When the input is not in a language, you never find out.
2. It is not always possible to enumerate all the words in $L$. A language $L$ for which this is possible is known as *recursively enumerable* (r.e.), and by many other terms. An example of a language which is not r.e. is the language of encodings of Turing machines which don't halt on the empty input. That is, $\langle M \rangle$ is in the language if $M$ never halts when running on the empty input.

In your specific example, there is a very simple Turing machine accepting $L$. The Turing machine examines the first symbol, accepts if it is $a$, and rejects otherwise.

# Answer
> 3 votes
Yes, a Turing machine can decide that langauge: it just looks at the first character and accepts or rejects without even needing to look at the rest of the string.

The question "Are all recursive languages finite?" is not a generalization of "Is this particular infinite language recursive?" The fact that $\\{ax\mid x\in\Sigma^\*\\}$ is recursive (decided by a Turing machine) and infinite (contains infinitely many strings) already shows that the answer to "Are all recursive languages finite?" is no.

To enumerate the strings in a language informally means to write them all down in a list but, as you've observed, this informal definition doesn't make a whole lot of sense if the language is infinite: you'd never finish. What we require is that, although the process of listing the strings in the langauge takes infinitely long, any single string in the language must be guaranteed to appear after a finite amount of time.

So, for example, 1, 2, 3, ... is an enumeration of the natural numbers. You'll never finish writing down the list but, if I pick a natural number (say, 2,938,427,365), I'll only have to wait a finite amount of time until you write that number. Conversely, if I pick something that isn't a natural number (e.g., a frog), I'm guaranteed that you'll never write that down. By way of a non-example, listing all the even numbers, then all the odd numbers *isn't* an enumeration of the naturals: you'll never finish writing the evens, so you'll never start writing the odds, so 1 will not appear in any finite amount of time.

---
Tags: turing-machines
---


# Question
Title: Given n distinct numbers show that the second smallest element can be found in n + lg n - 2 comparisons in the worst case
This is a question from Introduction to Algorithms by CLRS (Exercise 9-1-1).

The approach I thought of is

* compare the first two numbers, assign the lower number min and the bigger one to next\_min
* loop through numbers 3 - n, if the number is lower than min, set min to that number. else if the number if lower than next\_min set next\_min to that number

If this is the optimal solution how can I prove the number of comparisons is n + lg n - 2.

# Answer
The algorithm with $n + \lceil \lg n \rceil -2$ comparisons uses "tournament" (lecture note from utdallas).

* To form a tournament tree: Compare $A\[2i−1\]$ with $A\[2i\]$ for $i = 1$ to $n$. We compare the "winners" in pairs and so on.
* Collect all the keys that *directly* lost to the maximum and compute their maximum. That is, the second largest key.

The time complexity is $(n-1) + (\lceil \lg n \rceil - 1) = n + \lceil \lg n \rceil -2$.

---

Actually, the lower bound for "finding the second largest/smallest element" is $n + \lceil \lg n \rceil -2$, which can be proved by adversary argument (at the end of the lecture above).
> 3 votes

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


# Question
Title: Why is f(n) of class O(g(n)) in this graph?
There is a lot of explanation about big O, but I'm really confused about this part.

Acoording to the definition of Big-O, in this function

$$f (n) \le c g(n), \quad \text{for } n \ge n\_0$$ $f (n)$ is $O(g(n))$.

But a description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

So for example 34 is a upper bound for the set $\\{ 5, 10, 34 \\}$.

So in this graph, how is $f(n)$ in $O(g(n))$ because if I get the upper bound of $g(n)$ function its value would be different than what is mentioned here for $n\ge n\_0$.

# Answer
> 4 votes
I think you're confused about the notion of upper bounds for a function. We're not trying to compute an upper bound for the function $f$ in the sense of saying that, e.g., $f(n) \leq 45$ for all $n$ (or all $n$ greater than some $n\_0$). Rather, we're trying to say that, for all $n\>n\_0$, the value (number) $c\\,g(n)$ is an upper bound for the value $f(n)$. The graph indicates this informally (since it only shows what happens for some unstated but limited range of values of $n$).

---
Tags: asymptotics, landau-notation
---


# Question
Title: Why is it true that the relation R and its negation are not semi decidable?
An example given for a relation R where its negation and itself are not semi-decidable was:

$R(x,y)$ holds iff $y = 0$ then $R\_{HALT}(x)$ holds, otherwise $y = 1$ and $R\_{HALT}(x)$ does not hold.

It's stated with the assumption that the proof is trivial (which for most it probably is), but I am struggling to see why it is the case. Can anyone run me through why it is true?

# Answer
> 2 votes
If the relation $R$ was semi-decidable, then the halting problem would be decidable: if you want to know whether program $x$ terminates, just enumerate the elements of $R$ until you find either $(x,0)$ or $(x,1)$. In the first case, output "$x$ halts"; in the second, "$x$ does not halt." One of these is guaranteed to happen, so you have a decider for the halting problem, contradicting the undecidability of that problem.

The argument for the complement of $R$ is nearly identical: observe that $\overline{R} = \\{(x,1-y)\mid (x,y)\in R\\}$.

---
Tags: computability, undecidability, halting-problem, semi-decidability
---


# Question
Title: Nomenclature for deterministic algorithms that might fail
What do you call an algorithm which is

* Deterministic
* When an answer is returned, it is correct
* For some input, the algorithm returns no answer (fails, in bounded time).

Such algorithms crop up a lot in cryptographic attacks, for instance, where a cipher is deemed broken when an attack (provably or demonstrably) works "most of the time".

I'm working in a different field (coding theory) with an algorithm of the above kind. For random, uniformly distributed input, the probability that the algorithm fails seems to be so low that in practice it can be more or less ignored. However, we have no succinct characterisation of input which cause failure. Previous work on this algorithm has called it "a probabilistic algorithm" but I find this an abuse of the term, since the algorithm is deterministic, once the input is known.

# Answer
> 2 votes
I do not have an authorative answer but two proposals.

1. Such algorithms compute partial functions, so you could call them *partial* or *partially correct* algorithms.
2. Working off your literature, the class of algorithms you defined is that of Las Vegas algorithms. Even though the implication is that the algorithm is randomised it certainly need not be; even though you have access to random bits you don't have to use them.

If you want to stress determinism, you can use *deterministic Las Vegas algorithm*.

---
Tags: algorithms, terminology
---


title: Rational subsets of a monoid

text:
# Question
Title: Rational subsets of a monoid
In "Rational Set of Commutative Monoid", S. Eilenberg and M.P. Schützenberger define the class of rational subsets of a monoid $M$ as the least class $F$ of subsets of $M$ such that satisfy the following properties:

1. the empty set is in $F$;
2. Each single element set is in $F$;
3. If $X, Y$ are in $F$, then $X \cup Y$ is in $F$;
4. If $X, Y$ are in $F$, then $XY$ is in $F$;
5. If $X$ is in $F$, then $X^\*$ is in $F$.

In 4. $XY = \\{xy \mid x \in X \text{ and } y \in Y \\}$, what is this product? concatenation product?

In the following link, there is a complete paper http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1969-3RationalSetsCommutativeMonoids.pdf

# Answer
> 3 votes
The product is the monoid product. A monoid is a set equipped with an operation (which we can call *product*) satisfying certain axioms. The classical monoid we use in formal languages is $\Sigma^\*$ (for some alphabet $\Sigma$), in which case the monoid product is indeed concatenation. But this is not the only possibility: for example, every group is a monoid, since the monoid axioms are a subset of the group axioms.

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


# Question
Title: Curry Howard correspondence and Church-Turing thesis
Curry-Howard correspondence states the equivalence between logic/deduction and types/programs.

The Church-Turing thesis states the equivalence of some models of computation. Specifically, all computable functions can be written both on a Turing Machine and in Lambda Calculus.

Not all logics are equivalent however. 2nd order logic can quantify over sets whilst 1st order can't.

Can someone explain the dissonance? Can some computable functions be expressed at a "higher-level" but not at a "simpler-level"?

\[CLARIFICATION\]

If I define a model for computation off say 2nd order logic whilst the Turing Machine is a model for 1st order logic, then does that mean my hypothetical language can compute "uncomputable" functions? It appears so to me because 2nd order logic is more powerful than 1st order logic. This is clearly nonsense because Haskell is based off a flavor of 2 order logic (system F with extensions) but isn't more powerful than say C: any program achievable in Haskell is achievable in C. The mapping (or equivalence) between logic and computation does not appear to preserve the notion of strength: 2nd order logic is stronger than 1st order logic but programming languages off 2nd and 1st order logic have the same strength. Does that make sense?

The only conclusion I can come to is that the relationship between logic and types is not a straightforward mapping. The Turing Machine is not based off any specific logic and that any logic/deductive system can be mapped to the Turing Machine. Can you confirm?

\[CLOSING WORDS\]

I think that my mistake is in not realizing that there is a large divide between the colloquial "program" and programs in the context of types.

Haskell which is based on a stronger, more expressive type system does indeed provide stronger, more expressive programs. These programs are stronger in the sense that more can be guaranteed about them (in the same sense as "type safe"). This does not mean that Haskell can "compute" more; it is still merely Turing complete.

# Answer
> 4 votes
I'm not sure where you see the dissonance.

The Church-Turing thesis is a hypothesis stating that Turing Machines (equiv. Lambda Calculus or Recursive Functions) can do anything that we'd think of as computable.

The Curry-Howard correspondence is a much stronger statement that certain types of intuitionistic logic are structurally identical to things kind of like the Lambda Calculus. It doesn't really say which logic it corresponds to, it just shows that you can map the logical constructions in a canonical way to a (typed) computational model and vice versa. If you take different logics, you get different models and vice versa. The models may or may not be Turing-complete, although if we believe the Church-Turing thesis (it does seem to be doing alright so far), if you get a model that's more powerful than a Turing Machine, then you've got something incomputable in there.

Nonetheless, the logic you deal with does limit what you can compute in the corresponding model. For example, the Calculus of Inductive Constructions, which is a type theory and the basis for Coq, only allows types that it can verify have decreasing definitions (i.e. a recursive destruction of the type will terminate), but there are perfectly computable types which it can't verify, so you're locked out of using them.

# Answer
> 5 votes
TLDR: A sound logic corresponds to a non-Turing-complete lambda calculus, so the Church-Turing thesis doesn't apply.

It's important to remember that most Dependently Typed programming languages aren't Turing Complete. When you allow for non-halting programs, your logic becomes unsound. So the Curry-Howard Isomorphism doesn't really apply to

Consider Haskell, which is Turing Complete. Basically, it allows for general recursion by having an axiomatically defined fixed-point operator of type $(\alpha \rightarrow \alpha) \rightarrow \alpha$. Basically, it allows you to write a function taking a "self" argument, and create a new function which receives itself as the "self" argument.

This can be done with something like the Y-combinator, but there's no way to properly type such a function. So, there's an axiom that asserts that this fixpoint function is well typed.

The problem is, this now allows you to write programs that don't halt. When you use Curry-Howard, this allows you to prove False theorems.

Look at the type of that function as a proposition. $(P \implies P) \implies P$ as an axiom lets you prove anything, since every proposition implies itself. There's a result called the Recursion Theorem that basically says you can always find such a function in a Turing-Complete language.

Allowing for non-halting programs is what makes Turing Machines powerful, and is at the heart of the Church-Turing thesis. But as soon as you allow that, any meaningful relation to logic is lost.

Coq and Agda get around this by enforcing termination using structural recursion, but neither language is Turing Complete in the conventional sense, so the Church-Turing thesis doesn't apply to them.

---
Tags: computability, logic, functional-programming, church-turing-thesis, curry-howard
---


# Question
Title: Computer Architecture, cache hit and misses
I am currently enrolled in a computer organization and design class, which I am struggling mightily with, and I have a final homework in my class that I need to get a perfect score on. One of the questions covers cache hit-misses, and the lecture we had on the subject was relatively brief. The question I have having issues with is:

A processor has a CPI of 1.4 with level 1 caches with a 100% hit rate. When running benchmarks, the level 1 instruction cache has a 1% miss rate and the level 1 data cache has a 3% miss rate. 30% of the instructions access memory through load and store operations. Main memory has a 50 nano second access time and the clock is running at 2.5 GHz.

What is the actual CPI of the processor with just the level 1 caches?

A level 2 cache is added to the processor. The hit time of this cache is 1.5 nanoseconds, and it has a global miss rate of 0.5%. Compute the actual CPI of the processor after the addition of the level 2 cache.

What is the speedup achieved by adding the level 2 cache?

So my first attempt is this:

I-cache miss rate = 1%
D-cache miss rate = 3%
Miss penalty to main memory = main memory access time / clock time
50 ns / .4 ns per clock cycle = 125 clock cycles
Base CPI = 1.4
Load and store = 30% of instructions
Main memory access time = 50 ns
Processor clock = 2.5 GHz

What is the actual CPI of the processor with just the level 1 caches?

Instruction miss cycles = I x 1% x 125 = 1.25 x I
Data miss cycles = I x 30% x 3% x 125 = 1.125 x I
Total number of memory-stall cycles is 2.375 I
Total CPI including memory stalls is 1.4 + 2.375 = 3.775

A level 2 cache is added to the processor. The hit time of this cache is 1.5 ns and it has a global miss rate of 0.5%. Compute the actual CPI of the processor after the addition of the level 2 cache.

Secondary cache access time = 1.5ns
Processor clock = 2.5 GHz
Miss penalty for an access to second-level cache = 1.5ns / .4 ns per clock cycle = 3.75 clock cycles
For a two level cache, total CPI is the sum of the stall cycles from both levels of cache and the base CPI
1.4 + (.005 x 125) + (.005 x .3 x 125) + (.01 x 3.75) + (.01 x .3 x 3.75) = 2.26125
\*****This is where I'm most unsure. The "global miss rate of 0.5%" is throwing me off, and I'm not sure I performed this calculation correctly.\**

What is the speedup achieved by adding the level 2 cache?
3.775 / 2.26125 = 1.67
\***This answer is dependent on the result from the calculation above. If I did that wrong, this answer will be different.

# Answer
You may wish to ask your TA/Prof. what they mean by "0.5% *global* miss rate". The way I read it is the following:

> Out of $x$ accesses to the L2 cache, $0.005x$ accesses are a miss.

This interpretation makes more sense than assuming the miss rate is out of all the store/load instruction.

So each miss of the L1 cache becomes an access to the L2 cache, and out of these, 0.5% are a miss at the L2 cache. From here, it seems you can fill out the details by yourself, building on your own attempts.
> 1 votes

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: How to create this pushdown transducer? (formal languages and automata)
Create a pushdown transducer that translates $a^m b^{2m}c^{m+n}$ into $b^{n-m}$, with $n\geq m \geq 0$. How should I use the stack to remember or to compute how many characters of c to read? And how can I output $b^{n-m}$?

I have also tried to simplify the problem and firstly create a pushdown automata for $a^m b^{2m}c^m$, but I didn't succeed.

Thank you!

# Answer
It is no surprise you could not create that PDA: the language $\\{a^m b^{2m}c^m\mid m\geq 0\\}$ is not CF. The same is true of $\\{a^m b^{2m}c^{m+n}\mid n\geq m\geq 0\\}$. You may try to prove it.

Hence, I suspect that the pushdown transducer is not supposed to recognize the input string but assumes it is well formed, and simply has to translate correctly when it is.

So I would simply use the pushdown stack of the transducer to collect the information to be found in the input (supposed to be well formed) to produce the correct output, without worrying about acceptance. You do not care what happens when the input string is not well formed. It is actually quite simple to produce $b^{n-m}$
> 1 votes

---
Tags: formal-languages, automata, pushdown-automata
---


# Question
Title: What is the decidable language in $P/poly$ but not in $P$?
Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$

# Answer
Take a language $L$ which is not in $\mathsf{E} = \bigcup\_{c=1}^\infty \mathsf{TIME}(2^{cn})$. Now consider the language $L' = \\{1^m : m \in L\\}$. Then $L'$ is clearly in $\mathsf{P/poly}$, but it's not in $\mathsf{P}$: if it were decidable in time $O(m^k)$, then we could decide $L$ in time $O((2^n)^k)$, and so $L$ would be in $\mathsf{E}$. Our decision procedure works as follows: on input $m$ of length $n = \log m$, we run the algorithm for $L'$ on the input $1^m$. This runs in time $O(m^k) = O((2^n)^k)$.

It remains to ensure that $L'$ is decidable. To that end, all we need to do is to choose some $L \notin \mathsf{E}$ which is decidable, for that makes $L'$ trivially decidable: given an input, if it's not of the form $1^m$, reject; otherwise, answer according to whether $m \in L$.

The existence of a decidable language $L \notin \mathsf{E}$ is guaranteed by the time hierarchy theorem.
> 9 votes

---
Tags: complexity-theory, polynomial-time, circuits
---


# Question
Title: pumping lemma for $L=\{a^n b^m c^k \mid n = m \vee m\neq k\}$
Using pumping lemma, how can I prove that $L=\\{a^n b^m c^k \mid n = m \vee m\neq k\\}$ is not regular?.

If I choose $w= a^m b^m c^m$ and pump up with $i=2$, if have $a^m=1 b^m c^m$ but the string is still in the language. Any hint?

# Answer
> 1 votes
The easiest way to show that $L$ isn't regular is by noticing that $$ L \cap b^+c^+ = \\{ b^m c^k : m,k \geq 1, m \neq k \\}. $$ This should look familiar.

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


# Question
Title: NFA-style representation of regexps which includes AND
I'm looking for a regexp matching strategy that supports conjunction and which is based on an NFA-style machine. I know how to handle conjunctions using a DFA, or using Brzozowski's approach, but for various reasons, I can't use Brzozowski's technique and bump into state explosion when using a DFA.

I know about the cross-product construction to compute the intersection of two NFAs, but there as well: while the state explosion is not as severe as when going through a DFA, it is sometimes still too severe for my needs, so I'd like an NFA-like representation that lets me build the cross-product "on the fly", kind of like "Thompson's NFA" matching constructs the DFA states on the fly.

# Answer
It is a bit difficult to answer you because you state that you are using NFA to do the matching. NFA being non deterministic, that leave the interpretation technique open, depth first, breadth first, or variants. So I am trying to give you an answer that should fit any interpretation of the NFA. This technique should be applicable to other constructions than intersection.

You have 2 NFAs, $A\_i=(Q\_i,\Sigma,\delta\_i,\hat q\_i, F\_i)$ for $i=1,2$. The intersection is a NFA $A=(Q,\Sigma,\delta,\hat q, F)$ defined as usual for the intersection, notably with $Q=Q\_1\times Q\_2$.

The idea of the technique is to implement the transition function $\delta$ not as a table, but as a function $\delta: (Q\_1\times Q\_2)\times\Sigma\to 2^{(Q\_1\times Q\_2)}$, that calls in turn the function $\delta\_1$ and $\delta\_2$.

```
function delta((q1,q2),a)
{ return (delta1(q1,a), delta2(q2,a))}

```

This is to be read as a non deterministic program, in the sense described in this answer to How does one formulate a backtracking algorithm? That means that, in actual interpretation, the functions are actually returning sets of results, one by one if backtracking, or together if breadth-first.

The rest is up to the way you translate non-determinism into determinism, either by a compiler, or by hand. It can be done depth-first or breadth first. It can even use memo function to compute incrementally and remember the part of the transitions of the automaton $A$ that is needed for the string at hand, and possibly keep it for future strings to be matched.

Of course, if your automata are DFAs, this is much simpler to read as usual deterministic functions (possibly implemented by tables for `delta1` and `delta2`. Then memoisation of `delta` will construct incrementally the table for the cross product.

The can be seen as an incremental construction, or as a generalisation of call by need. Rather than building the automaton up-front, you build the parts you need when you need them (and you can even forget some, if you run out of space). This can also be used for the powerset construction, and in many other circumstances.
> 2 votes

# Answer
The simple solution is to run your two NFAs in parallel, then see if they both accept.

Apparently, you have two NFAs, $M\_1,M\_2$. You have an input string $x$. You want to see whether $x$ matches their conjunction.

A good solution is to first check whether $x$ matches $M\_1$, then check whether $x$ matches $M\_2$, and accept $x$ only if matches both. Note that this is much more efficient than using the product construction to compute a NFA $M$ for the conjunction of $M\_1$ and $M\_2$, then matching $x$ against $M$: $M$ will have quadratically many states, so the running time of matching $x$ against $M$ will be quadratic (in the size of $M\_1,M\_2$), whereas the running time of matching $x$ against $M\_1,M\_2$ separately will be linear (in the size of $M\_1,M\_2$).
> 0 votes

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


# Question
Title: Splicing squares on a Turing Machine finite tape
Trying to explain a problem, I thought of a variant of Turing Machines. It is unlikely to be new, but I do not recall ever seing it before, and I wonder whether it has been used or has a name. The idea is that the TM uses a "linked list" rather than a tape, so that the head can splice a new symbol position between two existing ones (one could also think of removing some, but I had no use for it :). Of course, that requires having a new item in the description of a transition to specify whether a new square should be spliced in, on the left or on the right of the head (both are needed).

The final point is that *it does start with a finite tape*. I did not give all the details, but I do not think the rest matters much.

I have not done any proof, but I conjecture its computing power is that of usual TM **:)** .

As I said I thought of it as a convenient way of explaining some other problem. Then it hit me that, while TM are finitely defined, they are stuck with their infinite tape from the very beginning. It never bothered me very much, until some physicist started explaining that TM are not realistic because of their infinite tape (which I only saw as a convenient mathematical shorthand). I could fight that technically in various ways. But this splicing idea should just do away with such silly objections using no mathematics at all.

So **my question is**: *where has this model, or some similar one, been considered before, by whom and under what name?*

# Answer
It seems just too close to a two-stack automaton to be studied separately. The two stacks can be seen as two parts of your linked list (before and after the position of the reading head). Pushing a new symbol is the equivalent of your splicing a tape cell.
> 2 votes

# Answer
Yes, it has the same computing power as an ordinary TM.

* It's a standard exercise in computation theory/complexity theory textbooks that the ability to insert characters into the tape (and delete them from it) can be simulated by a standard Turing machine with a quadratic loss of efficiency. For example, this is Exercise 2.8.8 of Papadimitriou's book (*Computational Complexity*, Addison Wesley, 1994); he doesn't give a name to this extension of the standard Turing machine or attribute it to anyone which suggests to me that it's folklore – he's pretty good at citing and attributing.
* Since you can insert characters at will, reaching the end of the initially finite tape makes no difference: you can just use insertion to extend the tape. A halting computation will only need to do this a finite number of times. The infinite tape of an ordinary TM is just a definitional convenience: it suffices to have a finite tape that gets extended any time the head reaches the end.
> 4 votes

# Answer
Turing machines are not supposed to be "realistic" in a physical (concrete) sense. That said, to say that the tape is infinite is obviously not precise. The tape is better thought of as being unlimited, or "growing" in size as needed, which makes it essentially identical to what you propose, at least in what it can compute.
> 1 votes

---
Tags: terminology, turing-machines, reference-request, computation-models
---


title: Turing Machine construction

text:
# Question
Title: Turing Machine construction
How should I go about building a Turing machine for the following language:

$$L = \\{ a^ib^j \in (a,b)^\* \mid i \le j \le 2i \\} $$

I know how to construct a Turing machine for $\\{ a^nb^nc^n \mid n \in \mathbb N \\}$ but don't really where to start for the one above.

# Answer
> 2 votes
How would you construct a TM for $\\{a^i b^j \mid i \le j\\}$? Well, the easiest solution is to keep removing letters on both sides until you run out of $a$s or $b$s. At this point you can look at what you are left with and decide whether $i \le j$ was initially true.

Now, what if, instead of removing $a$s, you were moving them somewhere to keep for later use? This way you’d be able to test for $i \le j$ and still have all your $a$s available. By doing something similar with all those saved $a$s and the remaining $b$s you will be able to check the second condition, $j \le 2i$.

---
Tags: formal-languages, turing-machines
---


title: When to pump up and down?

text:
# Question
Title: When to pump up and down?
When I'm solving a question I usually spent too much time testing whether I should pump or down? Is there any formula to know when to use which?

Also, on proofing non context free grammar we use three pumping lemma, and one that's confused me is $|uvy| \le p$. I mean in the example given in the book I read, it is not even used. Can someone please tell on which situation this is will be useful?

Any help will be very appreciated.

# Answer
To fix symbols, let us choose the decomposition $z = uvwxy$.

One of the examples where $|vwx|\le p$ comes in, is the language $L =\\{ a^mb^na^mb^n\mid m,n\ge 1\\}$.

Start with the "generic" string $a^pb^pa^pb^p$ where $p$ is the pumping constant. To have any chance of finding a pumping pair $v,x$ such that $uv^iwx^iy$ is within the language is by choosing $v$ in the first set of $a$'s and $x$ in the second set of $a$'s (or similarly for the $b$'s). Now the length of $vwx$ will be more than $p$ as it contains all $b$'s between the two sets of $a$'s.

Without that restriction $L$ can be pumped, and the pumping lemma is no longer suited for proving $L$ is not context-free.
> 3 votes

---
Tags: context-free, pumping-lemma, pushdown-automata
---


# Question
Title: Can I find a clique with more than 2 nodes in a bipartite graph?
As in the title, is it possible to find a clique with more than 2 nodes in a bipartite graph?

# Answer
> 4 votes
A graph is bipartite if and only if it is 2-colorable. A clique of size at least 3 contains a triangle, and a triangle $K\_3$ clearly cannot be colored with 2 colors. It follows we can't find a triangle in a bipartite graph, so the corresponding decision problem is very easy for a bipartite graph.

---
Tags: graphs, clique
---


# Question
Title: Is a LBA with stack more powerful than a LBA without?
Even so a linear bounded automata (LBA) is strictly more powerful than a pushdown automata (PDA), adding a stack to a LBA might make it more powerful.

A LBA with stack should not be Turing complete, because its halting problem should be decidable. (It seems to be equivalent to the halting problem for a PDA).

Can a deterministic LBA with stack decide all problems decided by a nondeterministic LBA?

Or on the other hand, maybe a LBA with stack is (provably) not more powerful than a LBA?

---

**Edit** I think I found out how a deterministic LBA with stack can simulate a nondeterministic LBA. The stack can be used to store and recall the current state of the external memory (the linear bounded memory) as often as needed. The internal state is finite, so there is a global bound for the maximal number of nondeterministic moves available in a single step. So backtracking can be used to recursively simulate the result of each nondeterministic move.

I will have to think about how to make these two observations (halting problem is decidable, nondeterministic LBA can be simulated deterministically) more rigorous, before self-answering. I'm away next week, so don't hold your breath.

# Answer
**Theorem** The following are equivalent.

1. $L$ is accepted by a deterministic LBA with stack
2. $L$ is accepted by a nondeterministic LBA with stack
3. $L$ is in $\operatorname{DTIME}(c^n)$ for some constant $c$.

So the computational power of a LBA with stack for decision problems is well understood. The exponential runtime limits the usefulness of this knowledge in practice. But the notion of an *LBA with stack* can be generalized to an *$S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA)*. It consists of

1. a read-only input tape, surrounded by endmarkers,
2. a finite state control,
3. a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
4. a stack

In "Hopcroft/Ullman (1979) *Introduction to Automata Theory, Languages, and Computation (1st ed.)* we find:

**Theorem 14.1** The following are equivalent for $S(n)\geq\log n$.

1. $L$ is accepted by a deterministic $S(n)$-AuxPDA
2. $L$ is accepted by a nondeterministic $S(n)$-AuxPDA
3. $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$.

with the surprising:

**Corollary** $L$ is in $\mathsf P$ if and only if $L$ is accepted by a $\log n$-AuxPDA.

The proof consists of three parts: (1) If L is accepted by a nondeterministic $S(n)$-AuxPDA with $S(n)\geq \log n$, then $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$. (2) If $L$ is in $\operatorname{DTIME}(T(n))$, then $L$ is accepted in time $T^4(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input). (3) If $L$ is accepted in time $T(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input), then $L$ is accepted by a deterministic $\log T(n)$-AuxPDA.

Part (1) is basically a rigorous proof that the "halting problem is decidable", where the number of operations was counted thoroughly. Part (2) is the creative idea that prepares the stage for part (3). Part (3) uses the auxiliary storage for tracking the time step, which allows to reconstruct the head position due to the very simple forward-backward head scan pattern, and the stack for recursive backtracking. (So this proof also contains the two observations which I wanted to make more rigorous. This answer is already long enough anyway, so I won't go into more detail here.)

---

This leads to the following answer for the initial question *Is a LBA with stack more powerful than a LBA without?*: The question is equivalent to a well know open problem, and the expectation is that it is indeed more powerful.
> 8 votes

---
Tags: automata, computation-models, turing-completeness, stacks, linear-bounded-automata
---


title: speed, cost and capacity tradoff

text:
# Question
Title: speed, cost and capacity tradoff
I'm reading William Stalling's Operating System Design and internals. Talking about memory, the following tradeoff was introduced:

> As might be expected, there is a tradeoff among the three key characteristics of memory: namely, capacity, access time, and cost. A variety of technologies are used to implement memory systems, and across this spectrum of technologies, the following relationships hold:
> • Faster access time, greater cost per bit
> • Greater capacity, smaller cost per bit
> • Greater capacity, slower access speed

Now what exactly makes a faster memory more costly, and why does bigger memory mean slower memory?

# Answer
Increasing the speed of memory typically involves increasing the size of the bit cell. For example increasing the capacitor size in a DRAM (which using one transistor and one capacitor to store a bit) allows faster reading of the bit but obviously also reduces the number of bit cells that can be fit onto a chip. (Similarly, SRAM is less dense but faster than DRAM.)

From an economic perspective, since speed is generally valued, techniques to increase speed are allowed spend more effort (i.e., cost) in research, design, and manufacture to increase speed.

Aside from the cost factor (users seeking higher capacity will seek lower cost per bit), higher capacity memories are generally slower from a combination of lesser integration and greater distance between a bit cell and the consumer of the data. Greater integration (on the same chip, in the same package, on the same board, in the same system/enclosure) not only reduces physical communication overhead (crossing physical boundaries has overhead) but also interface overhead as less integrated interfaces are typically more generic and less optimized for one specific use.

Indexing overhead is an additional factor making larger memories slower. Hardware effectively traverses a binary tree to select the desired data. (This factor is typically minor, but it seemed worth mentioning.)

---

Another significant tradeoff in memory system design is access granularity/randomness. Larger access granules and less random access correlate with increased density/lower cost per bit. This is also a result of economic and physical factors.
> 1 votes

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: prove that a language is context free given a regular language
R is a regular language over $\Sigma=\\{0,1\\}$
$Sub(R)=\\{0^i1^j \mid \exists w\in R.|w|=i-j \\}$
I need to prove that Sub(R) is context free.

I know that the quotient of a context free language with a regular language is context free but I can't seem to continue for there..

# Answer
> 3 votes
Let $\phi(R) \subseteq 0^\*$ result from $R$ by substituting $0$ for $1$. Alternatively, $\phi(R) = \\{ 0^{|w|} : w \in R \\}$. The previous description makes it clear that $\phi(R)$ is also regular. Now $$ \operatorname{Sub}(R) = \phi(R) \\{ 0^j 1^j \\}, $$ the concatenation of the regular language $\phi(R)$ and the context-free language $\\{0^j 1^j\\}$.

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


# Question
Title: Searching for multiple partial phrases so that one original phrase can not match multiple search phrases
Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases:

```
index      phrase
-----------------------------------------
0          Stack Overflow
1          Math Overflow
2          Super User
3          Webmasters
4          Electrical Engineering
5          Programming Jokes
6          Programming Puzzles
7          Geographic Information Systems

```

The expected behaviour is:

```
query         result
------------------------------------------------------------------------
s             Stack Overflow, Super User, Geographic Information Systems
web           Webmasters
over          Stack Overflow, Math Overflow
super u       Super User
user s        Super User
e e           Electrical Engineering
p             Programming Jokes, Programming Puzzles
p p           Programming Puzzles

```

To implement this behaviour I used a trie. Every node in the trie has an array of indices (empty initially).

To insert a phrase to the trie, I first break it to words. For example, `Programming Puzzles` has `index = 6`. Therefore, I add `6` to all the following nodes:

```
p
pr
pro
prog
progr
progra
program
programm
programmi
programmin
programming
pu
puz
puzz
puzzl
puzzle
puzzles

```

The problem is, when I search for the query `prog p`, I first get a list of indices for `prog` which is `[5, 6]`. Then, I get a list of indices for `p` which is `[5, 6]` as well. Finally, I calculate the intersection between the two, and return the result `[5, 6]`, which is obviously wrong (should be `[6]`).

How would you fix this?

# Answer
> 2 votes
Let's fix some names. Let $q\_1, \dots, q\_k$ be the query strings and $w\_1, \dots, w\_n$ the existing phrases. Denote with $w\_{i,1}, \dots, w\_{i,k\_i}$ the words contained in phrase $w\_i$, and with $a \sqsubseteq b$ the relation "$a$ is a prefix of $b$".

Currently, you have implemented to obtain this:

$\qquad\displaystyle \\{ i \in \[1..n\] \mid \forall j \in \[1..k\]\ \exists j' \in \[1..k\_i\].\ q\_j \sqsubseteq w\_{i,j'}\\}$.

Note how the $\exists$-operator does not preclude the same $j'$ for multiple $j$, and that's your problem (as far as I can tell). What you want is

$\qquad\displaystyle \\{ i \in \[1..n\] \mid \exists J = \\{j\_1, \dots, j\_k\\} \subseteq \[1..k\_i\]\ \forall j \in \[1..k\].\ q\_j \sqsubseteq w\_{i,j\_j}\\}$.

One way to implement this is to go with the double-indexing I used to describe the problem formally: each node gets the set of labels $(i,j)$ if its corresponding string is a prefix of $w\_{i,j}$. Now, $i$ is a match if

* every $q\_l$ leads to a node with label $(i,\\\_)$ and
* the second components of these labels are pairwise distinct (if there are multiple $(i,\\\_)$ for a single $q\_l$, one has to check if there is a choice fulfilling the condition).

In your example, instead of just adding `6` to all these nodes you list, you'd add `(5,1)` and `(6,1)` to the prefixes of `programming`, and `(6,2)` to those of `puzzles`. Now, `prog p` gives you `(5,1), (6,1)` for `prog` and `(5,1), (6,1), (6,2)` for `p`; you can exclude `5` because it has the same second component for both query phrases whereas `6` has a "valid" match with `(6,1)` and `(6,2)`.

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


# Question
Title: Efficient algorithm to generate two diffuse, deranged permutations of a multiset at random
### Background

$\newcommand\ms\[1\]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak S}\newcommand\mfm\[1\]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{2}}}\def\pth{\color{#6c0}{\mfm{3}}}\def\pf{4}\def\pv{\color{#999}5}\def\gr{\color{#ccc}}\let\ss\gr$Suppose I have two identical batches of $n$ marbles. Each marble can be one of $c$ colors, where $c≤n$. Let $n\_i$ denote the number of marbles of color $i$ in each batch.

Let $\msS$ be the multiset $\small\\{\overbrace{\po,…,\po}^{n\_1},\\;\overbrace{\pt,…,\pt}^{n\_2},\\;…,\\;\overbrace{\vphantom 1\pc,…,\pc}^{n\_c}\\}$ representing one batch. In frequency representation, $\msS$ can also be written as $(\po^{n\_1} \\;\pt^{n\_2}\\; … \\;\pc^{n\_c})$.

The number of distinct permutations of $\msS$ is given by the multinomial: $$\left|\mfS\_{\msS}\right|=\binom{n}{n\_1,n\_2,\dots,n\_c}=\frac{n!}{n\_1!\\,n\_2!\cdots n\_c!}=n! \prod\_{i=1}^c \frac1{n\_i!}.$$

### Question

Is there an efficient algorithm to generate two diffuse, deranged permutations $P$ and $Q$ of $\msS$ at random? (The distribution should be uniform.)

* A permutation $P$ is **diffuse** if for every distinct element $i$ of $P$, the instances of $i$ are spaced out roughly evenly in $P$.

> For example, suppose $\msS=(\po^4\\;\pt^4)=\\{\po,\po,\po,\po,\pt,\pt,\pt,\pt\\}$.
>
> + $\\{\po, \po, \po, \pt, \pt, \pt, \pt, \po\\}$ is not diffuse
>     + $\\{\po, \pt, \po, \pt, \po, \pt, \po, \pt\\}$ is diffuse

More rigorously:

+ If $n\_i=1$, there is only one instance of $i$ to “space out” in $P$, so let $\Delta(i)=0$.
    + Otherwise, let $d(i,j)$ be the distance between instance $j$ and instance $j+1$ of $i$ in $P$. Subtract from it the expected distance between instances of $i$, defining the following: $$\delta(i,j)=d(i,j)-\frac n{n\_i}\qquad\qquad\Delta(i)=\sum\_{j=1}^{n\_i-1} \delta(i,j)^2$$ If $i$ is evenly spaced in $P$, then $\Delta(i)$ should be zero, or very close to zero if $n\_i\nmid n$.

Now define the statistic $s(P)=\sum\_{i=1}^c\Delta(i)$ to measure how much every $i$ is evenly spaced in $P$. We call $P$ diffuse if $s(P)$ is close to zero, or roughly $s(P)\ll n^2$. (One can choose a threshold $k\ll1$ specific to $\msS$ so that $P$ is diffuse if $s(P)\<kn^2$.)

> This constraint recalls a stricter real-time scheduling problem called the *pinwheel problem* with multiset $\ms A=n/\msS$ (so that $a\_i=n/n\_i$) and density $\rho=\sum\_{i=1}^c n\_i/n=1$. The objective is to schedule a cyclic infinite sequence $P$ such that any subsequence of length $a\_i$ contains at least one instance of $i$. In other words, a feasible schedule requires all $d(i,j)≤a\_i$; if $\ms A$ is dense ($\rho= 1$), then $d(i,j)=a\_i$ and $s(P)=0$. The pinwheel problem appears to be NP-complete.
* Two permutations $P$ and $Q$ are **deranged** if $P$ is a derangement of $Q$; that is, $P\_i ≠ Q\_i$ for every index $i\in\[n\]$.

> For example, suppose $\msS=(\po^2\\;\pt^2)=\\{\po,\po,\pt,\pt\\}$.
>
> + $\\{\po, \pt, \po, \pt\\}$ and $\\{\po, \po, \pt, \pt\\}$ are not deranged
>     + $\\{\po, \pt, \po, \pt\\}$ and $\\{\pt, \po, \pt, \po\\}$ are deranged

### Exploratory analysis

I am interested in the family of multisets with $n=20$ and $n\_i=4$ for $i\lesssim4$. In particular, let $\msD=(\gr1^4\\,\gr2^4\\,\gr3^4\\,\gr4^3\\,\gr5^2\\,\gr6^1\\,\gr7^1\\,\gr8^1)$.

* The probability that two random permutations $P$ and $Q$ of $\msD$ are **deranged** is about 3%.

> This can be calculated as follows, where $L\_k$ is the $k$th Laguerre polynomial: \begin{align\*} \left|{\mathfrak D}\_{\msD}\right| &=\int\_0^\infty \\!\\!dt\\; e^{-t}\\, \prod\_{i=1}^c L\_{n\_i}(t) =\int\_0^\infty \\!\\!dt\\; e^{-t}\\, \bigl(L\_4(t)\bigr)^3\bigl(L\_3(t)\bigr)\bigl(L\_2(t)\bigr)\bigl(L\_1(t)\bigr)^3\\ &=4.5\times10^{11}\\ \left|\mfS\_{\msD}\right| &=n!\prod\_{i=1}^c \frac1{n\_i!} =\frac{20!}{(4!)^3\\,(3!)\\,(2!)\\,(1!)^3} =1.5\times10^{13}\\ p&=\left|{\mathfrak D}\_{\msD}\right|/ \left|\mfS\_{\msD}\right|\approx0.03\end{align\*} See here for an explanation.
* The probability that a random permutation $P$ of $\msD$ is **diffuse** is about 0.01%, setting the arbitrary threshold at roughly $s(P)\<25$.

> Below is an empirical probability plot of 100,000 samples of $s(P)$ where $P$ is a random permutation of $\msD$.
>
> At medium sample sizes, $s(P)\sim \text{Gamma}(\alpha\approx8,\beta\approx18)$.
>
> \begin{array}{ccl}\renewcommand\mfm\[1\]{\textbf{#1}} \hline P & s(P) & \text{cdf}(s(P)) \\ \hline \\{\po, \ss8, \pt, \pth, \pf, \po, \pv, \pt, \pth, \ss6, \po, \pf, \pt, \pth, \ss7, \po, \pv, \pt, \pf, \pth\\} & \frac{11}9\approx1\\, & \<10^{-5} \\ \\{\ss8, \pt, \pth, \pf, \po, \ss6, \pv, \pt, \pth, \pf, \po, \ss7, \po, \pt, \pth, \pv, \pf, \po, \pt, \pth\\} & \frac{140}9\approx16 & \<10^{-4} \\ \\{\pth, \ss6, \pv, \po, \pth, \pf, \pt, \po, \pt, \ss7, \ss8, \pv, \pt, \pf, \po, \pth, \pth, \pt, \po, \pf\\} & \frac{650}9\approx72 & \phantom{\<1}0.05 \\ \\{\pth, \po, \pth, \pf, \ss8, \pt, \pt, \po, \po, \pv, \pth, \pth, \pt, \ss6, \pf, \pf, \pt, \po, \ss7, \pv\\} & \frac{1223}9\approx136 & \phantom{\<1}0.45 \\ \\{\pf, \po, \po, \pf, \pv, \pv, \po, \pth, \pth, \ss7, \po, \pt, \pt, \pf, \pth, \pth, \ss8, \pt, \pt, \ss6\\} & \frac{1697}9\approx189 & \phantom{\<1}0.80 \\ \hline \end{array}

The probability that two random permutations are valid (both diffuse and deranged) is around $v\approx(0.03)(0.0001)^2\approx10^{-10}$.

### Inefficient algorithms

A common “fast” algorithm to generate a random derangement of a set is rejection-based:

```
do
    *P* ← random_permutation(**D**)
until is_derangement(**D**, *P*)
return *P*

```

which takes approximately $e$ iterations, since there are roughly $n!/e$ possible derangements. However a rejection-based randomized algorithm would not be efficient for this problem, as it would take on the order of $1/v\approx10^{10}$ iterations.

In the algorithm used by Sage, a random derangement of a multiset “is formed by choosing an element at random from the list of all possible derangements.” Yet this too is inefficient, as there are $v\\,|\mfS\_{\msD}|^2\approx10^{16}$ valid permutations to enumerate, and besides, one would need an algorithm just to do that anyway.

### Further questions

What is the complexity of this problem? Can it be reduced to any familiar paradigm, such as network flow, graph coloring, or linear programming?

# Answer
> 3 votes
One approach: you can reduce this to the following problem: Given a boolean formula $\varphi(x)$, choose an assignment $x$ uniformly at random from among all the satisfying assignments of $\varphi(x)$. This problem is NP-hard, but there are standard algorithms for generating an $x$ that is approximately uniformly distributed, borrowing methods from #SAT algorithms. For instance, one technique is to pick a hash function $h$ whose range has a carefully chosen size (about the same size as the number of satisfying assignments of $\varphi$), choose uniformly at random a value $y$ from within the range of $h$, and then use a SAT solver to find a satisfying assignment to the formula $\varphi(x) \land (h(x)=y)$. To make it efficient, you can choose $h$ to be a sparse linear map.

This might be shooting a flea with a cannon, but if you have no other approaches that seem workable, this is one you could try.

# Answer
> 0 votes
some extended discussion/ analysis of this problem commenced in cs chat with further background which uncovered some subjectivity in the complex requirements of the problem but did not find any outright errors or oversights.1

here is some tested/ analyzed code which, compared to the other solution based on SAT is relatively "quick and dirty" but was nontrivial/ tricky to debug. its loosely conceptually based on a local pseudorandom/ greedy optimization scheme somewhat similar to eg 2-OPT for TSP. the basic idea is to start with a random solution that fits some constraint, and then perturb it locally to look for improvements, greedily searching for improvements and iterating through them, and terminating when all local improvements have been exhausted. a design criteria was that the algorithm should be as efficient/ avoid rejection as much as possible.

there is some research into derangement algorithms\[4\] eg used in SAGE\[5\] but they are not oriented around multisets.

the simple perturbation is only "swaps" of two positions in the tuple(s). the implementation is in ruby. following is some overview/ notes with refs to line numbers.

qb2.rb (gist-github)

the approach here is to start with two deranged tuples (#106) and then locally/ greedily improve the dispersion (#107), combined in a concept called `derangesperse` (#97), preserving the derangement. note that swapping two same positions in the tuple pair preserves derangement and can improve dispersion and that is (part of) the disperse method/ strategy.

the `derange` subroutine works left to right on the array (multiset) and swaps with elements later in the array where the swap is not with the same element (#10). the algorithm succeeds if, with no further swaps at the last position, the two tuples are still deranged (#16).

there are 3 different approaches to deranging the initial tuples. the 2nd tuple `p2` is always shuffled. one can start with tuple 1 (`p1`) ordered by `a.` "highest powers 1st order" (#128), `b.` shuffled order (#127), `c.` and "lowest powers 1st order" ("highest powers last order") (#126).

the dispersion routine `disperse` is more involved but conceptually not so difficult. again it uses swaps. rather than trying to optimize dispersion in general over all elements it simply tries to iteratively alleviate the current worst case. the idea is to find the 1st least disperse elements, left to right. the perturbation is to swap either the left or right elements (`x, y` indexes) of the least disperse pair with other elements but never any between the pair (which would always decrease dispersion), and also skip attempting to swap with same elements (`select` in #71). `m` is the midpoint index of the pair (#65).

however the dispersion is measured/ optimized over both tuples in the pair (#40) using the "least/ leftmost" dispersion in each pair (#25, #44).

the algorithm attempts to swap "farthest" elements 1st (`sort_by / reverse` #71).

there are two different strategies `true, false` for deciding whether to swap the left or right element of the least disperse pair (#80), either the left element for swap position to the left/ right element to the right side, or the farthest left or right element in the disperse pair from the swap element.

the algorithm finishes (#91) when it can no longer improve dispersion (either moving worst disperse location right or increasing max dispersion over the entire tuple pair (#85)).

statistics are output for rejects over `c`=1000 derangements over the 3 approaches (#116) and `c`=1000 derangesperses (#97), looking at the 2 disperse algorithms for a deranged pair from rejection (#19, #106). the latter tracks total average dispersion (after guaranteed derangement). an example run is as follows

```
c       0.661000
b       0.824000
a       0.927000
[2.484, 2, 4]
[2.668, 2, 4]

```

this shows that the `a-true` algorithm gives best results with ~92% nonrejection and an average worst disperse distance of ~2.6, and a guaranteed minimum of 2 over 1000 trials, ie at least 1 nonequal intervening element between all same-element pairs. it found solutions as high as 3 nonequal intervening elements.

the derangement algorithm is linear time pre-rejection, and the dispersion algorithm (running on deranged input) seems to be possibly ~$O(n \log n)$.

1 the problem is to find quizbowl packet arrangements that satisfy so-called "feng shui"\[1\] or a "nice" random ordering where "nice" is somewhat subjective and not yet "officially" quantified; the author of the problem has analyzed/ reduced it to the derange/ dispersion criteria based on research wrt the quizbowl community and "feng shui experts".\[2\] there are different ideas on "feng shui rules." some "published" research has been done on algorithms but it appears in early stages.\[3\]

\[1\] Packet feng shui / QBWiki

\[2\] Quizbowl packets and feng shui / Lifshitz

\[3\] Question Placement, HSQuizbowl resource center forum

\[4\] Generating Random Derangements / Martinez, Panholzer, Prodinger

\[5\] Sage derangement algorithm (python) / McAndrew

---
Tags: algorithms, combinatorics, probability-theory, permutations, sampling
---


# Question
Title: Defining function for arithmetic expressions
I've got these arithmetic expressions

```
a  ::=  n  |  x  |  a1 + a2  |  a1 ? a2  |  a1 − a2

```

which are a part of language.

An undefined element is allowed ⊥ which extends the set of intergers to Z∪{⊥}.

**Problem:**

I need to define the function

> A: Aexp → (State → Z∪{⊥})

by defining equations for each form of the arithmetic expression `a`.

Now I've tried to come up with an solution but I am pretty sure I am wrong and I gotta admit I am pretty stuck.

Some help understanding this problem would be great.

# Answer
> 1 votes
Hint: Here is one example

$A($ `a1 - a2`$, s) = minus(A($ `a1`$,s),A($ `a2`$,s))$

or alternatively

$A($ `a1 - a2`$) = \lambda s . minus(A($ `a1`$,s),A($ `a2`$,s))$

where $minus$ is the substraction in $\mathbb Z\cup\\{\bot\\}$

---
Tags: semantics, denotational-semantics
---


# Question
Title: Rearranging function in 'Theorems for free'
I'm reading Wadler's 'Theorems for free'. In section 3.5 he states that $m\_{AA}(I\_A)$ is a rearranging (i. e. injective) function. $I\_A$ is the identity function on the type A. $$m : \forall X.\forall Y. (X \rightarrow Y) \rightarrow (X^\* \rightarrow Y^\*)$$ How does he use section 3.4 to prove this without any $\forall^{(=)}X$-types? Why can't $m\_{AA}(I\_A)$ e. g. drop a few elements in the list?

# Answer
> 2 votes
It can, as good evidence for it define `m` as something like

```
m f = map f . drop 2

```

And everything still typechecks. Here "rearranging" is supposed to refer to structural operation on the list without regards to the specific values of each element. This is captured by the free theorem at this type,

```
m (\x -> x) . map f = map f . m (\x -> x)

```

`m (\x -> x)` performs all the structural changes to the list and `map f` actually alters this element. This theorem implies that they are independent of each other.

---
Tags: type-theory
---


# Question
Title: An example of a code that is neither p-code or s-code but is uniquely decodable?
As the title says, code can't be a prefix-code and can't be a suffix-code, but it must be uniquely decodable. One possible code is this: {1, 101, 1001, ... }. Number of zeroes corresponds to the index of the letter in a given alphabet (starting from 0). Clearly it's not p-code and not a s-code and it's uniquely decodable. But I need to find another example of such code. And no, I wont accept {0, 010, 0110, ...}. By the way, code words must consist of 0 and 1, i.e. be binary.

# Answer
An easy way to get new codes of any size is to *compose* a prefix non-suffix code and a suffix non-prefix code. For instance, start with the prefix non-suffix code $X\_5 = \\{0, 10, 110, 1110, 1111\\}$ and compose it with the suffix non-prefix code $\\{0,01\\}$, which consists to replace $1$ by $01$ in $X\_5$ to get $$ S\_5= \\{0, 010, 01010, 0101010, 01010101\\}. $$ The resulting set is a code that is neither prefix nor suffix.

**N.B.** The advantage of this method is that you always get codes, no verification needed.
> 3 votes

# Answer
These lecture notes suggest that 0, 01, 011, 1110 is such an example. An even simpler example is (presumably, I didn't check) 0, 01, 110.

This link came up as the first result for the search *uniquely decodable code examples* on a popular search engine.
> 1 votes

---
Tags: information-theory
---


# Question
Title: Memory Hierarchy and storing data in caches
Question: How many 32 bit integers can be stored in a 16 bit cache line. Answer: 4

can somebody please explain for me why the answer is 4 i did not understand the reason and i think they should give us more given like the number of blocks in the cache..

# Answer
There's probably a typo there: it's not 16 *bits* but rather 16 *bytes*. Each 32 bit integer takes 4 bytes, so 16/4 = 4.
> 2 votes

---
Tags: cpu-cache
---


title: Infinite u decidable languages

text:
# Question
Title: Infinite u decidable languages
I am trying to see if infinite languages are always decidable. I believe it is not always decidable because there will not be a maximum length of string for the Turing machine to halt. Am I on the right path? I am having difficulty coming up with an example infinite language That is decidable.

# Answer
> 3 votes
There are many infinite languages which are decidable, for example $\Sigma^\*$, or the language of all (binary representations of) primes. However, in some sense "most" languages are undecidable, since there are uncountably many languages, but only countably many decidable languages. We also know many explicit undecidable languages, such as the language of (encodings of) Turing machines which halt on the empty input.

All *finite* languages, on the other hand, are decidable.

---
Tags: formal-languages, turing-machines, undecidability
---


# Question
Title: Hardness of a problem related to set cover
Suppose $C\_1, \ldots, C\_m$ are subsets of $\\{1, \ldots, n\\}$. The goal is to find the smallest subcollection of $C\_1, ..., C\_m$ such that each element of $\\{1, \ldots, n\\}$ appears at least $k$ times in this subcollection.

If $k=1$, this is set cover. I would be interested to learn how to prove NP-hardness for $k=2$ and $k=3$.

# Answer
Hine: Given an instance of set cover, add $k-1$ copies of the set $\\{1,\ldots,n\\}$.
> 4 votes

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


# Question
Title: Tackling overlearning neural network issue
I'm trying to train a neural network using this sort of data (for a homework): Number of Features : 42, Target data : 0 or 1, Number of Samples : 111 Individuals ( 69 Cases + 42 Controls )

However i'm facing an over-learning issue (the learning curve approaches the goal set, however the validation curve shows no improvement): the learning stops after less than 15 iterations because of a great number of validation fails: no improvement in the quality of validation tests. I managed to have great results by using 444 (4\*111) examples in my training as I repeated the initial data four times. but i'm not sure if this is clean. In other words, is it alright to repeat existing examples to have more values for training ?

Thanks in advance.

# Answer
> 1 votes
Yes, it is alright to repeat training data, as long as each one is repeated an equal number of times: this does not violate assumptions. That said, it smells to me like a kludge. If you have no theoretical understanding of why the approach was failing without that adjustment, then just randomly tweaking things (like repeating points) in hopes that it will happen to succeed does not seem like the right approach.

Be careful that you don't do cross-validation on the result after repeating samples. You need to separate the test set from the training set *before* repeating. If you repeat samples, then do cross-validation, there is a high likelihood that most or all samples in the test set will also appear in the training set (due to the repetition) and thus you'll be over-fitting -- the cross-validation results won't be meaningful in that case.

---
Tags: neural-networks
---


# Question
Title: Are there two kinds of polynomial hierarchy collapses?
It seems to me that there are two different situations which get called \`\`PH collapse",

(1) That $\exists i \geq 1$ s.t $\Sigma\_i ^p = \Sigma\_{i+1}^p$
(2) That $\exists i \geq 1$ s.t $\Sigma\_i^p = \Pi\_i^p$

* Are these two different independent situations?

---

AFAIK the only natural relation is that $\Sigma\_i^p \subseteq \Pi\_{i+1}^p \subseteq \Sigma\_{i+2}^p$ and I don't think this is enough to make the two above scenarios be equivalent.

* Is there any natural relation even between $\Sigma\_i^p$ and $\Sigma\_{i+1}^p$ or between $\Pi\_i^p$ and $\Pi\_{i+1}^p$? For some $k \> i$, if one shows that $\Sigma\_k^p \subseteq \Sigma\_i^p$ does that say anything about $\Pi\_k^p$ vs $\Sigma\_i^p$ ?

---

* Do both these scenarios lead to the conclusion that $PH = \cup \_{j \geq 1} \Sigma\_j^p = \Sigma\_i ^p$ ? (If yes, then can someone kindly help with the proof?)

---

*Roughly* I guess the proof has to go like this :

That inductively assume that for some $k \> i$ one has shown that $\Sigma\_j^p \subseteq \Sigma\_i^p$ $\forall j$ s.t $i\leq j \leq k$. Now sit at the threshold of the inductive hypothesis — and take some $L \in \Sigma\_{k+1}^p$ and by truncating the first quantifier construct a language $L'$ such that $\langle x,u\_1\rangle \in L'$ iff $x \in \Sigma\_{k+1}^p$ *with* its first existential quantifier fixed to $u\_1$. This makes $L' \in \Pi\_{k}^p$

Now I don't know... something needs to be claimed about $L' \in \Pi\_{k}^p$ to show that $L \in \Sigma\_i^p$. But I don't see what goes here.

# Answer
> 4 votes
Suppose that $\Sigma\_i^p = \Sigma\_{i+1}^p$ (and so $\Pi\_i^p = \Pi\_{i+1}^p$). Then every statement of the form $(\exists y\_1) \cdots (Q y\_{i+1}) f(x,\vec{y})$ for polytime $f$ is equivalent to another statement $(\exists y\_1) \cdots (Q y\_i) g(x,\vec{y})$ for polytime $g$.

Now suppose you have a predicate in $\Sigma\_{i+2}^p$, say $(\exists y) (\forall z\_1) \cdots (Q z\_{i+1}) f(x,y,\vec{z})$. The inner $i+1$ quantifiers are a $\Pi\_{i+1}^p$ predicate, and so they are equivalent to a $\Pi\_i^p$ predicate $(\forall z\_1) \cdots (Q z\_i) g(x,y,\vec{z})$. Adding back the outer quantifier $(\exists y)$, we find that the original predicate is equivalent to a $\Sigma\_{i+1}^p$ predicate, and so $\Sigma\_{i+2}^p = \Sigma\_{i+1}^p = \Sigma\_i^p$.

In the same way, we show that $\Sigma\_i^p = \Sigma\_{i+1}^p$ implies $\Sigma\_i^p = \Sigma\_{i+j}^p$ for all $j$, so that $\mathsf{PH} = \Sigma\_i^p$.

Note that $\Pi\_i^p \subseteq \Sigma\_{i+1}^p$. Indeed, if $(\forall y\_1) \cdots (Q y\_i) f(x,\vec{y})$ is a $\Pi\_i^p$ predicate, then the equivalent $(\exists w) (\forall y\_1) \cdots (Q y\_i) f(x,\vec{y})$ is a $\Sigma\_{i+1}^p$ predicate.

Since $\Pi\_i^p \subseteq \Sigma\_{i+1}^p$, we see that $\Sigma\_i^p = \Sigma\_{i+1}^p$ implies that $\Pi\_i^p \subseteq \Sigma\_i^p$ and so $\Pi\_i^p = \Sigma\_i^p$.

---

Now for the other direction. Suppose that $\Pi\_i^p = \Sigma\_i^p$, and consider some $\Sigma\_{i+1}^p$ predicate $(\exists y\_1) (\forall y\_2) \cdots (Q y\_{i+1}) f(x,\vec{y})$. The inner $i$ quantifiers are a $\Pi\_i^p$ predicate, and so they are equivalent to some $\Sigma\_i^p$ predicate $(\exists z\_2) \cdots (Q z\_{i+1}) g(x,\vec{y})$. Adding back the outer quantifier $(\exists y\_1)$ and folding $y\_1,z\_2$, we obtain a $\Sigma\_i^p$ predicate equivalent to our original $\Sigma\_{i+1}^p$ predicate.

Summarizing, if $\Pi\_i^p = \Sigma\_i^p$ then $\Sigma\_i^p = \Sigma\_{i+1}^p$, and so (as we have seen above) $\mathsf{PH} = \Sigma\_i^p$.

---
Tags: complexity-theory, logic
---


# Question
Title: Occurrences notation in "Compiling Pattern Matching to Good Decision Trees"
From Compiling Pattern Matching to Good Decision Trees (Luc Maranget, *Proceedings of ML '08*, pp. 35–46. ACM, 2008.)

> We also consider the usual *occurrences*. Occurrences are sequences of integers that describe the positions of subterms. More precisely an occurrence is either empty, written $\Lambda$, or is an integer $k$ followed by an occurrence $o$, written $k\cdot o$. Occurrences are paths to subterms, in the following sense: $$\begin{align\*} v/\Lambda &= v\\ c(c\_1, \dots, v\_a)/k\cdot o &= v\_k/o \quad(1\leq k\leq a) \end{align\*}$$

Could anyone explain the occurrences notation a bit?

# Answer
I will try to illustrate the concept more intuitively and informally by representing terms as trees.

A term can be represented as a rooted tree, where the leafs are atomic operands (literals, or variables) and the other nodes are operators. Typically abstract syntax trees can be built on that model as this example (taken in another answer), for which I am giving both the textual syntax and the tree representation.

```
if (x > y) {
   if (y < a) {
     x:= a
     y:= b
   } else {
    x:= b;
   }
 }
              if
     ________/|\________
    /         |         \
   >          if        :=
  / \    ____/|\____   /  \
 x   y  /     |     \ x    b
       <     :=     :=
      / \   /  \   /  \
     y   a x    a y    b

```

But the concept is used in a lot of different contexts, with different kinds of operators. The example term above could also be written as in the text of your question in function call style:

```
if(>(x,y),if(<(y,a),:=(x,a),:=(y,b)),:=(x,b))

```

where the operators are `if`, `>`, `<`, and `:=`.

Whatever the kind of term you are interested in, an occurrence is a position in the tree (to which we can associate corresponding positions in any of the strings representation).

A subterm corresponds to a subtree, and an occurrence is the location of the main operator of a subterm, i.e. its root.

A simple way to designate unambiguously an occurrence is to give the path to access that occurrence from the root of the tree. The path is simply a string of integers that tell you at each node which of the daughter you should consider.

So the empty word $\Lambda$ correspond to the root itself (the top `if` in my example), since there is no path to be followed.

The string $2\\;1\\;2$ tell you to go to the second daughter, then to the first, then the second again. So it is an occurrence corresponding to the position of the leftmost `a`.

That in particular is useful to distinguish the two occurrences of `a`, the other one being $2\\;2\\;2$.

An the occurrence of the term `:=(y,b)` is $2\\;3$.

Of course, an occurrence is meaningful only with respect to a term, and that is why your document systematically associate the reference term with the path, i.e. string, denoting an occurrence in that term.

Actually, the notation used in your document is a bit abusive, though it is common, because an occurrence is really a position in the term, where some subterm occurs, but it is not that subterm (though it is sometimes taken as such if the context makes it unambiguous).

To get the subterm, you should normally explicitly apply a function that takes an occurrence as argument and returns whatever subterm is found there.
> 3 votes

# Answer
An *occurrence* is a sequence of indices (separated by $\cdot$; $\Lambda$ is the empty sequence), which is used to index a vertex in an expression tree. For an expression $e$ and an occurrence $\sigma$, $e/\sigma$ is the vertex at address $\sigma$ in $e$. For example: $$ a(b(x\_1,x\_2),c(y\_1,y\_2)) / 1 = b(x\_1,x\_2), \\ a(b(x\_1,x\_2),c(y\_1,y\_2)) / 1 \cdot 2 = b(x\_1,x\_2) / 2 = x\_2. $$ The definition that you quote is an inductive definition of $e/\sigma$. If $\sigma$ is the empty sequence $\Lambda$, then $e/\sigma = e$. Otherwise, you separate $\sigma$ into the first index $i$ and the rest of the list $\tau$ (which could be empty). If $e\_i$ is the $i$th item in $e$, then $e/i\cdot \tau = e\_i/\tau$, that is, we first go to the $i$th item, and then follow the rest of the address $\tau$ (see the example above).
> 1 votes

---
Tags: functional-programming
---


title: Removing Left Recursion

text:
# Question
Title: Removing Left Recursion
Im currently learning about removing left recursion. Ive watched a few youtube clips and understand the basics. For example, i can remove left recursion for the following;

$E \rightarrow E+T \mid T$

Answer

$E \rightarrow TE'$

$E'\rightarrow \varepsilon \mid +TE'$

Ive been given the following question which has sort of 3 parts to it and has me confused a lot (compared to the question example above). The question is remove the left recursion from the following grammar;

$A \rightarrow Ba$

$B \rightarrow dab \mid cB$

$C\rightarrow cB\mid Ac$

Is there another rule to follow for this, or when it has more than 1 statement as such.

Any help will be much appreciated

# Answer
> 1 votes
The fact confusing you might be, that the given grammar isn't left recursive at all and so nothing has to be done.

To be left recursive there would have to be a nonterminal Symbol, that by a chain of productions results in a sequence of sybols starting with the same nonterminal.

This is not true for `A` since after `A -> B` the only options available are `A -> B -> dab` and `A -> B -> cB` both already starting with terminal symbols on the left.

Trivially the same goes for `B` as `B -> dab` and `B -> cB` are the only options.

Taking a look at `C` the production `C -> cB` can't cause any trouble, since the sequence is already starting with a terminal.

But even the second option `C -> Ac` is harmless, as after `C -> Ac -> Bac` the only options are `C -> Ac -> Bac -> dabac` and `C -> Ac -> Bac -> cBac`, both starting with a terminal symbol again.

---
Tags: formal-grammars, left-recursion
---


title: Eliminate Left Recursion

text:
# Question
Title: Eliminate Left Recursion
The part I want to modify:

```
B -> F | B A | A

```

What is the correct way to remove this left recursion?

I was thinking

```
 B -> F R | A R
 R -> A R | ε

```

But I've been told this is incorrect

# Answer
The "standard" pattern to eliminate the immediate left recursion would have been:

```
B  -> F B' | A B'
B' -> ε | A B'

```

I guess this is why you have been told your solution is not right.

Nevertheless the information that your solution is incorrect is incorrect.

Terms derivable from the original grammar fragment `B -> F | B A | A` are of the form `(F|A)A*`.

The grammar fragment you constructed produces exactly the same language. Hence your solution is correct.
> 1 votes

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


title: Compare vs Radix

text:
# Question
Title: Compare vs Radix
Is it better to use comparison or radix sort to sort a long sequences of java int array?

I know that I should probably use mergesort (NlogN) for comparison sort, since it is one of the fastest and compare that to LSD or MSD. I thought about how for extremely large N, the logarithm would be larger than runtime for LSD, but other than that, the mergesort (comparison) is better.

I wonder if my reasoning is correct because I have seen a question asking about Strings and the answer was the aforementioned. Now this question is about long sequences of java int array and I wonder if I am missing the point.

Any help is appreciated :).

# Answer
In theory sorting a long sequence of int should be a prime candidate for radix sort as it grows linear in the number of elements to be sorted, while any comparison based sorting algorithm can't be faster than N log N.
> 2 votes

---
Tags: sorting, comparison, radix-sort
---


# Question
Title: Checking if several sets of pairs covers a given set of pairs
Suppose we have $N$ arrays of pairs, e.g. for $N=3$:

$A\_1 = \[ \[3,2\], \[4,1\], \[5,1\], \[7,1\], \[7,2\], \[7,3\] \]$,

$A\_2 = \[ \[3,1\], \[3,2\], \[4,1\], \[4,2\], \[4,3\], \[5,3\], \[7,2\] \]$ and

$A\_3 = \[ \[4,1\], \[5,1\], \[5,2\], \[7,1\] \]$.

We can assume that the pairs in every array are sorted by the first number, and then by the second number. Also, the same pair won't appear in the same array more than once (same pair can appear in multiple arrays, as you can see above).

The numbers in every pair are arbitrary integers $\geq 1$.

How could I find all the $k$'s that satisfy:

$\exists \\{ p\_1, p\_2, ... , p\_N\\}\subseteq \[1..N\]\ \forall n \in \[1..N\]: \[k,n\]\in A\_{p\_n}$

The expected result for the example above is: $\[5, 7\]$.

**Note**: Speed is the most critical factor of the algorithm, then memory. If it helps to optimise for speed/memory, assume that $N\leq 10$. The number of pairs in an array can be ~50000.

# Answer
> 1 votes
Here are some hints.

First, reduce your problem to the following one: given a collection of $N$ subsets $A\_1,\ldots,A\_N \subseteq \[N\]$, determine if there is some permutation $\pi$ such that $\pi(i) \in A\_i$.

Given the $A\_i$, construct a bipartite graph in which node $i$ on the left is connected to node $j$ on the right if $i \in A\_j$. A permutation $\pi$ such that $\pi(i) \in A\_i$ exists iff this graph contains a perfect matching. We know how to test whether a bipartite graph contains a perfect matching efficiently.

---
Tags: algorithms, decision-problem
---


# Question
Title: Proving regular languages are closed under a form of interleaving
I've got the following definitions:

$$\mathrm{Interleave}\\,(x,y) = \\{w\_1\dots w\_n\mid w\_i\in\\{x\_i,y\_i\\} \text{ for }i=1, \dots, |x|\\}$$

when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w\_i$ means the $i$-th letter in $w$.

$$\mathrm{Interleave}\\,(L\_1,L\_2)\ \ = \\!\\!\\!\\!\bigcup\_{\substack{x\in L\_1,\ y\in L\_2,\\ |x|=|y|}}\\!\\!\\!\\! \mathrm{Interleave}\\,(x,y)$$ when both $L\_1$ and $L\_2$ are languages.

I have to prove that if I know that $L\_1$ and $L\_2$ are both regular languages, $\mathrm{Interleave}\\,(L\_1,L\_2)$ is a regular language as well.

I have absolutely no idea how to do it .

Thanks in advance.

# Answer
**Hint.** Because $L\_1$ and $L\_2$ are both regular, you know they're accepted by NFAs (or DFAs; it doesn't matter) $M\_1$ and $M\_2$, respectively. To show that $\mathrm{Interleave}\\,(L\_1,L\_2)$ is regular, show that it's accepted by some NFA $M$. For each character it receives, $M$ can decide to act either like $M\_1$ or like $M\_2$.
> 3 votes

# Answer
**Any family of language that is a trio is closed under interleaving with a regular set.**

This includes of course interleaving of 2 regular sets, since regular sets form a trio.

## Proving the result (and more) only with closure properties

**Note:** *I created the definitions below for the purpose of this question. I do not know whether there are established definitions for this, which might exist under another name.*

The purpose of this approach is to avoid any complex construction of automaton. But we need at least one specific operation to account for dealing with several strings at the same time. And, as an unexpected benefit, the end result is much more general (*this is actually more to be expected from proofs based on closure properties*). However, the proof is centered on the question asked, and only includes remarks to show how it generalizes.

Consider two alphabets $\Sigma\_i$ for $i=1,2$. We can consider their product $\Sigma\_1\times\Sigma\_2=\\{(a\_1,a\_2)\mid a\_1\in\Sigma\_1\wedge a\_2\in\Sigma\_2\\}$ as a new alphabet, where the symbols are pairs of symbols of $\Sigma\_1$ and $\Sigma\_2$.

Similarly, with 3 alphabets, we can build an alphabet of triples (instead of pairs). We ignore the trivial issue of associativity in using pairs to build triples, or $n$-tuples, here and in the rest of this answer.

Now, given two strings $x\in\Sigma^\*$ and $y\in\Pi^\*$ such that $|x|=|y|$ we can define the conflation of these two strings as the string $z=\mathrm{Conflate}\\,(x,y)\in(\Sigma\times\Pi)^\*$ with the same size, such that $\forall i\in\[1,|x|\], z\_i=(x\_i,y\_i)$.

We can similarly conflate $n$ strings of equal length into a single string of $n$-tuples of symbols ... but we will not go beyond $n=3$.

Finally, given two languages $L\_1\subseteq\Sigma\_1^\*$ and $L\_2\subseteq\Sigma\_2^\*$ we can define the conflation of these two languages:

$$\mathrm{Conflate}\\,(L\_1,L\_2)=\\{\mathrm{Conflate}\\,(x,y)\mid |x|=|y|\wedge x\in L\_1 \wedge y\in L\_2\\}$$

We can also conflate similarly any number of languages, to produce a language on the cross product of their alphabets.

This $\mathrm{Conflate}$ operation has many simple properties, that are rather trivial to prove.

Given two alphabets $\Sigma\_1$ and $\Sigma\_2$ and two languages $L\_1\subseteq\Sigma\_1^\*$ and $L\_2\subseteq\Sigma\_2^\*$:

* $\mathrm{Conflate}\\,(L\_1,L\_2)\subseteq(\Sigma\_1\times\Sigma\_2)^\*$
* $\mathrm{Conflate}\\,(L\_1,\Sigma\_2^\*)$ is regular iff $L\_1$ is regular
* $\mathrm{Conflate}\\,(\Sigma\_1^\*,L\_2)$ is regular iff $L\_2$ is regular
The proof uses a projection homomorphism that keep only the $L\_1$ or the $L\_2$ component of the conflation.
* side note: the above is also true for context-free, and more generally families of languages closed under non-erasing homomorphism and inverse homomorphism (such as trios). For example, if $\mathcal F$ is a trio, and $L$ is a language, and $\Sigma$ and alphabet (not necessarily the alphabet of $L$), then $\mathrm{Conflate}\\,(L,\Sigma^\*)\in\mathcal F\\;$ iff $\\;L\in\mathcal F$.
* $\mathrm{Conflate}\\,(L\_1,L\_2)= \mathrm{Conflate}\\,(L\_1,\Sigma\_2^\*) \cap \mathrm{Conflate}\\,(\Sigma\_1^\*,L\_2)$
* Hence, if $L\_1$ and $L\_2$ are both regular, then $\mathrm{Conflate}\\,(L\_1,L\_2)$ is also regular.

Now we consider also the alphabet $B=\\{0,1\\}$, and the alphabet cross-product $\Sigma\_1\times\Sigma\_2\times B$, and we define on this alphabet the substitution $\sigma$ as follows:

$\forall (a\_1,a\_2,b)\in(\Sigma\_1\times\Sigma\_2\times B),\\; \sigma((a\_1,a\_2,b))=\\;($ if $b=0$ then $a\_1$ else $a\_2)$.

If $L\_1$ and $L\_2$ are both regular, then $\mathrm{Conflate}\\,(L\_1,L\_2)$ is also regular, and thus $\mathrm{Conflate}\\,(\mathrm{Conflate}\\,(L\_1,L\_2),B^\*)$ is regular, since $B^\*$ is.

Applying the substitution $\sigma$, since regular sets are closed under substitution, we know that the language $\sigma(\mathrm{Conflate}\\,(\mathrm{Conflate}\\,(L\_1,L\_2),B^\*))$ is regular.

But it can fairly easily be proved that

$$\mathrm{Interleave}\\,(L\_1,L\_2)=\sigma(\mathrm{Conflate}\\,(\mathrm{Conflate}\\,(L\_1,L\_2),B^\*))$$

Hence $\mathrm{Interleave}\\,(L\_1,L\_2)$ is regular.

The interesting point here is that, with nearly no further work, we can prove identically that many families of languages, context-free for example, and more generally trios (hence also AFLs), are closed under $\mathrm{Interleave}$ composition with regular languages, notably because the substitution $\sigma$ is non-erasing. This essentially follows from the fact that trios are closed under inverse homomorphism, under intersection with regular sets, and under non-erasing homomorphism.
> 1 votes

---
Tags: regular-languages, finite-automata, closure-properties
---