# Question
Title: If L is regular, show that even(L) is also regular
I am stuck on the following question.

> If $L$ is regular show that $\text{even}(L)$ is also regular. Here $\text{even}(L) = \\{ \text{even}(w) : w \in L \\}$, $\text{even}(w)$ is the string obtained by extracting from $w$ the letters in even numbered positions. For example, if $L=\\{0, 01, 02, 0202, 12120\\}$, then $\text{even}(L)=\\{\epsilon, 1, 2, 22\\}$.

How can I prove that $\text{even}(L)$ is also regular?

# Answer
We can also solve this question using closure operations. Let $\Sigma$ be the original alphabet, and let $\Sigma' = \\{x' : x \in \Sigma\\}$ be a second copy of the alphabet. Define two homomorphisms $h$ and $d$ by $h(x) = h(x') = x$ for all $x \in \Sigma$ and $d(x) = x$, $d(x') = \epsilon$ for all $x \in \Sigma$. Then $$ \operatorname{even}(L) = d(h^{-1}(L) \cap (\Sigma'\Sigma)^\*(\epsilon+\Sigma')). $$
> 7 votes

# Answer
1) Since $L$ is regular we can build a DFA $M = (Q,\Sigma,\delta,q\_0,F)$ accepting it.

2) Next we build a DFA $C = (\\{c\_0,c\_1\\},\Sigma,\delta\_c,c\_0,\\{c\_0\\})$ that accepts all strings of even length -- it will help us "count". I'll let you figure out $\delta\_c$.

3) Make a product $\epsilon$-DFA $P = (Q\_p,\Sigma,\delta\_p,(q\_0,c\_0),F\_p)$ from $M$ and $C$, where

$$Q\_p = Q \times \\{c\_0,c\_1\\}$$

Accepting states are just all state pairs, with an accepting state from the original DFA $M$: $$ F\_p = \\{(q\_i,c\_j) \mid (q\_i,c\_j) \in Q\_p \wedge ~q\_i \in F \\} $$ And the transition function looks like this:

* all transitions from the "even" state pairs $(q\_i,c\_0)$ are replaced by $\epsilon$-transitions: $$ \begin{array}{ll} \delta\_p((q, c\_0),~a) = \emptyset,~\forall a \in \Sigma,~\forall q \in Q\\ \delta\_p((q, c\_0),~\epsilon) = \\{(\delta(q,a),~c\_1) \mid a \in \Sigma\\},~\forall q \in Q \end{array} $$
* all transitions from the "odd" state pairs $(q\_i,c\_1)$ mimic the original DFA $M$ (or more precisely, unmodified product automaton): \begin{array}{ll} \delta\_p((q, c\_1),~a) = \\{(\delta(q,a),~c\_0)\\},~\forall a \in \Sigma,~\forall q \in Q \\ \delta\_p((q, c\_1),~\epsilon) = \emptyset,~\forall q \in Q \end{array}

Intuitively, the $\epsilon$-NFA $P$ works as follows: it guesses (or skips) all the odd-numbered symbols in the input string.

We have got an $\epsilon$-NFA accepting even(L), thus even(L) is regular.

**Example**. Let our original automaton be a DFA which accepts the same language L as the regular expression $(001)^\*$ (dead states are not shown):

Here is our product $\epsilon$-NFA accepting even(L):
> 5 votes

# Answer
Let $(Q,\Sigma,\delta,q\_0,F)$ be a DFA for $L$. Define a NFA with ε-moves $$D=(Q \times \\{0,1\\} , \Sigma, \delta', (q\_0, 0), F\times \\{0,1\\})$$ where the transitions (not into the empty set) are:

* $\delta'((q,0),\epsilon) = \\{ (\delta(q,\sigma),1) \mid \sigma \in \Sigma\\}$.
* $\delta'((q,1),\sigma) = \\{ (\delta(q,\sigma),0)\\}$.

It is immediate that $\sigma\_1\sigma\_2\cdots\sigma\_k$ is accepted by $D$ if and only if there are $\mu\_1, \mu\_2, \cdots, \mu\_k\in \Sigma$ and $\mu\_{k+1}\in\\{\epsilon\\}\cup\Sigma$ such that $\mu\_1\sigma\_1\mu\_2\sigma\_2\cdots\mu\_k\sigma\_k\mu\_{k+1}\in L$.

(The above straightforward construction is easier for me to understand. If you find this answer too brief, you may want to look at Anton's answer for more details and explanations.)
> 1 votes

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


# Question
Title: Can I say the two cases of Recursion Tree are always either $\theta{(n)}$ or $\theta({n\log{n}})$
Given positive constants: $c\_1, c\_2, ..., c\_k, c^\prime$, assume that
$T(n) = T(c\_1n) + T(c\_2n) + ...+ T(c\_kn) + c^\prime n$

There are two cases:

1. $c\_1 + c\_2 + ...+ c\_k \< 1$
2. $c\_1 + c\_2 + ...+ c\_k = 1$

As I observed (from some problems), in case 1 $T(n) = \theta{(n)}$, in case 2 $T(n) = \theta{(n\log{n})}$ But I didn't find the theory says this always true, so I'm wondering, generally is this true or a theorem or is there any counterexample?

---

For example, of Case 1 : $T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + T(\frac{n}{8}) + n = \theta{(n)}$
and of Case 2 : $T(n) = T(\frac{n}{3}) + T(\frac{2n}{3}) + n = \theta{(n\log{n})}$

# Answer
Your observation is correct. More specifically, we have the following proposition.

(**Asymptotic behavior of a kind of linear recurrence**) Suppose $T(n)\ge0$ is defined for all $n$ greater than some constant. $$T(n) = T(c\_1n+h\_1(x)) + T(c\_2n+h\_2(n)) + ...+ T(c\_kn+h\_k(n)) + c n$$ where $c\_1, c\_2, ..., c\_k, c$ are positive constants smaller than 1 and $h\_1, h\_2, ..., h\_k$ are functions bounded by a constant. There are three cases.

* If $c\_1 + c\_2 + ...+ c\_k \< 1$, then $T(n) = \Theta({n})$.
* If $c\_1 + c\_2 + ...+ c\_k = 1$, then $T(n) = \Theta(n\log n)$.
* If $c\_1 + c\_2 + ...+ c\_k \> 1$, then $T(n) = \Theta(n^p)$, where $p$ satisfies $\sum\_{1 \le i \le k} {c\_i}^{p} = 1$.

Note that $h\_i(n)$ represents a small perturbation in the index of $T$. Since $\lfloor c\_{i}x\rfloor =c\_{i}x+(\lfloor c\_{i}x\rfloor -c\_{i}x)$ and that the absolute value of $\lfloor c\_{i}x\rfloor -c\_{i}x$ is always between 0 and 1, $h\_{i}(n)$ can be used to ignore the floor function in the index. Similarly, one can also ignore the ceiling function. For example, $T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lfloor\frac{n}{4}\rfloor) + T(\lceil\frac{n}{8}\rceil) + n$ and $T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + T(\frac{n}{8}) + n$ will have the same asymptotic behavior. Because of this same asymptotic behavior, recurrence relations might be written sloppily from time to time when only their asymptotic behavior are the only concern, such as possibly the case of the current question.

The above proposition is just a special case of the more general situation handled by the Akra-Bazzi method, also explained here.

The question has provided examples for the first two cases of the proposition.

Here is an example of the third case. Let $$T(n)= T(\lfloor\frac12n\rfloor) + T(\lfloor\frac23n\rfloor) + T(\lfloor\frac56n\rfloor)+2019n$$ and $T(1)=0$. Since $(\frac12)^3+(\frac23)^3+(\frac56)^3=1$, we conclude that $T(n)=\Theta(n^3)$.

---

Exercise. How about $T(1)=1$ and $T(n)= T(\lceil\frac27n\rceil) + T(\lceil\frac37n\rceil) + T(\lceil\frac67n\rceil)+2018n$?
> 3 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Fitting a regular grammar to strings from a PCFG: how big does it get?
Let $G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $u\_1, \ldots, u\_n$ a set of $n$ strings generated by $G$.

For finite $n$, it is always possible to find a regular grammar $\hat G=(\hat V, \Sigma, \hat R, S)$ which generates the strings $u\_1, \ldots, u\_n$.

Intuitively, as $n$ goes to infinity, we expect $\hat G$ to get larger: my guess is that the cardinal of $\hat R$ (and maybe also the cardinal of $\hat V$?) would need to go to infinity.

Are there results which formalize this, e.g. by giving a lower bound on these cardinals as a function of $n$?

# Answer
The question, if understood in the simplest naive way, might be uninteresting.

Here is a simple example. Let $G$ be the regular language $\\{a^n\mid n\ge0\\}$ over the alphabet $\\{a\\}$. Consider the strings $\epsilon, a, a^2, \cdots, a^n$ in $G$. What are the regular languages that contains those strings?

* The minimal such language, i.e., which contains no other strings, will need $n+1$ generation rules $S\to a^i$ for $0\le i\le n$.
* The language with the least generation rules is $G$ itself, which has two generations rules $S\to \epsilon$ and $S\to aS$.

---

However, once we start to twiddle with the ways how to approximate context-free grammar by regular grammar, there are tons of research.

Here is a related question that links to many related stuff, Is there a known method for constructing a grammar given a finite set of finite strings?.

This paper considers approximating CFG from above by a regular grammar.

You can browse the google search result for approximate context-free grammar by regular grammar or the google scholar.
> 1 votes

---
Tags: regular-languages, context-free
---


title: Halting problem with extra input

text:
# Question
Title: Halting problem with extra input
Can there be a function `HALT(f, y)` so that:

* There are some `x` such that `f(x)` halts iff there are some `y` such that `HALT(f, y)` return true;
* There are some `x` such that `f(x)` doesn't halt iff there are some `y` such that `HALT(f, y)` return false;
* `HALT` always halt and return a boolean

? It makes lots of old conflict don't work. E.g. If `f(x)` loops forever when `HALT(f, x)` is true, `HALT` may return true for half of `x`.

# Answer
I assume you mean "Turing machine" by "function", otherwise it is meaningless to say a function halts on some input.

Suppose $\mathrm{HALT}$ exists, then we construct a Turing machine $H$ as follows:

On input $\langle M, w\rangle$ where $M$ is an (encoding of) Turing machine:

1. Construct a Turing machine $N\_{\langle M, w\rangle}$ with input $x$ as follows: run $M$ on $x$ and return what $M$ returns.
2. Run $\mathrm{HALT}$ on $\langle N\_{\langle M, w\rangle}, 0\rangle$ and return what $\mathrm{HALT}$ returns.

Note the result of running $N\_{\langle M, w\rangle}$ has nothing to do with its input $x$. If $M$ halts on $w$, $N\_{\langle M, w\rangle}$ halts on all inputs, thus $\mathrm{HALT}( N\_{\langle M, w\rangle}, 0)$ returns true. otherwise $N\_{\langle M, w\rangle}$ halts on no input, thus $\mathrm{HALT}( N\_{\langle M, w\rangle}, 0)$ returns false.

Now we can see $M$ halts on $w$ if and only if $H$ accepts $\langle M, w\rangle$. Since $H$ always halts, $H$ is a decider for the normal halting problem, a contradiction!

So $\mathrm{HALT}$ does not exist.
> 2 votes

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


# Question
Title: Binary search in log time on a Turing Machine
I was thinking about TM (Turing Machine) as a computation model, and I came up with the following question :

Is it possible to make a TM that answers binary search (tell wether $x$ belong to a sorted array $A$) in $\log$ time ? That is, is it possible to simulate random access on a TM ?

My thoughts so far are that it is not possible, because the memory of a TM has to be accessed sequentially, e.g. in binary search, reading the element at $n/2$ in the array (first comparison for binary search) takes at least $n/2$ steps.

If it is indeed impossible, does the same hold for structures like binary trees ?

# Answer
> 0 votes
## **Can't be done.**

Assuming the TM receives its input as $\langle x, A \rangle$ (i.e., $x$ followed by $A$) and that $x$ as well as the array contents are binary encoded, then the asymptotic log-time bound ensures almost all inputs are such that the TM is *not even able to read past $x$*, let alone search the array. Even if you bound the contents of the array (i.e., a constant number of values, one value per cell), the TM can only read up to the first $\log n$ entries for a list of size $n$; searching for an $x$ strictly larger than those entries will fail.

I am not sure how you intend to represent binary trees (with pointers?). I am sure it is the same case as above.

That being said, there are models which add random access capabilities to TMs, in particular random-access TMs. You might want to look into those.

---
Tags: turing-machines, time-complexity, binary-search
---


# Question
Title: Is the language $(a^n)^mb^n$ context free?
$(a^n)^mb^n$ for $m,n\ge 1$
This can be rewritten as $a^{nm}b^n $
i.e. number of $a$'s is a multiple of number of $b$'s, or for every m $a$'s there is one $b$. I thnk this language can be accepted by NPDA. For every m $a$'s one a can be pushed into the stack, and similarly one can be popped on encountering a $b$. But the NPDA needs to try this for every possible m, where m varies from 1 to maximum string length of $a$'s.

# Answer
> 1 votes
The difficulty of trying every possible $m$ is, in fact, insurmountable. That language is not context-free.

For the sake of contradiction, assume it is context-free. Let $p$ be its pumping length. Consider the word $a^{p^2p}b^{p^2}$. I will let you take it from here.

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


# Question
Title: Why $2R\sigma\sqrt{T+logT+1}=\tilde{{O}}(\sigma\sqrt{T})$?
On page 17 on the paper Online Learning with Predictable Sequences, we find a regret of an algorithm equal to

$$ \text{Reg}\_T=\frac{R^2}{\eta}+\frac{\eta}{2}\sigma^2(T+logT+1) $$ where $T$ is the entire time, $\eta$ is learning rate, $R$ is constant, and $\sigma^2$ is the variance of data. The above using arithmetic mean-geometric mean inequality can be lower bounded by

$$ \sqrt{2}R\sigma\sqrt{T+logT+1}\leq \frac{R^2}{\eta}+\frac{\eta}{2}\sigma^2(T+logT+1) $$

why the left hand side is $\tilde{{O}}(\sigma\sqrt{T})$?

According to $\tilde{{O}}$ vs $O$, $\tilde{{O}}$ ignores logarithmic factors that means when $f(n) \in \tilde{O}(g(n))$ there exist a $k$ such that $f(n) \in O(g(n)\log^k g(n))$, now I have $f(T)=\sqrt{2}R\sigma\sqrt{T+logT+1}$, why I can write it $O(\sigma\sqrt{T}log^kT)=\tilde{O}(\sigma\sqrt{T})$? and what is my $k$?

# Answer
What is $\tilde O$? There are two different definitions.

* According to exercise 3.5 of *Introduction to Algorightms* by Corman et al., $\tilde O$ can mean $O$ with logarithmic factors ignored: $$\tilde O(g(n))= \\{f(n): \text{there exist nonnegative constant } k \\ \text{ and positive constants } c, k, \text{ and }n\_0 \text{ such that }\\ 0\le f(n)\le cg(n)(\log n)^k\text{ for all }n\ge n\_0\\}$$
* According to Wikipedia entry, $f(n) = \tilde O(g(n))$ is shorthand for $f(n) = O(g(n)\left(\log g(n)\right)^k)$ for some $k$.

For any value $x\>0$, $x^0=1$. If we take $k=0$ simply, we can see that for either definition, $$f(T)=\sqrt{2}R\sigma\sqrt{T+\log T+1}=O(\sigma \sqrt{T}) =O(\sigma \sqrt{T}\\,1)=\tilde{O}(\sigma\sqrt{T})$$

---

Here is the explanation for the second equality in the above equation.

$\log T=o(T) \Rightarrow T+\log T+1=\Theta(T) \Rightarrow \sqrt{T+\log T+1}=\Theta(\sqrt T)$

W can also proceed more rigorously, using L'Hôpital's rule once.

$$\lim\_{T\to\infty}\frac{\sqrt{T+\log T+1}}{\sqrt T} = \sqrt{\lim\_{T\to\infty}\frac{T+\log T+1}{T}} = \sqrt{\lim\_{T\to\infty}\frac{1+\frac1T}{1}}=1$$
> 1 votes

---
Tags: asymptotics
---


# Question
Title: What is the set of languages accepted by empty stack pda?
I am having a confusion. Empty stack pda will always accept episilon. Therefore a language not accepting episilon will still be accept episilon, so how can we avoid this?

# Answer
> 4 votes
When defining the semantics of PDAs accepting with an empty stack, we initialize the stack with a special "bottom-of-stack" symbol. This solves your difficulty.

The set of languages accepted by empty-stack PDAs is the context-free languages. It is exactly the same set of languages accepted by final-state PDAs. The picture changes when considering deterministic PDAs: final-state DPDA accept the deterministic context-free languages, whereas empty-stack DPDAs accept the prefix-free deterministic context-free languages.

---
Tags: automata, pushdown-automata
---


# Question
Title: Common idea in Karatsuba, Gauss and Strassen multiplication
The identities used in multiplication algorithms by

seem very closely related. Is there a common abstract framework/generalization?

# Answer
The classical framework is the one of bilinear algorithms and tensor rank decompositions; basically, you construct the 3-way tensor associated to the bilinear map $f(A,B) = A \cdot B$, in the basis of the coefficients, then look for a decomposition of it as a sum of rank-one tensors (i.e., those of the form $T\_{i,j,k} = u\_i v\_j w\_k$). You'll find this explained in more detail, for instance, in this article by Bläser, or in the book by Bürgisser, Clausen, Shokrollahi, *Algebraic Complexity Theory*.

As far as I understand, the reformulation in terms of group respresentations that Suresh mentions in his answer is a later one, and I find it less suitable for a first approach to the subject (but, of course, that might be bias on my part).
> 5 votes

# Answer
A partial answer to your question is the group-theoretic approach first developed by Cohn and Umans and further developed by Cohn, Kleinberg, Szegedy and Umans. It can "sort of" capture Strassen and Coppersmith-Winograd for matrix multiplication.
> 8 votes

---
Tags: algorithms, matrices
---


# Question
Title: Prove that every CFL is decidable in O(n) space
this question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was:

> Prove that every context free language $A$ is in $\mathrm{SPACE}(n)$. You can assume that $A$ is given in CNF (Chomsky Normal Form)

I saw CYK algorithm but it's space complexity is $O(n^2)$.

# Answer
Let $G$ be a context-free grammar in Chomsky normal form. We will show how to determine whether a nonempty word $w$ of length $n$ is accepted by $G$.

Every parse tree for $w$ is first of all a full binary tree with $n$ leaves. It is known that the number of such trees is $C\_{n-1}$. Moreover, there is a bijection with words containing $n-1$ pairs of balanced parentheses and full binary trees with $n$ leaves. We can go over all full binary trees with $n$ leaves in space $O(n)$ by going over all words of length $2(n-1)$ over the alphabet $\\{(,)\\}$, converting each of them which is balanced to a full binary tree.

For each full binary tree $T$, we consider all possible labelings of nonterminals to the vertices of the tree in which the root is labeled using the start symbol, which can be done in $O(n)$ space (here the constant depends on $G$). We check each such parse tree for validity: for each internal vertex labeled $A$ with children labeled $B,C$, we check that $A \to BC$ is a production, and for the $i$'th leaf labeled with $A\_i$, we check that $A\_i \to w\_i$ is a production. If we find a valid parse tree in this process, then $w \in L(G)$. Otherwise, $w \notin L(G)$.
> 3 votes

---
Tags: complexity-theory, context-free, parsers
---


# Question
Title: Hard connected instances for Weisfeiler-Lehman test of isomorphism
There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm.

However, one of these graphs is disconnected. So what are the instances of undirected **connected** graphs for which WL algorithm fails?

# Answer
> 7 votes
Yes, there are non-isomorphic connected graphs that cannot be distinguished by Weisfeiler–Lehman. The following construction is due to Cai, Fürer and Immerman (*An Optimal Lower Bound on the Number of Variables for Graph Identification*, *Combinatorica* 12(4):389–410, 1992; PDF).

Take any connected, $3$-regular graph $G=(V,E)$. We will produce non-isomorphic graphs $G\_\parallel$ and $G\_\times$ from $G$, that are indistinguishable by Weisfeiler–Lehman. These will be made by producing a gadget for each vertex of $G$ and, for each edge $xy\in E$, connecting the gadgets for $x$ and $y$ by a pair of parallel edges.

The vertices of $G\_\parallel$ are is defined as follows.

* For each $xy\in E$, we create four (distinct) vertices, $a\_{x,y}$, $a\_{y,x}$, $b\_{x,y}$ and $b\_{y,x}$.
* For each $x\in V$, we create a vertex $c\_{x,S}$ for each odd-cardinality subset of $\Gamma(x)$ (the neighbours of $x$ in $G$). So, if $x$'s neighbours are $u$, $v$ and $w$, we create vertices $c\_{x,\\{u\\}}$, $c\_{x,\\{v\\}}$, $c\_{x,\\{w\\}}$ and $c\_{x,\\{u,v,w\\}}$.

The edges of $G\_\parallel$ are defined as follows. For each edge $xy\in E$, we add:

* the two edges $a\_{x,y}a\_{y,x}$ and $b\_{x,y}b\_{y,x}$;
* the edges $a\_{x,y}c\_{x,S}$ for each $S$ such that $y\in S$;
* the edges $b\_{x,y}c\_{x,S}$ for each $S$ such that $y\notin S$.

Note that $G$ is undirected so if $xy\in E$, then $yx\in E$ also, and we follow the above rules twice for each edge of $G$.

Now, let $xy$ be any edge in $G$ and let $G\_{xy}$ be the graph made from $G\_\parallel$ by deleting the edges $a\_{x,y}a\_{y,x}$ and $b\_{x,y}b\_{y,x}$ and replacing them with the "cross" edges $a\_{x,y}b\_{y,x}$ and $b\_{x,y}a\_{y,x}$. The following lemma is the key point of the construction.

**Lemma 1.** For any edges $uv,xy\in E$, the graphs $G\_{uv}$ and $G\_{xy}$ are isomorphic.

*Proof sketch*. You can move the cross edge around the graph in the following sense. For any pair of edges $ij,jk\in E$, there's an isomorphism of $G\_{ij}$ that exchanges $a\_{j,i}$ and $b\_{j,i}$ and exchanges $a\_{j,k}$ and $b\_{j,k}$. This isomorphism is a permutation of the vertices $c\_{j,S}$, and it fixes every other vertex in $G\_{ij}$. If you draw the fragment of the graph corresponding to vertex $j$ and its incident edges, the isomorphism should be pretty obvious.

This means that $G\_{ij}\simeq G\_{jk}$, because the isomorphism "uncrosses" the edge $ij$ and "crosses" the edge $jk$. Since $G$ is connected, it contains a path whose first edge is $uv$ and whose last edge is $xy$, and we can use the isomorphisms corresponding to each adjacent pair of edges in this path to move the cross in $G\_{uv}$ to $xy$$\Box$

By Lemma 1, we're entitled to use the name $G\_\times$ for an arbitrary graph $G\_{xy}$. We now have the graphs $G\_\parallel$ and $G\_\times$; it remains to show that they're non-isomorphic and that they're indistinguishable to Weisfeiler–Lehman.

**Lemma 2.** For any connected, 3-regular graph $G$, we have $G\_\parallel \not\simeq G\_\times$.

*Proof sketch.* It turns out that the only isomorphisms of $G\_\parallel$ and $G\_\times$ are isomorphisms induced by isomorphisms of $G$, and isomorphisms of the form used in the proof of Lemma 1. But no such isomorphism can transform $G\_\times$ into $G\_\parallel$ because $G\_\times$ has a cross edge and $G\_\parallel$ does not. $\Box$

Now, indistinguishability. Weisfeiler–Lehman is definable in so-called "fixed-point logic with counting." This is first-order logic plus:

* counting quantifiers: for each natural number $n$, you can write $\exists^{\geq n}x\\,\varphi(x)$, meaning "There exist at least $n$ values of $x$ that satisfy $\varphi$." This can already be expressed in ordinary first-order logic, just by saying that there exist distinct $x\_1, \dots, x\_n$ that all satisfy $\varphi$, but the (rather subtle) point here is that the counting quantifier only uses just one variable, whereas the "pure" first-order expression uses $n$ distinct variables.
* inductive definitions. These let you build up a relation $R$ as follows. You start with $R=\emptyset$. Then, you add to $R$ all the tuples that satisfy a formula $\varphi$, and keep doing that until you run out of tuples to add. $\varphi$ itself can depend on $R$, so you can build up some interesting things.

In particular, you can build up an equivalence relation corresponding to the colour-classes of Weisfeiler–Lehman. The counting quantifiers let you talk about the numbe of neighbours of each colour, and the inductive definitions let you recursively refine the colouring based on the number of neighbours of each colour in the previous step.

A *separator* of a graph $G=(V,E)$ is a set $S\subseteq V$ such that no component of $G-S$ has more than $|V|/2$ vertices. In the following, I say "less than about $2k$" because I'm silently translating from fixed-point logic with counting to so-called "infinitary logic with counting", which roughly doubles the number of variables. I don't remember the exact details, and it's not important enough to hunt them down.

**Theorem 3.** Let $\varphi$ be a formula of fixed-point logic with counting, using $k$ distinct variables. If $G$ is a graph with no separator of size less than about $2k$, then $\varphi$ cannot distinguish $G\_\parallel$ from $G\_\times$.

*Proof sketch.* Very roughly speaking, while you're evaluating the formula $\varphi$ on $G\_\parallel$ or $G\_\times$, you might need to consider $k$ vertices as being the value of some variables at the current iteration of an inductive construction and $k$ more variables as being the value of the variables at the previous iteration. The fact that $G$ has no small separators means that, even if we fix those vertices, we can still move the cross around in a large component of the rest of the graph, without the formula "knowing" that we've done that, so the formula can never "see" the cross, so it can never tell the difference between the graph with the cross and the graph without it. $\Box$

For any fixed $d$, $d$-dimensional Weisfeiler–Lehman can be expressed as a formula of fixed-point logic with counting, using some number $k$ of variables ($k\approx 2d$ is enough, as I recall). Since that formula can't tell the difference between the non-isomorphic graphs $G\_\parallel$ and $G\_\times$ as long as $G$ has no small separators, nor can Weisfeiler–Lehman.

Guess who got a PhD doing this kind of stuff...

# Answer
> 4 votes
Connect all vertices to a common one.

# Answer
> 3 votes
One epic answer by David, one simplest answer by Yuval. However, there is no graphs. I mean, actual visual graphs.

Here is the famous beautiful negative instances to 1-dimensional Weisfeiler-Lehman test of graph isomorphism. The Shrikhande graph is at the left and the $4\times 4$ rook's graph is at the right.  The above picture is taken from mathematicaladd.wordpress.com.

Both graphs are strongly regular with parameters $\\{16,6,2,2\\}$. In the Shrikhande graph, the neighbors of each vertex form a cycle of six vertices. In the $4\times 4$ rook's graph, the neighbors of each vertex form two disjoint triangles.

---
Tags: graphs, combinatorics, graph-isomorphism
---


# Question
Title: Whats the difference between an oracle and a decider in Computational Theory?
I'm learning about Turing reductions at the moment and I'm just wondering is there any difference between an oracle and a decider, As they seemingly do the exact same thing. I understand the point of a oracle is that we don't have to know how it gets its answer but it will always give us the right answer.

> **An oracle for a language B is an external device that is capable of reporting whether any string w is a member of B**

which is the exact same thing as what a decider does. Is there any sort of difference between the two?

# Answer
Oracles are entities capable of deciding even undecidable problems. Deciders, on the other hand, are essentially Turing machines (without an oracle) and therefore cannot solve undecidable problems (e.g. Halting problem).

---

> I understand the point of a oracle is that we don't have to know how it gets its answer but it will always give us the right answer.

This is in fact the key difference.

An oracle doesn’t have an implementation, it is just a black box giving answer to **any** particular question (most importantly, the ones we cannot answer), whereas a decider has to be well defined Turing machine. In other words, we **must know how** a decider gets the answer, meaning it cannot answer *any* question.
> 4 votes

---
Tags: turing-machines
---


# Question
Title: Given a bitstring generate all bitstring with n flipped bits
For an algorithm I need to be able to iterate over all bit strings where $k$ bits are flipped given a bit string with length $n$ and $n \geq k$. For instance let's say I have the bit string $1001$ and I want to have all bit strings with $2$ bits flipped. That should result in the following bit strings:

```
1010
1100
1110
0000
0011
0101

```

So given a bit string of length $n$ and where $k$ bits will be flipped the result will be $\binom{n}{k}$ bit strings. Is there an efficient way to generate all of them? The bit strings I have as input are just unsigned integers so I can use bit twiddling!

# Answer
Let your initial bit string be `x`.

For all numbers `b` with `k` bits set (i.e. where `k` bits are 1), output `x xor b`.

Finding all numbers with `k` bits set is described elsewhere, for example here
> 2 votes

---
Tags: algorithms, combinatorics, bit-manipulation
---


title: finding separating words (Nerode)

text:
# Question
Title: finding separating words (Nerode)
i have found the equivalence classes of given $R\_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me how to do so. also, if you can, would appreciate if you could check if i obtained the correct equivalence classes for both languages.

1)$L=\bigg\\{w\in \sum^\*\bigg| w\quad \text{starts and ends with} \quad aa\bigg\\}$

equivalence classes i've obtained:

$S\_1 = \epsilon$

$S\_2 = a$

$S\_3 = (b+c)\sum^\*+a(b+c)\sum^\*$

$S\_4 = aa+aaa+aa\sum^\*aa$

$S\_5 = aa\sum^\*(b+c)a$

$S\_6 = aa\sum^\*(b+c)$

2)$L=\\{\sum^\*-(\\{\epsilon, a,b\\}\cup \\{bba^i|i\ge 0\\})\\}$

equivalence classes i've obtained:

after joining $\\{\epsilon, a,b\\}\cup \\{bba^i|i\ge 0\\}=\\{\epsilon, a,b,bba^\*\\}$ and using the complementary, i've obtained:

$S\_1 = \epsilon$

$S\_2 = a$

$S\_3 = b$

$S\_4 = bba\*$

$S\_5 = c\Sigma^\*+a\Sigma^++b(a+c)\Sigma^\*+bb\Sigma^\*(b+c)\Sigma^\*$

how can i find the separating words? also, if you can, could you verify that i've obtained the correct results?

thank you very much!

# Answer
> 2 votes
There are systemic approaches to find the separating words (a.k.a. distinguishers).

However, for small instances of regular languages, I prefer to use plain argument in plain English sometimes. Let me use your case 1) as an example, where you have got all the equivalent classes correctly.

$L$ contains words that start and end with $aa$.
$S\_1$ is the empty word.
$S\_2$ is the word $a$.
$S\_3$ are the words that do not start with $aa$.
$S\_4$ are the words that start with $aa$ and end with $aa$.
$S\_5$ are the words that start with $aa$ but do not end with $a$.
$S\_6$ are the words that start with $aa$ and end with $a$ but not $aa$.

What kind of words can be attached to each group of words to make them in $L$?

$S\_1$ \+ $L$
$S\_2$ \+ words that start with $a$ and end with $aa$.
$S\_3$ won't work
$S\_4$ \+ $a$ or words that end with $aa$.
$S\_5$ \+ words that end with $aa$.
$S\_6$ \+ words that end with $a$.

Now that we know these completion groups of words, it is easy to find the separating words.

For example, $S\_1$ and $S\_2$. We need a word that is in $L$ or that starts with $a$ and ends with $aa$, but not both. The word $abaa$ will do.

For example, $S\_5$ and $S\_6$. We need a word that ends with $aa$ or that ends with $a$ but not both. The word $a$ will do.

---
Tags: automata, finite-automata, compilers, partitions
---


# Question
Title: How to make an unambigous grammar of a programming language
We know that the decision problem of whether an arbitrary context-free grammar is ambiguous is undecidable. My question is how are made the unambigous grammar of programming language? My guessing is that maybe starting from a simple grammar, which is easy to prove that is not ambigous, then adding some rules for which the new grammar is also not ambiugous, of course there must be some theorems which say what kind of rules can be added. If my guessing is correct I would like to know that theorems.

# Answer
> 5 votes
Grammars of real programming languages are often more restricted than CFG in order to enable efficient parsing. You may have heard of LL(k) and LR(k) grammars, for instance. All these grammars are, by definition, unambiguous; the corresponding language classes are (strict) subsets of DCFL.

You would realize a grammar is ambiguous (or otherwise not in the grammar class at hand) when the algorithm constructing a parser from it fails. Speaking in computability terms, membership for these grammar classes is decidable.

---
Tags: context-free, programming-languages, ambiguity
---


# Question
Title: IA network that is path-consistent, but not consistent
I'm studying continuous CSP from the slides of my professor and i got that with the PATH-CONSISTENCY algorithm you can check consistency for PA (Point Algebra), SIA and ORD-Horn; however it cannot be used to determine consistency for IA (Interval Algebra), since it is just a necessary but not sufficient condition. From this i would say that it must exist a IA Network which is path consistent, but not consistent. However i cannot construct such a network. Is my assumption wrong? If not what would be an example of a IA network which is path consistent but not consistent?

# Answer
Yes, you are correct.

Here is the classic example of an interval algebra network that is path consistent, but not consistent. It appears in Allen, James F. (26 November 1983) "*Maintaining knowledge about temporal intervals*". Communications of the ACM. ACM Press: 832–843. doi:10.1145/182.358434.

It seems the arc between interval $B$ and $C$ in the above figure is missing its arrowhead. However, you can assign either direction to that arrow since the relationship $(d\ di)$ is symmetric.

> It should be noted that this algorithm, while it does not generate inconsistencies, does not detect all inconsistencies in its input. In fact, it only guarantees consistency between three node subnetworks. There are networks that can be added which appear consistent by viewing any three nodes, but for which there is no consistent overall labeling. The network shown in Figure 5 is consistent if we consider any three nodes; however, there is no overall labeling of the network. To see this, if we assign the relationship between $A$ and $C$, which could be $f$ or $fi$ according to this network, to either $f$ alone, or $fi$ alone, we would arrive at an inconsistency. In other words, there is no consistent labeling with $A-(f)\to C$, or with $A-(fi)\to C$, even though the algorithm accepts $A-(f\ fi)\to C$.

I would encourage you to read that seminal paper by Allen for more information.
> 2 votes

---
Tags: constraint-satisfaction
---


# Question
Title: How do you find set of keywords present in set of words in linear time or log time?
I am trying to optimize a program, where I need to know whether a given set of keywords present in the set of words. I believe using the dictionary is the **only** way to optimize it. Any other technique so that I can get better time complexity? The below python script is my version of the code, this works for a small sentence with a time complexity `O(len(keywords)) + O(frequency_table CONSTRUCTION TIME)`. Space complexity is not a problem, but time.

```
def cover_test(keys, sentence):
    frequency_table = collections.Counter(sentence)
    count = 0
    for key in keys:
        if key in frequency_table:
            count += 1
    return count == len(keys)

cover_test("word1 word4".split(), "word2 word1 word3 word4".split())
# output
# True, because word1 and word4 is present in the sentense

```

examples of input

> Set of words
>
> \['apple', 'green', 'horse', 'ink', 'ball', 'cat', 'dog', 'elephant', 'fun'\]
>
> Set of keywords
>
> \['fun, 'green'\]

Output for the above input is True

**Update: More clarifications:** The goal is to ensure that every word from the keys list is included in the sentence list, in linear or less time complexity.

# Answer
> 1 votes
I'm interpreting your question as wanting to quickly ensure that every word from the `keys` list is included in the `sentence` list.

Assuming you're using a sane version of python, the running time for the initial construction of the counter object is linear in the length of the sentence's description. At least as long as no word appears so many times that the integer stored in the counter exceeds INT\_MAX.

So the overall running time, for sane inputs, is linear in the input, which is the best you can possibly expect (since Python has to read the entire input anyway, which takes linear time already).

That said, there's no compelling reason to use a counter here. You could just as easily have used a Set object and achieved the same running time without the assumption on word counts not exceeding a certain value. It might also be easier to read.

For example

```
def cover_test(keys, sentence):
    sentence_word_set = set(sentence)
    for key in keys:
        if key not in sentence_word_set:
            return False
    return True

```

or even

```
def cover_test(keys, sentence):
    sentence_word_set = set(sentence)
    return all(i in sentence_word_set for i in keys)

```

Set construction is promised to be expected linear-time in the size of `sentence`, with expected constant-time lookups. And the for loop goes through each key once (totalling to something linear in the size of `keys`) so the running time is expected linear in the whole input. Which again is the best you can do.

---
Tags: algorithms, complexity-theory, runtime-analysis
---


# Question
Title: Reduce the total internal border of a set of touching rectangles (using graphs)
I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas

I will go over the algorithm, however the final structure still consisting of rectlinear rectangles has a more complex representation as shown below. I think it will still work.

Possible steps

Example of a Real World problem

# Answer
Here's a naive attempt at a greedy solution.

I'm assuming the initial input is a polyomino (polygon made up of grid aligned squares) on a grid as in your "real world example".

Let $b = (i, j, w, h)$ be the rectangle with lower left corner containing grid location $(i, j)$ with width $w$ and height $h$. A rectangle is valid if and only if all of its internal grid cells are part of the polyomino.

For a valid rectangel $r$, the boundary edges of $r$ will either also be boundary edges of the polyomino itself, or internal edges. Denote by $B\_r$ the number of boundary edges of the rectangle that are internal to the polyomino and $I\_r$ the number of grid edges that are internal to both the boundary and the rectangle. In the teal rectangle in my example below, $I\_r = 17$ and $B\_r = 6$ (the red sketchy edges). Now define the *quality* of the rectangle $r$ to be $Q\_r = I\_r - B\_r$.

The thought here is that the quality of a rectangle measures how good it is at eliminating internal edges.

Now, the greedy solution I have in mind is:

Generate all of the $O(n^4)$ possible rectangles $r$. For each rectangle $r$, check if $r$ is valid. * If $r$ is valid, compute its quality score and maintain the rectangle with the maximum quality. End for loop. Add the rectangle that maximized the quality to the output set, and color the squares it covers white. Repeat until all squares are white.

Unfortunately this is $O(n^5)$ where $n$ is the width and height of the grid. But if your problem size really is like the image, then that may not be an issue.

Also, I don't have a proof that it's optimal, but I'll think about it.

Ok, I wrote some code for this. It's quick and dirty, but it returns exactly your optimal result on your original small example. It is quick and dirty, so don't judge ;).

```
from functools import reduce

# Generates all valid rectangles that have a lower left hand corner in i and j
def validRectanglesFrom(grid, i, j):
    result = []
    w = 1
    while i + w <= len(grid) and grid[i + w - 1][j] == 1:
        h = 1
        row_is_valid = True
        while j + h <= len(grid[i + w - 1]) and row_is_valid:
            for k in range(i, i + w):
                if grid[k][j + h - 1] == 0:
                    row_is_valid = False
                    break
            if row_is_valid:
                result.append((i, j, w, h))
            h = h + 1
        w = w + 1
    return result

def left_edge_is_internal(grid, i, j):
    return i > 0 and grid[i - 1][j] == 1 and grid[i][j] == 1

def right_edge_is_internal(grid, i, j):
    return i < len(grid) - 1 and grid[i][j] == 1 and grid[i + 1][j] == 1

def bottom_edge_is_internal(grid, i, j):
    return j > 0 and grid[i][j - 1] == 1 and grid[i][j] == 1

def top_edge_is_internal(grid, i, j):
    return j < len(grid[i]) - 1 and grid[i][j] == 1 and grid[i][j + 1] == 1

def bottom_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda i: bottom_edge_is_internal(grid, i, rect[1]),
                    range(rect[0], rect[0] + rect[2])
                )
            )
        )
    )

def top_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda i: top_edge_is_internal(grid, i, rect[1] + rect[3] - 1),
                    range(rect[0], rect[0] + rect[2])
                )
            )
        )
    )

def left_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda j: left_edge_is_internal(grid, rect[0], j),
                    range(rect[1], rect[1] + rect[3])
                )
            )
        )
    )

def right_boundary_penalty(grid, rect):
    return len(
        list(
            filter(
                lambda isInt: isInt,
                map(
                    lambda j: right_edge_is_internal(grid, rect[0] + rect[2] - 1, j),
                    range(rect[1], rect[1] + rect[3])
                )
            )
        )
    )

def boundary_penalty(grid, rect):
    return (
        bottom_boundary_penalty(grid, rect) +
        top_boundary_penalty(grid, rect) +
        left_boundary_penalty(grid, rect) +
        right_boundary_penalty(grid, rect)
    )

def internal_grid_edges(rect):
    return ((rect[2] - 1) * rect[3]) + (rect[2] * (rect[3] - 1))

def quality(grid, rect):
    return internal_grid_edges(rect) - boundary_penalty(grid, rect)

def get_rectangles(grid):
    result = []
    grid_locations = [(i, j) for i in range(0, len(grid)) for j in range(0, len(grid[i]))]
    unfilled = {cell for cell in grid_locations if grid[cell[0]][cell[1]] == 1}
    while len(unfilled) > 0:
        rects = [rect for cell in unfilled for rect in validRectanglesFrom(grid, cell[0], cell[1])]
        qualityScores = list(map(lambda rect: quality(grid, rect), rects))
        bestRectIdx = reduce(lambda i, j: i if qualityScores[i] > qualityScores[j] else j, range(len(qualityScores)))
        bestRect = rects[bestRectIdx]
        result.append(bestRect)
        for i in range(bestRect[0], bestRect[0] + bestRect[2]):
            for j in range(bestRect[1], bestRect[1] + bestRect[3]):
                unfilled.remove((i,j))
                grid[i][j] = 0
    return result

# Your initial example
grid = [[1, 1, 1], [0, 1, 0], [0, 1, 1], [0, 1, 0]]
get_rectangles(grid)

# Your "real world" example
grid2 = [[0,0,0,0,0,0,0,0,1,1,1,0,0,0,0],
        [0,0,0,0,0,0,0,0,0,0,1,1,1,0,0],
        [0,0,0,0,0,0,0,0,0,1,1,1,0,0,0],
        [0,1,0,0,0,0,0,0,0,1,0,1,1,0,0],
        [1,1,0,0,0,0,0,0,0,0,0,1,1,1,0],
        [1,1,1,1,0,0,0,0,1,0,0,1,0,1,0],
        [0,0,0,1,1,0,0,1,1,1,1,1,0,1,0],
        [1,1,1,1,1,0,1,1,1,1,1,1,0,0,0],
        [1,1,1,0,1,0,1,1,1,1,1,0,0,0,0],
        [0,0,1,1,1,1,1,0,0,1,1,1,0,0,0],
        [0,0,0,1,0,0,0,0,0,0,1,0,0,0,0],
        [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0],
        [0,1,1,1,0,1,1,0,0,0,0,0,0,0,0],
        [0,1,1,1,0,1,0,0,0,0,0,0,0,0,0],
        [0,1,0,1,1,1,1,1,0,0,0,0,0,0,0]]
get_rectangles(grid2)

```

Here's the result my code returns for your "real world" example.
> 1 votes

# Answer
I coded a possible solution to the problem.

Given that the structure is quite large e.g. a grid of 25x25 and around the periphery of the structure other rectangles are added, it is very difficult to determine the optimal solutions. The structure may also contain holes which makes it NP complete.

Initially I used to the internal borders metric i.e. maximize the number of internal borders removed but the results I got were not very satisfactory. The next greedy technique I tried was to maximize the area removed at each step and this is giving good results as far as I can see. Good results re the improvement in computational efficiency for the next steps. The only I can see the overall effect of the metric is to do a statistical test. I will generate a couple of 1000 structure, apply both the internal perimeter and area matrics and see the improvement in the results.
> 1 votes

---
Tags: optimization, computational-geometry, dynamic-programming, graph-traversal
---


# Question
Title: is conflict possible In accepting state of LR(0)?
Consider the following grammar:

```
Stmts -> Stmt | Stmts;Stmt

Stmt -> Var =E

Var ->id[E] | id

E-> id | (E)

```

in accepting state we get

```
S' -> stmts .

stmts -> stmts . ;stmt

```

isn't it a conflict ?

# Answer
> 1 votes
I don't think there is a real conflict here.

It does look like a shift/reduce conflict but if you are at the end of the input there is no ";" symbol that can be shifted so only reduction to S' applies.

There are ways you can deal with things that look like conflicts near the accepting state.

One is to have a pseudo token for end of input. This distinguishes a parse where you consume all the input from one where you have unconsumed tokens (garbage) remaining.

If you have a choice between which rules to apply you can have a preference for a reduction to the start symbol and thus to accepting rather than applying further rules.

---
Tags: compilers, parsers
---


# Question
Title: What's the theoretical difference between class and type?
This question stems from my effort trying to learn ASN.1.

After I went through the PKCS#1 standard for RSA cryptosystem and X.680~X.683 side-by-side, I noticed that, they've defined

1. `ALGORITHM-IDENTIFIER` as a class, and
2. `AlgorithmIdentifier` as a sequence type that can be encoded using BER the basic encoding rule.

I've went through the Wikipedia pages on the subjects, in both computer science and mathematical fields. It seems to say that a "class" is more general than a "type" while "type" is more concrete than "class" on the other hand.

So what's the difference from a theoretical perspective? What are the examples? And possibly why the standard developers elect to use such terminology?

# Answer
> 2 votes
I am sure that the mentioned standard is using the terms "class" and "type" according to their basic English meaning, without referring to the scientific terms from mathematics and computer science.

In a standard you might have a parameter which identifies the general "form" of a packet, a message, a subprotocol, or even an algorithm. To name the possible "variants" allowed by the standard, one might refer to those as "classes", "forms", "kinds", "types", "groups", or similar English terms.

These terms are not used according to any scientific meaning, but become technical terms within the standard. E.g. the standard might consistently use "algorithm class" to refer to the value of a certain field of a packet, stating which algorithm was used to encrypt the payload. The standard might have instead used "algorithm type", or "algorithm kind" for the same thing, with no effect on the meaning. Usually the standard chooses a term and uses it consistently to help the reader understand it's referring to that field: using "algorithm" alone wouldn't be as effective.

It's only a coincidence that "type" is also used in type theory, and "class" is used in set theory.

---
Tags: terminology
---


title: Which of the following is recursive

text:
# Question
Title: Which of the following is recursive
Consider below two Languages

$L1=\\{\<M\>|$M takes atleast 2000 steps on some input $\\}$

$L2=\\{\<M\>|$M takes atleast 2000 steps on all inputs$\\}$

Where for each Turing machine M, $\<M\>$ denotes specific encoding of M.

Here I think both are recursive, because let's say I bound the number of steps the Turing machine runs to 2000, then Turing machine will only be able to process inputs of length atmost 2000.

Now, there are finite number of inputs of length 2000, I can check whether for all such inputs, my Turing machine is making 2000 steps or not.This answer L2.

And when L2 is answered, I have an answer to L1, making L1 and L2 both recursive.

Am I correct in my reasoning?

# Answer
> 2 votes
No, your reasoning is not correct, but I think you are very close to a correct answer.

A Turing machine in 2000 steps can only read the first 2000 symbols in the input tape, but is not forced to reject a longer input. In fact, it can accept it. So, the TM can process longer inputs, but its behavior is determined by the first 2000 symbols on the tape.

If $x$ and $y$ are words which are identical on their first 2000 symbols, then they are both accepted/rejected/neither in 2000 steps.

Because of this, we can partition the possible inputs according to their first 2000 symbols. For each of the finitely many partitions, we can extract any element and test for that one, only.

So, our decision procedure is the one given by the OP. The argument for correctness is a bit different, though.

---
Tags: turing-machines
---


# Question
Title: Number of literals in the given boolean expression
Count the number of literals in the following expression :

F = AB' + BC' + CD' + DE'

According to me, the answer should be 8. But my solution suggests that the answer should be 6. Can anyone help me out. What am I doing wrong?

Thanks in advance!

# Answer
Does your material use the (strange) convention of notating $\neg A$ as $A'$?

If so, there are 6 literals (5 without the LHS). If $A'$ is distinct from $A$, there are 9 (8 without LHS) and the solution book is wrong.
> 2 votes

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


# Question
Title: Missing part of the proof of Master Theorem's case 2 (with ceilings and floors) in CLRS?
I am trying to go through the proof of the Master Theorem in Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS). The theorem providers an asymptotic analysis for recurrence relations $T(n)=aT(n/b)+f(n)$ where $a\geq 1, b \> 1$ and $f(n)$ is an asymptotically positive function.

The authors create a formulation of the following lemma (4.3):

> 2. if $f(n) = \Theta(n^{\log\_ba})$, then $g(n)=\Theta(n^{\log\_ba}{\log\_bn})$

where $g(n) = \sum\_{j=0}^{\lfloor \log\_b n \rfloor - 1} a^jf(n\_j)$ and $n\_j = \begin{cases} n, & \text{if j = 0} \\ \lceil n\_{j-1}/b \rceil, & \text{if j \> 0} \end{cases}$

When it is proving for the situation in which floors and ceilings appear the autrors make a statement:

> For case 2, we have $f(n)=\Theta(n^{\log\_b a})$. If we can show that $f(n\_j) = O(n^{\log\_ba}/a^j) = O((n/b^j)^{\log\_ba})$, then the proof for case 2 of Lemma 4.3 will go through.

Well, I got it. When this condition is true we can find some constant $c$, such that

$g(n) \le c\sum\_{j=0}^{\lfloor \log\_b n \rfloor - 1} n^{\log\_b a}$

and conclude that $g(n) = O(n^{\log\_b a}{\log\_bn})$.

But it's **not** a proof that $g(n) = \Omega(n^{\log\_b a}{\log\_bn})$. Where is one? Should it be obvious? How can I prove this statement?

# Answer
As you said, the book does not include a proof for $g(n) = \Omega(n^{\log\_b a}{\log\_bn})$. **There is no need to**.

Recall that part of proof is to show the upper bound of $f(n)$, when $f(n)$ is defined by the following recurrence relation using the ceiling function, which is the formula 4.25 in CLRS. $$T(n) = aT(\lceil\frac nb\rceil) + f(n)$$ Noting that the lower bound for $T(n)$ "is routine, since we can push through the bound $\lceil\frac nb\rceil\ge\frac nb$", the book proceed to prove an **upper** bound for the above $T(n)$, where we only need to show an upper bound for $g(n)$.

---

What you meant might be the corresponding situation in the case when $f(n)$ is defined using the floor function as the formula 4.26 in CLRS, $$T(n) = aT(\lfloor\frac nb\rfloor) + f(n)$$ in which case, we will defined $h(n) = \sum\_{j=0}^{\lfloor \log\_b n \rfloor-1} a^jf(n\_j)$ and $n\_j = \begin{cases} n, & \text{if j = 0} \\ \lfloor n\_{j-1}/b \rfloor, & \text{if j \> 0} \end{cases}$.

Note that the definition of $h(n)$ is not the same as that of $g(n)$, although the two are almost the same.

I will leave as an exercise for you to prove a lower bound for the above $T(n)$ using $h(n)$. In particular, you will need to show that in case 2, i.e., when $f(n)=\Theta(n^{\log\_b a})$, $$h(n) = \Omega(n^{\log\_b a}{\log\_bn}).$$

Hint, as said in the last statement of section 4.6.2 and by Yuval's comment, the proof of the lower bounds is similar.
> 1 votes

---
Tags: asymptotics, master-theorem
---


# Question
Title: why is the max number of Nodes mod(N/m) + mod(N/m^2) + 1 in R-tree?
I am going through Antonin Guttman's paper on R-tree. It mentions the max no of nodes given N index records in an R-tree is `|N/m| + |N/m^2| + 1`.

If there are N index records and if we choose to have minimum number of entries (m) in each node, wouldn't we just need N/m nodes at max? Why do we also have N/m^2 + 1?

Here's a link to the paper

# Answer
Here is the relevant excerpt of that paper.

> The height of an R-tree containing $N$ index records is at most $\lceil\log\_m N\rceil$, because the branching factor of each node is at least $m$. The maximum number of nodes is $\lceil\frac Nm\rceil + \lceil\frac N{m^2}\rceil + \cdots + 1$. Worst-case space utilization for all nodes except the root is $\frac mM$.

The paper you saw is so fuzzy that you mistook the formula as $|\frac Nm| + |\frac N{m^2}| + 1$.

How to explain the correct formula? Since all leaves are on the same level and each leaf-node contains at least $m$ index records, there are at most $\lceil\frac Nm\rceil$ leaf nodes. The number of the parents of all leaf nodes is at most $\lceil\frac{\frac Nm}m\rceil=\lceil\frac N{m^2}\rceil$. And so on.

Here is a copy of that paper that is more legible.
> 1 votes

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


title: Weak Precedence Grammar and Parsing

text:
# Question
Title: Weak Precedence Grammar and Parsing
I am studying parsing, i.e. bottom-up parsing. it is said that there some rules which are used by weak precedence grammar. What does weak precedence grammar mean? What about precedence relation?

Any help will be appreciated. If it is possible, could you give an example. Thanks

# Answer
Weak precedence is first an algorithm for parsing (see Parsing Techniques - A Practical Guide 1st edition p. 186). So a weak precedence grammar would be a grammar which can be parsed by this algorithm (see the reference for a description of the algorithm, you'll probably want to start at least a few pages earlier).

IIRC, the interest of weak precedence parsing dropped at lot when practical LR(1) variants (SLR(1) and LALR(1)) were discovered, but precedence algorithms are still sometimes used in hand written parser for parsing expressions while the rest of the grammar is parsed with a recursive descend variant.
> 2 votes

# Answer
Weak precedence is a modification of Wirth-Weber "simple precedence" (which they introduced in a paper defining the language EULER). A simple precedence parser uses Boolean matrices to define three relations that can exist between any two symbols in the grammar, usually represented as \<, =, and \>. The algorithm reads the input, looking up the pairwise relations in tables generated from the Boolean matrices, and inserting the appropriate relation between each two symbols. When a \> relation is discovered, the parser looks backward to the nearest \< relation. The symbols between those constitute the right-hand side of a production in the grammar, which is then replaced by the nonterminal symbol on the left side of that production, and the parsing continues.

Problems occur when more than one relation can hold between two consecutive symbols. When this occurs, the grammar must be changed (usually by introducing new nonterminals) to keep the relationships clean, or the attempt to find a simple precedence grammar for the language must be abandoned. Jean Ichbiah and Steve Morse realized that this problem could be reduced by eliminating one of the relations, and they called the result "weak precedence." In a weak precedence parser, the only significant relation is \>. Symbols in the input are processed until a \> relation is found, then the series of symbols leading up to that is matched against the right-hand sides of all productions, with the longest possible match being taken. Reduction then occurs as in simple precedence, and parsing continues.

It is obvious that any simple precedence grammar is automatically also a weak precedence grammar. There are grammars, though, that are not simple precedence but are weak precedence grammars, so weak precedence is more powerful than simple precedence.
> 1 votes

# Answer
From memory I think it is in a paper by Ichbiah and Morse, CACM, 1970
> 0 votes

---
Tags: formal-languages, terminology, context-free, parsers
---


# Question
Title: What does a proof that Co-NP =P entail for the NP versus Co-NP question
What I wonder is what exactly would it entail. Would it,for instance imply that P=NP or would there be different consequences,I haven't found any assorted consequences so far in my research. Thank You, Akash

# Answer
> 5 votes
$\text{P}=\text{co-NP}$ implies that $\text{co-P}=\text{co-(co-NP)}=\text{NP}$. But $\text{co-P}=\text{P}$: you can just swap the accept and reject states of a deterministic Turing machine to complement the language that it decides.

---
Tags: complexity-theory
---


# Question
Title: Find a lambda term satisfying two equations
I'm just looking for the general idea on how to approach the following problem:

Find a term $\Delta=\lambda x.xUV$ such that:

1. $\Delta\Delta=K$
2. $\Delta K=S$

(it's a system of 2 equations, I didn't know how to format it properly)

Where $K=\lambda xy.x$ and $S=\lambda xyz.xz(yz)$

I think I need to use Bohm theorem but I don't know exactly how.

# Answer
This is not directly a consequence of Böhm's theorem. Böhm's theorem states that for any strongly normalizing $A$ and $B$ that are not $\beta\eta$-convertible, there exists $\Gamma$ such that $\Gamma A = K$ and $\Gamma B = S$. You don't get to constrain $\Gamma = A$ or the required form $\lambda x. x U V$. There may be a way to use Böhm's theorem on a different term, but this particular system of equations can easily be solved manually.

If such a term exists then $\Delta K = K U V = U$, so to satisfy the second equation it is necessary that $U = S$.

Then $\Delta \Delta = (\lambda x. x S V) (\lambda x. x S V) = S S V V = S V (V V) = \lambda y. V y (V V y)$. To satisfy the first equation, $V y (V V y) = K y = \lambda z. y$. One way to satisfy this is to take $V = \lambda y z z'. y$.

Finally, verify that $\Delta = \lambda x. x S (\lambda y z z'. y)$ satisfies the two equations.
> 5 votes

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


# Question
Title: How literally is "optimization" or "optimization algorithm" used in CS?
I have been confronted with two meanings of the term "optimization" or "optimization algorithm":

1. to find the **absolute maximum** in a set $X$ according to some criterion $f:X\to \mathbb R$
2. to find a "relatively high" or "increasingly high" or "locally maximum" element in a set $X$ according to some criterion $f:X\to \mathbb R$

A friend of mine claimed that nr $1$. is the only "official" meaning of the term, and that only laymen or people who speak informally use the meaning of $2$. **Is my friend correct?**

# Answer
> 2 votes
There is no governing body mandating the meaning of terms in computer science. Instead, just like all human language, the meaning of a term is defined implicitly by its use, and could depend on the language community.

In theoretical computer science, optimization is a wide topic that covers many different problems. The most common problem is to find the maximum or minimum of a function subject to constraints. Often one is interested in finding an approximate optimum, or an approximate optimum which only approximately satisfies the constraints (this is known as a *bicriteria approximation*).

When finding even an approximate optimum turns out to be difficult, it is reasonable to consider finding a local optimum or an approximate local optimum. This happens, for example, in machine learning, and is actively pursued by the optimization community.

Summarizing, there is no official meaning of the term *optimization* in computer science, any more than there is an official meaning of this term in English. In practice, in the theoretical computer science community, the term is widely used in the more relaxed sense corresponding to your second definition, and beyond.

---
Tags: optimization, terminology
---


title: Count-min sketch

text:
# Question
Title: Count-min sketch
I don't understand the use case of count min sketch. Based on *Count–min sketch*, it says "serves as a frequency table of events in a stream of data.".

If I know there are N types of events, why can't I just allocate an array of N slots or a hashmap to keep track of the event frequencies as the stream is ingested?

Am I right to say the use case is when N is unknown or N is so large that it is not possible to keep the entire frequency array/hashmap in memory?

# Answer
> 3 votes
Sketches are data structures used in streaming algorithms. The idea is that while the stream is very long, the hardware processing it has limited memory. We want to be able to retain statistical information about the data without storing it completely.

You can find more information about sketching here.

# Answer
> 2 votes
Yes, the use case is $N$ so large that the entire table would not fit in the main memory. For example, imagine that every event is tied to an IPv6 address. IPv6 uses 128 bits for each address, so you would in principle need an array with $2^{128}$ elements.

---
Tags: algorithms, counting
---


# Question
Title: Proof Idea: There are irrational numbers whose decimal expansion cannot be computed
The online lecture I am watching stated a proof idea:

The set of all possible programs is countably infinite, yet the set of irrational numbers is uncountably infinite.

I don't think this is sufficient, it assumes one program can only return one irrational number. How to show that I can not write one program that returns all irrational numbers?

# Answer
> 2 votes
You can't even write a program that outputs one single irrational number. What you *can* do, is write a program which will output for example every decimal digit of some irrational number, one after the other, assuming unlimited resources and unlimited time, and which will output every single digit eventually (but will *never* output all digits). We count that as "outputting a number".

If you tried to write a program that first outputs all digits of π, followed by all digits of e, that wouldn't work because it never will finish outputting the digits of π. What you could do is output the first decimal of π, followed by the first decimal of e, followed by the second digits of π and e, and so on. So a program can output two (or three or four or a billion) irrational numbers, if we change the definition a bit.

You could write a program that outputs a countable infinite number of irrational numbers. Start with the first digit of the first number. Then the second digit of the first, followed by the first digit of the second number. Then the 3rd digit of the first, 2nd digit of the second, and 1st digit of the third number, and so on forever. So this program would eventually output each digit of a countable infinite number of irrational numbers.

You can't extend this to an uncountable numbers. Being uncountable, it is impossible for example to output just the first digits of all these numbers.

So the best you can do, with a modified definition of what "outputting an irrational number" means, is that you can have a countable number of programs, which each calculate a countable number of irrational numbers, but countable times countable is still countable, so you cannot output all irrational numbers.

# Answer
> 1 votes
You cannot return all irrational numbers simply because you cannot put/store them all within your program that has **countable** amount of registers/memory.

Even if you could somehow store the irrational numbers as a concept within your program and return that concept, you could not use it to access/search a specific irrational number because we cannot order/list elements of sets that are uncountable (see Cantor’s diagonal argument), so it wouldn’t be of much use unless you invent some new operation on these “concept outputs”, but this is already too far fetched.

---

Another point is that we live (as it seems) in at best countable universe so everything that is equal or greater in cardinalty cannot be truly seen/experienced within it, at specific point or finite period of time.

We use approximations, but $3.1415$ is not $\pi$, $3.14159$ is not $\pi$,... If your program returns $3.1415926$, how do you know it is supposed to represent $\pi$ and not $3.14159264$?

You can write a program that, one by one, outputs digits of $\pi$ and call this program a representation of $\pi$. It will never give you $\pi$ truly but it can infinitely run giving you something closer and closer to $\pi$.
For all irrationals, you would need uncountably many such (different) programs or one program with uncountably many instructions, both of which by definition cannot exist.

---

Well, there are some theories that you could throw a program into a black hole where it would run for infinite amount of time while you would experience this time as $0$, giving you the result of infinite computation instantly. That would also be problematic for the task we are discussing because it would need to create the entire inifinite universe to store the irrational number.

# Answer
> 0 votes
From discussion in the comments:

> obviously if I want to output an irrational number, it will just be to a certain accuracy p which may be input to the program.

Of course, there is a program that infinitely outputs all possible decimal expansions. Any irrational number will eventually appear in this output (within certain accuracy $p$).

But look at the statement of the theorem. Could such a program be used to find decimal expansion of certain irrational number of interest? When exactly should we expect decimal expansion of this number to appear? This is undecidable.

It might be easier to understand this via another example. Consider this problem:

> You are given the source code of some (deterministic) program. You're also given a proof that this program terminates and outputs some positive integer. What is this number?

You tried to run the program, but it is still running and there's no progress bar. It might take 10 minutes, it might take 1000 years. You don't know. You only have a proof that the program eventually stops.

Surely, you can write a program that outputs all possible positive integers. Surely, the correct answer to the problem appears somewhere in this infinite list. But does it help to solve the problem?

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


# Question
Title: Regular expression or automata for language with odd number of 0's and odd number of 1's
Let $\Sigma=\\{0,1\\}$ and $L=\\{u \in \Sigma^\* : u \text{ has odd number of 0's and odd number of 1's}\\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I guess $L$ is not regular, but I haven't been able to prove it with the pumping lemma.

If it is not regular, can you give me a hint to prove it?

# Answer
> -1 votes
Hint: You are trying to solve two problems (i.e., odd number of zeros and odd number of ones) at once. Try to solve each separately instead and then combine the solutions appropriately.

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


# Question
Title: Data structure for getting the k'th largest element
I'm given a set of $n$ numbers. Is there a data structure that builds in $O(n)$ (linear time) and gets the $k$'th largest element in $O(k)$ time? Also, is there anything better than $O(k)$?

# Answer
> 3 votes
Here is a solution that uses only comparisons. For simplicity, assume that $n$ is a power of 2.

Find the median of the original array in $O(n)$, and extract the largest $n/2$ elements. Then find the median of the new array in $O(n/2)$, and extract the largest $n/4$ elements. Continue in this way, extracting the $n/8,n/16,\ldots,1$ largest elements. In total, preprocessing takes time $$ O(n+n/2+n/4+\cdots) = O(2n) = O(n). $$

Given $k$, find $\ell$ such that $n/2^{\ell+1} \< k \leq n/2^{\ell}$. By construction, $n/2^\ell \< 2k$. The $k$th largest element is thus one of the $n/2^{\ell}$ largest elements. Using the linear time selection algorithm, locate the $k$th element among them in $O(n/2^\ell) = O(k)$.

---

We can improve the running time for $k \leq Cn/\log n$ (for arbitrary $C$) to $O(1)$ as follows.

During preprocessing, use a linear time selection algorithm to locate the $Cn/\log n$-th largest element in $O(n)$, and extract all larger elements. Sort them in $O(n)$.

During query time, locate the $k$th largest element for $k \leq Cn/\log n$ in $O(1)$ using the new array.

Conversely, we can show that this $O(1)$ behavior cannot extend beyond $O(n/\log n)$ for comparison-based algorithms. Indeed, suppose that there is an algorithm which preprocesses an array in $O(n)$, and is able to locate the $k$th element in $O(1)$ for $k \leq f(n)$, where $f(n) = \omega(n/\log n)$. This allows us to sort an array of size $f(n)$ in time $O(n) + O(f(n)) = o(f(n) \log f(n))$ by adding $n - f(n)$ dummy elements, contradicting the well-known lower bound for sorting.

# Answer
> 0 votes
If you can apply Radix sort, just sort the data and you are done.

If you only can compare data, then such algorithm can be used to find arbitrary element of sorted sequence in O(N), while it was proved that such sorting requires O(n\*log(N)).

So, no way.

# Answer
> 0 votes
Since these are numbers, we can sort them with Radix Sort in O(N) time and then find k'th largest element in O(1) time.

Extra memory required for radix sort is O(n^epsilon) where epsilon may be any positive number up to 1.

# Answer
> -2 votes
I don't think there is such algorithm. If there was, you would be able to find median in O(n) which is AFAIK unknown or even it is proven it doesn't exist.

---
Tags: algorithms, data-structures, time-complexity
---


# Question
Title: Show that $A_\mathrm{LBA}$ is PSPACE-Complete?
I want to show that $A\_\mathrm{LBA}$ is PSPACE-Compelte.

Say we proved it is in PSPACE. Now for PSPACE-HARD:

I had an idea, which was very similar to some solution i found on the web- say we have a TM M which decides some language `A` in PSPACE. Then given an x in `A` we can simulate M on x to determine the number of steps M makes.

Suppose the above simulation is defined as another TM M' and k steps are needed for M to run x.

Build a TM M'' which simulates M on "x, $space^{\mathrm{k}}$" - the word x concatenated with k spaces. return (M'', "x, $space^{\mathrm{k}}$")

What i don't understand - the input is **only** `x` and its length is |x| so how do we know that **simulating M on x is poly-time(x)** ? we don't know the size of the description of M, which must be fed to the single-tape LBA M''.

How come all the solutions i've encountered don't even mention that the size of the description of M might not be poly-time(x) ? then we have that the mere **writing of M on M''s tape might be more than poly-time(x)**. (?)

No relation is given between |x| and |M| (the decider for A) because the input is only the word x...

# Answer
> 1 votes
As I understand, you are asking two questions. Let me address them separately:

1. **You don't.** Your assumption on $M$ did not require anything more than $L(M) = A$, which is too weak for such a proof. You need to use $A \in \textbf{PSPACE}$ and require the existence of a polynomial $p: \mathbb{N} \to \mathbb{N}$ such that $M$ uses at most space $p(n)$ for any input of length $n$.
Incidentally, you also need this to know what $k$ should be. In your proof, you give no explicit way of computing $k$ other than simulating $M'$, but you do not state why this could ever be done in poly-time. (In fact, this could only ever work for arbitrary $M$ if $\textbf{P} = \textbf{PSPACE}$.)
2. The description of $M$ remains *constant* as the length of the input $x$ increases, so it is negligible, asymptotically speaking.

---

## **The real issue**

It appears your approach is based on fixing $A$ and $x$ and then constructing an LBA $M''$ to simulate $M$ on $x$. *This is not how reductions work.* $A$ and $M$ should be fixed, but you need to keep $x$ *arbitrary*, otherwise the proof is quite incorrect (since the result of running $M$ on $x$ could be simply hardcoded into a TM which produces the result immediately upon reading $x$ as input; this proves absolutely nothing).

---
Tags: complexity-theory, turing-machines, reductions, space-complexity, linear-bounded-automata
---


# Question
Title: If $L$ is a regular language, then $s(L)$ is also regular
...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression.

For example, if $L=a^\*b$ and $s(a) =ab, s(b) = b^\*$, we have $s(L) = (ab)^\*b^\*$.

My thoughts so far are that replacing characters in a regular expression with regular expressions still gives us a regular expression overall. Namely I can show for $x \in L$ that $s(x)$ will be a regular set, and then I can do a union over $s(x)$ for all $x \in L$ to show $s(L)$ is regular (by closure of union).

My problem here is carefully showing the substitution will produce a regular set. Does it suffice to say if $x$ is something captured by a regular expression, then $s(x)$ is regular as well? I'm not sure how to prove this.

# Answer
First thing you must understand is that regular expression are closed under union(+), closure(\*) and concatenation (.) . reason being every regex denotes a regular language and regular languages are closed under union, closure and concatenation.

Second thing you should know that if r1 and r2 are regex then the following regex are also regular

1. r1 + r2
2. r1.r2
3. r1\* ,r2\*

so if you are substituting a regex by another regex it should fall among the above three categories or in simple words you will be able to form the regex(after substitution) with use of above relation. coming to you question the language generated after substitution can be formed using above closed properties over regex. let say r1 = a , r2 =b then we have

( ((r1.r2) * ) . r2\* ) making it regular

one more thing the only operation defined to regex are the above three and if so any substitution of regex by regex will have either of the three operation associated with it thus making it regular again
> 2 votes

# Answer
The easiest proof goes as follows:

> Apply the substitution $s$ to a regular expression for $L$.

The proof is by routine induction. What we show inductively is that if $r$ is a regular expression then $$ L\[s(r)\] = s(L\[r\]), $$ where $L\[r\]$ is the language generated by the regular expression $r$.
> 2 votes

# Answer
For simplicity, let us fix the alphabet $\Sigma=\\{a,b\\}$.

$$E \to \phi \mid \epsilon \mid a \mid b \mid (E) \mid EE \mid (E)^\* \mid (E\text{+}E)$$

The above context-free grammar generates the language of all regular expressions as a language over the alphabet $\Delta=\\{\phi, \epsilon, a, b, (, ), {}^\*, +\\}$, according to the formal definition of regular expressions, where "+" denotes alternation.

Note that $\phi$ is the empty regular expression that generates the language that has no words, not even the empty word. The regular expression $\epsilon$ generates the language that has only one word, the empty word.

We have the following proposition.

(**Recursive property of regular expressions**) Let $F$ be a regular expression. Let $F'$ be $F$ but with one of the occurrences of the symbols in $\Sigma$ replaced by another regular expression $G$. For example, $F=aba^\*$ and, if we replace the second $a$ by $(ba)$, we will obtain $F'=ab(ba)^\*$. Then $F'$ is also a regular expression.

Proof. Suppose $F=uav$ where $u,v\in\Delta^\*$ and $a$ is the occurrence as in the proposition. $w$ is obtained by a derivation tree which has a leaf node that corresponds to that $a$, whose parent node must be a node of the only non-terminal $E$. If we replace this derivation of $E\to a$ by the derivation tree of $E\to G$, we will obtain a derivation tree that generates $F'$. Done.

---

The above property can be understood simply as the following context-free grammar,

$E \to \phi \mid \epsilon \mid A \mid B \mid (E) \mid EE \mid (E)^\* \mid (E\text{+}E)$
$A \to E \mid a$
$B \to E \mid b$

also generates the language of regular expressions.

---

Applying the above recursive property of the regular expressions multiple times, we obtain the claim in the question, which can be stated more formally as the following.

(**Regular expressions closed under homomorphisms**) Let $s$ be a map from $\Sigma$ to regular expressions. We can extend $s$ to all regular expressions naturally. Given any regular expression $E$, $s(E)$ is also a regular expression.
> 1 votes

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


# Question
Title: Is there a way to compare computing work spent in two blockchains when every one of them is using different mathematical function as a Proof-of-Work?
If I am a Bitcoin node, I can evaluate two blockchains in terms of each one consisting of more Terahashes than the other and thus deduct which one is the "correct" one. There is impartial source of consensus - hashes done.

But what if I had two blockchains, each one making a different function, e.g. one is Bitcoin and making SHA-256 and another is making other random computation. Could I impartially deduct which "chain" has the most computation work/effort spent even if in those two chains the "way" this computation work is spent is different? Is there common impartial denominator then?

Or, to make it even more interesting, if a blockchain had self-amending possibility like Tezos, and in a certain point of time it reached a consensus to change it's Proof-of-Work method to e.g. more memory-hard (in order to discontinue usic ASICs) then could a node that wasn't connected to the network before that change somehow use a common denominator of computing effort (now not necessarily Hashes used) to evaluate the right chain by checking how much computing effort was spent on chain both before the amendment (when e.g. SHA-256 was used) and after change (when some new Proof-of-Work is used)?

# Answer
> 0 votes
Short answer - no. Any denominator used to compare computing work spent on two different functions would be subjective to those functions. Therefore it cannot be source of consensus spreading over many functions. It'd like comparing apples to oranges.

---
Tags: computation-models, blockchain
---


# Question
Title: How fast can we optimally cluster 1-D data?
K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) is minimized overall, i.e. the clusters as as "tight" as possible.

While NP-hard in the general case, I know it is $\text{PTIME}$-tractable if the points are on a line.

What is the best known upper bound on the time complexity of optimal clustering for the 1-dimensional case?

Note: Lower bounds are also interesting, but less so.

# Answer
> 1 votes
Here's what my search has come up with:

There's a straightforward dynamic programming solution of the problem in this case, which requires $\mathop{\Omega}\left( k \cdot n^3 \right)$ time; and with some thought one can avoid redundant computation of sums-of-squares by this algorithm, reducing the complexity to $\mathop{\Omega}\left( k \cdot n^2 \right)$. This is described in:

> Wang, Haizhou, and Mingzhou Song. Ckmeans. 1d. dp: optimal k-means clustering in one dimension by dynamic programming. The R journal 3, no. 2 (2011): 29.

That being said - I'm thinking perhaps this can be improved to $\mathop{o} \left( k \cdot n \log{n} \right)$ somehow, or at least $\mathop{\omega} \left( k \cdot n^2 \right)$.

---
Tags: algorithms, time-complexity, optimization, clustering, upper-bound
---


# Question
Title: Solving " Tricolor Arrangement " Efficiently
A rectangular board with three rows and $n$ columns is filled with $3n$ counters, of which $n$ are red, $n$ are white, and $n$ are blue. The object is to rearrange the counters to have counters of each of the three different colors in every column. The only operation allowed is to swap counters in the same row. Design an algorithm to accomplish such a task or prove that such an algorithm does not exist.

Let $\mathcal{O}(1)$ be the cost of swapping the counters in the same row.

Iterate over each column. Let us consider that up to column $i-1$, we are done. Now we are at column $i$, there will be three counters, if they are of different colors then we are done, else fix one counter ( say white ) and scan other two rows to get two different color counters ( red and blue ). Running the previous step for a constant number of times ( six ) will solve the problem. More precisely there will be six possibilities in each column (123,132,.....,321), so I will try each of those.

The runtime of the above algorithm will be $\mathcal{O}(n^3)$ as there are $n$ columns and time spent on each column is $\mathcal{O}(n^2)$.

**Question:** Is it possible to solve the above-described problem linear time $\mathcal{O}(n)$ time as input here has size $\mathcal{O}(n)$? I am not even able to come up with an algorithm faster than $\mathcal{O}(n^3)$ time.

I have taken this question from the book titled Algorithmic Puzzles ( problem 46 )

# Answer
An idea can be to reduce this problem to *sorting*.

Consider a final configuration with each colour appearing exactly once per column. You can move the columns around to obtain a final configuration that looks like that :

```
aaaaaaaaaaaa|bbbbbbbbbbbbbbb|ccccccccccccccccccc
bbbbbb|ccccc|cccccccc|aaaaaa|aaaaaaaaa|bbbbbbbbb
cccccc|bbbbb|aaaaaaaa|cccccc|bbbbbbbbb|aaaaaaaaa

```

Where $a, b$ and $c$ are the three distinct colours. We are now going to create that kind of configuration. Let $a\_1$ (resp. $b\_1$ and $c\_1$) denote the number of $a$'s (resp. $b$'s and $c$'s on the first row), same with $2$ on the second row. We can find those by counting, a simple $\mathcal{O}(n)$ first pass.

Now let $x\_\*, y\_\*$ denote the size of the first and second chunk of the colour $\*$ on the second row (i.e. we have $x\_a, x\_b$, etc...). You can see it that way for the first two rows :

```
|    a_1    |     b_1   |    c_1    |
| x_b | x_c | y_c | x_a | y_a | y_b |

```

We then have the following equations :

* $a\_1 = x\_b + x\_c$
* $b\_1 = y\_c + x\_a$
* $c\_1 = y\_a + y\_b$
* $x\_a + y\_a = a\_2$ and so on.
$6$ equations with $6$ unknowns : you can find the size of each block - you only need to know the number of times each colours appears on rows 1 and 2.

Now create 3 arrays of weights, one for each row :

* On the first row, give weight $0$ to elements of colour $a$, $1$ to elements $b$, $2$ to elements of colour $c$.
* On the second row, give weight $0$ to $x\_b$ elements of colour $b$, weight $1$ to $x\_c$ elements of colour $c$, etc.
* Same on the third row, but with the other colours.

This an be done in $\mathcal{O}(n)$ by simply iterating the arrays (First row and weight array for the first row) and keeping track of how many elements of each colour we have seen so far.

Then sort each row : we obtain the solution described above. The complexity is then $\mathcal{O}(n +f(n))$ where the sorting you use is $\mathcal{O}(f(n))$.

So, now, all you have to do is to find a sorting algorithm that is efficient and that fits the problem : it has to sort by swapping elements. At least quicksort works (and you can find the median easily) so you have $O(n\log(n))$ complexity.

I think you could extend it to linear time using a sorting algorithm that counts.
> 2 votes

# Answer
Here is an algorithm with $O(n)$ time-complexity.

First, count how many counters of each color there are on each row. With $O(n)$ time, we will obtain the number of red counters $r\_i$, the number of white counters $w\_i$, the number of blue counters $b\_i$ on row $i$, $i=1,2,3$.

Second, we can solve the following equations for nonnegative integer variables $a\_k$, $1\le k\le6$ in $O(1)$ time.

$$r\_1 = a\_1 + a\_2$$ $$w\_1 = a\_3 + a\_4$$ $$b\_1 = a\_5 + a\_6$$ $$r\_2 = a\_4 + a\_5$$ $$w\_2 = a\_1 + a\_6$$ $$b\_2 = a\_2 + a\_3$$ $$r\_3 = a\_3 + a\_6$$ $$w\_3 = a\_2 + a\_5$$ $$b\_3 = a\_1 + a\_4$$

Third, we arrange the three rows into the following configuration. $$ \begin{array}{|l|l|l|l|l|l|} \hline a\_1\text{ red} & a\_2\text{ red} & a\_3\text{ white} & a\_4\text{ white} & a\_5\text{ blue} & a\_6\text{ blue} \\\hline a\_1\text{ white} & a\_2\text{ blue} & a\_3\text{ blue} & a\_4\text{ red} & a\_5\text{ red} & a\_6\text{ white} \\\hline a\_1\text{ blue} & a\_2\text{ white} & a\_3\text{ red} & a\_4\text{ blue} & a\_5\text{ white} & a\_6\text{ red} \\\hline \end{array} $$

We are done.

---

Here are a couple of exercises that fill the gap in the above specification of the algorithm.

**Exercise 1.** Find an algorithm that solves in $O(1)$ time that system of 9 equations for nonnegative integer variables $a\_k$, $1\le k\le6$, given the condition that $r\_i+w\_i+b\_i=n$ for all $i$ and $\sum\_{i=1}^3r\_i=\sum\_{i=1}^3w\_i=\sum\_{i=1}^3b\_i=n$. Show that there is always a solution.

**Exercise 2.** Check that arrangement in third step can be done in $O(n)$ time by swapping the counters in each row.

---

Here is a problem that may not be easy to do.

**Problem 1.** Generalize the problem of tricolor arrangement to $m$ rows and $m$ colors, $m\>3$. Solve it with an $O(n)$ algorithm, assuming $m$ is a constant. (Hint, use Hall's marriage theorem to reduce the sum of the number of distinct colors in each row.)
> 2 votes

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


# Question
Title: Assign m agents to N points by minimizing the total distance
Suppose we have $N$ fixed points (set $S$ with $|S|=N$) on the plane and $m$ agents with fixed, known initial positions ($m\<N$) outside $S$. We should transfer the agents so that in our final configuration they are all positioned to different points of $S$. How could we achieve it by minimizing the total distance covered by the agents?

# Answer
> 4 votes
My understanding of this question is that you have a two lists of $n$ two-dimensional coordinates. The first list represents the position of a bunch of agents (robots, maybe, or police cars). The second list represents where those agents need to go (which places need to have police cars dispatched to them), and may be longer than the first list.

It is always possible to minimize the sum distance traveled by all agents, if that's what you're worried about: there are $!n$ ways we could dispatch the robots to new positions, we can enumerate all of them, calculate the distance the agents have to travel, and pick the one that has the least distance. As written, "enumerate all the possibilities" I think counts as an answer to your question, though it's probably not the one you wanted.

There are a couple of more precise questions, all or none of which might be interesting and/or research-level. (I'm not a Theory A person...)

* Is a solution possible if each agent (robot/police officer) has to make a decision independently, or has a limited ability to coordinate with other agents?
* How quickly could the central dispatcher come up with a plan to dispatch everyone most efficiently?

Aaron Roth observes in the comments that this can be solved as a min-cost flow problem. I think that solution looks like this (hopefully I won't make a total fool of myself here): each agent is a source vertex and each dispatch target is an intermediate vertex. There is a capacity-1 edge from each source to a vertex representing the dispatch target, and the cost along that edge is proportional to the distance between the agent's initial position and the dispatch target. There is also a capacity-1, cost-0 edge from each dispatch target vertex to the sink.
* How quickly could the central dispatcher come up with a plan to dispatch everyone that is some multiple of the most efficient solution?

# Answer
> 4 votes
This is an assignment problem which can, for example, be solved by the Hungarian algorithm or by expressing it as linear program. Note that you can adapt your problem to the definition by padding the set of agents with $N-m$ dummy agents which have travel cost $0$ to all nodes.

# Answer
> -1 votes
how about creating tuples of all M agents with N points, sorting them by distance and then greedily picking the first M. this is basically what kruskal does. we could modulate this as a graph where we have a root noe connected to all agents(with edge weight 0) then create all edges from agents to points with the distance as weight, the mst should be the answer we are looking for. is this correct?

---
Tags: algorithms, graphs, optimization
---


title: How to Solve TSP Given Length of Path?

text:
# Question
Title: How to Solve TSP Given Length of Path?
I am trying to devise an algorithm in which given the length of a path that satisfies the constraints of the Traveling Salesman Problem, I can find the path. Currently, my only solution is to find a cost matrix of every possible path and brute force adding them up until I get a solution that equals the length of the path.

Is there a better way to find a TSP path given the length?

# Answer
This decision problem ("does this graph contain a tour of length at most this?") is NP-complete, so you won't find a polynomial-time algorithm most likely.

In addition to the brute-force method you describe, you can have a look at Held-Karp, which solves the problem in $O^\*(2^n)$ time using dynamic programming. For an even more practical solution, you can have a look at the Concorde TSP solver, which has been successfully used to solve instances with tens of thousands of cities optimally.
> 0 votes

# Answer
The additional information can be used by changing the usual LP model to one with an additional constraint that requires the total length to be equal to the known path length (or for numerical safety, bracketed tightly from both sides but not demanding exact equality). This will still result in fractional solutions, but they can be dealt with as usual. Also the overall search is just for *the first* integral solution, so the tree search (if any) is small, only used as a fallback for when the cut-generation algorithms fail to find any cut while the solution is still fractional, and quickly pruned when it tries a bad guess (as this quickly results in infeasibility of the LP model).

In a quick informal test on an instance with 51 cities this helped significantly (finding the result in under 3k simplex pivots vs 13k for solving the same instance normally), but I am comparing my own bad solver against a quick modification of it, which either way does not use any fancy cuts so likely it makes the difference more pronounced than it should be.
> 0 votes

---
Tags: traveling-salesman
---


title: Is $O(T+\log T)= O(T\log T)$?

text:
# Question
Title: Is $O(T+\log T)= O(T\log T)$?
Is $O(T+\log T)= O(T\log T)$?

I think this is true but I do not know how to show it mathematically?

Please show it using the definition.

Also, if it is true, is the following true?

$O((T+\log T)^{1/n})= O((T\log T)^{1/n})$

# Answer
Let $b$ be the base of the logarithm. If $T \> \max(b^2, 2)$, then $\log T =\log\_b T\> 2$. So $$T\log T - (T+\log T) = (T-1)(\log T -1) -1 \> 1\times 1 -1 =0$$ i.e., $T+\log T\< T\log T$.

So, any function that grows asymptotically slower than $T+\log T$ modulo a constant factor also grows asymptotically slower than $T\log T$ modulo the same constant factor. According to the definition of multiple usages of big O-notation, $$O(T+\log T)= O(T\log T)$$

Yes, it is true that $O((T+\log T)^{1/n})= O((T\log T)^{1/n})$, where we consider $n$ as a constant.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Why $xx^TM$ requires $O(dk)$ operations?
Suppose $x \in \mathbb{R}^d$ and $M \in \mathbb{R}^{d \times k}$.

Why $xx^TM$ requires $O(dk)$ operations?

# Answer
The matrix $xx^T$ has the $(i,j)$th entry $x\_i x\_j$. Hence $$ (xx^TM)\_{ij} = \sum\_k (xx^T)\_{ik} M\_{kj} = \sum\_k x\_i x\_k M\_{kj} = x\_i \sum\_k x\_k M\_{kj}. $$ We can compute $\sum\_k x\_k M\_{kj}$ for each $j$ in linear time. Given that, we can compute the product matrix in linear time using the above formula.
> 1 votes

---
Tags: complexity-theory, time-complexity, runtime-analysis
---


# Question
Title: How does the instanceof operator work in the context of downcasting in java?
I am trying to understand the purpose of using the instanceof operator as a way to properly downcast an object in java. I really hope someone can help. Below is more code:

```
public class Test {
    public static void main(String [] args) {
            Dog k = new Dog();
            Animal v = new Dog();
            if (v instanceof Dog){
                k = (Dog)v;

            k.getAnimalName(); // displays Parent Animal
            k.getDogName(); // displays Dog
    }
}

public class Dog extends Animal{
    public void getDogName(){
        System.out.println("Dog");
    }
}

public class Animal{
    public void getAnimalName(){
        System.out.println("Parent Animal");
    }
}

```
1. Confused about how v is an instance of type Dog. Can someone please explain this?
2. Confused about what was displayed in the method calls (referring to k.getAnimalName() and k.getDogName). Is the reason behind why k could call both methods is because the type of k is a subclass of Animal?

# Answer
> 1 votes
new Dog() returns a reference to a Dog object.

Animal v = new Dog () creates a Dog object, and assigns a reference to the variable v. At this point the compiler forgets what kind of object v is a reference to (it is a reference to an Animal or a subclass), but the reference *is* a reference to a Dog object.

v instanceof Dog checks what the object really is. You could have assigned a reference to a Cat object, but you *did* assign the result of new Dog(), so v is actually a Dog object and v instanceof Dog returns true.

(Dog) v would fail if v wasn't really a Dog object, but it is a Dog object (even though it is only declared as an Animal), so the assignment is fine.

---
Tags: java
---


# Question
Title: Polynomial time algorithm - Matching pairs of vertices
Let T be a tree with root r and S a set with an even number of vertices of T. Design a polynomial time algorithm that finds |S|/2 simple and disjoint paths in edges matching pairs of vertices in S. The following figure shows an example in which S consists of the six vertices enclosed in circles and three paths (denoted by three different types of dotted lines) that match those vertices.

**Hint:** Gain intuition by making instances like the one in the figure and observing what happens when you walk the entire border of the tree almost touching it, but not really doing that; then think about how to express the idea of such walk with a recursive algorithm.

I tried to analyze the problem but I don't really understand how to express it as a recursive algorithm, could you help me, please?

# Answer
The idea is to use recursion. Let us suppose that the children of the root $r$ are $v\_1,\ldots,v\_d$, and let $S\_1,\ldots,S\_d$ consist of those elements of $S$ in the subtree rooted at $v\_1,\ldots,v\_d$, respectively.

One easy case is when $r \notin S$ and $|S\_i|$ is even for all $i$. In this case, we can simply recurse on the subtrees. There are two complications that arise in the general case:

1. Some $|S\_i|$ might be odd.
2. The root might belong to $S$.

The two complications are related, but let us tackle them one by one. Suppose first that $r \notin S$. If $|S\_i|$ is odd for some $i$, then we would like to fix that. The only reasonable way is to add $v\_i$ to $S\_i$ if $v\_i \notin S\_i$, and to remove $v\_i$ from $S\_i$ is $v\_i \in S\_i$. We now solve the modified problem recursively, and have to somehow derive a solution for the original problem.

Let us introduce some notation: $O$ is the set of $i$ such that $|S\_i|$ is odd, and $S'\_i$ is the set $S\_i$ after modification (adding or removing $v\_i$). Consider a solution for the new instance. We will derive a solution for the original instance by pairing up the indices in $O$. Suppose that we chose to pair $i,j$, and consider the solutions for $S'\_i,S'\_j$. There are three cases to consider:

1. $v\_i \in S\_i$ and $v\_j \in S\_j$. In this case we add a path from $v\_i$ to $v\_j$ via $r$.
2. $v\_i \notin S\_i$ and $v\_j \notin S\_j$. In this case we add a path from $v\_i$ to $v\_j$ and "erase" $v\_i,v\_j$. That is, in the solution to the new problem, $v\_i$ is connected to some $w\_i$ in its subtree, and $v\_j$ is connected to some $w\_j$ in its subtree. We connect $w\_i$ and $w\_j$ via the path $w\_i-v\_i-r-v\_j-w\_j$.
3. $v\_i \in S\_i$ and $v\_j \notin S\_j$. In this case we add a path from $v\_i$ to $v\_j$ and "erase" $v\_j$. That is, in the solution to the new problem, $v\_j$ is connected to some $w\_j$ in the subtree. We connect $v\_i$ and $w\_j$ via the path $v\_i-r-v\_j-w\_j$.

When $r \in S$, we only have to modify the above strategy a little. We arbitrarily pair $r$ with some $i \in O$, and then proceed much as above. This time there are only two cases:

1. $v\_i \in S\_i$. In this case we simply connect $r$ and $v\_i$.
2. $v\_i \notin S\_i$. In this case we add the edge between $r$ and $v\_i$ and "erase" $v\_i$. That is, in the solution to the new problem, $v\_i$ is connected to some $w\_i$ in its subtree. We connect $r$ and $w\_i$ via the path $r-v\_i-w\_i$.
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis, trees, recursion
---