# Question
Title: Proving that recursively enumerable languages are closed against taking prefixes
Define $\mathrm{Prefix} (L) = \\{x\mid \exists y .xy \in L \\}$. I'd love your help with proving that $\mathsf{RE}$ languages are closed under $\mathrm{Prefix}$.

I know that recursively enumerable languages are formal languages for which there exists a Turing machine that will halt and accept when presented with any string in the language as input, but may either halt and reject or loop forever when presented with a string not in the language.

Any help for how should I approach to this kind of a proof?

# Answer
Below is a hint for working with the Turing Machine (TM) formalism for RE languages. But finishing that approach from the hint depends on how you've been working with TMs.

You have a TM, say $T\_L$ to accept L and you want to construct a new TM $T\_L^'$ for $\text{Prefix}(L)$. You can start $T\_L^'$ on a string $x$ and then do something to finish up with the hypothetical $y$ that completes $xy\in L$. How you do that depends somewhat on the methods you have been using to work with TMs. But that's a hint so far.
> 3 votes

# Answer
Given $TM\_L$ which acceps language $L$, let's construct $TM\_{PL}$ to accept $Prefix(L)$.

Since the set of strings is countable, we can find an one-to-one mapping $f: N \to \Sigma^\star$ from natural numbers to all strings. So $TM\_{PL}$ accepts $x$ iff there is an $i$ that $TM\_L$ accepts $w(i) = x$ ## $f(i)$ (here ## means string concatenation). The intuitive idea to construct $TM\_{PL}$ is to enumerate all $w(i)$ one by one and put $TM\_L$ with input $w(i)$ to an universal turing machine $UTM$ to find whether $w(i) \in L$. But it fails to return the correct answer when $TM\_{L}$ accepts $w(a)$ while it falls into an infinite loop in some $w(b)$ with $b \< a$. Let's find how to avoid this situation.

Remember how to prove the conclusion that $N\_+ \times N\_+$ is countable, where $N\_+$ is the set of all positive natural numbers. We can enumerate $(i, j)$ in the order $(1, 1) \to (2, 1) \to (1, 2) \to (3, 1) \to (2, 2) \to (1, 3) \ldots$. The same technique can be used to solve this problem, where pair $(i, j)$ means "Put $TM\_L$ with input $w(i)$ to $UTM$ and find whether $TM\_L$ accepts $w(i)$ in no greater than $j$ steps". The answer of each pair $(i, j)$ can be got in finite number of steps, and it's not hard to see that $x \in Prefix(L)$ iff there is a pair $(i, j)$ whose answer is yes.
> 2 votes

# Answer
RE means a TM generates the strings. Run that one, and each time there is some output, write its prefixes to the real output.
> 2 votes

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


title: Initial Algebra example

text:
# Question
Title: Initial Algebra example
If the definition of Initial Algebra is:

"An object is initial if there exists a unique morphism from the object to every object in the category"

Why do we need such object, and could any one give an example ?

# Answer
> 6 votes
An initial algebra is an initial object in the category of $F$-algebras for a given endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$.

This construction is widely used to gives semantics to data-structures in (functional) programming languages. Intuitively, the functor $F$ captures the "shape" of the data-structure (e.g., $F(X) = 1 + A \times X$, with $A$ a fixed set for instance).

The underlying set $\mu F$ of the initial algebra $\langle \mu F, \alpha \rangle$ intuitively captures the set of syntactic expressions you can build by induction on the shape functor (e.g., for the previous functor with $A = \\{a,b \\}$, $\mu F = \\{(1), (a,1), (b,1), (a,a,1), (a,b,1) \ldots \\}$ is the set of finite lists of $A$-elements).

The initiality is the key property to construct inductive function (see catamorphism). Some excellent references on this topic:

---
Tags: semantics, formal-methods
---


title: Search spaces and computation time

text:
# Question
Title: Search spaces and computation time
This question follows on previous questions (1), (2), where we define an initial space of possibilities and reason about how a solution is chosen from that.

Consider a problem P where we are given:

1. the initial space of possibilities is exponential in the size of the input,
2. the search space decreases monotonically as we read the input,
3. for the algorithm that correctly computes P and has the minimum worst-case performance, the search space is still exponential in the size of the input even after the final input is read.

Can we conclude that P requires exponential time? If not, what would a polynomial-time counterexample look like?

# Answer
No, in general you can't assume that an exponential search space requires exponential time to search. Linear programming generally has an exponential search space but can be done in (weakly) polynomial time.
> 2 votes

# Answer
No, it completely depends on how much structure your space has. Suppose you want to search for an element in an exponentially large sorted list. Using binary search you only need to look at a polynomial number of elements.

For some special kinds of spaces you can even search infinitely many elements using only finite time. See for example here how to do that in Haskell.

So unless I misunderstand what you mean with "the search space is getting smaller as we read the input" (i.e. how much computational ressources are you allowed to expend to make the search space smaller?) the answer is no, having an exponential (or even larger) search space is not enough to show a lower bound.
> 2 votes

# Answer
The short answer is No. Here is the counter-example:

Problem P: Find the shortest path from source $s$ to target $t$ in a undirected graph $G = (V, E)$.

Input: Initially, the input is |V|, and the complete graph of |V| vertices is assumed. Subsequently, the input consists of edges that need to be *removed* from this original complete graph. (This roundabout input is to cater to your need of search space decreasing monotonically as we read the input).

Search space: All possible paths from $s$ to $t$ in $G$.

The number of paths from $s$ to $t$ grows faster than exponential in |V| (it is a factorial function). But the shortest path can be found in polynomial time, even in the worst case.

In other words, **exponential search space does not imply that no polynomial time algorithm is possible**.
> 2 votes

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


# Question
Title: Closure of Deterministic context-free languages under prefix
For a formal language $L \subseteq \Sigma^{\*}$ I define the set Pref(L) to be:

$\text{pref}(L) = \\{\alpha \in \Sigma^{\*} : \exists \beta \in \Sigma^{\*} \text{ such that } \alpha \beta \in L\\}$

ie. the set of all (not necessarily proper) prefixes of words in $L$. I know that if $L$ is context-free then pref(L) is context-free but if $L$ is deterministic context-free then is pref(L) deterministic context-free?

I am sure this is known but I cannot find the answer anywhere and it's not in Hopcroft and Ullman.

# Answer
DCFL are known to be closed under quotient with regular languages, but the quotient of $L$ with $\Sigma^{\*}$ is precisely $\text{pref}(L)$ so yes, if $L$ is a DCFL then $\text{pref}(L)$ is a DCFL.
> 9 votes

# Answer
DCFLs have LR(0) grammars, and LR parsers have the property that they report the error on the first symbol that can't be legally there. So the strategy would be simply to run the LR parser and accept whatever doesn't give an error before ending the string. (Way overkill, there must be a "simpler" way to prove it, but this convinces me that the result is in fact true. Building a DPDA for the prefixes isn't so easy, a DPDA could just fall into some kind of loop eating up the string without any chance of accepting at the end; to prove it directly by that route you'd have to make sure somehow that if there are legal moves from the current state, there is a path that leads to ultimate acceptance with some remainder, and that looks messy.)
> 1 votes

# Answer
According the concept of context free language very context can be represented in the form of "CHOMSKY NORMAL FORM".so if in the rule we made change like if A-\>BC change it to the A-\>BC/B now this type of replacement will generate the context free language of prefix language of the given
> -1 votes

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


title: Is this intersection of DFAs correct?

text:
# Question
Title: Is this intersection of DFAs correct?
I'm constructing a deterministic finite automata (DFA) for a language of all strings defined over $\\{0,1\\}$ whose length is even and number of $1$s is odd. I constructed each DFA separately and then combined:

* Is the given procedure for combining DFAs correct?
**EDIT:** Originally wrote union; actually taking the intersection.
* Would someone suggest material on constructing DFAs
given restrictions on length and number of $0$s or $1$s?

According to link given by Merbs, I have developed this FA.
This FA does not accept a language of even length.

# Answer
> 8 votes
Yes, this is called the *Product Constuction* \- given DFAs $M\_1$ and $M\_2$, we can construct $M=M\_1\times M\_2$:

* $M$ consists of pairs of states from its constituent DFAs, so if the original DFAs have states $A,B,C$ and $x,y,z$, the product would be $\\{Ax,Ay,Az,Bx,By,Bz,Cx,Cy,Cz\\}$.
* The transition function is updated such that if on a particular step, a string would cause $M\_1$ to transition from state $A$ to $B$ and $M\_2$ to transition from $x$ to $y$, then the product would transition from $Ax$ to $By$
* The initial state is the pair consisting of the initial states of the constituent DFAs (i.e. $Ax$).
* If we are constructing the DFA that determines whether **both** of the two constituent DFAs would accept the string, then the accept states of $M$ is the **intersection** (those pairs made up of accept states from both).
If we are constructing the DFA that determines whether **either** of the two constituent DFAs would accept the string, then the accept states of $M$ is the **union** (those pairs made up of accept states from either).
In your example, $x\_1$ and $y\_0$ are the accept states of $M\_1$ and $M\_2$; the intersection would be $\\{x\_1y\_0\\}$ while the union would be $\\{x\_1y\_0,x\_1y\_1,x\_0y\_0\\}$.

I’ve included some other DFAs regarding restrictions on length for reference.

# Answer
> 1 votes
OK, "laymanized" a bit. Take DFAs $M\_1 = (Q\_1, \Sigma, \delta\_1, q\_1, F\_1)$ and $M\_2 = (Q\_2, \Sigma, \delta\_2, q\_2, F\_2)$. Consider the DFA $M = (Q\_1 \times Q\_2, \Sigma, \delta, (q\_1, q\_2), F\_1 \times F\_2)$, where $\delta$ is defined by: $$ \delta((q', q''), a) = (\delta\_1(q', a), \delta\_2(q'', a)) $$ The idea is that the state of $M$ records the states in which $M\_1$ and $M\_2$ would be if they processed the string separately. $M$ accepts only if both of them do.

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


# Question
Title: Intersection and union of a regular and a non-regular language
> Let $L\_1$ be regular, $L\_1 \cap L\_2$ regular, $L\_2$ not regular. Show that $L\_1 \cup L\_2$ is not regular or give a counterexample.

I tried this: Look at $L\_1 \setminus (L\_2 \cap L\_1)$. This one is regular. I can construct a finite automaton for this: $L\_1$ is regular, $L\_2 \cap L\_1$ is regular, so remove all the paths (finite amount) for $L\_1 \cap L\_2$ from the finite amount of paths for $L\_1$. So there are a finite amount of paths left for this whole thing. This thing is disjoint from $L\_2$, but how can I prove that the union of $L\_1 \setminus (L\_1 \cap L\_2)$ (regular) and $L\_2$ (not regular) is not regular?

# Answer
We can prove this by contradiction. Lets define $\overline{L\_1} = \Sigma^\* \setminus L\_1$. Then we can reformulate $L\_2$:

$L\_2 = ((L\_1 \cup L\_2) \setminus L\_1) \cup (L\_1 \cap L\_2) = ((L\_1 \cup L\_2) \cap \overline{L\_1}) \cup (L\_1 \cap L\_2)$

We know:

* Regular Languages are closed under union, intersection and complement
* $\overline{L\_1}$ and $L\_1 \cap L\_2$ are regular
* $L\_2$ is not regular

Now assume $L\_1 \cup L\_2$ is regular: Then $((L\_1 \cup L\_2) \cap \overline{L\_1}) \cup (L\_1 \cap L\_2)$ is regular (as it is only a union/intersection of regular languages), so $L\_2$ would be regular. That is a contradiction, therefore our assumption is false, and $L\_1 \cup L\_2$ can not be regular.
> 19 votes

# Answer
That is wrong. Consider $L\_1 = \\{a, b\\}^\*$, $L\_2 = \\{a^n b^n : n \ge 0\\}$. $L\_1$ is regular, $L\_2$ isn't; but $L\_1 \cup L\_2 = L\_1$.
> -4 votes

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


title: Simple routing table question

text:
# Question
Title: Simple routing table question
I'm having difficulties understanding the solution to the following question:

> Consider the following description of a LAN:
>
> The main Internet connection is connected to our gateway router. This in turn is part of the backbone network on the 65.21.1.0/24 subnet. The backbone also supports two further routers SALES and RESEARCH. There is one Sales subnetwork 65.21.6.0/23, and two research subnetworks 65.21.100.0/24 and 65.21.200.0/26.
>
> ```
> If the Interface addresses are:
>
> • i1–65.21.1.1
> • i2–65.21.1.2
> • i3–65.21.6.1
> • i4–65.21.1.3
> • i5–65.21.100.1
> • i6–65.21.200.1
>
> ```
>
> What are the routing tables for the SALES and RESEARCH routers?

How is the **via** and **interface** column derived in the solution?

Thanks in advance.

# Answer
This is a simple question on the definition of routing tables. I will add a brief explanation.

Let's take the SALES router. It has two interfaces.

The interface top (65.21.1.2) is connected to the network 65.21.1.0/24.

The interface bottom (65.21.6.1) is connected to the network 65.21.6.0/23.

This can be expressed as the following routing table:

```
network          via        interface
---------------+-----------+---------
65.21.1.0/24     direct      top
65.21.6.0/24     direct      bottom

```

Now we have two research networks accessible via the router RESEARCH. This router has an ip address 65.21.1.3 on the network 65.21.1.0/24. This network is already in the routing table, so the traffic to the research networks can be routed with the following rules.

```
network          via        interface
---------------+-----------+---------
65.21.100.0/24   65.21.1.3   top
65.21.200.0/24   65.21.1.3   top

```

Finally the traffic to all other networks should be sent to the GATEWAY for further processing. Here is the final routing table.

```
network          via        interface
---------------+-----------+---------
65.21.1.0/24     direct      top
65.21.6.0/23     direct      bottom
65.21.100.0/24   65.21.1.3   top
65.21.200.0/24   65.21.1.3   top
default          65.21.1.1   top

```

The routing table for the RESEARCH router can be assembled following the same logic.
> 4 votes

---
Tags: algorithms, computer-networks, routing
---


# Question
Title: Clarification on halting predicate computability
I am tackling the halting problem right now and its remarkable theorem. My book states $\text{HALT}(x,y)$ is true if $\psi^{(1)}\_{\mathcal P}$ is defined and conversely $\text{HALT}(x,y)$ is false if $\psi^{(1)}\_{\mathcal P}$ is undefined.

The purpose of the theorem, of course, is showing that $\text{HALT}(x,y)$ is a not computable predicate. I will report the extract of the proof given:

Suppose $\text{HALT}(x,y)$ were computable. Then we could construct the program $\mathcal P$:

$$\[A\]\\;\\;\\;\\;\\;\text{IF HALT}(X,X)\text{ GOTO } A$$

It is quite clear that $\mathcal P$ has been constructed so that

\begin{equation} \psi^{(1)}\_{\mathcal P}= \begin{cases} \text{undefined} \\;\\;\\; \text{if HALT}(x,x) \\ 0 \\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\text{if ~HALT}(x,x) \end{cases} \end{equation}

I don't understand how $\psi^{(1)}\_{\mathcal P}$ is undefined if $\text{HALT}(x,x)$ is true, shouldn't $Y$ be equal to $0$ by default and moreover how could a non-terminating program ~~be defined~~ can have $0$ as output value. What am I missing here?

***Edit***: $\psi^{(1)}\_{\mathcal P}(x)$ is the value of the output variable $Y$ at the terminal snapshot.

# Answer
> 5 votes
Let's walk through the proof given by \[Davis94\]. I am familiar with this text and have it in front of me. The HALT predicate is defined:

$$ HALT(x,y) \Longleftrightarrow \text{program number $y$ eventually halts on input $x$.} $$

Given this defintion of HALT, don't worry about how such a program would be defined. It is not important. Just *assume* that HALT exists, that it works, and that this is what it does: It uses $y$ (a Gödel number -- see Section 8 of Ch. 3) which represents a particular program, and $x$, an input to that program, and tells us if that program halts when it is run with that input. It can do this for *any* program, with *any* input.

Now, let's define a new program called $P$:

$$ \[A\]~\text{IF}~HALT(X,X)~\text{GOTO A} $$

Look at how we are using HALT here: we are asking "Does program X halt when given an input of X (itself)?" And if it does halt, we loop infinitely -- creating a program that does not terminate -- a program that does not halt. In other words:

$$ \psi\_P^{(1)}(x) = \begin{cases} \text{undefined} & \text{if} & ~~~~HALT(x,x) \\ 0 & \text{if} & \sim HALT(x,x) \end{cases} $$

Let's pause and answer your first question about $\psi\_P^{(m)}$ being undefined: this is part of the definition given in Section 4 of Chapter 2: $\psi\_P^{(m)}(r\_1,...,r\_m)$ is undefined if $P$ never terminates. And our program never terminates when $HALT(x,x)$ is true because we have written it that way, it loops infinitely. As to your second question about the default output of 0: this happens when the program $P$ ***does*** terminate.

Now let the Gödel number of our new program $P$ be $y\_0$. This means that

$$ HALT(x,y\_0) \Longleftrightarrow ~ \sim HALT(x,x). $$

(we are taking the left side from the definition of HALT and the right side from our program $P$). Since this is true for *any* input $x$ we could also write:

$$ HALT(y\_0,y\_0) \Longleftrightarrow ~ \sim HALT(y\_0,y\_0), $$

which is clearly a contradiction; HALT cannot exist.

# Answer
> 4 votes
In the definitions in this question the relationship between the program and its inputs and the arguments of the $\text{HALT}(x,y)$ predicate is missing.

Suppose $\text{HALT}(x,y)$ is true if the program encoded by the number $x$ terminates on an input $y$.

Now assuming $\text{HALT}(x,y)$ is computable, define a program $\mathcal{P}$ as in the question. Note that if $\text{HALT}(x,y)$ is false, the program does nothing and the tape holds its default value of 0.

The input-output relation defined by the program $\mathcal{P}$ is

$$ \psi^{(1)}\_\mathcal{P} (x) = \left\\{ \begin{array}{ll} undefined,&\textrm{if }\text{HALT}(x,x) \\ 0, &\textrm{if not } \text{HALT}(x,x)\end{array}\right. $$

Now let $x\_{\mathcal{P}} = \mathop{\textrm{code}}(\mathcal{P})$ be the number that encodes the program defined above. Then $HALT(x\_{\mathcal{P}},x\_{\mathcal{P}})$ might be either true or false.

Consider the first case when $\text{HALT}(x\_{\mathcal{P}},x\_{\mathcal{P}})$ is true. Then $\mathcal{P}$ terminates on x\_{\mathcal{P}, therefore $\psi^{(1)}\_\mathcal{P} (x\_{\mathcal{P}}) = 0$, but according to the definition of $\mathcal{P}$ it should be undefined. Thererfore $\text{HALT}(x\_{\mathcal{P}},x\_{\mathcal{P}})$ cannot be true.

Similarly $\text{HALT}(x\_{\mathcal{P}},x\_{\mathcal{P}})$ cannot be false (you can check).

This is a contradiction to our initial assumption of the computability of $\text{HALT}(x,y)$.

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


title: Is this language regular or not?

text:
# Question
Title: Is this language regular or not?
$L\_1=\\{a^ku \mid u \in \\{a,b\\}^\* $ and $u$ contains at least $k$ a's, for $k\geq 1\\}$.

If it is regular, I haven't found its regular expression or any closure property to prove it.

If not, it seems pumping theorem holds for it...

Also, what about the language where the above "at least" is changed to "at most"?

# Answer
> 10 votes
Take $k=1$. No need to go further, any more $a$ can be absorbed by $u$ without risk.

So you need $u$ to have at least 1 $a$ and only $a$'s or $b$'s. Therefore, $L\_1$ is described by $a(a|b)^\*a(a|b)^\*$ and is regular.

For the side question (at most $k$ $a$'s, let's call that language $L\_2$), you can reason in a similar fashion to get $u$ as small as possible. For simplicity let's consider $L\_3$ the intersection of $L\_2$ with the one denoted by $a^\*ba^\*$. You have $L\_3=\\{a^k b a^j, k \geq j\\}$. Intersection with its reverse yields $\\{a^kba^k\\}$ which is not regular, therefore $L\_2$ is not regular either since regular languages are closed under intersection and reversal.

# Answer
> 6 votes
They way I read the question for the first time, I understood $k$ to be a fixed parameter. Define the following languages, for $k\ge 1$:

$$L\_k = \\{ a^ku \mid u\in \\{a,b\\}^\* \text{ and $u$ has at least $k$ $a$'s }\\}$$

$$\tilde L\_k = \\{ a^ku \mid u\in \\{a,b\\}^\* \text{ and $u$ has at most $k$ $a$'s }\\}$$

The difference is that for any $L\_k$, $k$ is only one specific fixed value (while one can understand $L\_1$ to be the union for any $k\ge1$).

Still, those languages are regular. A regular expression for the first might be $a^kb^\*\underbrace{ab^\*\ldots ab^\*}\_{k \text{ times}}(a+ b)^\*$. A regular expression for the second may be $a^kb^\*\Big(a+ab^\*a + ab^\*ab^\*a + \ldots + \underbrace{ab^\*ab^\*\ldots a}\_{k-1\ a\text{'s}}\Big)b^\*$. It is not too hard to come up with NFAs for both languages.

---

This gives a very nice example about (infinite) unions of regular languages: although $L\_k, \tilde L\_k$ are regular for any $k$, and although regular languages are closed for unions, when we take their **infinte** unions (abusing notations!): $$ L\_1 = \bigcup\_k L\_k \qquad L\_2 = \bigcup\_k \tilde L\_k$$ $L\_1$ **is** regular, while $L\_2$ is **not**!
(where $L\_1$ is defined in the OP's question, and $L\_2$ is the like $L\_1$ but with "at most")

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


# Question
Title: The use of multiset ordering in proving termination
Based on the definition of a multiset and the information in this paper, why do we use multisets in proving the termination of a program? Is not the well-founded order enough?

# Answer
As I understand the paper (and I was not familiar with it before) to prove termination of a program using the method of Floyd it is enough to find a function $\tau$ that maps the states of the program into some well-founded set $(S,\prec)$ such that this function is consistent with the program steps. Here consistency means that if a state $s$ follows $s^\prime$, then $\tau(s^\prime)\prec \tau(s)$.

Prior to Manna and Dershowitz the method of Floyd was used by mapping the states into the set of natural numbers or into the set of $n$-tuples thereof with lexicographic ordering (both sets are well-founded). The authors suggest a new source of well-founded sets for the Floyd method, that is the set of multisets of finite structures with multiset ordering and show how this can simplify termination proofs.

Note also that contrary to the sets of natural numbers and lexicographically ordered $n$-tuples, multisets ordering is only a partial ordering.
> 5 votes

---
Tags: algorithm-analysis, proof-techniques, correctness-proof, sets
---


# Question
Title: DFA that accepts decimal representations of a natural number divisible by 43
First, I have tried to build a DFA over the alphabet $\sum = \\{0,\dots, 9\\}$ that accepts all decimal representations of natural numbers divisible by 3, which is quite easy because of the digit sum. For this I choose the states $Q = \mathbb{Z}/3\mathbb{Z}\cup\\{q\_0\\}$ ($q\_0$ to avoid the empty word), start state $q\_0$, accept states $\\{\[0\]\_3\\}$ and $\delta(q, w) =\begin{cases} \[w\]\_3 &\mbox{if } q = q\_0 \\ \[q + w\]\_3 & \mbox{else } \end{cases}$

Of course, it doesn't work that way for natural numbers divisible by 43. For 43 itself, I would end in $\[7\]\_{43}$, which wouldn't be an accepting state. Is there any way I can add something there or do you have other suggestions on how to do this? Thanks.

# Answer
If the string read has a certain decimal value, then reading the next digit changes that value: multiply by $10$ and add that digit. The DFA keeps track of that value modulo $43$. Thus, for $q\in \\{0,1,\dots,42\\}$ and $a\in \\{0,1,\dots,9\\}$ you do

$\qquad \delta(q,a) = (10\cdot q + a) \bmod 43$.

Note that the DFA does not actually perform the computation; the transition is hard-coded.
> 10 votes

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


title: Questions about amortised analysis

text:
# Question
Title: Questions about amortised analysis
As a preperation of an exam about algorithms and complexity, I am currently solving old exercises. One concept I have already been struggling with when I encountered it for the first time is the concept of amortised analysis. What is amortised analysis and how to do it? In our lecture notes, it is stated that "amortised analysis gives bounds for the "average time" needed for certain operation and it can also give a bound for the worst case". That sounds really useful but when it comes to examples, I have no idea what I have to do and even after having read the sample solution, I have no idea what they are doing.

> Let's add up 1 in base 2, i.e. 0, 1, 10, 11, 100, 101, 110, 111, 1000, ... Using amortised analysis, show that in each step only amortised constantly many bits need to be changed.

(the exercise originally is in German, so I apologise for my maybe not perfectly accurate translation)

Now the standard solution first defines $\phi(i) := c \cdot \\# \\{\text{1-bits in the binary representation}\\}$ for some constant $c \> 0$. I think this is what is called the potential function which somehow corresponds to the excessive units of time (but I have no idea why I would come up with this particular definition). Assuming that we have to change $m$ bits in the $i$-th step. Such a step always is of the form

$$\dots \underbrace{0 1 \dots 1}\_m \to \dots \underbrace{1 0 \dots 0}\_m.$$

This statement is understandable to me, however again I fail to see the motivation behind it. Then, out of nowhere, they come up with what they call an "estimate"

$$a(i) = m + c(\phi(i) - \phi(i-1)) = m + c(-m + 2)$$

and they state that for $c=1$, we get $a(i)=2$ which is what we had to show.

What just happened? What is $a(i)$? Why can we choose $c=1$? In general, if I have to show that in each step only amortised constantly many "units of time" are needed, does that mean that I have to show that $a(i)$ is constant?

There are a few other exercises regarding amortised analysis and I don't understand them either. I thought if someone could help me out with this one, I could give the other exercises another try and maybe that'll help me really grasp the concept.

Thanks a lot in advance for any help.

# Answer
> 6 votes
Let $a\_i$ be the amortized costs of operation $i$, $c\_i$ be the actual costs of operation $i$, and $D\_i$ the data structure after operation $i$. The amortized costs of an operation are **defined** as $$a\_i:=c\_ i+ \Phi(D\_i) -\Phi(D\_{i-1}).$$ You usually assume the following

1. The potential is always positive, that is $\forall\colon i \Phi(D\_i)\ge 0$,
2. In the beginning the potential is 0, that is $\Phi(D\_0)=0$.

These two assumptions are not always necessary but they are commonly used and make the life easier. Now you can consider the potential at costs that have already been paid by previous operations.

To justify this definition consider the accumulated costs of all operations. We get the following telescoping sum $$ \sum\_{i=1}^n a\_i = \sum\_{i=1}^n (c\_i +\Phi(D\_i) -\Phi(D\_{i-1})) = \Phi(D\_n) -\Phi(D\_{0}) + \sum\_{i=1}^n c\_i \ge \sum\_{i=1}^n c\_i. $$ So you see that the sum of the amortized costs exceeds the total actual costs. Hence the amortized costs give an upper bound.

I have not seen the use of the $c$ in your formula. But the $c$ can be simply added to the potential function $\Phi$. So think of the $c$ as a factor that weights the potential, and be redefining the function $\Phi$ you can get rid of it.

So to answer your concrete questions. $a(i)$ denotes the amortized costs for the $i$th operation, that is the actual costs in a sequence of operation charged to operation $i$. The $c$ is some positive factor you can pick. And the $a(i)$s are not constant in general (they are in your example) - you don't have to show anything for the $a(i)$ costs, the values $a(i)$ are the result of your analysis.

Since you seem to speak German, you might also have a look at my German class notes to the potential function.

# Answer
> 4 votes
The potential function method is complicated, your example is simple. The number of bits changed is 1 about half the time, 2 about a quarter of the time, 3 about an eighth of the time, and so on. This is because the number of bits changed, starting from 0, is 1,2,1,3,1,2,1,4 and so on (you get the pattern). So the average number of bits changed is $$ \sum\_{k=1}^\infty \frac{k}{2^k} = \sum\_{k=1}^\infty \sum\_{l=k}^\infty \frac{1}{2^l} = \sum\_{k=1}^\infty \frac{1}{2^{k-1}} = 2. $$

# Answer
> 3 votes
Amortized analysis deals with the runtime cost of an operation as an *average over a sequence of operations.* This is similar to the financial concept of amortization -- a single lump sum, such as a loan, is *amortized* over a period of time. This fixes a monthly payment for example, even though the principal balance is growing smaller.

In this way, an *amortized running time* is a type of average, although not the same as an average-case runtime which involves probabilistic analysis on a distribution of inputs.

There are three standard techniques for performing amortized analysis: (1) the aggregate method, (2) the accounting method, and (3) the potential method. This last one is what you are seeing in your lecture notes, and the one A. Schulz is using in his answer. It is also a bit more complicated.

I'd point you to JeffE's excellent lecture notes which include an explanation of all three techniques, starting with the oft-cited example (and the one you encountered) of incrementing a binary counter. It shows that the amortized cost of an increment operation is $O(1)$ when averaged over a sequence of such operations even though the worst-case runtime is $O(\log n)$.

Another resource would be Chapter 17 of \[CLRS01\], which starts with another common example, a stack with a "multi-pop" operation.

# Answer
> 2 votes
I think the problem statement is clearer when you think of it as a counter that starts at 0 and has an operation that increments the value by one. Every time the counter from your problem is incremented, exactly one bit is flipped on and zero or more bits are flipped off$^\*$. The potential function from the example problem is not as out-of-the-blue as you might think. The key to the matter is that only a bit that has previously been turned on can be flipped off. So every time we do an increment operation and turn on a bit, we will store one unit of time in to our "savings account" (the potential function) which we can use for turning that bit off later on.

$^\*$This is because when incrementing the counter, you first look at the rightmost bit. If it is off, you turn it on. If it is on, you turn it of and look at the bit one position to the left. If it is off, turn it on and stop. If it is on, turn it off and look at the bit to the left of that bit. So the number of bits you flip in one operation is equal to the position of the first 0-bit from the right.

Initially, both the counter and potential function are 0. After doing one increment operation, the counter is 1 and the potential function is 1 as well. If we increment again, the counter becomes 10. The potential function remains 1. After another step, the counter is 11 and the potential function 2. If we were to increment the counter again, we would need to flip 3 bits to go from 011 to 100. For this we have to use some of the potential and we end up with a new potential of 1. The trick is that the total number of bits actually flipped so far plus the potential function is always equal to two times the number of increment operations. Because the potential function is never negative, the total number of bitflips after $n$ increment operations is at most $2n$, so each operation takes amortized $2$ bitflips.

Another very good example is the array list. Here we have a list (supporting iterating over all the elements and adding a new element) which is implemented by storing the elements in an array. The array initially starts out quite small (say 2 places). When we add an element, it is stored in the array. When we are about to add the 3rd element, there is no more space in the array. To counter this, we create a new array of double the size and copy over all the elements from the original array. This can take a very long time (linear in the number of elements) but amortized analysis shows that each add operation takes only constant time. The array list performs really well in the real world (much better than the linked list). Each operation can be done in constant time, with the caveat that occasionally an operation will take much longer. So these kinds of data structures are not very fit for use in real-time systems but if on occasion you can afford to wait they're very good.

---
Tags: algorithm-analysis, proof-techniques, amortized-analysis
---


# Question
Title: Analyzing rules of articles in languages
I'm interested in finding a solution for the following problem:

* problem space: any language that has more than 1 article
* let's take German language as example. So the articles in German are "der", "die", "das". - every word has an article as prefix and you must use the article. for example you can't say just "Auto"(car), you must say "das Auto".
* If you are not a native German speaker, you have bad luck, because you have to memorize the article too, when learning a new word, since there are only 3-4 rules to know which word takes which article. And those rules are perhaps about max. 10% percent of the vocabulary. (for example if a word ends with "-ung", it takes "die")

---

So here comes the funny part: as a non-native-German-speaker, i wanted to analyze the language from an IT-point of view and asked some friends of mine random words with the following properties:
* first I reduced the input set from "any German word" to "a German word", for which no known article rule exists".
* then I extended the input set with "made up words", which do not exist.

Every candidate had the same answer for German words, which should be not surprise. But when I asked them per word "why do you think/feel that the article of the word is "der/die/das"?" they couldnt give an answer. They just know it, without knowing why.

Here comes the real hammer: every candidate had the same answer for any made-up non-German word. I say anything, make any meaningful voice, and they all give the same answer (ie. article).

I'm pretty sure that I'm not the first human being in the world who made thoughts about this topic. And I'm interested in any scientific papers/research about that topic. By the way, what I definitely do NOT need is, any method (like neural networks) which outputs a pure mathematical function. I thought about following possibilities:

* focusing on feelings of subjects psychologically (I think it can be managed with colors somehow etc.)
* analyzing the words statistically according to their syllable structure

Where can I begin? What are your suggestions? Are there any Machine Learning research about that topic?

# Answer
> 1 votes
A language is a result of a complex historical development. If the development were guarded by simple language generating rules it would've been different like some artificial languages such as the Esperanto language.

Many natural languages have nouns split into several categories. These categories are often referred to as the Gender. Though the link between the grammatical gender and the natural or biological gender is not always obvious.

In Slavic languages for instance the gender of a word can be guessed from the flection at the end of the word. E.g. in Russian "облако" (a cloud) is neutral, "-о" is the flection, and "зима" (the Winter) is femenine, "-а" is the flection.

In Old English the category gender did exist but was eliminated during the evolution towards the Modern English. In general all languages that stem from the Latin language inherited some form of grammatical gender (for more details see the discussion in Wikipedia).

When learning the language one has to memorize at least the words and there meaning. In learning languages that keep grammatical gender one has to memorize the gender as well. You can find the gender of a word in any German dictionary.

Look at the small letter *f*, *m*, or *n*, printed in italics next to the word.

E.g.

**Bündel**, *n* a bundle;

**Bus**, *m* a bus;

**Tasse**, *f* a cup;

That is "Das Bündel", and "Der Bus", and "Die Tasse".

When a comprehensive dictionary is available for a language with all the nouns annotated with their respective grammatical gender, I guess there is little space left for machine learning. It is much more easy to keep the complete dictionary in memory than to devise a set of rules that would always be prone to errors.

---
Tags: machine-learning, natural-language-processing
---


title: Show $H_1(x)$ is partially computable

text:
# Question
Title: Show $H_1(x)$ is partially computable
I need to show that $H\_1(x)$ defined as follows is partially computable.

\begin{equation} H\_1(x)= \begin{cases} 1 \\;\\;\\;\\;\\;\text{ if } \Phi(x,x) \downarrow \\ \uparrow \\;\\;\\;\\;\\; \text{ otherwise} \end{cases} \end{equation}

The thing is my textbook, that is "Computability, Complexity, and Languages" by Davis, Sigal and Weyuker, lacks of examples and walkthroughs so, personally, I find hard solving even the easiest exercises.

I think I can prove $H\_1(x)$ partially computable, if I can find a program $\mathcal P$ that executes it.

First of all for the Universality Theorem:

$$\Phi(x,x) = \psi^{(1)}\_{\mathcal P}(x) \text{ and } \\# (\mathcal P)=x$$

so I can write a program that computes $\psi^{(1)}\_{\mathcal P}(x)$:

\begin{array} \\ \\;\\;\\;\\;\\;\\;\\;\\;\\;Y \gets 0 \\ \\;\\;\\;\\;\\;\\;\\;\\;\\;\text{IF } X \neq 0 \text{ GOTO } A \\ \[E\] \\;\\;\\;\text{ GOTO } E \\ \[A\]\\;\\;\\;\\; Y \gets Y+1 \end{array}

I don't know if I am on the right track. I would greately appreciate every comment, suggestion, nudge in the right direction, because I really feel kind of lost.

**Attempt #2**: First of all I am so very sorry for not providing you enough details. Basically: $$\Phi^{(n)}(x\_1, \ldots, x\_n, x\_{n+1}) = \psi^{(n+1)}\_{\mathcal P}(x\_1, \ldots, x\_n, x\_{n+1})$$

in plain English $\psi^{(n)}\_{\mathcal P}(x\_1, \ldots, x\_n)$ is the value of the output at the terminal snapshot; $\Phi^{(n)}(x\_1, \ldots, x\_n, y)$, where $\\#(\mathcal P) = y$ is the universal program $\mathcal U\_n$, which works as an interpreter, it keeps track of the current snapshot by *decoding* the number of program being interpreted, decides what to do next and do it. So $f(x) = \Phi^{(1)}(x,y)=\psi^{(2)}\_{\mathcal U\_1}(x,y)$. So my answer would be:

\begin{array} \\ \\;\\;\\;\\;\\;\\;\\;\\;\\;\text{IF } \Phi(x,x) \text{ GOTO } C \\ \[A\] \\;\\;\\;\text{ GOTO } A \\ \[C\]\\;\\;\\;\\; Y \gets 1 \end{array}

or

\begin{array} \\ \\;\\;\\;\\;\\;\\;\\;\\;\\;\text{IF STP}^{(2)}(x,x,y,k) \text{ GOTO } C \\ \[A\] \\;\\;\\;\text{ GOTO } A \\ \[C\]\\;\\;\\;\\; Y \gets 1 \end{array}

where $STP^{(n)}(x\_1, \ldots, x\_n, y, t)$ is a primitive recursive predicate that happens to be true if the program with number $y$ on input $(x\_1, \ldots, x\_n)$ eventually stops after $t$ steps.

# Answer
> 4 votes
Many such exercises are best solved by writing down programs in your favorite programming language. However, a typical programming language cannot examine its own source code, or the source code of a subroutine, or of another program, whereas a Turing machine can. So we need to enrich the language with two special constructs:

* `eval(x,y)` which runs source code `x` on input `y` and returns the result. This is more or less the universal Turing machine. (Yes, the Python toplevel interactive shell is the same thing as a universal Turing machine.)
* `uneval(f)` which accepts a function `f` and returns its source code. This allows us to inspect source code, and to simulate it step-by-step (we can implement a "debugger" by hand once we get acces to source code).

Strictly speaking, `eval` is not needed because it can be implemented in a general-purpose programming language. It amounts to implementing an interpreter for the language inside the language itself, a favorite programming exercise of people who design programmng languages.

So, to so solve your exercise in Python:

```
def H1(x):
  "Simulate the machine x on input x. Return 1 if it halts, cycle otherwise."
  eval(x, x)
  return 1

```

That was easy, and to the point. Fiddling with Turing machines just obscures the fact that this is a very easy exercise (although at some point you do need to convince yourself that Turing machines can do all the things that a programming language can do, and vice versa).

By the way, when you pose questions here, you should not assume that everyone knows your textbook by heart. You should explain notation such as $\Phi(x,x)$. I had to guess what you meant.

---
Tags: computability, check-my-proof
---


# Question
Title: Can a collection of oracle machines decide every language?
If I have a collection of oracle machines, can I decide every language? (I got this question from a former university exam and it sparked my interest).

I thought if my collection has to be countable than I can't decide every language, since there's an uncountable amount of languages.

But if my collection can be of any kind I figured could just add an oracle machine for every language with an oracle for that language, which would be sort of a trivial - brute force approach (the size of the collection would be uncountable than).

Is there an issue with my approach / did I miss something? What happens if I have a countable number of oracles that can be used?

# Answer
> 5 votes
This answer assumes that "a collection of oracle machines" means "a sequence of oracles", that is, you have a Turing machine with access to a sequence of oracles.

A sequence of oracles is equivalent to a single oracle: if the original sequence is $O\_i$, choose some pairing function $\langle \cdot,\cdot \rangle$ (e.g. $\langle x,y \rangle = 2^x (2y+1)$), and define a single oracle $O$ by $\langle x,y \rangle \in O$ if $y \in O\_x$.

It is known that a machine with oracle access to $O$ cannot decide all languages, for reasons of cardinality. We can also exhibit a specific language undecidable by such a machine, namely the halting problem for oracle machines with oracle access to $O$.

# Answer
> 3 votes
Yes, if your collection of oracles is $2^{\Sigma^\*}$ then every language in $2^{\Sigma^\*}$ can be decided by a oracle machine from this class (the language itself): the Turing machine will pass its input to the oracles and will output the oracle's answer.

If the size of the set of oracles is countable the by the cardinality argument there are many languages that cannot be decided by OTMs with oracles from that set.

---
Tags: formal-languages, computability
---


# Question
Title: NP-Hard problems that are not in NP but decidable
I'm wondering if there is a good example for an easy to understand NP-Hard problem that is not NP-Complete and not undecidable?

For example, the halting problem is NP-Hard, not NP-Complete, but is undecidable.

I believe that this means that it is a problem that a solution for can be verified but not in polynomial time. (Please, correct this statement if this is not the case).

# Answer
> 35 votes
By the nondeterministic version of the time-hierarchy theorem, we have $\mathsf{NP} \subsetneq \mathsf{NEXP}$, where $\mathsf{NEXP}$ is the class of problems solvable in non-deterministic exponential-time. Thus it suffices to consider any problem which is $\mathsf{NP}$-hard and in $\mathsf{NEXP}$, but not in $\mathsf{NP}$. For instance, we may consider any $\mathsf{NEXP}$-complete problem, such as

* **3-colourability of graphs described by succinct circuits** — or any other NP-complete problem on graphs — where a "succinct circuit" is a format for representing very large graphs at the input: instead of explicit representation of a graph *e.g.* by adjacency lists, we instead provide a circuit computing some function $f: \\{0,1\\}^{n} \times \\{0,1\\}^n \to \\{0,1\\}$ which computes the coefficients of a $2^n \times 2^n$ adjacency matrix.
* **(Non-)equivalence of two regular expressions,** where the Kleene star is replaced by squaring (repeating a sub-pattern exactly twice, rather than zero or more times), and where we ask whether two such regular expressions represent different sets of strings.

Note that in the latter case, if we take regular expressions as we are used to considering, including the Kleene star, the resulting problem is $\mathsf{EXPSPACE}$-complete: because we have the containments $\mathsf{NP} \subset \mathsf{NEXP} \subseteq \mathsf{EXPSPACE}$, this is still a decidable problem which is $\mathsf{NP}$-hard, and not in $\mathsf{NP}$.

# Answer
> 10 votes
*Disclaimer: This answer is based on the assumption that $\mbox{PSPACE} \neq \mbox{NP}$, a hypothesis most scientists strongly believe, but we have yet to prove. This means that there is a possibility that these problems are in $\mbox{NP}$ and thus also $\mbox{NP}$-complete.*

I would say the simplest most are True quantified Boolean formula and Generalized geography, both $\mbox{PSPACE}$-complete.

TQBF is given a *quantified* boolean formula, test whether the formula is true, i.e. formulae on the form $\forall x \exists y \forall z . \\; \[(x \lor y) \land z\]$ is false, because setting $z$ to false yields a false statement.

Generalized Geography is a fun game (see Word chain) where you have a list of strings (e.g. city names) and Player 1 starts by saying a name, and Player 2 responds with a name starting on the letter the previous name ended with. Then it's Player 1's turn, until someone get stuck (this game is recommended to play as a drinking game where objects are bands/artists, movies, cities, capitals, famous mathematicians or whatever floats your boat. The one who cannot respond within reasonable time must of course drink). The formal problem is stated as the question *"does Player 1 have a winning strategy"*.

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


# Question
Title: Variation of the dining philosophers: is the standard solution still valid?
I have a problem that is almost equal to the standard one of the dining philosophers, but has a quirk: while a philosopher thinks, he still holds the fork on his left.

If after the period of thinking (which isn't infinite), I release the fork on the left and then apply the normal solution (that is, acquire forks in the order of their priority), then would this solution be correct for this problem?

# Answer
> 1 votes
If the philosopher eats (holding both forks), drops the right fork and thinks for a while, and then drops the left fork to take a nap (or something similar), it is just the original problem: Each philosopher must ensure getting both forks without deadlock. Take a look at Allen B. Downey's "The Little Book on Semaphores" for in-depth discussion (this problem is *hard*!).

---
Tags: operating-systems, concurrency, synchronization
---


title: NL- definition and a problem

text:
# Question
Title: NL- definition and a problem
The question is: What is the smallest complexity class in which the following problem is contained: Given a graph with $n$ nodes, Is there independent set of size of at least $n-10$?

I have a little difficulty to understand the meaning of being in ${\sf L}$ and examine problems in a correct way for deciding if they are in ${\sf NL}$ or ${\sf L}$

First I know that for being in ${\sf NL}$ I need to provide a verifier for a Turing machine which uses only $O(\log n)$ space on its working tape- So I wonder- I can give as a verifier this set of nodes to be independent set as requested, but how does the checking work? Can it go to all the lists of the pointers to the neighbors of each node , and for every node to check whether all the other nodes in the set given as independent set is not on that list- Is this considered of not using any space and I only need to count the nodes in the list that fulfill the requirement and therefore use only $O(\log n)$ space? Is this correct? Is there a way to prove that the problem is in ${\sf L}$?

# Answer
Hint: How much space do you need to store a set of $10$ vertices? How much space does it take to go over all pairs of nodes in a graph?

Another hint: How much space does it take to implement the following algorithm? (I replaced 10 with 3 to make it easier to follow)

```
 int algorithm(int n, int G[n][n]) {
   int x, y, flag;
   int v1, v2, v3;

   for (v1 = 0; v1 < n; v1++)
     for (v2 = 0; v2 < n; v2++)
       for (v3 = 0; v3 < n; v3++) {
         flag = 0;
         for (x = 0; x < n; x++)
           for (y = 0; y < n; y++)
             if ((x != v1) && (x != v2) && (x != v3) &&
                 (y != v1) && (y != v2) && (y != v3))
               flag |= G[x][y];
         if (flag == 0)
           return 1;
       }
   return 0;
 }

```
> 5 votes

---
Tags: complexity-theory, space-complexity
---


title: BPP clarification

text:
# Question
Title: BPP clarification
I know that $\sf BPP\[2/3,1/3\]= BPP\[\alpha,\beta\]$ when $\alpha\lt\beta$, but I read something on Wikipedia which got me confused:

> In practice, an error probability of $1/3$ might not be acceptable, however, the choice of $1/3$ in the definition is arbitrary. It can be any constant between $0$ and $1/2$ (exclusive) and the set $\mathsf{BPP}$ will be unchanged.

The reason for my question is the this question that I'm trying to answer:

We define the class $PP\_{\frac{7}{8}}$: $L \in PP\_{\frac{7}{8}}$. There's a probabilistic Turing machine that for $x \in L$ accepts $x$ with probability $\>$ than $\frac{7}{8}$ and for $x \notin L$ it accepts $x$ with probabilty $\leq \frac{7}{8}$.

So by the $\alpha, \beta$ first definition I can conclude that $PP\_{\frac{7}{8}}$ which equals to $\sf BPP\[7/8,7/8+\epsilon\]$ also equals to $\sf BPP\[2/3,1/3\]$ but the I am asked to prove that $\sf NP \subseteq BPP$ which we don't know yet.

# Answer
For what value of $\epsilon$ does PP$\_{7/8}$ equal BPP$\[7/8,7/8+\epsilon\]$? All you're given is that if $x \in L$ then the probability is strictly larger than $7/8$, while if $x \notin L$ then the probability is at most $7/8$. It could be that when $x \in L$, the machine accepts with probability $7/8 + 2^{-n}$. In fact, PP contains NP, while BPP is conjectured (by some) to equal P.
> 3 votes

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


# Question
Title: I have trouble to understand pattern calculus, could someone explain it in simple terms?
I am trying to understand the basic ideas of pattern calculus and do not have a lot of time to read through a rather long book. Can someone explain this in simple terms and give an example of how pattern calculus works?

http://bondi.it.uts.edu.au/

http://www.amazon.com/dp/3540891846/?tag=stackoverfl08-20

I don't understand "The ability to pass patterns as parameters (pattern polymorphism) is illustrated by defining a generic eliminator." as explained here in the Wikipedia article. If someone could work through an example showing how the patterns were transformed and why they were transformed in that way, that would be useful to me, thanks.

# Answer
> 3 votes
I can't really say that I know bondi (this is the first time I heard about it), but my experience with functional languages will allow me to give you hints.

Let's first discuss what the example given in the wikipedia page do. There are two functions called *elimLeafs* and *elimCount*. Both are accessed such as elimLeaf (Leaf 3) returns 3 and elimCount(Count 3) returns 3. "Do not focus on what these functions do !" .. There is a similarity between the two functions in that:

* elimLeaf (Laef x) or elimCount (Count x) can be return as elimPattern (Pattern x) where Pattern is either Count, Leaf or any other thing you want to name.

Knowing this, you can write both functions such as "Pattern" in elimPattern (Pattern x) is a variable .. and whence you can write both elimPattern and elimLeaf such as:

```
 elim = | x -> | {y} x y -> y

```

which can be called as:

```
  elim Leaf (Leaf 3) returns 3 .... for example.

```

The function elim above is actually two functions (or I dont know what is called in Bondi). First, you got the name of the function, which is elim. The name shall be followed by =| . Then you have the definition of the function"s" which is followed by -\>. So,

* "elim Leaf" is matched with "elim =| x" and therefore evaluated to | {y} x y
* Now, x is Leaf in "elim Leaf". Thus, "| {y} x y" is equivalent to "| {y} Leaf y".
* The function elim above can be further evaluated such that "| {y} Leaf y -\> y" (that is "| {y} Leaf y" is evaluated to y.) y in this case would be 3, given the input above.
* Note here that right now you did exactly what elimLeaf did ! You can do the same for elimCount by simply replacing Leaf by Count in the input.

To clarify more: Assume you want to do this with C++. The definition of the functions elimCount and elimLeaf are as follows:

```
int elimCount(int x) { return x;}
int elimLeaf(int x) { return x;}     // we are just assuming int in this example,

```

To write both these functions with only one, perhaps you would do something like:

```
int elim (const char* pattern, int x) {
    if (strcmp(pattern, "Leaf") == 0) return x
    if (strcmp(pattern, "Count") == 0), return x
 }

```

---
Tags: functional-programming
---


# Question
Title: Name of a sequence that is unknown to stop on a given input
Several years ago I was self learning lisp by a book which I do not remember. As an example there was a recursively defined sequence which was said to be unknown to be finite or not for every input --- to generate a sequence you were required to provide two(?) initial values. At least that is how I remember.

There was a Wikipedia article on it but I can't find it either. Does anyone know what I'm talking about?

# Answer
It has many names, I first heard about it as the **Syracuse problem**, but the most prominent name is maybe Collatz Conjecture.
> 3 votes

---
Tags: reference-request, recurrence-relation
---


# Question
Title: Easy proof for context-free languages being closed under cyclic shift
The *cyclic shift* (also called *rotation* or *conjugation*) of a language $L$ is defined as $\\{ yx \mid xy \in L \\}$. According to wikipedia (and here) the context-free languages are closed under this operation, with references to papers from Oshiba and from Maslov. Is there an easy proof of this fact?

For regular languages the closure is discussed in this form as "Prove that regular languages are closed under the cycle operator".

# Answer
> 6 votes
You can try to use pushdown automata. Given a pushdown automaton for the original language, we construct one for the cyclic shift. The new automaton operates in two stages, corresponding to the $y$ and the $x$ part of the word $yx$ (where $xy$ is in the original language). In the first stage, whenever the automaton would like to pop a non-terminal $A$, it can instead push a non-terminal $A'$; the idea is that at the end of the first stage, the stack would contain, in reverse order, the symbols that are found in the stack after reading $x$ by the original automaton. In the second stage (the switch is non-deterministic), instead of pushing a non-terminal $A$, we are allowed to pop a non-terminal $A'$. If the original automaton can indeed generate the stack upon reading $x$, then the new one would be able to exactly pop the entire stack.

Edit: Here are some more details. Suppose we are given a PDA with alphabet $\Sigma$, set of states $Q$, set of accepting states $F$, non-terminals $\Gamma$, initial state $q\_0$, and a set of allowable transitions. Each allowable transition is of the form $(q,a,A,q',\alpha)$, meaning that when in state $q$, upon reading $a \in A$ (or $a = \epsilon$, in which case it's a free transition), if the top-of-stack is $A \in \Gamma$ (or $A = \epsilon$, which means stack is empty), then the PDA can (it's a non-deterministic model) move to state $q'$, replacing $A$ with $\alpha \in \Gamma^\*$.

The new PDA has a new non-terminal $A'$ for each $A \in \Gamma$. For every two states $q,q' \in Q$ and $A \in \Gamma \cup \\{\epsilon\\}$, there are two states $(q,q',1),(q,q',2,A)$. The starting states (the actual starting state is chosen non-deterministically among them via $\epsilon$-transitions) are $(q,q,1)$. For each transition $(q,a,A,q',\alpha)$ there are corresponding transitions $((q,q'',1),a,A,(q',q'',1),\alpha)$ and $((q,q'',2,B),a,A,(q',q'',2,B),\alpha)$. There are other transitions as well.

For each transition $(q,a,A,q',\alpha)$, there are transitions $((q,q'',1),a,B',(q',q'',1),B'A'\alpha)$, where $B \in \Gamma \cup \\{\epsilon\\}$ and $\epsilon' = \epsilon$. For every final state $q \in F$, there are transitions $((q,q'',1),\epsilon,A,(q\_0,q'',2,\epsilon),A)$, where $A \in \Gamma \cup \\{\epsilon\\}$.

For every transition $(q,a,\epsilon,q',\alpha)$, there are transitions $((q,q'',2,A),a,B',(q',q'',2,A),B'\alpha)$, where $A \in \Gamma \cup \\{\epsilon\\}$. For every transition $(q,a,\epsilon,q',A)$, there are transitions $((q,q'',2,B),a,A',(q',q'',2,A),\epsilon)$, where $B \in \Gamma \cup \\{\epsilon\\}$. For every transition $(q,a,A,q',B)$, there are "generalized transitions" $((q,q'',2,C),a,B'A,(q,q'',2,C),\epsilon)$; these are implemented as a sequence of two transitions through an intermediate new state. Transitions $(q,a,\epsilon,q',\alpha)$ with $|\alpha| \geq 2$ are handled similarly. For every transition $(q,a,A,q',A)$, there are transitions $((q,q'',2,A),a,B,(q',q'',2,A),B)$, where $B \in \Gamma' \cup \\{\epsilon\\}$. Transitions $(q,a,A,q',A\alpha)$ are handled similarly. Finally, there is a sole final state $f$, and transitions $((q,q,2,A),\epsilon,\epsilon,f,\epsilon)$.

(There might be a few transitions that I missed, and some of the details that I'm omitting are somewhat messy.)

Recall we're trying to accept a word $yx$, where $xy$ is accepted by the original PDA. A state $(q,q',1)$ means that we're at stage 1, at state $q$, and the original PDA is at state $q'$ after reading $x$. A state $(q,q',2,A)$ is similar, where $A$ corresponds to the last $A'$ that was popped. At stage 1, we are allowed to push $A'$ instead of popping $A$. We do that for each non-terminal that is produced while processing $x$, but only popped while processing $y$. At stage 2, we are allowed to pop $A'$ instead of pushing $A$. If we do this, then we have to remember that the top-of-stock is really $A$; this only applies when there are no "temporary" things on the stack, which in the simulated PDA is the same as the top-of-stack being $\epsilon$ or of the form $B'$.

Here is a simple example. Consider an automaton for $x^n y^n$ that pushes $A$ for each $x$, and pops $A$ for each $y$. The new automaton accepts words of two forms: $y^k x^n y^{n-k}$ and $x^k y^n x^{n-k}$. For words of the first form, stage 1 consists of pushing $k$ times $A'$, stage 2 consists of popping $k$ times $A'$, pushing $n-k$ times $A$, and popping $n-k$ times $A$. For words of the second form, we first push $k$ times $A$, then pop $k$ times $A$, push $n-k$ times $A'$, transition to stage 2, and pop $n-k$ times $A'$.

Here is a more complicated example, for the language of balanced parentheses of various types ("()","\[\]","\<\>") such that the immediate descendants of each type of parentheses must belong to a different type. For example, "(\[\]\<\>)" is OK but "()" is wrong. For each "(", we push $A$ *if the top-of-stack isn't $A$*, for each ")", we pop $A$. Similarly $B$,$C$ are associated with "\[\]" and "\<\>". Here is how we accept the word "\>)(\[()\]\<". We consume "\>)", pushing $C'A'$, and transition to stage 2. We consume "(", popping $A'$ and remembering the top-of-stack $A$. We consume "\[()\]" , pushing and popping $BA$; when pushing $B$, we are aware that the "real" top-of-stack is $A$, and so square brackets are allowed (we wouldn't be fooled by "\>)(()\<"); when pushing $A$, since the top-of-stack is $B$ (which is not $\epsilon$ or of the form $X'$), then we know that $B$ is also the "real" top-of-stack, and so round parentheses are allowed (even though the shadow top-of-stack is $A$). Finally, we consume "\<" and pop $C'$.

# Answer
> 4 votes
Consider Greibach normal form. To construct a shifted language you only need to change productions $S \to \alpha A\_1 \dots A\_n$ to $S \to A\_1\dots A\_n \alpha$ and add a new non-terminal $S'$ that behaves like $S$ used to, in case some some production referenced $S$.

# Answer
> 4 votes
It turned out to be a good idea to check the old Hopcroft and Ullman classic *Introduction to Automata Theory* (1979). Closure under cycle is Exercise 6.4c and is marked S\**. The double stars mean it is one of the most difficult problems (in the book). Fortunately the S indicates it is one of the selected problems with a solution.

The solution is as follows. Take a CFG in Chomsky normal form. Consider any derivation tree and basically turn it upside down. Consider a path $S=X\_1, X\_2, \dots , X\_n$ in the original tree. To the left the tree has contributions $x\_1, x\_2, \dots, x\_n$ to the right $y\_1, y\_2, \dots, y\_n$, meaning the string derived equals $x\_1 x\_2 \dots x\_n y\_n \dots y\_2 y\_1$. (Actually as the grammar is CNF when the path continues left, the contribution will be to the right and the corresponding $x\_i$ is empty, etc.)

The tree upside down has a path $S', \hat X\_n, \dots \hat X\_2, \hat X\_1$ with contributions $y\_n, \dots, y\_2 y\_1$ to the left and $x\_n, \dots, x\_2 x\_1$ to the right, so the result is a derivation for $ y\_n \dots y\_2 y\_1 x\_1 x\_2 \dots x\_n $. As required.

Full details of the construction are given in the book.

Note how this reminds of the (accepted) solution by Yuval. The nonterminals that are pushed instead of popped are in the opposite order on the stack. Quite similar to upside down in the tree.

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


title: Visualized definition of cohomology

text:
# Question
Title: Visualized definition of cohomology
I cannot imagine how cohomology is related to graph theory, actually I read solid definition from wiki, and to be honest, I cannot understand it. e.g I know what is homotopy (in simple term), group of functions such that I can continuously convert each of them to another one, and I think this is useful for understanding homology, but, is there similar visualization method for cohomology? (I'm not looking for exact definition, I want to imagine it, actually this is in graph theoretic concept). for more information see introduction of this paper. I want to understand it in this paper, how is useful? how to imagine it?

P.S1: my field is not related to group theory, and as in introduction author wrote, this paper doesn't need deep group theoretic definition! and I don't want to be deep in group theory. Just looking for simple way to understand them.

P.S2: I think I can imagine what is free group (which is in introduction of paper), at least by Calay graph seems to be easy to imagine it.

P.S3: I also asked this in math.stackexchange but I think this is something between two field and may I get some mathematical answer there and some others here (from CS point of view) to understand it well.

# Answer
Apparently all algebraic topology is useful for is earning imaginary internet points. More than I expected, I guess... (Actually now that I've finished writing I expect to lose points on this...)

**tl;dr:** Honestly, I don't think anyone here can give you an easy way to really understand what homology and cohomology are, with just a short description. I made an attempt below, but I took a whole course on the subject and I still don't really know what they are. Particularly if you don't know, or care to know, what a group is. These things are groups, that's sort of the whole point. As they relate to graph theory, you can treat a graph as a simplicial complex of dimension 1. Thus you can consider the homology and cohomology groups of the graph and use them to understand the topology of the graph. Here are some notes by Herbert Edelsbrunner on homology and cohomology, the latter of which provides a useful example.

Before I can define cohomology I must first make sure you understand the definition of homology. For simplicity I'll describe everything using simplicial complexes, but (co)homology can be, and usually are, defined for more complex complexes (see what I did there?). Simplicial complexes are enough for graph theory, at least as far as I've seen.

It turns out that it's really difficult to try to create homeomorphisms between two topological spaces to show that they're topologically equivalent. It's even harder to try an show that no such homeomorphism exists. So the idea is to establish topological invariants, a property that must be equal for two topological spaces if they are topologically equivalent. If the invariant isn't the same for both spaces, then they can't possibly be topologically equivalent. Homology and cohomology groups are two such invariants. They attempt to put a group structure on a topological space, so that we can work with groups and homomorphisms instead of topological spaces and homeomorphisms. Computer scientists like homology groups because they are easy to compute and lead to fast algorithms. The downside is they're much more difficult to visualize.

So how do we describe a topological space in such a way that we can place a group structure on it? Well we build our topological space with a set of simplicies, called a simplicial complex. A 0-dimensional simplex is a vertex, a 1-dim simplex is an edge, 2-simplex is a triangle, 3-simplex is a tetrahedron, etc. A valid simplicial complex must obey certain rules about how it's simplices connect to one another: the intersection of two simplices must also be a simplex in the set and all subsimplces must be in the set. Notice that graphs can be thought about in this way.

It makes sense to talk about sums of simplices of the same dimension $p$, what we call $p$-chains. So a $p$-chain can be written as $\sum\_{i} a\_i \sigma\_i$ where $\sigma\_i$ is a $p$-simplex and $a\_i$ is an integer. With this operation we can define the group of $p$-chains $(C\_p,+)$, or just $C\_p$.

We also have one more operation called the boundary operator, which takes a chain to it's boundary. So for an edge $(v,u)$ in some graph, the boundary is just the sum of its vertices $u+v$. The boundary operator of a $p$-simplex $\sigma = \[u\_0,\ldots, u\_1\]$ is defined as $\partial \sigma = \sum\_{i}\[u\_0, \ldots, \hat{u\_i}, \ldots, u\_n\]$ where $\hat{u\_i}$ means that we remove the $u\_i$ simplex and create a sum of $p-1$-simplices. To apply the boundary operator to a $p$-chain $c$, we just apply it to each of it's $p$-simplices, $\partial c = \sum\_{i}a\_i \partial \sigma\_i$.

Now there are two very important types of chains which we use to construct homology groups, cycles and boundaries. A $p$-cycles is a $p$-chain $c$ with no boundary, meaning $\partial c = 0$. A $p$-boundary $c$ is a $p$-chain that is the boundary of some $p+1$-chain $d$, $c = \partial d$. Once again we can define groups $Z\_p$ (our group $p$-cycles) and $B\_p$ (our group of $p$-boundaries). The group $B\_p$ is a subgroup of $Z\_p$ which is a subgroup of $C\_p$.

**Homology groups are** not a group of functions where one element can be deformed into another. Intuitively, what the homology group is trying to do is characterize the different loops. Think of a torus (donut) which has two distinct loops, colored in the image below. I can move the blue loop anywhere around the torus, but it's still the same loop because it differs only by it's boundary.

The elements of a homology group are equivalence classes, where two $p$-cycles in the simplicial complex are in the same equivalence class if and only if they differ only by a boundary chain. Meaning if you take two cycles $c,d \in Z\_p$, and there exists boundaries $a,b \in B\_p$ such that $c+a = d+b$, then $c$ and $d$ are in the same equivalence class. They are constructed as the quotient groups $H\_p = Z\_p/B\_p$.

**Now cohomology is much less geometrically intuitive and motivated by algebraic considerations.**

We define cohomology groups in terms of cochains. A $p$-cochain is a homomorphism $\psi: C\_p \rightarrow G$, where $G$ is the group used for the coefficients $a\_i$ (usually $\mathbb{Z}$ or $\mathbb{Z\_2}$). Instead of considering a group of chains, we consider the group of cochains, all homomorphisms between $C\_p$ and $G$ denoted as $C^p=Hom(C\_p, G)$.

Similarly we can define a boundary operator on cochains, as the dual homomorphism of $\partial$, which we denote $\delta: C^{p} \rightarrow C^{p+1}$. Notice that since the boundary operator $\partial$ took $p+1$-chains to $p$-chains, the dual homomorphism takes $p$-cochains to $p+1$-cochains. Now consider a $(p-1)$-cochain $\psi$ and $\partial c$ a $p-1$-chain. The coboundary operator $\delta$ requires that $\psi$ applied to $\partial c$ is the same as $\delta \psi$ applied to $c$.

Once we have the coboundary operator, we can define cocycle and coboundary groups, denoted $Z^{p}$ and $B^{p}$, just as we did before. Then the $p$th cohomology group is a set of equivalence classes where two cocylces are equivalent iff they differ by a coboundary. They are constructed as the quotient groups $H^{p}=Z^{p}/B^{p}$. Do you see why this is much less geometrically intuitive?
> 6 votes

---
Tags: graphs, group-theory
---


title: Gap problems clarifation

text:
# Question
Title: Gap problems clarifation
Here's a simple question which made me confused.

Please tell me if my analysis of the problem and my conclusions are correct.

For an optimization problem $\sf Gap-A\[a,b\] \in L$ for $b\>a$. I want to discuss what I can know about $\sf Gap-A\[a/2,b/2\]$.

$\sf(i)$ Is it correct to say that $\sf Gap-A\[a/2,b/2\]$ is not in $\sf NP-Hard$ and it is easy only because the realtion $\frac{a/2}{b/2}=\frac{a}{b}$ and we already know that it is easy to approximate $A$ with factor of $a/b$?

$\sf (ii)$ Is it true that I can't say though that $\sf Gap-A\[a/2,b/2\]$ is in $\sf L$ since there is no intersection between the gaps? In order that gap $B$ would be in the exact class that gap $A$ is in, we have to have $A \subseteq B$?

# Answer
> 4 votes
You are confusing NP and NP-hard. The fact that a problem is (say) in L doesn't preclude it being in NP, in fact, quite the contrary: any problem which is in L is a fortiori in NP, i.e. L$\subseteq$NP. On the other hand, it is not likely to be NP-hard (and assuming that P$\neq$NP, if it is in L then it cannot be NP-hard).

Another mistake you're making is that a problem which is approximable can't be NP-hard (or rather, its decision version can't be NP-hard). Considering MAX-3SAT, there is a trivial 7/8-approximation algorithm (pick a random assignment; this can be derandomized), yet the decision version 3SAT is NP-complete.

You're right that GAP-A$(a,b)$ being easy doesn't imply that GAP-A$(a/2,b/2)$ is easy. One example (replacing $1/2$ with an arbitrary $c$) is MAX-2SAT. GAP-2SAT$(a,1)$ is easy for any $a\<1$, yet there exist some $b,c$ for which GAP-2SAT$(b,c)$ is NP-hard. (Unfortunately, $c=1/2$ doesn't work, since every 2SAT instance can be $1/2$-satisfied.)

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


# Question
Title: Hardness of finding a true or a false assignment into a generic boolean formula?
I read some research that analyzes the hardness of SAT solving in the average case. In fact, for a 3CNF formula if you compute the ratio of clause to variables there is an interval (more or less between 4 and 5) in which solving the formula is hard. But it is easy (between 0 and 4) high probability of satisfiable assignment and high probability of unsatisfiable assignment after ratio 5.

My question is, what about a generic formula that is not in normal form. We can say something about its hardness?

# Answer
You can always convert your formula or circuit to an equivalent CNF formula of polynomial size.

The result you mention is only for 3CNF formulas. In general for kCNF-SAT the assumed threshold phenomenon happens on a point depending on $k$, the values you mention are only for 3CNF-SAT.

Also remember what these result say is *w.h.p.* in a particular distribution of k-CNF formulas. It doesn't mean that this will hold for all formulas. In fact it is quite easy to come up with formulas that have values mentioned in the range but are easy and also formulas that are outside this range but are hard (think about padding formulas to obtain your desired ration). So given a particular 3CNF formula with some clause ration, you can't say anything about its difficulty (or the time it will take a particular SAT solver to solve it).
> 2 votes

# Answer
If your question really is about hardness of finding either a true or false assignment to an arbitrary formula, this is always easy. Pick any assignment and it will always either satisfy the formula or not.

It is only the random instances of SAT that exhibit the phase transition you mention. There is also work that tries to characterize the hardness of an arbitrary formula. For more on this, see my answer to the question Measuring the difficulty of SAT instances. Also, recall that every propositional formula can be converted into an equivalent formula that is in CNF. See Conversion into CNF on Wikipedia for example.
> 1 votes

---
Tags: complexity-theory, satisfiability, average-case
---


# Question
Title: Prove that the language of unary not-prime numbers satisfies the Pumping Lemma
Here is a question from Daniel I. A. Cohen's book *Introduction to Computer Theory*:

> Consider the language:
>
> $\quad \mathrm{PRIME}' = \\{ a^n \mid n \text{ is not a prime} \\} = \\{ \varepsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots \\}$
>
> 1. Prove that $\mathrm{PRIME}'$ is non-regular.
> 2. Prove, however, that $\mathrm{PRIME}'$ does satisfy the pumping lemma.

Part 1. is really easy to prove. I start my proof of part 2. like this:

1. We pick $m$ s.t. $m \geq 4$.
2. The opponent picks $w = a^{n^2}$, where $n$ is any prime number greater than m.

Now I don't know how to decompose $w$ into $xyz$. Any help would be appreciated.

---

**Update**: According to the answers below, $\mathrm{PRIME}'$ doesn't satisfy the Pumping Lemma we commonly talk about (requiring $|xy| \leq m$). I have checked the book at the library and found there are two versions of the Pumping Lemma in it. The weaker one, which clearly this question refers to, doesn't require a fixed pumping length.

# Answer
Let $w \in \mathrm{PRIME}'$ with $|w| \geq 5$. Distinguish two cases.

1. $|w|$ is even -- in that case, choose $x = \varepsilon$, $y = aa$ and $z = a^{|w|-2}$. Then, for all $i\geq 0$, we have $|xy^iz|$ is even and greater than two, as $|z| \geq 3$, and therefore not prime; $xy^iz \in \mathrm{PRIME}'$.
2. $|w|$ is odd -- in this case, we can not verify the pumping property. This can be seen as follows.

We have

$\quad \forall m \geq 1.\\, \exists n \geq m.\\, \forall 1 \< k \leq m.\\, \gcd(k, n-k) = 1 \qquad (\star)$

that is for every assumed pumping length $m$, there is a longer word $a^n$ which you can not separate into $a^k$ and $a^{n-k}$ with $k \leq m$ (note that $k=1$ trivially violates the pumping property) so that $k$ and $n-k$ share a divisor. Therefore, we can invoke Dirichlet's theorem for every possible separation, which yields that there are (infinitely many) primes you get by $(n-k) + ik$. So we can't find a pumpable split of $a^n$, and thus the pumping property is violated for $a^n$, which is enough to "contradict" the lemma.

$(\star)$ can be shown by contradiction. Pick $n\>m$ non-prime so that $n$ has no prime factor $\leq m$, e.g. $n = p^2$ for $p\geq m$ prime. Assume there was a $1\<k\leq m$ so that some $1\<d\leq k$ divided both $k$ and $n-k$, i.e. $k = id$ and $n-k = jd$ for some natural $i,j$. But then, $n = (i+j)d$, i.e. $d \leq m$ divides $n$, which contradicts the choice of $n$.
> 4 votes

# Answer
Pick $xyz$ so that $|y|$ is not coprime to $|xyz|$. This does not work when $|xyz|$ does not have prime factors smaller than the pumping length though. In that case there will be a prime amongst all $|xy^nz|$ by Dirichlet's theorem.
> 3 votes

---
Tags: formal-languages, automata, pumping-lemma
---


# Question
Title: Show how a sentence can be produced from a grammar (Dragon book 2.1)
In the Dragon book (Aho, Sethi, Ullmann) there is one exercise I don't get.

> Chapter 2, Exercies: 2.1
> Given the context-free grammar $$S \to S S + \mid S S * \mid a$$ Task: Show how the signs aa+a\* can be produced from this grammar.

I understand the grammar, $S$ can have the form $S S +$… and so on. But I don't know what I'm supposed to do in this task. Sadly I can't find any solutions on the web.

# Answer
> 4 votes
$$\begin{align\*} S \Rightarrow & SS\* \\ \Rightarrow & SS+S\* & \text{(leftmost derivation )} \\ \Rightarrow & aS+S\* \\ \Rightarrow & aa+S\* \\ \Rightarrow & aa+a\* \\ \end{align\*}$$

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


# Question
Title: An efficient data structure supporting Insert, Delete, and MostFrequent
Assume that we have a set $D$ and each member of $D$ is a data and key pair. We want a data structure that would support the following operations:

* Insert $(d,k)$ into $D$,
* Delete member $e$, (no need to search to find $e$, e.g. $e$ points to a member in $D$),
* MostFrequent, which returns a member $e \in D$ such that $e.key$ is one of the most frequent keys in $D$ (note that the most frequent key doesn't need to be unique).

What would be an efficient implementation of this data structure?

My solution is a heap for the keys and their frequencies prioritized by the frequencies plus a hash table where the hash function maps members with the same key to the same slot in the hash table (with pointers from each part to the other).

This can give $\Theta(\lg n)$ for the first two operations and $\Theta(1)$ for the third (worst case running time).

I am wondering if there is more efficient solution? (or a simpler solution with the same efficiency?)

# Answer
> 7 votes
In the comparison-based model of computation, you may implement the priority queue using a Fibonacci heap instead of an ordinary heap. This will give you the following bounds: $\mathcal{O}(1)$ amortized time for insert and $\mathcal{O}(\log n)$ amortized time for deletion operations.

If you depart from the comparison-based model and adopt the RAM model where keys are regarded as binary strings, each one contained in one or more machine words, you may implement your priority queue in $o(\log n)$. Indeed, you can achieve for both insert and delete operations $\mathcal{O}(\sqrt{\log \log n}) $ and $\mathcal{O}(1) $ time for the findMin operation. Thorup proved that

If we can sort $n$ keys in time $S(n)$ per key, then we can implement a priority queue supporting find-min in constant time and updates (insert and delete) in $S(n)$ time.

See M. Thorup. Equivalence between priority queues and sorting, 2002. in Proc. FOCS 2002

Since we can sort in $\mathcal{O}(n \sqrt{\log \log n}) $ expected time and linear space, as shown by

Y. Han and M. Thorup. Integer sorting in $\mathcal{O}(n \sqrt{\log \log n}) $ expected time and linear space. in Proc. FOCS 2002

the bound is proved.

# Answer
> 2 votes
You can do all of these in $O(1)$ expected amortized time. The essential trick is that we don't need the full power of a priority queue, since key frequency only changes by 1 during each insert or delete.

My solution below is really just your solution with an "inefficient" priority queue that happens to work well for this case: a max priority queue implemented as a doubly linked lists of buckets of keys has O(1) insertMin, deleteMax, removeFromBucket, and increaseKey.

---

Maintain a doubly-linked list of Buckets, where each Bucket has a non-empty hash set of keys (that I'll call a Cohort) and a positive integer (that I'll call the ValCount). In a Bucket b, each key k in the Cohort of b has the same number of unique values associated with it in the set you are maintaining. For example, if your set has the pairs (a,apple), (a,avocado), (b,banana), (c,cucumber), (d,dragon fruit) where the single letters are the keys and the fruits are the values, then you would have two Buckets: One Bucket would have a ValCount of 2 and a Cohort consisting only of one key: a. The other Bucket would have a ValCount of 1 and a Cohort consisting of the three keys b, c, and d.

The doubly-linked list of Bucket should be kept ordered by the ValCount. It will be important that we can find the head and the tail of the list in $O(1)$ time and that we can splice in a new Bucket in $O(1)$ time if we know its neighbors. Unimaginatively, I'll call the list of Buckets the BucketList.

In addition to the BucketList, we'll need a SetMap, which is a hash map mapping keys to ValueBuckets. A ValueBucket is a pair consisting of the ValueSet (a non-empty hash set of values) and a non-null pointer to a Bucket. The ValueSet associated with a key k contains all the unique values associated with k. The Bucket pointer associated with a ValueSet has a Cohort equal to the size of the ValueSet. The Bucket associated with a key k in the SetMap is also associated with the key k in the BucketList.

In C++:

```
struct Bucket {
    unsigned ValCount;
    unordered_set<Key> Cohort;
    Bucket * heavier;
    Bucket * lighter;
};
Bucket * BucketListHead;
Bucket * BucketListTail;

struct ValueBucket {
  unordered_set<Value> ValueSet;
  Bucket * bucket;
};
unordered_map<Key, ValueBucket> SetMap;

```

To find a max-frequency key-value pair, we just need to look at the head of the BucketList, find a key in the Cohort, look up that key in the SetMap, and find a value in the ValueSet of its ValueBucket. (phew!)

Inserting and deleting key-value pairs is trickier.

To insert or delete a key-value pair, we first insert or delete it in the SetMap This will change the size of the ValueSet, so we need to modify the Bucket associated with the key. The only Buckets we will need to look at to make this change will be the immediate neighbors of the Bucket the key used to be in. There are several cases here, and they are probably not worth spelling out fully, though I'd be happy to elaborate if you're still having trouble.

# Answer
> -3 votes
### Worst-case complexity

**Insert**: $\mathcal{O}(1)$

**Find-min**: $\mathcal{O}(1)$

**Decrease-key**: $\mathcal{O}(1)$

**Delete**: $\mathcal{O}(\log \log n)$

**Space**: $\mathcal{O}(n)$

### Proof

> THEOREM 1. *We can implement a priority queue that with n integer keys in the range $\[0 , N )$ in linear space supporting* **ﬁnd-min**, **insert**, *and* **dec-key** *in constant time, and* **delete** *in $\mathrm{\mathcal{O}(log\ log\ min \\{n, N\\})}$ time.*

Which is established with a combination of:

> LEMMA 3. *Let $\tau(n, N)$ be the* **delete** *time for a priority queue for up to $n$ integers in the range $\[0 , N)$ supporting* **insert** *and* **dec-key** *in constant time. Then $\tau ( n, N ) \le τ ( N, N)$. This holds whether $\tau$ is amortized or worst-case.*

and:

> THEOREM 6. *Theorem 6. We can implement a priority queue that with $n$ integer keys in the range $\[0 , N)$ in linear space supporting **ﬁnd-min**, **insert**, and **dec-key** in constant time, and **delete** in $\mathrm{\mathcal{O}(1 + log\ log\ n − log\ log\ q)}$ time for a key of rank $q$.*

### Reference

Thorup, Mikkel. “Integer Priority Queues with Decrease Key in Constant Time and the Single Source Shortest Paths Problem.” In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, 149–158. STOC ’03. New York, NY, USA: ACM, 2003.

---
Tags: algorithms, data-structures, abstract-data-types
---


# Question
Title: Is there a name/interest for regular languages that have a non-ambiguous ending?
The basic idea is to have one or more symbol that clearly indicate the end. For example:

Non-ambiguous:

> $ab^\*c$
> $(a|b)c$
> $ab^+c$
> $ab?c$
> $a(b|c)$
> $c(ab)^\*ccc$
> $acc^\*d$
> $abc|bcd$

Ambiguous:

> $abc^\*$
> $abc^+$
> $abc?$
> $acc^\*$ or $ac^\*c$

An alternative definition of a non-ambiguous ending would be that the corresponding DFA can have multiple final states, but none of them can have a outgoing transition.

# Answer
> 4 votes
According to your alternative definition, you're looking for a language such that $u\in L\Rightarrow \forall v\neq\epsilon, uv\notin L$ (where $\epsilon$ denotes the empty string).

That property defines a useful kind of language in coding, called **prefix-free codes**. Note that this language class doesn't include nor is included in regular languages.

So what you're looking for is the intersection of those two classes. That would be a **prefix-free regular language**.

As for the interest, it seems to have some, since a google search returned this research paper.

# Answer
> 0 votes
Are you merely looking for unicity of the *last* character?

In that case, you may mean a property such as:

* the regular expression ends with a character (it is `xc` for some expression `x` and character `c`)
* the language described by the regular expression ends with a character (it is `Lc` for some regular language `L` and character `c`)

They are different properties: `acc*` meets 2 but not 1.

Or are you looking for a stronger property, that must also apply elsewhere in the expression?

In that case, you may be looking for *determinism*. Determinism is the property of never having to backtrack and retry while trying to parse (match) a string. It is usually defined assuming parsing from left to right, so it applies to unicity of prefixes rather than suffixes; and it is usually defined for finite automata or context-free grammars rather than regular expressions (but not always - see, e.g., this paper about deterministic regular expressions). In that case, you may be looking for a property such as:

* the reverse of the regular expression is deterministic

Here, the reverse is the regular expression obtained by swapping all concatenation arguments, e.g. the reverses of `ab*c`, `(a|b)c`, `ab+c`, `ab?c`, `abc*`, `a(b|c)`, `abc+`, `abc?` are `cb*a`, `c(a|b)`, `cb+a`, `cb?a`, `c*ba`, `(b|c)a`, `c+ba`, `c?ba`, respectively.

I don't know a name for any of these properties.

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


# Question
Title: Where do these DRAM row/column calculations come from?
Let r be the number of rows in a DRAM array, and c be the number of columns.

Apparently, DRAM with organization 16x1 requires least pins when r = c = 4 because fewer address bits are required to represent them, and so does DRAM with organization 16x4. Why are these the same? Doesn't the latter have 4 columns instead of 1?

# Answer
> 1 votes
The first value describing the DRAM is the number of data-interface-sized "chunks" it contains and the second value is the width of the data interface in bits, i.e., bits per "chunk". A 16x1 DRAM would only have 16 bits addressable at 1-bit granularity, with four rows and four columns allowing a minimization of address pins. A 16x4 DRAM would have 64 bits addressable at 4-bit granularity (and with 16 addressable units a 4 row and 4 column arrangement would minimize address pins).

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


title: Lambda Calculus simplification

text:
# Question
Title: Lambda Calculus simplification
Below is the lambda expression which I am finding difficult to reduce i.e. I am not able to understand how to go about this problem.

$$(\lambda mn.(\lambda sz.ms(nsz)))(\lambda sz.sz)(\lambda sz.sz)$$

I am lost with this.

if anyone could lead me in the right direction that would be much appreciated

# Answer
> 16 votes
Lambda terms are simplified by the β-reduction rule: $$(\lambda x.M)N\\,\rightarrow\_\beta\\,M\[x:=N\]$$

It means, if you have a subterm that looks like $(\lambda x.M)N$ (called *redex*) you can replace it by $M\[x:=N\]$, which is $M$ with $N$ substituted for $x$. The replacement $M\[x:=N\]$ is often called *contractum*. (Capital letters likes $M$ and $N$ are used to denote terms.)

In your case, the first reduction would be:

$$(\underbrace{(\lambda mn.(\lambda sz.ms(nsz)))(\lambda sz.sz)}\_{\mbox{redex}})(\lambda sz.sz) \rightarrow\_\beta \underbrace{(\lambda n.(\lambda sz.(\lambda sz.sz)s(nsz)))}\_{\mbox{contractum}}(\lambda sz.sz)$$ where we replaced $m$ with $\lambda sz.sz$. Note that we now have $\lambda sz$ inside $\lambda sz$ which isn't very convenient (yet allowed). It is better to rename bound variables ($\alpha$-conversion) to be distinct, for example to:

$$(\lambda n.(\lambda uv.(\lambda sz.sz)u(nuv)))(\lambda sz.sz)$$

Some notes:

* Substitution applies only to *free* variables. Bound variables stay always intact.
* Sometimes substitution is not directly possible. For example, you cannot substitute $x:=y$ into $\lambda y.xy$ because $y$ is bound under $\lambda$. You'd get $\lambda y.yy$ which would change the meaning of the term. So first, you have to rename the bound variable first, for example to $\lambda z.xz$ and then you can safely substitute $x:=y$ to get $\lambda z.yz$. The Wikipedia article gives formal definition of substitution and shows when it's necessary to rename bound variables.
* Lambda associates to the right, so $\lambda sz.sz$ is $\lambda s.(\lambda z.sz)$.
* Application associates to the left, so $xyz$ is $(xy)z$.

# Answer
> 1 votes
An alternative way of expressing a lambda abstraction and reduction. Indexes are used instead of lettered terms based on the order of input. Abstractions are surrounded by \[\]'s

```
(λmn.(λsz.ms(nsz)))(λsz.sz)(λsz.sz)
m -> 1, n -> 2, s -> 3, z -> 4
(λmn.(λsz.ms(nsz))) = [1 3 (2 3 4)]
(λsz.sz) = [1 2]
[1 3 (2 3 4)][1 2][1 2]
[[1 2] 2 (1 2 3)][1 2]   ;1 was replaced with [1 2], remaining terms decremented
[[1 2] 1 ([1 2] 1 2)]    ;1 was replaced with [1 2], remaining terms decremented
[1 ([1 2] 1 2)]          ;1 2 was replaced by 1 ([1 2] 1 2)]
[1 (1 2)]                ;1 2 was replaced by 1 2
(λmn.m(mn))

```

The notation above is just a more compact and unambiguous way of expressing lambda abstractions. Compound abstractions reduce to a single normal form automatically, alpha reduction is not needed.

Single positive indexes are used for bound terms. Negative indexes are used for kill terms. Negative indexes are placed last in order of decreasing magnitude.

```
I = λx.x = [1]
K = λxy.x = [1 -2]
KI = λyx.x = [2 -1]
S = λxyz.xz(yz) = [1 3 (2 3)]

```

Applying S to K:

```
[1 3 (2 3)][1 -2]
[[1 -2] 2 (1 2)]  ;1 was replaced with [1 -2], remaining terms decremented
[[.2 -1] (1 2)]   ;reducing: 1 replaced by .2*, -2 decremented (in magnitude)
[2 -2 -1]         ;(1 2) bound terms become kill terms due to -1.
[2 -1] = KI       ;-2 kill term is void due to surviving 2 term

* the . notation signifies the bound term is from the outer abstraction
  and must be used to prevent decrementing and double replacement of the
  term until the substitution of all terms in the abstraction is complete.

[2 -1][anything] ;applying KI to anything
[1] = I          ;yeilds I, therefor SK[anything] = [1] = I

```

Applying K to K:

```
[1 -2][1 -2]
[[1 -2] -1]  ;kill terms are absorbed and also increase the magnitude of bound terms
[2 -3 -1]    ;applying this result to anything yields K.
[2 -3 -1][anything]
[2 -1]

```

---
Tags: logic, lambda-calculus
---


# Question
Title: Is there a non-brute force algorithm for Eulerization of graphs?
Given some undirected, unweighted, connected, and potentially parallel-edged graph $G$, an Euler circuit may be constructed iff every vertex in $G$ has an even degree.

In graphs with two or more vertices of odd degree (there may only be multiples of two), one must "Eulerize" the graph, connecting the odd vertices with additional edges through other vertices if necessary.

The optimal case for Eulerization is with the construction of only $n/2$ edges, where $n$ is the number of odd degree vertices, but this can only be the case if each odd vertex has an adjacent partner, thus allowing us to connect both vertices with one edge and making them both even.

That being said, most graphs will require more than $n/2$ edges. As humans, we tend to Eulerize graphs by always choosing each pair of odd vertices that are adjacent to one another, and then using trial and error for the rest. However, this does not always work.

For instance, in the following graph, choosing to add an edge between the pair of adjacent odd vertices, $1\leftrightarrow 2$ and using $5$ edges to connect $3\leftrightarrow 4$ results in an Eulerization that costs $6$ edges. However, choosing to instead connect $1\leftrightarrow 4$ and $2\leftrightarrow 3$ yields an Eulerization that costs $5$ edges, even though it did not use the adjacent odd vertices to its advantage.

I know for sure that this problem is solvable, at least by brute force, because the number of pairs of odd vertices which should be connected with some number of edges is finite; specifically, there are $2^{n/2} \Gamma(\frac{n+1}{2})/\sqrt{\pi}$ (Mathematica said so) possible sets of pairs of odd vertices to connect. It's possible to go through each one, linking up each vertex to its partner (finding the shortest path between the two vertices in an undirected graph is probably a challenge within itself, which Wikipedia fails to give a time complexity for).

In the end, the whole deal probably runs in polynomial times exponential times factorial time, which is pretty nasty. I've done some basic research into whether there are algorithms which Eulerize paths, but can't seem to find any.

*Mathematica* code for graphic:

```
GraphPlot[
  {1 -> 2, 2 -> 5, 5 -> 3, 3 -> 6, 6 -> 3, 6 -> 7, 7 -> 6, 2 -> 7, 7 -> 8, 8 -> 9, 9 -> 10, 10 -> 4, 4 -> 11, 11 -> 4, 11 -> 12, 12 -> 1, 1 -> 12},
  VertexRenderingFunction ->
    (If[#2 < 5,
        Text[Style[#2, Large], #1, Background -> Yellow], Null] &)]

```

# Answer
> 5 votes
Consider the Chinese Postman Problem on undirected graphs: Given an undirected graph $G$, find the shortest circuit of the graph that travels every edge atleast once. Now, if $G$ is Eulerian, then the Euler circuit is the shortest such circuit. If not, some edges will be traveled more than once. In other words, some edges will be duplicated, and the circuit will be Eulerian on the graph with these extra edges.

Now, for obtaining the shortest circuit, the edge duplication has to be minimized. This is the same as your problem. You need to find a new graph $H$ which has all the edges of $G$, and a few extra parallel edges - as few extra edges as possible - so that $H$ is Eulerian. Each extra edge in $H$ corresponds to the fact that its corresponding parallel edge in $G$ is visited again in a shortest complete circuit of $G$. In other words, the optimum (minimal) "eulerization" is equivalent to the Chinese Postman problem. For a better expressed explanation of this, refer to Section 4 (Chinese Postman Problem) and Definition 11 (Eulerization, Minimal Eulerization) of these notes. Fortunately, this is solvable in polynomial time for undirected graphs.

For the Chinese Postman problem, Wikipedia has one solution. I describe another algorithm from Steven Skiena's The Algorithm Design Manual \[1\]:

1. Find the shortest paths between each pair of odd-degree vertices in $G$: $O(n^3)$.
2. Finding the best set of shortest paths to add to $G$ reduces to identifying the minimum-weight perfect matching in a special graph $G' = (V', E')$. The vertices $V'$ of $G'$ correspond the odd-degree vertices of $G$, with the weight of the edge $(i, j) \in E'$ defined to be the length of the shortest path from $i$ to $j$ in $G$. Note that a matching is a set of pairwise non-adjacent edges. Thus, each edge in the matching connects two vertices, and no vertex is part of two matching (a matched vertex is matched with exactly one other vertex). A perfect matching is a matching where each vertex has been matched. Now, for each matching edge obtained, you can consider the two end vertices to be paired up. The constraint of "minimum-weight" when obtaining the matching ensures that the total weight of each edge in the matching is as small as possible. Since the weight of each edge is the distance between its end points in $G$, which in turn is the number of edges that need to be duplicated when the end points are paired up - this condition ensures that globally, the total number of edge duplication is minimized. Obtaining such a matching is described in \[2\], and is based on the Blossom algorithm. An efficient implementation is described by Kolmogorov \[3\] (preprint copy) with an implementation here. The implementation is an improvement over the ideas and review presented by Cook and Rohe in \[4\]. This can be done $O(n^3)$.
3. Once the matching is obtained, each odd vertex is paired with another odd vertex. This is the pairing that you want.

Thus, you can obtain the optimal "Eulerization" in time polynomial (cubic) in the number of odd-vertices. This is based on a paper by Edmonds and Johnson \[2\] which solves the Chinese postman problem.

References:

1. Steven S. Skiena. The Algorithm Design Manual. ISBN: 978-1-84800-069-8 e-ISBN: 978-1-84800-070-4 and DOI: 10.1007/978-1-84800-070-4
2. J. Edmonds and E. Johnson. Matching, Euler tours, and the Chinese postman. Mathematical Programming, 5:88–124, 1973.
3. Vladimir Kolmogorov. Blossom V: A new implementation of a minimum cost perfect matching algorithm. In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.
4. W. Cook and A. Rohe. Computing minimum-weight perfect matchings. INFORMS Journal on Computing, 11(2):138–148, February 1999.

---
Tags: graphs
---