# Question
Title: If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?
I have only begun studying this subject and have only completed the first few chapters of the *Elements of the Theory of Computation*.

I have seen the answers (on this site and elsewhere) saying that the set of all Turing machines is countably infinite. Intuitively, this makes sense to me, as I can imagine the equinumerosity of this set with the set of the natural numbers.

I have also seen the answers saying that a Turing machine cannot have infinite states by definition (the *Elements* provides one such definition). Moreover, an infinite state machine would be so powerful that it would not merit study, these answers say.

My question then is, how is it possible that a Turing machine must always have a finite set of states? If this were the case, could one not ask for the maximum number of states a Turing machine can have? And would one not expect this to be some fixed number?

I feel there are points about this theory that I am missing.

# Answer
You are mentally reversing two logical quantifiers, that are implicit in the statement "Turing machines must always have a finite set of states".

You read this sentence as "there exists a finite set $S$ of states such that all Turing machines $M$ use only states in $S$". Logically, this is a "$\exists S \forall M$" property.

Instead, the sentence is meant to be read as "for each Turing machine $M$, there exists a finite set $S$ of states such that $M$ uses only states in $S$". Logically, this is a "$\forall M\exists S$" property.

This is a matter of natural language being sometimes too easy to be misread.
> 8 votes

# Answer
If the set of integers is infinite, how can any integer be finite?

If the set of words of $\\{0,1\\}^\*$ is infinite, how can any word be finite?

You get the idea.
> 21 votes

# Answer
Maybe consider a simpler example. All Strings over the alphabet $\Sigma = \\{0, 1\\}$ have finite length, but there are an infinite number of strings over $\Sigma$. The reason for this is simple, suppose the longest String $x \in \Sigma^\*$ has length $|x| = m \in \mathbb{N}$. Then we can build a new string $y = x1$ of length $|y| = m + 1$, so $x$ can't have been the longest ↯.

Note that both $x$ and $y$ have finite length, but that doesn't mean that the length of strings must have an upper bound.

The same argument works on Turing machines, if $M$ is the Turing machine with the greatest number of states $m$, then you can always build a new machine that has $m + 1$ states by simply adding a superfluous state.
> 13 votes

# Answer
Each individual Turing machine has a *finite fixed* number of states. But not every two Turing machines have the same number of states.

There are Turing machines with one state, there are Turing machines with two states, there are Turing machines with three states, and this up to (excluding) infinity.

If we forget about Turing machines, the set of natural numbers is countably infinite, but every number is fixed and not infinite.
> 8 votes

# Answer
Any (Turing Machine, initial tape contents) pair may be transformed into a Turing machine where each tape position is either marked or unmarked (two states), and where the tape is initially blank. The complexity of any such machine may be be expressed using a single parameter: the number of states. For every number of states, some machines will terminate while others won't. Every machine that terminates will execute some finite number of steps and will be in a different state for each of them. Thus, the total number of states visited by machines having any given number of states will the sum of a finite set of finite numbers, i.e. a finite number. This number grows so quickly relative to the number of states that no Turing Machine could compute it for arbitary N, but it's nonetheless finite.
> 1 votes

---
Tags: turing-machines, computability, infinity
---


# Question
Title: Compute matrix inversion / multiplication using a black box
Suppose you're given a black box $A$, and you're told $A$ can invert a matrix (assuming the matrix is invertible) $M$ in $O(T\_A)$. You're also given a black box $B$, and you're told $B$ can multiply two matrices $X$ and $Y$ in $O(T\_B)$.

**There are two problems as follow:**

* How is it possible to compute $X \times Y$ by just using $A$ in $O(T\_A)$?
* How is it possible to compute $X^{-1}$ by just using $B$ in $O(T\_B)$?

**Some ideas that come to mind:**

We already know that if $X$ is invertible, then:

$$X\times X^{-1}=I$$

where $I$ is an identity matrix. But how can I compute $X^{-1}$? Any hint will be constructive.

# Answer
It was shown in 1969, by Strassen, that matrix multiplication and matrix inversion have the same computational complexity.

Details can be found on Wikipedia.
> 3 votes

---
Tags: algorithms, matrices, matrix-multiplication
---


# Question
Title: Finding a Maximum Cut With Force Labeled Vertices for Planar Graphs
The maximum cut problem is a combinatorial optimization problem that seeks to partition the vertices of a graph into two sets, $S$ and $T$, in a way that maximizes the number of edges that cross between the two sets. The problem is tractable for planar graphs. However, the vertices can be assigned to any of the two sets arbitrarily. A variant of the maximum cut problem for planar graphs forces some of the vertices to be in the same set and leaves the other set empty. Is there a fast algorithm to solve the forced variant?

# Answer
A special case of your problem, where the neighborhoods of the vertices you force together are disjoint, is equivalent to solving (regular) Max-Cut on an apex graph (a graph that is planar, save for one vertex).

Let $D$ be the set of vertices that are forced to one side. Recall that the neighborhoods of vertices in $D$ are disjoint. Make a graph $G'$ by contracting $D$ into a single vertex $d$. $G'$ is an apex graph - it may well not be planar, but if you take away $d$, the rest of the graph must be planar since it is unchanged from $G$. Solving Max-Cut on $G'$ solves your problem on the original graph $G$.

In the other direction, you have an apex graph $G$ with an apex $d$, and want to solve Max-Cut on this graph. Let $N(d)$ be the neighborhood of $d$, and let $r=|N(d)|$. Make a graph $G'$ by deleting $d$ and adding a set $D$ of $r$ vertices, each of them adjacent to exactly one vertex in $N(d)$ (all of them different). Adding a bunch of leaves to a planar graph clearly does not destroy planarity, so $G'$ is planar. Solving Forced Max-Cut on this graph where every vertex in $D$ is forced, solves Max-Cut on the original apex graph $G$.

So, what is the complexity of Max-Cut on apex graphs? The ISGCI page says it's NP-hard. Bear in mind that I haven't read their reference, but it's probably true.
> 2 votes

---
Tags: np-hard, planar-graphs, bipartite-graph, max-cut
---


title: Is Everything a Hardware Interrupt?

text:
# Question
Title: Is Everything a Hardware Interrupt?
Just need a little help understanding hardware interrupts.

As I understand (feel free to correct) a hardware interrupts occurs when hardware wants attention of the computer. In basic terms the hardware sends a message down the interrupt line which is then controlled by the PIC. The CPU receives the interrupt and carries out the instruction once it has completed the current one it is on.

Every time I've seen examples of interrupts they have been 'printer running out of paper', 'network adapter receiving data packet' etc. My question is, how is the process of the hardware interrupt any different from pressing a key on a keyboard or moving a mouse? Each of these actions requires attention from the CPU but as I understand they are never used as examples of interrupts. Are they interrupts? Does everything I do with an input device cause an interrupt?

Any clarification would be much appreciated.

# Answer
> 6 votes
In general, no, on modern platforms, not everything is a hardware interrupt -- though you could imagine a platform where it is.

On some platforms, hardware interrupts are used for all input events (including, yes, pressing a key on a keyboard or moving a mouse).

However, interrupts come with some performance implications. Therefore, in modern platforms, we often use a combination of interrupts and other I/O mechanisms. We might use interrupts for some input devices, but other input devices might use memory-mapped I/O. For instance, your Ethernet card might use memory-mapped I/O, to write incoming packets into a region of memory dedicated for this use. Memory-mapped I/O can be combined with interrupts or with polling.

You can find more on interrupts, polling, memory-mapped I/O, DMA, and related topics in a good operating systems textbook.

# Answer
> 1 votes
Not everything is a hardware interrupt. Hardware interrupts are mostly used to gather input from IO devices. Today, it is rather complex and quite different from how it used to work with the old 8259 PIC. Today, there's a combination of IO APIC which serves the whole CPU and local APIC which serves a specific core of the CPU.

The IO APIC is becoming more and more obsolete with the MSI/MSI-X capability of PCI devices. PCI devices are MMIO meaning that you write to certain (uncached) part of RAM and it sends the data to the PCI devices instead. I don't know exactly how it is implemented in hardware itself. I would guess that there is a separate part in the CPU which is configured by the PCI devices themselves. For example, when you plug a PCI device, it would send signals to the CPU. Again, I don't know how that works exactly. What I know is that the configuration space of a PCI device can change position. For example, a BAR can point to different addresses depending on the device and its version.

Most chips today are PCI-express and they have the mandatory MSI-X capability. They thus bypass the IO APIC and send some kind of inter-processor interrupt to the CPU. It thus makes the IO APIC more and more obsolete because everything is PCI today.

For x86, you could think of the AHCI which drives SATA hard-drives, the xHCI which drives USB devices, network cards which are PCI or graphics cards which are also PCI.

# Answer
> 0 votes
I think there is quite a lot lacking from the above answers.

Let’s first think about what an interrupt provides. An interrupt is how we accomplish preemption in a computer system. That is, stopping program execution in arbitrary positions in their code. All preemption in a computer system is accomplished via interrupts. Many software frameworks and operating systems have features that feel & look like preemption but without an interrupt it has not actually preempted a processor core.

There are a few different kinds of interrupts, maybe more than listed

Line Interrupts - A physical wire/pin on the CPU. Trigger types: (Edge Triggered/Level Triggered)

Messaged Interrupts - There aren’t enough pins on the CPU to support enough interrupts in modern computers. Modern CPUs such as Intel/AMD with many cores have a network inside of the CPU between cores, cache, memory & I/O. Messaged interrupts are effectively a packet in the CPU core/mesh network. It is a hw implementation.

NMI - Non-Maskable interrupt. Interrupt that cannot be ignored, most commonly used to crash/shut down a system after an uncorrectable error etc.

Interrupts controllers often supports interrupt priority. Some interrupt controllers support interrupt nesting. (Interrupting an interrupt)

Most people talk about I/O as being the most common source of interrupts. There are a few other interrupt sources of interest.

Timers - Processor can set a hw timer & receive an interrupt when the timer expires.

MMU - memory management unit sends interrupts on TLB exceptions. Page faults etc.

Errors - Many things can generate interrupts when a correctable or uncorrectable error occurs. (DRAM, PCIe devices etc). Processor Exceptions such as overflows, zero division, segment errors, protection faults etc.

CPU Cores - Many platforms support CPU cores sending interrupts to other CPU cores. A common thing in some OS schedulers for task migrations etc.

---
Tags: operating-systems
---


title: Shortest paths in $k$-partite DAG

text:
# Question
Title: Shortest paths in $k$-partite DAG
Let

* $D(V, A)$ be a $k$-partite DAG;
* $P = \\{ p\_k : 1 \leqslant k \leqslant |P| \\}$ such that $p\_k \cap p\_l = \emptyset$, $\forall k,l : k \neq l$, and $\bigcup\_{1 \leqslant k \leqslant |P|} p\_k = V$ be the set of partitions;
* $A = \\{ (i, j) : \forall\_{1 \leqslant k \leqslant |P| - 1} (i \in p\_k \wedge j \in p\_{k + 1}) \\}$ be the set of arcs; And
* $d\_{ij}$ be the distance of arc $(i, j) \in A$.

For instance, consider the following DAG example.

We aim to calculate the shortest paths length $l\_{ij}$, $\forall i, j \in V$. For this purpose, straightforwardly, we could take the Floyd & Warshall algorithm, consuming $\mathcal{O}(|V|^3)$. But, I am looking for better ways of doing this, since the general Floyd & Warshall simply does not consider the specificities of the input graph.

Thanks and regards.

# Answer
> 3 votes
If $|p\_k|\leqslant N$ for all $k\in \\{1, …, |P|\\}$, then a dynamic programming algorithm can compute all those distance in $\mathcal{O}(|V|^2\times N)$ which could be lesser than $|V|^3$.

The idea is the following:

* if $i\in p\_k$ and $j \in p\_{k+1}$ for some $k$, $\ell\_{ij} = d\_{ij}$ (or $\infty$ if there is no edge between $i$ and $j$);
* if $i \in p\_k$ and $j\in p\_{k'}$, $k'\>k+1$, then $\ell\_{ij} = \min\limits\_{v\in p\_{k'-1}}\\{\ell\_{iv} + d\_{vj}\\}$.

---
Tags: graphs, shortest-path, partitions, dag
---


# Question
Title: Creating a context-sensitive grammar (CSG) for the language L = {anbna2n: n ≥ 1}
Need a grammar that can create this language, I am having issues getting a language to work and was looking for help.

# Answer
This is probably not the simplest, but here's a grammar for $L = \\{a^nb^na^{2n} : n \geq 1\\}$. Let $G = (\\{S, A, B\\}, \\{a, b\\}, P, S)$ where $P$ contains exactly

$$S \to aAbaa$$ $$A \to aAbBB | \varepsilon$$ $$Bb \to bB$$ $$Ba \to aa$$

then $L(G) = L$.
> 0 votes

---
Tags: context-free, context-sensitive
---


# Question
Title: why DFA to regex by two different methods differ
I was learning converting DFA to regex. I came across Arden's method which solve given DFA as follows:

**Ardens method**

Let us form the equations

$q\_1 = q\_10 + q\_30 + є$

$q\_2 = q\_11 + q\_21 + q\_31$

$q\_3 = q\_20$

Solving the eq\_uations

$q\_2 = q\_11 + q\_21 + (q\_20)1 = q\_11 + q\_2(1 + 01)$

$q\_2 = q\_11 (1 + 01)^\*$

So, $q\_1 = q\_10 + q\_30 + є$

$q\_1= q\_10 + q\_11(1 + 01)^\*00 + є$

$= q\_1(0 + 1(1 + 01)^\*00) + є$

$= є (0 + 1(1 + 01)^\*00)^\*$

$q\_1=(0 + 1(1 + 01)^\*00)^\*$

So the regular expression for the given automata is $=(0 + 1(1 + 01)^\*00)^\*$

When I solved above using state reduction method I got different answer:

**State Reduction method**

So final regex was $0+11^\*0(11^\*0)^\*0$

1. However this is different from what we get from Arden's method. Am I making any mistake?
2. Or both are correct?
3. If correct, is there any way to get same regex as Arden's using state reduction?
4. Does Arden's method gives shortest regex?
5. Any other observations about two methods?

# Answer
No, these methods are not guaranteed to yield the shortest regexp. Therefore, there's no reason to expect them to necessarily yield the same regexp.

Given a regexp $R$, finding the shortest regexp $R'$ that is equivalent to $R$ is known to be PSPACE-complete, by a result of Meyer Stockmeyer. Consequently, none of these procedures can be expected to yield the shortest regexp. If they did, then we could just take $R$, convert it to a NFA, then convert it back to a regexp $R'$ using that method, and we'd have an efficient way to find the shortest regexp, implying that P = PSPACE -- something that is not believed to be true.

(In fact, it's even hard to approximate, i.e., to find a regexp that is close to the shortest.)

To learn more, see On Learning Regular Languages on the CSTheory.SE blog.
> 6 votes

# Answer
* There is a unique minimal state machine.
* There is NO unique minimal regular expression.

For example,

$(a b)^\*a = a (ba)^\*$

So even algorithms that yield a minimal expression need not yield the same result.
> 0 votes

# Answer
Replacing your $\\{0,1\\}$, respectively by $\\{a,b\\}$ and using more algebraic notation with $1$ in place of $ε$, the automaton can be presented either as a right-affine system $$ A ≥ a A + b B + 1,\quad B ≥ a C + b B,\quad C ≥ a A + b B,\quad A $$ or a left-affine system $$ A ≥ A a + C a + 1,\quad B ≥ A b + B b + C b,\quad C ≥ B a,\quad A $$ where, in both cases, the last item refers to the "starting expression", following the remainder of the system, which is a fixed-point system of inequations in $(A,B,C)$ whose solution is to be applied to the starting expression. The solution is chosen as the least fixed point solution over a Kleene algebra. That's the contemporary framing of the problem (i.e. **inequations**, not **equations**).

Apart from that, everything else you said applies. Your methods - worked out on the left-affine system - yield $$(a + b (b + a b)^\* a a)^\*,\quad (a + b b^\* a (b b^\* a)^\* a)^\*,$$ and you forgot the Kleene-star on the second expression, as your diagram indicates should be there.

All Kleene algebra identities can be derived from a small set of equational properties (namely: those for an idempotent semiring, a.k.a. "dioid" as it is sometimes also known as) ... plus two conditional properties that can be stated as follows: $$μx·(a + b x) = b^\* a,\quad μx·(a + x c) = a c^\*,$$ where $μx·φ(x)$ denotes the least fixed point solution to $x ≥ φ(x)$. You could call those the "Arden Equations", if you wish. They have no official name. All finite one-sided affine systems have least fixed point solutions - under these axioms. And all properties of the algebras of regular expressions (which are known as the "free Kleene algebras") can be derived from these axioms.

For your case, you have the identity $(u + v)^\* = u^\* (v u^\*)^\*$. Thus $$(b + a b)^\* = b^\* (a b b^\*)^\*.$$ From this, it follows that $$a + b (b + a b)^\* a a = a + b b^\* (a b b^\*)^\* a a.$$

Then, you have the identity $(u v)^\* u = u (v u)^\*$, from which it follows that $$b b^\* (a b b^\*)^\* a = b b^\* a (b b^\* a)^\*.$$ Thus, $$a + b (b + a b)^\* a a = a + b b^\* a (b b^\* a)^\* a.$$ This shows that your two expressions are equal.

Using distributivity $u (v + w) = u v + u w$, you can proceed to write $$a + b b^\* (a b b^\*)^\* a a = (1 + b b^\* a (b b^\* a)^\*) a.$$ From the property $1 + u u^\* = u^\*$, it follows that $$(1 + b b^\* a (b b^\* a)^\*) a = (b b^\* a)^\* a.$$

Thus, your expression can also be written as $$((b b^\* a)^\* a)^\*.$$ Using the property $(u^\* v)^\* = 1 + (u + v)^\* v$ (which can be derived from the ones already listed), it follows that $$((b b^\* a)^\* a)^\* = 1 + (b b^\* a + a)^\* a.$$ Using distributivity on the other side $(u + v) w = u w + v w$ and the other properties already cited, we have $$(b b^\* a + a)^\* = ((b b^\* + 1) a)^\* = (b^\* a)^\* = 1 + (a + b)^\* a,$$ which also used commutativity $a + b = b + a$.

Thus $$((b b^\* a)^\* a)^\* = 1 + (b b^\* a + a)^\* a = 1 + a + (a + b)^\* a a.$$

For the right-affine system you can reverse-substitute $C$ in for $a A + b B$ to get: $$ A ≥ C + 1,\quad B ≥ a C + b B,\quad C ≥ a A + b B,\quad A. $$ Nobody ever said you always had to eliminate variables. You can put them back in, too.

Now, you can eliminate $A$, applying distributivity (and commutativity) $$ B ≥ a C + b B,\quad C ≥ a + a C + b B,\quad 1 + C. $$ Then you can reverse-substitute $B$ for $a C + b B$ to get $$ B ≥ a C + b B,\quad C ≥ a + B,\quad 1 + C. $$ Then, you can forward-substitute and eliminate $C$ (and apply distributivity) to get $$ B ≥ a a + (a + b) B,\quad 1 + a + B. $$ Finally, use the Arden axiom on $B$ to get $$ B ≥ (a + b)^\* a a,\quad 1 + a + B. $$ and substitute out $B$: $$1 + a + (a + b)^\* a a.$$

For the left-affine system, if you first factor, you get: $$ A ≥ (A + C) a + 1,\quad B ≥ (A + B + C) b,\quad C ≥ B a,\quad A. $$ This shows that the **actual** variables are not $(A,B,C)$, but $$(A, D, E) = (A, A + C, A + B + C).$$ Reverse-substitute for $A$ and $B$ in $D$, and for $A$, $B$ and $C$ in $E$, and use commutativity to get $$ A ≥ 1 + D a,\quad B ≥ E b,\quad C ≥ B a,\quad A. $$ Then, reverse-substitute on the left-hand side and use commutativity and distributivity to get: $$ A ≥ 1 + D a,\quad D ≥ 1 + D a + B a = 1 + (B + D) a = 1 + E a,\\ E ≥ 1 + E a + E b = 1 + E (a + b),\quad A. $$ Forward-substitute for and eliminate $A$: $$ D ≥ 1 + E a,\quad E ≥ 1 + E (a + b),\quad 1 + D a. $$ Then, forward substitute for and eliminate $D$ and apply distributivity $$ E ≥ 1 + E (a + b),\quad 1 + a + E a a. $$ Apply the Arden axiom on $E$ $$ E ≥ (a + b)^\*,\quad 1 + a + E a a. $$ Then forward-substitute for and eliminate $E$: $$1 + a + (a + b)^\* a a.$$

If "simplicity" is measured by star-height, then this is optimial. It has star-height 1, while the other expressions have star-height 2. The problem of minimizing star-height is highly non-trivial, but solved (in the 1990's).

You can go much further with everything ... nowadays.

To get an algebra suited for **context-free expressions** it suffices to replace the Arden axioms by the μ-continuity/distributivity axiom $$u (μx·φ(x)) v = \sup\_{n≥0} u φ^n(0) v,$$ where $$φ^0(x) = x,\quad φ^1(x) = φ(x),\quad φ^2(x) = φ(φ(x)),\quad φ^3(x) = φ(φ(φ(x))),\quad ⋯,$$ and $φ(x)$ is an *arbitrary* Kleene-polynomial in $x$. Solutions can be expressed Kleene-algebraically, using *context-free expressions*, e.g. $$μx·(u x v + w) = b (u p + q v)^\* d,$$ which - here - extends the Kleene algebra given by $X = \\{u,v,w\\}$ by the inclusion of the "bracket operators" $Z = \\{b,d,p,q\\}$ satisfying $$b d = 1 = p q,\quad b q = 0 = p d,\quad x z = z x\quad (x ∈ X,\quad z ∈ Z).$$

They are known equivalently as μ-continuous Chomsky algebras / C-dioids the two characterizations having arisen, respectively, in 2013 and 2008, their equivalence proven in 2018. Their representation as Kleene-algebras with the bracket operators affixed is via a result, (finally and belatedly) put into the peer review literature a few years ago, that is an algebraic generalization of, and a completion of, the Chomsky-Schützenberger Theorem.

So, similar and more elaborate exercises can be used to crunch *non-linear* fixed-point systems (e.g. systems that correspond to context-free grammars, or translation grammars such as arise in parsing theory) into context-free expressions.

The worst cases, if you allow the sharing of sub-expressions, are cubic in the number of variables for turning one-sided affine systems into regular expressions; but linear (and star-height 1) - for both the affine and more general non-linear systems, if you use the bracket operators $\\{b,d,p,q\\}$.

If you allow for commutativity of the product - the situation that occurs with Parikh's Theorem - then the Arden axioms, alone, suffice and you can write $μx·φ(x) = φ'(φ(0))^\* φ(0)$, where the usual rules of differentiation on polynomials (after noting, for instance, that $d(x^2)/dx = 2x = x$, since $x + x = x$ in Kleene algebras) is extended to the Kleene star with $d(x^\*)/dx = x^\*$. For commutative Kleene algebras, the star behaves like the exponential: $u^\* v^\* = (uv)^\*$ and $0^\* = 1$.
> 0 votes

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


# Question
Title: Different application of Arden's theorem leads to different answers
So, I have to solve for the following set of equations

> $q\_1$ = $q\_1$a + $q\_2$b + $\epsilon$
>
> $q\_2$ = $q\_1$a + $q\_2$b + $q\_3$a
>
> $q\_3$ = $q\_2$a

There are two ways to do this.

I did this

> $q\_1$ = $q\_2$b + $\epsilon$ \+ $q\_1$a
>
> $q\_1$ = ($q\_2$b + $\epsilon$)a\* Applying Arden's theorem

Now substituting in $q\_2$ the values of $q\_1$ and $q\_3$

> $q\_2$ = $q\_2$ba\*a + a\*a + $q\_2$b + $q\_2$aa
>
> $q\_2$ = a\*a + $q\_2$(ba\*a+b+aa)
>
> $q\_2$ = a\*a(ba\*a+b+aa)\* Applying Arden's theorem
>
> $q\_2$ = a\*a(ba\*+aa)\*

Now substituting in $q\_3$, the answer should be

> $q\_3$ = a\*a(ba\*+aa)\*a

However, the correct answer is

> (a + a(b+aa)\*b)\*a(b+aa)\*a

which can be obtained by first substituting $q\_3$ in $q\_2$, and then substituting $q\_2$ in $q\_1$, and finally solving $q\_2$, $q\_3$ from the obtained regular expression for $q\_1$.

Can someone tell where I have gone wrong in the above method, or am I applying ardens theorem in the wrong way ?

# Answer
The two regular expressions describe the same language.
> 1 votes

# Answer
Using various Kleene algebraic properties, such as the following $$ (u + v)^\* = v^\* (u v^\*)^\* = (v^\* u)^\* v^\* = u^\* (v u^\*)^\* = (u^\* v)^\* u^\*,\\ u u^\* = u^\* u,\quad (u v)^\* u = u (v u)^\*,\quad u^\* φ(u)^\* = u^\*,\\ u + v = v + u,\quad (u + v) w = u w + v w,\quad u 1 = u,\quad 1 + u u^\* = u^\*, $$ where $φ(u)$ denotes an arbitrary Kleene-algebraic polynomial in $u$, we can write $$\begin{align} a (a + b)^\* a &= a a^\* (b a^\*)^\* a\\ &= a a^\* (a a)^\* (b a^\* (a a)^\*)^\* a\\ &= a^\* a (a a)^\* (b a^\* (a a)^\*)^\* a\\ &= a^\* a (b a^\* + a a)^\* a,\\ \end{align}$$ and $$\begin{align} a (a + b)^\* a &= a a^\* (b a^\*)^\* a\\ &= a a^\* (a a)^\* (b a^\* (a a)^\*)^\* a\\ &= a a^\* (b a^\* + a a)^\* a\\ &= a a^\* (b (1 + a a^\*) + a a)^\* a\\ &= a a^\* (b + a a + b a a^\*)^\* a\\ &= a a^\* ((b + a a)^\* b a a^\*)^\* (b + a a)^\* a\\ &= (a a^\* (b + a a)^\* b)^\* a a^\* (b + a a)^\* a\\ &= (a^\* a (b + a a)^\* b)^\* a^\* a (b + a a)^\* a\\ &= (a + a (b + a a)^\* b)^\* a (b + a a)^\* a. \end{align}$$

So, actually, you could have said it was $a (a + b)^\* a$.
> 0 votes

---
Tags: automata, regular-expressions
---


title: How to correctly learn algorithms?

text:
# Question
Title: How to correctly learn algorithms?
**Background:**

I've a degree in computer engineering that I completed 5 years ago. I got really good grades at algorithms class but forgot everything that I studied. My notes were lost while migrating to a different place.

Now, I want to relearn it. I have very little memory of how I learnt it at that time.

**Resources**

How To Best Learn About Algorithms In Depth

I've Cormen, Skiena books in pdf format and I've purchased "Design and Analysis of Algorithms" by S. Sridhar by Oxford Publications (I am from Nepal).

I've purchased couple of udemy courses(by Edufulness Atchyut and Himayatullah Sharief)

I've purchased Data Structures books by Lipschultz.

I go to google, type "filetype:pdf "algorithm i want to learn"" and read the slides. I also go to books.google.com and search for books that contains the contents "quicksort algorithm" and read them.

**My learning objectives**

* Be able to dry run the algorithm.
* Be able to calculate the time complexity.

I am surprised that I am not even able to dry run algorithms. I started with searching and sorting algorithms. It was a breeze to learn binary search, linear search type of algorithms. But as soon as I came towards "merge sort" , "quick sort", I am feeling very tough to understand. I've spent 3 daysX3 hrs on quick sort alone and still I can't do a dry run of the algorithm on my own, neither can I understand the dry run done by someone else.

I feel I am missing some prerequisites to learn algorithms. My plan is not to learn only algorithms but many computer science subjects(like operating system, distributed system, database management systems, computer networks, web security etc).

https://teachyourselfcs.com/

This is the complete roadmap I want to follow.

I know discrete mathematics and can understand them. My problem is not that I am having problem with proofs, I don't care about proofs. I just want to dry run the algorithm and call it a day.

Edit: I've watched numerous videos like these

https://www.youtube.com/watch?v=MZaf\_9IZCrc

But they're not helping me.

# Answer
> 1 votes
A good text (even available for free) is Jeff Erickson's "Algorithms". No, there is no solution manual.

Algorithms is a required subject in the ACM/IEEE recommendations, you'll find lots of class notes, homework problems, exams by looking around on the 'net.

Some areas that often are relegated to "graduate studies" are approximation algorithms (many problems have no reasonable algorithmic solutions, design an algorithm that gives an approximate solution, hopefully with performance guarantees) and average case analysis (a problem is classified as "hard" if there are cases that are hard, perhaps the typical case/cases met in practice/average are much easier). This is very relevant, but even harder than just complexity. Another area to look at is randomized algorithms, for some hard problems surprisingly simple algorithms which select alternatives at random give good average performance.

Note there are two main approaches: What I call the encyclopaedia approach (give a huge list of algorithms for a slew of problems) and the design/analysis approach (analyse a few algorithms in depth, emphasizing a range of design techniques and how to derive performance measures). Both have their place, check any texts you find, see if they agree with your personal learning style.

---
Tags: algorithms
---


# Question
Title: How to select hash functions for cuckoo hashing?
In cuckoo hashing, an insertion failure occurs when there is an infinite loop of displacements. This is detected by a “max iterations” count on the insert function.

When the insert fails, the table is rehashed using two new hash functions. These are selected from a given hash family.

My question - how are these hash functions chosen in practice?

I know there are common black-box hash functions like Murmur, Jenkins32, FNV, etc. I guess they could be used in sequence, but they’re optimised for different things. And rehashing the table can also fail, so such a “sequence” couldn’t be short, otherwise it’d risk another possible infinite loop.

I know that we can create arbitrary hash functions with various bitwise manipulations and arbitrary constant multiplications, but levels of dispersion and avalanching changes depending on the constants picked.

Further, I know that certain hashes allow us to seed their outputs, but my understand is that the choice of hash constants is significant to how well it performs, and the seed determines this.

I feel like I’m missing a fundamental understanding of how we can pick an arbitrary set of “good” hash functions from a given hash family.

# Answer
> 1 votes
Great question, well, actually a family of questions :)

Let's start with Cyckoo hashing. I checked the Wikipedia article to be sure, and indeed it doesn't mention any families. So, the answer is simple - you just use 2 hash functions, whose avalanche and other properties are good enough for you.

These 2 functions are fixed for each cuckoo hashtable, providing 2 allowed positions for each key. Just think about it - if you use NEW hash functions for each rehashing operation, then you can't find a key with 2 lookups, since this key can end up in ANY position of the hashtable!

# Answer
> 0 votes
If you only have one hash function $h$, you can turn it into two as follows:

$$\begin{align\*} h\_0(x) &= h(0 || x)\\ h\_1(x) &= h(1 || x) \end{align\*}$$

where $||$ denotes concatenation. In other words, you prefix the value being hashed with an identifier of which hash function you are using.

# Answer
> 0 votes
So apparently the right answer here is Tabulation hashing which guarantees the behavior for Cuckoo hashing. The linked paper provides the rather technical details and proofs.

---
Tags: hash-tables, hashing
---


# Question
Title: Sequence alignment with one to many characters
I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with one character beside allowing character substitution, deletion or insertion.

For example, if I have a set of similarly sounding characters, like

```
monir, monier, muneer, munir, mounir, mouneer

```

The alignment algorithm will produce the following output

```
m u n i - r
| | | |   |
m o n e e r

```

Is there a way to adapt these algorithms (or an alternative algorithm) to consider aligning/substituting character with more than one character in order to output something like

```
m u n i  r
| | | |  |
m o n ee r

```

Please note that, I'm using the standard java implementation for these algorithms and I don't have a predefined list of similarly sounding characters, so I'm trying to aligning the similar words together in order to extract these alignments.

# Answer
You can do this with a variant of the Smith-Waterman algorithm. It assigns a penalty for an insertion or deletion, and also assigns a penalty for a substition, that depends on the two letters. (This is used for calculating the similarity of protein sequences, e.g. with a lower penalty for replacing an acidic residue with another acidic one.)

For your case, the penalty score needs to depend on the previous context, so you will have to adapt a standard implementation.
> 0 votes

# Answer
If I understood your problem correctly, a trie data structure may help you. The main challenge would be after the first mismatch, match the upcomming characters. I'm not sure how I would hack it, but it may not be that hard.

Hope it helps. Regards
> -2 votes

---
Tags: algorithms, strings, edit-distance
---


# Question
Title: Selection sort on the array $\{5,9,11,10,2\}$
I want to understand how the algorithm of selection sort sorts the given array, $$A\[5\]=\\{5,9,11,10,2\\}$$ Step -$1:-$ I compare A\[0\] with remaining elements of the array and since $A\[4\]\<A\[0\]$ I swap them which leaves me with, $$A=\\{2,9,11,10,5\\}$$ Step-$2:-$ Repeating the similar procedure for $A\[1\]$ gives $$\\{2,5,11,10,9 \\}$$ Step-$3:-$ Repeating similar procedure gives $$\\{2,5,10,11,9\\}$$ And the for loop stops. But the array isn't sorted yet. Is there any mistake with my interpretation of the algorithm?

C program for selection sort:-

```
#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;

    for (i = 0; i < n - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

```

# Answer
> 0 votes
You are stopping the `i` loop too soon.

You should try it again and keep track of the value of $i$ and keep in mind that in an array of length $n$, indices of the array are between $0$ and $n-1$.

---
Tags: algorithms, sorting, c
---


# Question
Title: Parse tree choices for proving the pumping lemma for CFL
I was studying pumping lemma for CFL and in the proof it says that, we choose the shortest parse tree if there are multiple parse trees and we also choose $R$ the repeating variable such that it's the lowest in the tree. It says that it satisfies **condition 2** $(|vy| \gt 0)$ & **3** $(|vxy| \leq p)$. I don't understand how.

# Answer
> 1 votes
In the book "Introduction to the Theory of Computation, 3rd Edition" by Michael Sipser, he provides arguments for why two conditions follow( you can check theorem 2.34). Additionally, he mentions these arguments in his online lectures, which can be found here: https://www.youtube.com/watch?v=IycOPFmEQk8.

Essentially, the reasoning behind the two conditions is as follows:

The choice of repeating R as the lowest is made to guarantee the fulfillment of the third condition. This choice ensures that the border word remains minimal. If the border word were any larger, it would result in another repetition, because if the border word were any larger it would give us another repetition, so bottom 2 would've changed(your chosen lowest 2 won't be lowest 2),

Also he argues that opting for the smallest parse tree guarantees the fulfillment of the second condition. If it (vy) were empty, it would imply the existence of a smaller parse tree, contradicting the condition requiring the parse tree to be minimal.

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


# Question
Title: Initialization of embedding space value for VQ-VAE
I am trying to study a research paper about VQ-VAE: Neural Discrete Representation Learning, Aaron van den Oord, Oriol Vinyals, Koray Kavukcuoglu, NeurIPS 2017.

I have difficulty to understand the value of embedding vectors $e\_j$ in this part (page 3 from the research paper):

> The posterior categorical distribution $q(z|x)$ probabilities are defined as one-hot as follows:
>
> $q(z=k|x)=\begin{cases}1, & \text{for k = }argmin\_j ||z\_e(x) - e\_j||\_2\\ 0, & \text{otherwise} \\ \end{cases}$

Here we define latent embedding space $e\in R^{K×D}$ and there are K embedding vectors $e\_i \in R^D$.

My question is how to initialize latent embedding space and its value. Is it random initialization? Because we need to subtract our $z\_e(x)$ with $e\_j$ so embedding space $e$ must have some value.

# Answer
> 0 votes
In initializing codebook embeddings, a common practice is to employ random initialization due to its simplicity and effectiveness in various contexts. A widely adopted method among practitioners is to sample values uniformly from a specified range. Specifically, the range is typically chosen to be between $-1/K$ and $1/K$, where K represents the total number of embeddings in the codebook.

Here is an example of an implementation using this initialization:

---
Tags: machine-learning, encoding-scheme, research
---


# Question
Title: Is Group Theory useful in Computer Science in areas other than cryptography?
I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot find out where and how to apply Group Theory to other areas in CS, such as algorithms, data structres, graphs, complexity and so forth.

# Answer
> 21 votes
Algorithms for isomorphism problems such as graph isomorphism rely heavily on group theory.

An unusual example of group theory applied to computer science is the famous proof of Barrington's theorem, which uses the nonsolvability of the symmetric group $S\_5$ to show equality of two complexity classes that superficially have nothing whatsoever to do with groups.

# Answer
> 15 votes
Group theory is indeed useful in algorithm design. For example, matrix multiplication is a fundamental problem for which such approaches have been used (see e.g., Cohn et al. \[1\] or these lecture notes).

There are also algebraic algorithms for other problems in e.g., graph theory (Hamiltonian path/cycle, graph motif, and various other path problems) based on techniques such as inclusion-exclusion and clever use of polynomials. These techniques often make use of finite field arithmetic.

---

\[1\] Cohn, H., Kleinberg, R., Szegedy, B. and Umans, C., 2005, October. Group-theoretic algorithms for matrix multiplication. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) (pp. 379-388). IEEE.

# Answer
> 9 votes
The theory of continuous groups underlies a lot of modern computer graphics and computer vision, because Lie group theory is one of the more natural representations of a space of transformations.

Also, Galois theory is one of the workhorses of modern computer algebra systems.

# Answer
> 7 votes
Symmetry in combinatorial optimization.

An important group-theoretic algorithm often applied in theoretical computer science is Buchberger's algorithm.

# Answer
> 6 votes
# Category Theory

If you accept Category Theory as a kind of generalization of groups, then we can conclude that modern type theory as related to the design of programming languages absolutely depends on it. For instance, take a look at this Q & A. Also, structures within programming languages, such as monads, are also categories.

# Answer
> 6 votes
To give a yet another example, constraint satisfaction problems can be solved with a semiring formalism, using pretty much schoolbook algebra and lattices.

Also, any machine integers are a special case of a residue arithmetic, which is basically, $Z/nZ$. That's not mentioning all the computer algebra.

And formal "muscle" from undergrad algebra would help you with something like relational algebra (hello, SQL) or automata and formal languages, or communicating sequential processes and $\pi$-calculus (hello, theory of parallel computing).

# Answer
> 5 votes
Dijkstra shortest path algorithm relies heavily on algebraic properties of the way you compare/combine paths (we call it the algebra in this case). Network routing algorithms often use veresions of Dijkstra'a algorithm which are based on a different algebra, and their correctness is guaranteed by the algebraic properties of the compare/combine laws.

You can have a look at this document which describes in length how one can generalize Dijkstra's algorithm to other algebras than the usual $(\mathbb{R}, \min, +)$.

# Answer
> 3 votes
There are many applications of group theory directly or indirectly to computer science. The group isomorphism problem in which given two groups to check if they are isomorphic or not. Let us assume that input groups are given by their multiplication tables. The fastest algorithm, in this case, is given by Tarjan (miller credited it to Tarjan)takes $n^{\log n}$ time. The idea is as follows, given $G$ and $H$, first find a generating set (say $S$) of $G$ (one can find it easily by the greedy algorithm) then set all possible maps from $S$ to $H$ (brute force) and check if any map is bijective homomorphism or not.

The group isomorphism problem when input groups are given by their Cayley table (multiplication table) polynomial-time reducible to the graph isomorphism problem. For graph isomorphism problem there has been lots of use of group theory. The graph isomorphism problem when input graphs have a degree at most three then also the algorithm used is heavily based on group theory.

There has been work on data structures and algorithm side also when input groups are given by a set of generators. Even there has been a data structure (like Schreier–Sims tree or vectors) that is designed for a group theory. See Link

There are many other interesting problems that have been studied in the past like finding the minimum generating set of a group given by a Cayley table. Arvind and Toran design a polynomial-time algorithm for nilpotent groups (groups very close to commutative groups). See link.

One more interesting problem is given a group and you need to compute all indecomposable factors. If you don't know much about group theory then think like you are given a number and want to factor it into prime factor. There are polynomial-time algorithms for this problem whether the input group is given by generating set or Cayley table.

Groups when given by generator relator representation, in this case, many problems like chacking whether a given group is nontrivial or finite are undecidable.

# Answer
> 3 votes
Group theory is used all over the place in quantum computing. Some examples:

* The set of reversible quantum logic gates on $n$ qubits is the group $SU(2^n)$.
* Some important finite groups of quantum logic gates include the Pauli and Clifford groups which are essential constructs in quantum error correction, and the efficient simulation of quantum circuits using classical computers.

# Answer
> 2 votes
Group theory is also useful, via applications to number theory, in non-cryptographic pseudorandom number generating algorithms. See for example Niederreiter and Winterhof's Applied Number Theory (which also discusses cryptography and other CS topics).

The chapter on PRNGs in that book focuses mainly on simple algorithms such as linear congruent generators, but I'm pretty sure that group theory also plays a role in recent more complex PRNGs such as generalized linear shift registers. Those definitely make use of finite fields, but I'm not sure to what extent results from group theory per se are important for those algorithms.

---
Tags: algorithms, complexity-theory, graphs, data-structures, group-theory
---


# Question
Title: How can primitive recursion be a special case of minimization?
In several posts on StackExchange and elsewhere, I have seen claims that you only need to show you can construct constants, successor, projection, composition, and minimization to prove a language Turing-complete, since primitive recursion is allegedly a special case of minimization. But as I have been thinking about it, I don't see how minimization can be used effectively at all without primitive recursion.

1. Minimization searches for zero
2. The only way to get zero without primitive recursion is a constant zero
3. So any application of minimization must either:
4. Return a constant zero all the time (since there is no way to do conditionals either w/o p.r.), or
5. Return the input unmodified, since any number of successors other than zero would never return zero

So if every minimization must either return constant zero or zero only when the input is zero, how can you construct any function more powerful than this? Or is this a false assumption?

# Answer
> 6 votes
Your suspicion is correct. Without primitive recursion we get a very small class of functions, namely maps of the form $f(\vec{x}) = x\_i + m$, possibly with some undefined values.

Let $\mathcal{F}\_k$ be the least class of partial maps $f : \mathbb{N}^k \to \mathbb{N}$ closed under $0$, successor, projections, composition and minimization.

> **Theorem:** *For every $f \in \mathcal{F}\_k$ there exist $i$ and $m$ such that, for all $\vec{x} = (x\_1, \ldots, x\_k) \in \mathbb{N}^k$, either $f(\vec{x})$ is undefined or $f(\vec{x}) = x\_i + m$.*

*Proof.* We proceed by induction on the structure of $f$. It is obvious that $0$, successor, projections, and compositions preserve the stated property. Now consider $f \in \mathcal{F}\_k$ which is defined by minimization of $g \in \mathcal{F}\_{k+1}$, so that $$f(\vec{y}) = \min \\{x \in \mathbb{N} \mid g(x, \vec{y}) = 0\\}.$$ By induction hypothesis there are two possibilities:

1. There exists $m$ such that $g(x, \vec{y}) = x + m$ whenever $g(x, \vec{y})$ is defined. In this case:

* If $m = 0$ then $f(\vec{y}) = 0$
    * If $m \> 0$ then $f$ is everywhere undefined
2. There exists $m$ and $i$ such that $g(x, \vec{y}) = y\_i + m$ whenever $g(x, \vec{y})$ is defined. In this case:

* if $m = 0$ then $$f(\vec{y}) = \begin{cases}0 & \text{if $y\_i = 0$ and $g(0, \vec{y})$ is defined}\\ \text{undefined} & \text{otherwise} \end{cases}$$
    * if $m \> 0$ then $f(\vec{y})$ is everywhere undefined.

In all cases minimization preserves the stated property. $\Box$

Let us also try to speculate how the falacy "primitive recursion is a special case of minimization" arises. Suppose $f : \mathbb{N} \to \mathbb{N}$ is defined by primitive recursion by \begin{align\*} f(0) &= k\\ f(n+1) &= h(n, f(n)), \end{align\*} where $h : \mathbb{N}^2 \to \mathbb{N}$ is primitive recursive. Then there is a primitive recursive function $g : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ such that $$ g(x, y) = \begin{cases} 0 & \text{if $f(x) = y$},\\ 1 & \text{otherwise.} \end{cases} $$ The map $g$ involves a good deal of arithmetic, encoding of lists as numbers, etc. Cruicially, $g$ may be more complicated than $f$ and $h$.

Therefore, we could define $f$ by minimization as $$f(x) = \min \\{y \mid g(x,y) = 0\\}.$$ However, we need the entire primitive recursion machinery to get the suitable $g$, so we cannot infer from this that primitive recursion can be dispensed with in the presence of minimization.

# Answer
> 1 votes
In Julia Robinson's "General Recursive Functions," she proves that all recursive functions can be obtained using only substitution (composition) and minimization, *provided* the initial functions are extended with additional members. In particular, she uses the two functions:

> $S(x, y) = x + y$ $Q(x) = \begin{cases} 1 & : x = k^2 \\ 0 & : \text{otherwise} \end{cases}$

It is possible to use only substitution and minimization with these functions (plus the standard initial functions, i.e. constant, projection, and successor) to build enough number theory to write Gödel's $\beta$-function, which allows us to define finite sequences, and in turn permits the emulation of any use of p.r.

---
Tags: computability
---


# Question
Title: Path Through Graph That Minimizes Node Attributes
I have a directed graph (DAG) containing many nodes, all with various attributes (node attributes not edge attributes). I have a single target (finish) node and a set of source (start) nodes. I want to find a path through this graph that minimizes the sum of all the attributes on said path, and return the top N minimized paths .

Example: the nodes are tasks in a to-do list. Some items on the list need to be completed before others can be started. In this example, an attribute could be the 'spare time' or 'wiggle room' an item has before its delay would have a knock-on effect and delay the next item. So I want to find the path that minimizes the total 'spare time'. i.e. the most optimal way of working through the task from A to B.

I considered using Dijkstra's algorithm where I replace the distance parameter with the node attribute I wish to minimize. However, I am not sure how this would work as I only have node attributes, not edge attributes. I could set the edge attribute to be that of the source, or target nodes for that edge, but I don't think this is valid. E.g. if using the source node attribute for the edge attribute, then the final node in the chain's attribute would never be used and vice versa. Additionally, the actual path length doesn't matter, just the sum of the attributes along the path.

Finally, another issue is that the attributes along the path that I am trying to minimize can be negative, so the minimized path sum can be negative or positive. This seems to rule out a BFS or DFS method with early stopping (threshold) as it could stop before a future negative attribute has been reached, which would decrease the total sum along the path.

Any help or suggestions would be great, thanks.

# Answer
> 0 votes
It's NP-hard with a single source and a single target, and looking for a single path.

Reduction from SAT. Let $\phi = C\_1 \land C\_2$ where $C\_1 = x \lor y$ and $C\_2 = \neg x \lor y$.

See attached picture. There is a path collecting exactly #variables many attributes if and only if $\phi$ is satisfiable.

In the example, you can find an $s$-$t$-path collecting exactly two attributes, the ones corresponding to your chosen truth assignment. Notice that if you in the start choose to visit $\neg y$, you need to visit three attributes.

---
Tags: graphs, network-analysis, network-topology, path
---


# Question
Title: Are runtime bounds decidable for anything nontrivial?
> **Problem** Given a Turing machine $M$ which has known runtime ${O}(g(n))$ with respect to input length $n$, is the runtime of $M \in {O}(f(n))$?

Is the above problem decidable for some nontrivial pairs of $g$ and $f$?A solution is trivial if $g(n) \in O(f(n))$.

This is related to the problem Are runtime bounds in P decidable? (answer: no). One can derive from Viola's answer that if $f(n)\not \in o(n)$ and $f(n)\not \in O(g(n))$ then the problem is undecidable.

The requirement that $f(n)\not \in o(n)$ is because the $M'$ in Viola's proof need $O(n)$ time to find its input size. Thus Viola's proof could not work when $f(n)=1$.

It would be interesting if we can decide on the run time of sublinear time algorithms. A special case is when we have arbitrary $g(n)$ and $f(n)=1$.

# Answer
Here are a few remarks which could be relevant:

1. Kobayashi proved that a TM running in time $o(n\log n)$ accepts a regular language (and so runs in time $O(n)$); recently this has been extended to non-deterministic TMs (Tadaki, Yamakami and Lin).
2. Machines running in time $o(n)$ actually run in constant time (consider any $n$ for which the running time is less than $n$; adding characters to the end doesn't affect the TM).
> 7 votes

# Answer
There are a few related posts and papers (summarized down below), but they don't quite answer this particular question. Here we mostly answer it. Consider the problem for an arbitrary pair of functions $f$ and $g$.

**Theorem 1 (lower bounds).** *For multi-tape TMs, the problem is either trivial or undecidable.*

*For 1-tape TMs, if $g(n) = \Omega(n\log n)$, the problem is either trivial or undecidable.*

**Theorem 2 (upper bound).** *For 1-tape TMs, if $g(n) = o(n\log n)$, the problem is decidable.*

The one main non-trivial decidable case is for 1-tape TMs when $g(n) = n$ and $f(n) = 1$.

The cases we leave open are for 1-tape TMs when $g$ is "ill-behaved" in that $g$ is neither $O(n\log n)$ nor $\Omega(n \log n)$, in other words, $\lim\inf \frac{g(n)}{n\log n} = 0$ and $\lim\sup \frac{g(n)}{n\log n} = \infty$.

---

Here are the decision problems we consider:

* $H\_{fg}$: *Given a multi-tape TM $M$ that runs in time $O(g(n))$, does $M$ run in time $O(f(n))$?*
* $H^1\_{fg}$: *Given a single-tape TM $M$ that runs in time $O(g(n))$, does $M$ run in time $O(f(n))$?*

Say that $H\_{fg}$ is *trivial* unless

* some TM $M$ that runs in time $O(g(n))$ also runs in time $O(f(n))$,
* and some TM $M$ that runs in time $O(g(n))$ doesn't run in time $O(f(n))$.

Likewise for $H^1\_{fg}$, but restricting "TM"s to 1-tape TMs.

The proof of Theorem 1 reduces the Halting problem to $H\_{fg}$ and $H^1\_{fg}$, similarly to several previous results, but with some new tricks to make sure the reduction produces a TM running in time $O(g(n))$. Theorem 2 follows easily from known upper bounds.

---

### Related work

Before we sketch the proofs, here is a summary of some related results. Note that OP's question has two distinctive properties: (i) it is about a *promise* problem (the given TM must run in $O(g(n))$ time), and (ii) it asks whether the TM runs in time $O(f(n))$. Most of the results published in traditional venues below are promise-free, and many concern *exact* (not big-$O$) bounds. The stack-exchange posts do consider promise problems. Informally, having a strong promise (small $g$), or having exact (as opposed to big-$O$) bounds for $f$ tends to reduce the computational complexity of $H\_{fg}.$

It is an easy exercise to show that the problem "*Given a TM $M$, does $M$ run in time $O(1)$?"* is undecidable, whereas "*Given a TM $M$ and a constant $c$, does $M$ run in time at most $c$?*" is decidable.

* For many interesting functions $f(n)$ (e.g. $f(n) = n+1$) it is not decidable whether a given *multi-tape* TM runs in time $f(n)$ (note no $O$-notation!) \[Hájek, 1979\].
* Any of the following properties guarantees that the language of a given 1-tape TM $M$ is regular:

> 1. $M$ is deterministic and runs in time $O(n)$ \[Hennie, 1965\],
> 2. $M$ is deterministic and runs in time $(o(n\log n))$ \[Hartmanis, 1968\],
> 3. $M$ is non-deterministic with all execution paths running in time $(o(n\log n))$ \[Kobayashi, 1985\].

* From the proofs of those results it more or less follows that every 1-tape TM running in time $o(n\log n)$ runs in time $O(n)$ \[Gajser, 2015\], and that, given any linear function $f(n)$, it is decidable whether a given 1-tape TM runs in time $f(n)$ (note the absence of big-$O$ here!) \[Gajser, 2019\]. (In fact Gajser shows this is in co-NP.)
* Given a TM whose run-time is promised to be bounded by some (unknown) polynomial, one cannot compute an explicit polynomial bound \[Math Overflow, 2010\]. Similarly, given such a TM and integer $k$, it is undecidable whether the TM runs in time $O(n^k)$ \[CS Theory stack-exchange, 2011\]. The latter post cites \[Hartmanis, 1989\] as covering similar material.

---

---

---

### Utility lemma

Both proofs use the following utility lemma.

**Lemma 1.** *If $H\_{fg}$ or $H^1\_{fg}$ is not trivial, then $f(n) = \Omega(1)$ and $g(n) = \Omega(n)$.*

*Proof.* Assume $H\_{fg}$ is not trivial. Some TM runs in time $O(f(n))$, so $f(n)$ and $g(n)$ are $\Omega(1)$. Let $t(n)$ be the run time of some TM such that $t(n)$ is $O(g(n))$ but not $O(f(n))$. As observed in e.g. Lemma 3.1 \[Gajser, 2015\] if $t(n\_0) \le n\_0$ for any $n\_0$, then it must be that $t(n) = O(1) = O(f(n))$ (because on inputs of size $n\_0$ the TM's tape head never leaves the input, so the TM also halts in at most $n\_0$ steps on any larger input). So $g(n)$ must be $\Omega(n)$. This proves Lemma 1 for $H\_{fg}$. The same proof (but restricted to 1-tape TMs) works for $H^1\_{fg}$ $~~~\Box$

### Proof sketch for Theorem 1

First consider $H\_{fg}$. Assume $H\_{fg}$ is not trivial. Let $M\_g$ be a TM with run-time in $O(g(n))$ but not $O(f(n))$. Our goal is to make the natural reduction from the Halting problem to $H\_{fg}$ work. Given a 1-tape DTM $M$, the reduction outputs a $2$-tape DTM $M'$ that does the following:

TM $M'$ on input $x$ of length $n=|x|$:

> 1. simulate $M$ on empty input until it halts or completes some $\Theta(n)$ steps, whichever comes first
> 2. if $M$ doesn't halt during that simulation, then simulate $M\_g$ on input $x$ until $M\_g$ halts

The implementation will ensure that the run time of $M'$ is always $O(g(n))$, and is $O(f(n))$ if and only if $M$ halts.

##### Implementation details and proof of correctness for $H\_{fg}$

Step 1 holds $x$ on its first tape while using its second tape to simulate $M$. Meanwhile, just before each simulated step of $M$, Step 1 moves the head of the first tape one cell to the right (thus using this head as a counter). Step 1 halts the simulation when $M$ halts or when the head of the first tape moves off of $x$. Step 1 then returns the head of the first tape to cell 1 of that tape. Step 2 of $M'$ then simulates $M\_g$ on input $x$ using just the first tape. This completes the reduction.

To see that it's correct, first consider the case that $M$ halts on empty input, in some $h$ steps. Note that $h=O(1)$, that is, it is independent of $x$. Step 1 of $M'$ then runs in time $O(\min(h, n)) = O(1)$. Step 2 of $M'$ only runs if $n\le h = O(1)$, so runs in time $O(\max\_{n \le h} g(n)) = O(1)$. So, in the case that $M$ halts on empty input, $M'$ runs in time $O(1)$. By Lemma 1 this is $O(f(h))$ and $O(g(h))$. So, if $M$ halts on empty input, then $M'$ runs in time $O(f(h))$ and $O(g(h))$.

Next consider the case that $M$ never halts. Step 1 of $M'$ takes $O(n=|x|)$ time. Step 2 then takes $O(g(n))$ time. So $M'$ runs in time $O(g(n) + n)$. By Lemma 2 this is $O(g(n))$. So, if $M$ doesn't halt on empty input, then $M'$ runs in time $O(g(n))$.

So $M$ always runs in time $O(g(n))$, and runs in time $O(f(n))$ iff $M$ halts on empty input. So the reduction is correct in the case $k\ge 2$. This proves Theorem 1 for this case.

##### Implementation details and proof of correctness for $H^1\_{fg}$

Assume $H^1\_{fg}$ is not trivial. Assume (per the theorem statement) that $g(n) = \Omega(n\log n).$ The proof is the same as for $H\_{fg}$, except that $M'$ implements Step 1 differently, as follows, using only the one available tape.

Step 1 of $M'$ will simulate $M$, meanwhile counting the number $t$ of simulated steps, and somehow detecting when (if) $t$ reaches $\Omega(n)$. The challenge is to do such a simulation with a slowdown of at most an $O(\log n)$ factor. That is, $M'$ should simulate the first $t$ steps of $M$ in $O(t \log t)$ time.

Throughout the simulation, we think of $M'$ as having three virtual tapes, sharing one common tape head. The first virtual tape holds $x$. This virtual tape is read-only during Step 1. The second virtual tape is used as the simulated tape of $M$. The third tape is used as a "work" tape for $M'$ to hold additional state as described below. (Each tape cell is initialized lazily, only when, in the course of the computation as described below, $M'$ encounters the cell. These virtual cells are implemented by introducing appropriate symbols into the tape alphabet of $M'$ in a standard way.)

As $M'$ simulates $M$, it stores on its work tape, just to the right of the tape head, a counter that holds the number $t$ of steps simulated so far. It encodes $t$ in binary, using $O(\log t)$ bits. Each time $M'$ simulates a step of $M$, it also increments $t$. Each increment takes $O(\log t)$ time, including the time to reposition $t$ to keep it just to the right of the tape head. This effectively slows the simulation by an $O(\log t)$ factor.

Also, each time $t$ passes a power of two, $M'$ pauses the simulation temporarily and does a *probe*. The probe moves the tape head $t$ steps to the right, looking for the end of the original input $x$. If it finds the end within $t$ steps, it knows that $n= \Theta(t)$, so it stops the simulation (and restores the tape to its original state for Step 2).

In order to look $t$ steps to the right, as $M'$ moves the tape head to the right, it brings along a "countdown" value $t'$, encoded in binary and held just to the right of the tape head. The probe initializes $t'=t$, then, with each step to the right, decrements $t'$ and shifts it one step to the right. If $t'$ reaches zero before the probe finds the end of $x$, the probe stops and returns the head to resume the simulation of $M$. Note that probing $t$ cells to the right in this way takes time $O(t\log t)$.

This completes the description of $M'$. Next we verify that the reduction is correct.

Using the probes, $M'$ ensures that $t = O(n)$ throughout the simulation, and that the simulation halts when $t = \Theta(n)$.

A probe (after $t$ simulated steps) takes $O(t\log t)$ steps. So the total time for $M'$ to simulate the first $t$ steps of $M$ is at most:

$$\begin{align} &O(t \log t) && \text{for simulating the } t \text{ individual steps, plus} \\ &+O(t \log t + \frac{t}{2} \log \frac{t}{2} + \frac{t}{4}\log \frac{t}{4} + \cdots) && \text{for the } {\log\_2 t} \text{ probes, making} \\ &=O(t\log t) && \text{total.} \end{align}$$

Suppose that $M$ halts on empty input, in, say, some $h$ steps. So $h=O(1)$ (independent of $x$). There are $O(2^h) = O(1)$ inputs of length $O(h)$, so the time for those is $O(1)$. For inputs with length $n = \Omega(h)$, the simulation will stop when $M$ halts, so will take time $O(h \log h) = O(1)$. Step 2 then does nothing. So, if $M$ halts, then $M'$ runs in time $O(h\log h) = O(1)$. This is $O(f(n))$ and $O(g(n))$ (as required) by Lemma 1. So the reduction is correct in this case.

In the case that $M$ never halts, Step 1 of $M'$ stops the simulation after $O(n)$ steps, so Step 1 takes $O(n\log n)$ time. Step 2 then takes $O(g(n))$ time. So in this case $M'$ takes time $O(n\log n + g(n))$. By assumption $g(n) = \Omega(n\log n)$, so this is $O(g(n))$. So the reduction is correct in this case. This proves Theorem 1. $~~~~\Box$

### Proof sketch for Theorem 2

Assume per the theorem statement that $g(n) = o(n\log n)$. By e.g. \[Gajser, 2015\] and Lemma 1, any 1-tape TM running in time $o(n\log n)$ runs either in time $\Theta(1)$ or time $\Theta(n)$. Also, $f(n) \ne O(g(n))$ (else the problem is trivial). So assume WLOG that $f(n) = \Theta(1)$ and $g(n) = \Theta(n)$.

By a result of \[Gajser, 2019\], given any constant $a \ge 1$ and 1-tape TM $M$, it is decidable whether $M$ finishes in at most $cn$ steps (on all $n$, for all inputs of length $n$). Further, given a 1-tape TM that runs in time at most $cn$, one can explicitly compute, from $M$ and $c$, a DFA $D$ such that the language of $D$ contains exactly the sequences of crossing sequences that represent accepting computations of $M.$

(Each crossing sequence has length $O(1)$. The symbols in the input alphabet for $D$ correspond to pairs $(\alpha, s)$, where $\alpha$ is an input symbol for $M$, and $s$ is a possible crossing sequence.)

Finally, here is the procedure for deciding, given a 1-tape TM $M$ that runs in time $O(g(n)) = O(n)$, whether $M$ runs in time $O(f(n)) = O(1)$:

1. Compute a $c$ such that $M$ runs in time $c n$. (Use Gajser's result with $c=1,2,\ldots$ to find the smallest such $c$.)
2. From $M$ and $c$, use Gajser's other result to compute a DFA $D$ such that the language of $D$ contains exactly those sequences that represent computations of $M$.
3. Return 'yes' (i.e., that $M$ runs in time $O(f(n))$) if $L(D)$ is finite, else return 'no'. (This is decidable given $D$.) $~~~~\Box$
> 3 votes

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


# Question
Title: Is this bayesian average calculation right?
I have asked it already on math.stackexchange.com and stackoverflow.com but they said it was off-topic and could not help me. They pointed me to cs.stackexchange.com so hopefully somebody here can help me or atleast point me in the right direction.

We have been using a bayesian average on a website of ours for a couple of years now and it seems to have working great but when using the same formula with other (good) data on another website the output was a bit disturbing.

We use this PHP code:

```
<?php
$avg_num_reviews = 6264.3636363636;
$avg_rating = 4.527272727272727;
$this_num_review = 4;
$this_average_rating = 4;
$bayesian_average = (($avg_num_reviews * $avg_rating) + ($this_num_reviews * $this_average_rating)) / ($avg_num_reviews + $this_num_reviews);
echo $bayesian_average;
?>

```

This normaly is filled in dynamicly but to give you an idea we will put in the data manualy.

So this data:

```
$avg_num_reviews = 6264.3636363636;
$avg_rating = 4.527272727272727;

```

is correct.

If we then calculate the Bayesian average, then in my opinion something is going wrong. It would help us enormously if someone could say something meaningful about this.

```
$this_num_reviews = total number over reviews for this company;
$this_average_rating = the average rating of this company;

```

Now we get to the weird part.:

**Company A**

```
$avg_num_reviews = 6264.3636363636;
$avg_rating = 4.527272727272727;
$this_num_review = 4;
$this_average_rating = 4;
$bayesian_average = (($avg_num_reviews * $avg_rating) + ($this_num_reviews * $this_average_rating)) / ($avg_num_reviews + $this_num_reviews);

$bayesian_average = 4.5269362613254;

```

**Company B**

```
$avg_num_reviews = 6264.3636363636;
$avg_rating = 4.527272727272727;
$this_num_review = 111;
$this_average_rating = 4.2;
$bayesian_average = (($avg_num_reviews * $avg_rating) + ($this_num_reviews * $this_average_rating)) / ($avg_num_reviews + $this_num_reviews);

$bayesian_average = 4.5215746565744;

```

**Company C**

```
$avg_num_reviews = 6264.3636363636;
$avg_rating = 4.527272727272727;
$this_num_review = 15468;
$this_average_rating = 4.4;
$bayesian_average = (($avg_num_reviews * $avg_rating) + ($this_num_reviews * $this_average_rating)) / ($avg_num_reviews + $this_num_reviews);

$bayesian_average = 4.4366864211353;

```

If we would sort this based on the bayesian average it will be like this:

1. Company A
2. Company B
3. Company C

But how can it happen that a company (Company C) with 15468 reviews and an average of 4.4 has a lower Bayesian average than a company (Company A) with 4 reviews and an average of 4?

The Bayesian average should ensure that these kinds of things are prevented.

The logical sequence should be as follows:

1. Company C
2. Company B
3. Company A

When we re-calculate it by hand the outcome is the same.

Can someone explain to me why this happens and whether there might be something wrong in the formula?

Am I missing something or should I use a different formula to do this better?

If anyone can say something meaningful about this, I would be very grateful to that person because I am a bit off track at the moment.

# Answer
There's nothing wrong with the formula. It's doing exactly what you told it to do. I suspect you might have a misunderstanding of how to apply the Bayesian average.

By setting `$avg_num_reviews` to a huge number like 6264, you've basically told the Bayesian average that you have extremely high confidence that the average rating should be 4.527. It takes a gigantic number of reviews to override this prior. So of course your formula assigns Company A an average of close to 4.527, because the number of reviews of Company A is so vastly smaller than 6264 that the prior dominates; but your formula assigns Company C an average close to the average of C's ratings, because 15468 is significantly larger than 6264 and this is enough to overcome the strong prior.

I would expect more typical values for `$avg_num_reviews` would be vastly smaller, like 10. It's basically a parameter you can set, which controls how strongly you want the prior to be. Perhaps your mistake is setting it to be equal to the average number of reviews per company -- that doesn't seem like a good choice to me.

See https://en.wikipedia.org/wiki/Bayesian\_average.
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: Proving that Breadth-First Search (BFS) results in a bipartition of a tree
In my studies of discrete mathematics, I've learned that a tree graph is inherently bipartite. I'm interested in finding an algorithmic approach to determine its bipartition. It seems to me that Breadth-First Search (BFS) could be a reasonable method for this task.

However, I'm struggling with the formal proof of this concept. Could anyone provide a detailed explanation or proof showing that applying BFS to a tree will indeed result in a valid bipartition? Any insights or resources would be greatly appreciated.

# Answer
> 1 votes
Let $r$ be an arbitrary root.

Denote by $d(v)$ the distance from $r$ to $v$. As you might know, every edge goes either between vertices of the same layer, ie, vertices of same $d(v)$, or between vertices in consecutive layers.

Now, there cannot be an edge going from one vertex in layer $\ell$ to another vertex in layer $\ell$ because then we would have a cycle of length $2\ell+1$, hence every edge goes between consecutive layers.

Let $L$ be the set of vertices with even $d(v)$ and $R$ the ones with odd $d(v)$.

It follows that there are no edges inside neither $L$ nor $R$.

---
Tags: graphs, trees, graph-traversal, breadth-first-search
---


title: What does $o_n(1)$ mean?

text:
# Question
Title: What does $o_n(1)$ mean?
I'm trying to read the following article, and in the abstract they write: Let $\xi$ be a non-constant real-valued random variable with finite support, and let $M\_n(\xi)$ denote a $n\times n$ random matrix with entries that are independent copies of $\xi$. For $\xi$ which is not uniform on its support, we show that: $Pr\[M\_n(\xi) \text{ is singular}\] = Pr\[\text{zero row or column}\]+ (1+o\_n(1))Pr\[\text{two equal (up to sign) rows or columns}\]$.

What does $o\_n(1)$ mean here?

# Answer
> 3 votes
As I understand it, this $o\_n(1)$ is meant as the standard “little o” notation (when $v\_n$ takes non-zero values, $u\_n = o(v\_n)$ means $\frac{u\_n}{v\_n} → 0$), except that because several variables are involved ($n$, $ξ$, $p$), they added the $n$ subscript to clarify that the limit is as $n$ goes to infinity, for fixed values of the other variables. A perhaps more standard notation for what they write as $$x = o\_n(y)$$ would be $$x \underset{n→+∞}{=} o(y)$$

# Answer
> 0 votes
Given functions $f(n)$ and $G(n)$, from $\[0,\infty)\rightarrow \[0,\infty) $ we can define

| Operands | Meaning |
| --- | --- |
| $f(n) = O\_n(G(n))$ | $\displaystyle \lim\_{n\rightarrow \infty} \inf \frac{G(n)}{f(n)} \> 0$ |
| $f(n) = o\_n(G(n))$ | $\displaystyle \lim\_{n\rightarrow \infty} \frac{G(n)}{f(n)} = 0$ |
| $f(n) = \Theta\_n(G(n))$ | $f(n) = O(G(n)) \\;\\&\\; G(n) = O(f(n))$ |
| $f(n) \sim\_{n} G(n)$ | $\displaystyle \lim\_{n\rightarrow \infty} \frac{G(n)}{f(n)} = 1$ |

---
Tags: complexity-theory, asymptotics, notation
---


# Question
Title: When is a variable bound or free in a lambda application?
I am currently reading the book "An Introduction to Functional Programming through Lambda Calculus" (the 2011 edition) and am a bit puzzled by the definitions of free and bound variables with regards to function application.

The book states, in section 2.10, that a variable is **bound** in an expression if

1. the expression is an application $(\langle function \rangle \langle argument \rangle)$ and the variable is bound in $ \langle function \rangle$ OR $\langle argument \rangle$, or
2. the expression is a function $\lambda \langle name \rangle. \langle body \rangle $ and the variable is named $\langle name \rangle$ or bound in $\langle body \rangle$.

Next, it states that a variable is **free** in an expression if

1. The expression is a single name and the variable has that name, or
2. the expression is an application $(\langle function \rangle \langle argument \rangle)$ and the variable is free in $\langle function \rangle$ OR $\langle argument \rangle$, or
3. the expression is a function $\lambda \langle name \rangle.\langle body \rangle$ and the variable is not named $\langle name \rangle$ and is free in $\langle body \rangle$.

What confuses me is the use of "or" in the definitions of both bound and free variables in applications. I figured that if a variable is **not** bound, it must be free, and if a variable is **not** free, it must be bound. So I would expect that if a variable is free, the point 1 in the definition of bound above is inverted, so with boolean logic $\neg(A \lor B)$ should become $\neg A \land \neg B$.

However, the book doesn't state that a variable is free if it is free in $\langle function \rangle$ AND $\langle argument \rangle$.

I checked Wikipedia for another reference and it states:

> The set of free variables of a lambda expression, M, is denoted as FV(M) and is defined by recursion on the structure of the terms, as follows:
>
> 1. $FV(x) = \\{x\\}$, where $x$ is a variable
> 2. $FV(\lambda x.M) = FV(M) \setminus \\{x\\}$
> 3. $FV(M N) = FV(M) \cup FV(N)$

So the set of bound variables in (M N) should be the complement of $FV(M) \cup FV(N)$ which I believe would be $FV(M)' \cap FV(N)'$ where ' denotes the complement.

The book repeats this definition later in a summary of the chapter, so I'm hesitant to think it would be a typo. I'm thinking that either I'm

* wrong in assuming that bound and free are full complements or
* wrong in thinking that a variable with the same name in the function and argument expressions of an application is the same variable.

What is the correct interpretation here? As an example, in the application expression $(\lambda x.x\ \ \lambda y.x)$, is $x$ bound or free, or is it senseless to speak of "x" outside of the scope of either the function or argument expressions?

# Answer
> wrong in assuming that bound and free are full complements

Yes. Each *occurrence* of a variable is either bound or free, but not both. But a variable is considered free if it has any free occurrences, and it's bound if it has any bound occurrences; it can be both at once.
> 4 votes

# Answer
A variable $x$ in a λ-term is bound, wherever it is contained, as a subterm, of any λ-term of the form $λx·(⋯)$, otherwise it is free. If it is bound, then it is bound to the $λx$ of the smallest such term it is contained in. If the smallest such term be written as $λx·T$, then (by definition) that particular occurrence of the variable will be free in the λ-term $T$. Thus, the variable $x$ is bound in $λx·(λx·yx)y$, and it is bound to the $λx$ of the subterm $λx·yx$, and is free in the term $yx$. It is not bound to the $λx$ of the larger subterm $λx·(λx·yx)y$, though it is - overall - bound in that term (to the innermost $λx$), nor (therefore) is it free in $(λx·yx)y$.
> 0 votes

---
Tags: lambda-calculus, variable-binding
---


# Question
Title: how to solve this lambda expression with free variable/s
Iam a beginner in Lambda Calculus, I have a expression saying

(λx.xy)

Here **y** is a free variable and **x** is a bound variable. My question is what would be the value of the expression (which has free variables).

# Answer
> 2 votes
The term $\lambda x . x y$ is in normal form. It does not reduce any further.

In general, to find out these things, you can just type them into a $\lambda$-calculus calculator. One is available in my PL zoo (hmm, it is momentarily under construction):

```
lambda @ programming languages zoo
Type Ctrl-D to exit or "#help;" for help.
# #constant y ;
y is a constant.
# ^ x . x y ;
    = λ x . x y

```

The language wants you to declare free variables as constants, which is why we first explain that `y` is a known constant.

# Answer
> 1 votes
You're asking what the value of $λx·xy$ as if the expression, itself, were a math problem to somehow be solved. The situation is similar to asking what the value of "4/3" is, as if it were to be treated as the math problem of "divide 4 by 3". However, there's nothing in this that excludes the expression "4/3", itself, from being the final answer to the question, though the kind of thing you have in mind is more akin to answering the question with "1.333⋯". So long as you're able to do reductions like "8/6 = 4/3" or "4/1 = 4", then you're fine just using the fraction notation as a final answer. Similarly, you can go $λx·(λz·z)xy = λx·xy$ and then treat the latter as "fully reduced" or go $λx·yx = y$.

If you want an answer more like $1.333⋯$, thinking of $λx·(⋯)$ as analogous to $(⋯)/x$ \- which indeed it is - then in addition to such rules as $(yx)/x = y$ (the η-rule), you'd want ways to crunch other $(⋯)/x$'s.

So, make a distinction between terms, like $a$ and $b$ that contain no $x$'s in them, versus terms like $u$ and $v$ that do contain $x$'s in them, but where $u ≠ x$ and $v ≠ x$. Then, treating $λx·(⋯)$ as just a fancy way of writing $(⋯)/x$, write the following: $$ x/x = I,\quad a/x = Ka,\quad (xx)/x = D,\\ (ax)/x = a,\quad (au)/x = Ba(u/x),\quad (xb)/x = Tb,\quad (vb)/x = C(v/x)b,\\ (ux)/x = W(u/x),\quad (vx)/x = U(v/x),\quad (uv)/x = S(u/x)(v/x). $$ Impose the following as axioms $$ Ix = x,\quad Kxy = x,\quad Dx = xx,\\ Bxyz = x(yz),\quad Txy = yx,\quad Cxyz = xzy,\\ Wxy = xyy,\quad Uxy = y(xy),\quad Sxyz = xz(yz), $$ as well as the axiom $A = (Ax)/x$ for any λ-term $A$. Then you can solve your problem by saying that $yx/x = Ty$, or in λ-term notation: $λx·yx = Ty$.

Internal consistency of the scheme is ensured, for instance, in that $$(xzy)/z = C((xz)/z)y = Cxy = (Cxyz)/z,$$ with similar results for the other cases. The extra axiom $A = (Ax)/x$ makes further reductions possible, such as $$ S(Ka)x = (S(Ka)xy)/y = (Kay(xy))/y = (a(xy))/y = Ba((xy)/y) = Bax,\\ S(Ka) = (S(Ka)x)/x = (Bax)/x = Ba,\\ BaI = (BaIx)/x = (a(Ix))/x = (ax)/x = a,\\ BIa = (BIax)/x = (I(ax))/x = (ax)/x = a,\\ B(Bab)cx = Bab(cx) = a(b(cx)),\\ (a(b(cx)))/x = Ba((b(cx))/x) = Ba(Bb((cx)/x))) = Ba(Bbc),\\ B(Bab)c = (B(Bab)cx)/x = (a(b(cx)))/x = Ba(Bbc),\\ S(Ka)(Kb) = (S(Ka)(Kb)x)/x = (Kax(Kbx))/x = (ab)/x = K(ab),\\ SKa = (SKax)/x = (Kx(ax)/x = x/x = I,\\ SK = (SKx)/x = I/x = KI. $$ where neither $x$ nor $y$ occur in any of the terms $a$, $b$ and $c$.

---
Tags: lambda-calculus, discrete-mathematics
---


# Question
Title: How to find smallest n so that all walks of length greater or equal to n include set of paths
If we have a finite (directed) graph G, and a set of walks P in G. And assume that there exists an n so that all walks of lengths greater than n have at least one p in P as subpath, how would we find n? Does anyone know a polynomial time algorithm in |G|?

For example if we have the graph

1 -\> 2 -\> 3 -\> 4

and P = {(2,3)}

n=2, because we have paths of length 1 that don't include (2,3) as subpath, but all paths of length 2 or 3 include the path/edge (2,3).

(also, to be clear, the graph might or might not have cycles, its allowed to have multiple edges and self-loops. When we talk about subpaths (subwalks) p has to appear contiguously. Like if we consider p as a ordered set of edges (u,v...,w), where each edge ends where the next one starts, a subpath (walk) of p is a substring of that ordered list)

# Answer
Current problem is $\mathrm{NP}$-hard, because directed Hamiltonian path problem can be reduced to the current one. (Taking the same graph with empty set of forbidden paths, or adding some new arcs and making each of them a forbidden path. Hamiltonian path exists if and only if the answer is at least $|G|$.)

On the other hand there are some polynomially solvable cases of the directed Hamiltonian path problem, like acyclic graphs. However it gives only a pseudopolynomial solution for the current problem, if the number of paths is limited by a constant. (Though paths of length $1$ may be not counted here, since each such a forbidden path is equivalent to a removed edge.)
> 1 votes

---
Tags: graphs
---


# Question
Title: What is special about a canonical representation of Boolean functions?
My textbook (Saurabh's *Introduction to VLSI Design Flow*) mentions while discussing formal verification that a representation of a Boolean function is said to be canonical if the following holds:

> If a representation is canonical, then the two functionally equivalent functions are represented identically. Conversely, if a representation is canonical and if two functions have the same representation, they are functionally equivalent.

In short, he seems to be saying that a representation is canonical if there is a bijection between the set of Boolean functions (say, of $n$ Boolean variables) and the strings in the given representation.

My question is about what is unique about such representations: I would imagine that any (even noncanonical) representations of Boolean functions have the property that two functions with the same representation are functionally equivalent, so is it just the other (first) direction which is unique to (i.e. *defines*) canonical representations?

Any other sources on this notion of canonicity would also be greatly appreciated.

# Answer
Yes. Two functions with the same representation will be functionally equivalent. The question is whether there can exist a function with two different representations (i.e., two different representations but they are functionally equivalent).

Consider $(x \lor x \lor x)$ vs $(x \lor x)$. Those are two different representations, but they are functionally equivalent. Therefore, CNF is not a canonical representation of a Boolean function.
> 4 votes

---
Tags: boolean-algebra, formal-methods
---


# Question
Title: How are PCFGs used in programming language design?
I've been reading the wikipedia article about probabilistic context-free grammars (PCFGs), and they state that

> PCFGs have application in areas as diverse as natural language processing to the study the structure of RNA molecules and **design of programming languages**.

but I'm having a hard time finding examples of their usage in programming language design. So my question is this, what are the uses of PCFGs in programming language design?

Any examples or references would be greatly appreciated, thanks in advance :\]

# Answer
> 1 votes
I am not aware of applications in programming language design, and I am a bit skeptical. However, PCFGs *are* useful for generating test cases, for program testing.

---
Tags: formal-grammars, programming-languages
---


# Question
Title: What is the computational complexity of the following problem
Given any number $N$ find a positive integer $k$ such that: $N + 12 k$ is a square.

And the second case when we add an additional constraint that $k$ must be as small as possible.

# Answer
What’s the solution for N = 12m + 2, 3, 5, 6, 7, 8, 10, 11?

You can prove that no solution exists or find a solution in O(log N). You can find the smallest solution in O(log N log log N) or more precisely in the time it takes to multiply numbers of log N digits.
> 1 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: Should upcoming computer scientists be worried about the rising competition in the field?
I am a high school student who is very interested in computer science and has been studying it since middle school. I've heard a lot of news about the rise in computer science majors in college and how that affects school acceptance rates. Should I be worried about this and how it'll affect my college application experience or is it not a big deal? If I should be worried about this, how do I separate myself from others and raise my odds of being picked?

# Answer
If you want to maximize your chances of admission, I suggest that you:

* Take the maximum number of computer science classes that you can.
* Take the maximum number of math classes you can. Take the most advanced math classes you can. For instance, if you have a chance to take AP calculus, do that.

Obviously, get as good grades in these classes as possible.

It's possible that it might also help to take as many science classes as possible (e.g., physics, etc).

And, of course, follow all the standard advice for how to do well in high school and maximize your chances for admission into college.

Important caveat: Admissions criteria vary by school, and generally are not public, so it's hard to know for sure what is best to do to raise your odds of admissions.
> 2 votes

---
Tags: education
---


# Question
Title: Proving a function of asymptotic Notation
I need help with this question. If it’s possible to do this without limits, please show. Thanks.

Q: If f(n) is Ω(n) and g(n) is O(n), then prove or disprove the following statement: f(n) is O(n)

# Answer
> 1 votes
Suppose $f(n) = n^2$. Clearly, we have $f(n) \in \Omega(n)$ but $f(n) \notin O(n)$. It does not require the information given for $g(n)$.

Had the quotation been to prove/disprove $f(n) \in O(g(n))$, we could proceed as follows:

Take $f(n) = n^2$ as before, along with $g(n) = \log n$. This satisfies the required criteria that $f(n) \in \Omega(n)$ and $g(n) \in O(n)$. Now clearly, $n^2 \> \log n ~~ \forall n \ge 2$. Thus, we have a case where $f(n) \notin O(g(n))$.

---
Tags: algorithm-analysis, asymptotics, functional-programming
---


# Question
Title: Distinct edge weights assumption in second best MST algorithms only replacing an edge in MST
In a CP-algorithms wiki *Second Best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor*:

> Let $T$ be the Minimum Spanning Tree of a graph $G$ . It can be observed, that the second best Minimum Spanning Tree differs from $T$ by one edge replacement. (For a proof of this statement refer to CLRS (3rd ed.) problem 23-1 here).
>
> So we need to find an edge $e\_{new}$ which is in not in $T$ , and replace it with an edge in $T$ (let it be $e\_{old}$ ) such that the new graph $T' = (T \cup \\{e\_{new}\\}) \setminus \\{e\_{old}\\}$ is a spanning tree and the weight difference ( $e\_{new} - e\_{old}$ ) is minimum.

It is questionable that the algorithms hinge on the lemma that *the* second best Minimum Spanning Tree differs from *the* Minimum Spanning Tree by one edge replacement. The word *the* in a Minimum Spanning Tree context is commonly understood to imply that it is unique but the algorithms supposedly work for all graphs.

In the problem *23-1 Second-best minimum spanning tree* and the proof being cited above:

> Let $G = (V, E)$ be an undirected, connected graph whose weight function is $w : E \rightarrow \mathbb{R}$, and suppose that $\lvert E\rvert \geq \lvert V\rvert$ and all edge weights are distinct.
>
> Let $T$ be the minimum spanning tree of $G$. Prove that $G$ contains some edge $(u, v) \in T$ and some edge $(x, y) \notin T$ such that $T - \\{(u, v)\\} \cup \\{(x, y)\\} $ is a second-best minimum spanning tree of $G$.
>
> **Proof** (sketch). Let $T$ be an MST and $T'$ be a second-best MST. Suppose for contradiction, there are two edges in $T - T'$, and let $e$ be an edge in $T - T'$ with minimum weight. If we add $e$ to $T'$, we get a cycle $c$, which contains an edge $e'$ in $T' - T$.
>
> We claim that $w(e') \> w(e)$. We prove this by contradiction, assume $w(e') \< w(e)$. If we add $e'$ to $T$, we get a cycle $c'$, which contains an edge $e''$ in $T - T'$. Therefore, $T'' = T - e'' + e'$ forms an ST, and we must also have $w(e'') \< w(e')$, since otherwise $w(T'') \< w(T)$. Thus, $w(e'') \< w(e') \< w(e)$ contradicts $e$ being an edge with minimum weight in $T - T'$.
>
> Since $e$ and $e'$ would be on a common cycle if we add $e$ to $T'$, $T'' = T' - e' + e$ forms an ST which differs from $T$ by only one edge, and we have $w(T'') \< w(T')$. Hence, $T''$ is a second-best MST.

The skepticism is warranted as it turns out that both the problem and the proof rests on the assumption of distinct edge weights which is a sufficient condition for the uniqueness of Minimum Spanning Tree.

There is an added problem that every other proof on the internet is all related to this CLRS (3rd ed.) problem 23-1 that assumes distinct edge weights, and the topic of second best Minimum Spanning Tree has never even been asked on this site.

Is it possible to prove this without distinct edge weights assumption? Is there another proof without distinct edge weights assumption? Is it possible to modify the above proof to work without distinct edge weights assumption?

It should be noted that it is only possible to extend the proof by defining a second best minimum spanning tree as a spanning tree different from a given minimum spanning tree with the least weight. It is used in an onlinejudge practical problem of finding two cheapest MST to choose from.

# Answer
> 0 votes
The proof provided may be modified to work without distinct edge weights assumption:

> **Proof** (sketch). Let $T$ be an MST and $T'$ be a second-best MST. Suppose for contradiction, there are two edges in $T - T'$, and let $e$ be an edge in $T - T'$ with minimum weight. If we add $e$ to $T'$, we get a cycle $c$, which contains an edge $e'$ in $T' - T$.
>
> We claim that $w(e') ≥ w(e)$. We prove this by contradiction, assume $w(e') \< w(e)$. If we add $e'$ to $T$, we get a cycle $c'$, which contains an edge $e''$ in $T - T'$. Therefore, $T'' = T - e'' + e'$ forms an ST, and we must also have $w(e'') ≤ w(e')$, since otherwise $w(T'') \< w(T)$. Thus, $w(e'') ≤ w(e') \< w(e)$ contradicts $e$ being an edge with minimum weight in $T - T'$.
>
> Since $e$ and $e'$ would be on a common cycle if we add $e$ to $T'$, $T'' = T' - e' + e$ forms an ST which differs from $T$ by only one edge, and we have $w(T'') ≤ w(T')$. Hence, $T''$ is a second-best MST.

Therefore, second-best MST algorithms are optimal without distinct edge weights assumption.

# Answer
> 0 votes
There is a proof on the internet without distinct edge weights assumption found in this document from flashmt's comment in codeforces. It is the equivalent of the proof provided, only written more tersely:

> Given connected graph $G = (V, E)$ where $\lvert E \rvert \geq \lvert V \rvert$. There exists an edge $(x, y) \in$ MST and an edge $(u, v) \notin$ MST such that we can obtain second-best MST by replacing $(x, y)$ with $(u, v)$ in MST.
>
> **Proof**: Let $T$ be an MST and $T'$ be a second-best MST. Let $(x, y)$ be an arbitrary edge $\in T - T'$. Hence, $T' + (x, y)$ contains a cycle and one edge in this cycle is not in $T$. Let this edge be $(u, v)$. We have $w(x, y) \leq w(u, v)$ (otherwise $T - (x, y) + (u, v)$ would be a better MST than $T$).
>
> * If $w(x, y) = w(u, v)$, $T - (x, y) + (u, v)$ will be the second-best MST with same cost as MST.
> * If $w(x, y) \< w(u, v)$, let $T'' = T' - (u, v) + (x, y)$, hence $T'' \< T'$, thus $T'' = T$ since only MST $\<$ second-best MST, ergo $T - (x, y) + (u, v)$ will be the second-best MST.

In addition to the Kruskal and Lower Common Ancestor approaches provided, the document provides the Disjoint Set approach yielding equivalent time complexity between second-best MST and MST.

---
Tags: graphs, proof-techniques, weighted-graphs, minimum-spanning-tree, spanning-trees
---


# Question
Title: How to find largest caterpillar in a tree
A caterpillar is a subgraph which consists of a path with at most four leaves (legs) attached to each node (but a node can also have no leaves). This is not the same as finding the longest path, because we measure the number of vertices (including the legs), not the length. Find an algorithm with time complexity of O(n).

# Answer
Hint: the heaviest caterpillar that can be formed by a path starting at a node and moving strictly downward in the tree (its down-weight) is

* the down-weight of the heaviest non-leaf child if it exists, plus
* the number of leaves attached to this node capped at 4, plus
* 1 for the node itself.

Then the heaviest caterpillar *going through* a node at its highest point is

* the down-weight of the heaviest non-leaf child if it exists, plus
* the down-weight of the second heaviest non-leaf child if it exists, plus
* the number of leaves attached to this node capped at 4, plus
* 1 for the node itself.

You can compute both properties inductively using any tree traversal that visits a nodes' children before itself, and get the global maximum by finding the heaviest weight going through any node in the tree.
> 1 votes

---
Tags: algorithms, graphs, trees, search-algorithms, graph-traversal
---


# Question
Title: What does this mean: "The compile-time and load-time address-binding methods generate identical logical and physical addresses"?
I read this in my Operating System textbook. Does it mean that the logical addresses generated by compile-time binding scheme are the same as the logical addresses generated by load-time binding? Or does it mean that the logical addresses and the physical addresses generated are the same in both compile-time binding as well as load-time binding?

If the first interpretation is correct, then how is it possible to generate same logical addresses in both compile-time and load-time? AFAIK in compile-time binding, we already have a fixed location in the memory where we'll load our program, so we can generate absolute addresses. But in load-time scheme, we do not know where the program will be loaded in memory. So we put relative addresses. How can absolute and relative addresses be the same?

# Answer
> 3 votes
What your TB says is absolutely correct & the answer is the latter i.e. the second interpretation.

More particularly:

* The logical address & the physical address generated in the compile-time address binding scheme are the same.
* The logical address & the physical address generated in the load-time address binding scheme are the same.

Why?

Context:

> Definition of Logical address: A logical address or virtual address is an address that is generated by the CPU during program execution. - afteracademy

> Definition of Physical address: physical address refers to a memory address or the location of a memory cell in the main memory - Techopedia

The compile-time binding is used when the base address of the process memory allocation is known before hand i.e. " *a priori* ". This never happens in real-life because you never know any mechanism/system to predict what the addresses will be at the time of writing the program itself.

However, in case that really happens (How? Static allocation / *magic*), the address generated by compiler (i.e. the logical address/virtual address) is indeed the actual physical address because the programmer hard-coded the addresses.

Similar (but not *same*) is the case with Load-time binding.

# Answer
> 0 votes
Silberschatz defined "logical address" as the address leaving the CPU. In this case, the address leaving the CPU is the same as the address sent to memory. But in execution-time binding, the addresses may differ.

---
Tags: operating-systems, virtual-memory
---


# Question
Title: Given a $n \times n$ matrix $M$ find a subset of d rows and d columns so that the sum of the elements in their intersection in maximized
Given a $n \times n$ matrix $M$ of positive integers and a constant $d$. If $R,C \subset \\{1,...,n\\} $ let $$S\_M(R,C) = \sum\_{r \in R,c \in C }M\_{i,j} $$

I want to find the sets $$R,C \subset \\{1,...,n\\}, |R|,|C| = d $$ such that $S\_M(R,C)$ is as big as possible.

I suspect this to be a known problem. I am wondering if anyone has seen this before and can point me towards research papers on this problem

# Answer
It is NP-hard, by reduction from the maximum balanced biclique problem.

Suppose you have a bipartite graph $G$, and the goal is to test whether there is a balanced biclique of size $d$. Let $M$ denote the adjacency matrix of $G$. Then there is a balanced biclique of size $d$ iff the maximum sum in your problem is $d^2$. Therefore, any algorithm for your problem would immediately yield an algorithm for the maximum balanced biclique problem.

In practice, one approach is try to solve it with integer linear programming or with a SAT solver.
> 1 votes

---
Tags: algorithms, dynamic-programming, matrices
---


# Question
Title: What is the set FirstHalves B? You can simply write out the set explicitly, enumerating the first four values
For any set of strings A, define the set FirstHalves A = {x∣∃y such that len(y) = len(x) and xy in A }. For example, FirstHalves {01, 111, 1010, 001101, 1011} = {0, 10, 001}, ie the first halves of the even length strings.

Let B = {01, 011, 0111, 01111, 011111, ...}. What is the set FirstHalves B? You can simply write out the set explicitly, enumerating the first four values.

* I tackled this question at first thinking that it is all even length strings and their first halves. So my first answer was {0, 01, 011, 0111, ....}

However, after having this checked the right answer is {0, 01, 0111, 01111}. Can someone help me understand why?

# Answer
> 1 votes
Your first answer appears to be correct. I think the other source is wrong. In particular, 011 is in FirstHalves B because 011111 is in B.

---
Tags: complexity-theory, finite-automata
---