# Question
Title: Does checking for correctness belong predominantly to "semantic analysis"?
Does checking for correctness belong predominantly to "semantic analysis"?

Or is it reasonable to be done in earlier phases (in a compiler like construction) as well? Mainly in syntax analysis. Or is syntax analysis often/always "formal", rather than semantical?

http://courses.cs.vt.edu/cs1104/Compilers/Compilers.020.html

# Answer
> 2 votes
> Does checking for correctness belong predominantly to "semantic analysis"?

It depends on what you mean with 'correctness'.

1. Correctness of syntax. This is checked during lexical analysis, and incorrect syntactical structures are rejected.
2. Correctness of semantics. During the semantical analysis the compiler rejects statements that are syntactically correct, but are nonsensical semantically. E.g. `10 / "blue"`.
3. Correctness of the effects of code. This has no place in a traditional compiler. A traditional compiler merely takes the code and transforms it into a different form (more) readily acceptable for execution. What the code is supposed to *implement* it does not care about.

However, it is not that black and white, as compilers will often warn about lexically and semantically perfectly legal constructs that are likely to be misinterpreted, e.g. in C++ an assignment inside a conditional:`if (x = 5) ...`.

---
Tags: compilers, semantics, program-correctness
---


# Question
Title: Can type information be encoded in the untyped lambda calculus?
I'm going to take the few pieces of knowledge I have about lambda calculi and ask a pair of very uninformed questions :-)

Is it possible to "embed" the corners of the lambda cube within the untyped lambda calculus?

It would seem that this might lead to a language where the programmer implements the type system in the language, rather than having it already implemented in the compiler. Also, maybe the concept of type system could be generalized to "any arbitrary compile-time or run-time constraint checking". Does such a language already exist?

# Answer
> 4 votes
As mentioned in the comments, it is possible to reduce simply typed lambda calculus to untyped lambda calculus. This is the approach associated with Alonzo Church, called "Church Types" or "intrinsic types". Here, types are embedded in the language, and are intrinsic to the language. Still, the language can be stripped of it's types.

However, it is also possible to construct simply typed lambda calculus from untyped lambda calculus. This approach is associated with Haskell Curry, called "Curry Types" or "extrinsic types". Here, types can be derived from the AST of the language.

The latter type is what you are looking for. A thorough overview of the subject is here

---
Tags: programming-languages, lambda-calculus, typing, type-checking
---


# Question
Title: Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well
My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof.

I've tried to prove it myself but I got stuck at the Inductive Step.

---

Let $G=(V,T,P,S)$ be a context free grammar.

Prove by induction on $n$ where $n\geq 1$ that:

For every $w\in T^\*$ and for every $\alpha\in (V\cup T)^+$ , if $\alpha \Rightarrow^n w$ then $\alpha \overset{\_{lm}}{\Rightarrow}^n w$

I.e

$\forall w\in T^\*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^n w \rightarrow \alpha \overset{\_{lm}}{\Rightarrow}^n w$

(The **leftmost derivation relation** is denoted as $\overset{\_{lm}}{\Rightarrow}$)

(From a high level point of view the claim says that if some terminal word $w$ can be derived form $\alpha\in (V\cup T)^+$ then there exist a leftmost derivation to derive $w$ from $\alpha$)

---

My try:

**Basis**

If $n=1$ then we must show that $\forall w\in T^\*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^1 w \rightarrow \alpha \overset{\_{lm}}{\Rightarrow}^1 w$:

Let $w\in T^\*$ and let $\alpha\in (V\cup T)^+$ such that $\alpha \Rightarrow^1 w$.

by definition of the $\Rightarrow$ relation we get that:

$\exists \psi,\chi,\gamma\in(V\cup T)^\*, \exists A\in V, \alpha = \psi A \chi \land w=\psi \gamma \chi \land (A\rightarrow \gamma)\in P$

Now since $w\in T^\*$ and since $w=\psi\gamma\chi$ we get that $\psi \in T^\*$ and so:

$\exists \psi\in T^\*,\exists \chi,\gamma\in(V\cup T)^\*, \exists A\in V, \alpha = \psi A \chi \land w=\psi \gamma \chi \land (A\rightarrow \gamma)\in P$

And we get by definition of $\overset{\_{lm}}{\Rightarrow}$ relation that $\alpha \overset{\_{lm}}{\Rightarrow} w$ as was to be shown.

**Induction hypothesis**

Suppose that for some $n=k\geq 1$ we get: $\forall w\in T^\*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^k w \rightarrow \alpha \overset{\_{lm}}{\Rightarrow}^k w$

**Induction step**

Now we'll prove that: $\forall w\in T^\*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^{k+1} w \rightarrow \alpha \overset{\_{lm}}{\Rightarrow}^{k+1} w$

Let $w\in T^\*$ and let $\alpha \in (V\cup T)^+$ such that $\alpha \Rightarrow^{k+1} w$,
And so we get that $\exists \beta \in (V\cup T)^\*$ such that $\alpha\Rightarrow\beta\Rightarrow^k w$.
Since $k\geq 1$ we get that $\beta \in (V\cup T)^\*V(V\cup T)^\*$ and so $\beta\in(V\cup T)^+$.
Now since $w\in T^\*$ and since $\beta \Rightarrow^k w$ we get by the induction hypothesis that $\beta \overset{\_{lm}}{\Rightarrow}^k w$

***Now I do not know how to proceed.***

I got that $\alpha \Rightarrow^1 \beta$ but how can I show that $\alpha \overset{\_{lm}}{\Rightarrow}^1 \beta$ and from there conclude that $\alpha \overset{\_{lm}}{\Rightarrow}^{k+1} w$ using the facts I've shown above?

---

thanks for any help.

# Answer
> 5 votes
Your method of proof can't work, since it implies that *every derivation is a leftmost derivation*. Indeed, here is a paraphrase of your proof:

> Let's prove by induction on the length of the proof that if a word $w$ can be derived from a sentential form $\alpha$ in $n$ steps, then $w$ can be derived from $\alpha$ in $n$ steps using a leftmost derivation. The case $n = 0$ is trivial. Now suppose that $n \> 0$, and suppose that the first step of the derivation is $\alpha \Rightarrow \beta$. By induction, $\beta \Rightarrow^\* w$ can be converted to a leftmost derivation of length $n-1$, so $\alpha \Rightarrow \beta \Rightarrow^\* w$ would be a leftmost derivation of length $n$.

Unrolling the proof, your suggested derivation is actually the same as the original derivation (prove it by induction!), and since not all derivations are leftmost, since can't work.

Concretely, consider the derivation $AB \Rightarrow Ab \Rightarrow ab$. The first step $AB \Rightarrow Ab$ cannot belong to a leftmost derivation. Answering your question, you can't prove that $\alpha \stackrel{lm^1}{\Rightarrow} \beta$, simply because it isn't true.

---

Here is a different approach. Consider the derivation tree used to derive $\alpha$ from $w$. Try to use this tree to generate a leftmost derivation. Note that the length of the derivation is exactly the number of nonleaf nodes in the tree.

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


# Question
Title: Context-free grammar for"not-at-all" palindromes
I need to bulid a context-free grammar for

$\qquad \mathscr{L\_4}=\\{w\in\\{a,b,c\\}^\* \mid w\text{ is not palindrome at all}\\}$

**Not palindrom at all:** We will say that a word $w$ is *not palindrome at all* if **for all** $i$ such that $1\leq i\leq |w|$ the $i$ letter from the beginning of $w$ is not the same like the $i$ letter of $w$ from the end, for example $abbacb\in \mathscr{L\_4}$ but $ca\color{gray}bba\color{gray}bcb\notin\mathscr{L\_4}$, the word must contain a even number of digits, because if there were an odd number of digits, so the middle digit "equals to itself".

**My attempt:** Let's denote $S\_{\text{pal}}$ from palindrome grammar and $S\_{\neg\text{pal}}$ for the not palindrome at all grammar

$$\\S\_{\neg\text{pal}}\to a S\_{\neg\text{pal}}b\big|bS\_{\neg\text{pal}}a\big|aS\_{\neg\text{pal}}c\big|cS\_{\neg\text{pal}}a\big|cS\_{\neg\text{pal}}b\big|cS\_{\neg\text{pal}}b\big|\epsilon$$

Similar question here. I'm not sure if my attempt is correct or not

# Answer
Your attempt looks correct to me

$$\\S\_{\neg\text{pal}}\to \color{red}a S\_{\neg\text{pal}}\color{blue}b\big|\color{blue}bS\_{\neg\text{pal}}\color{red}a\big|\color{red}aS\_{\neg\text{pal}}\color{green}c\big|\color{green}cS\_{\neg\text{pal}}\color{red}a\big|\color{blue}bS\_{\neg\text{pal}}\color{green}c\big|\color{green}cS\_{\neg\text{pal}}\color{blue}b\big|\varepsilon$$

Let us say that for a word of length $n$ such that $n\in\mathbb{N}$ is even for each letter in the $i$ from the begining $1\leq i\leq n$ you ensure that in the place $i$ from the end you have a diffrent letter

for example: $\color{red}a\color{blue}b\color{green}c\color{blue}b\color{red}a\color{blue}b\in \mathscr{L\_4}$
> -1 votes

# Answer
Just use something like:

$ S \rightarrow a S b \mid a S c \mid b S a \mid b S c \mid c S a \mid c S b \mid a b \mid a c \mid b a \mid b c \mid c a \mid c b $

This ensures the $i$-th symbol from the beginning is different from the $i$-th from the end.
> 0 votes

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


# Question
Title: How to do last step of Krom's algorithm for solving 2SAT problems
I was making a program for solving 2 SAT problems, using Krom's algorithm. I did not found a lot of information searching in Google, so I used Wikipedia's description of Krom's algorithm to implement it but I'm stuck in the last step.

If I understand it well, the algorithm could be resumed in this:

1) You have to reduce your original 2 CNF boolean formula using Krom's inference rule as much as you can:

```
(a or b) and (¬a or c) => (b or c)

```

2) While preserving consistency, for each variable in the original formula, you must add **only** one of these **special clauses**: **(x or x)** and **(¬x or ¬x)**.

(For Krom, a formula is consistent if there aren't both of these special clauses at the same time in the formula)

3) You assign to each variable TRUE or FALSE depending on which of these **special clauses** has been added to the formula. If the variable x has the special clause **(x or x)** then we assign **TRUE to x**; and if the variable y has the special clause **(¬y or ¬y)** then we assign **FALSE to y**.

**4) This is the step where I am stuck.**

My problem is that I don't know what to do once I have made the assignments to the variables. And the last paragraph of the Wikipedia describing the algorithm doesn't explain it clearly. Do I have to check satisfiability on this formula or also in the original formula as well?

Furthermore, for example:

I have this formula:`(a or b)`

Then I add for each variable its special clause (as the algorithm doesn't specify which of them you should pick) like this `(a or b) and (¬a or ¬a) and (¬b or ¬b)`

So I assign to the variables a and b the value FALSE, but then the first clause (the clause on the original formula) **becomes false**. What do I do in that case? Could somebody explain me the last step of Krom's Algorithm for solving 2SAT problems?

# Answer
The first step in implementing an algorithm is understanding why it works.

In your case, Krom's algorithm is based on repeated application of the resolution rule $$ \begin{array}{c} a \lor b \qquad \bar{a} \lor c \\\hline b \lor c \end{array} $$ Here $a,b,c$ are literals. This rule is valid, and applied to two 2-clauses produces a 2-clause. Hence there is no harm in running it until reaching a point at which it can be applied no more. If in this way we reach a clause $a \lor a$, then the literal $a$ must be true. So if we reach both $a \lor a$ and $\bar{a} \lor \bar{a}$, there is no solution.

More interestingly, if all solutions have $a$ set to true, then the *completeness* of resolution implies that $a \lor a$ will be generated.

This suggests the following algorithm:

1. Generate all 2-clauses reachable by resolution.
2. If you have generated both $a \lor a$ and $\bar{a} \lor \bar{a}$ for some variable $a$, then there is no solution.
3. Otherwise, if for some variable $a$ we have generated neither $a \lor a$ nor $\bar{a} \lor \bar{a}$, add one of them as you please and go back to step 1.
4. Output the truth assignment satisfying all literals $a$ for which we have generated $a \lor a$.

This is just one implementation; others are possible. (For example, we could immediately substitute any known values before step 3.)

Back to your example: $a \lor b$. Step 1 produces no new clauses. The variable $a$ is "free", so in step 3 we add (say) $\bar{a} \lor \bar{a}$. Step 1 is now more interesting: $$ \begin{array}{c} a \lor b \qquad \bar{a} \lor \bar{a} \\\hline b \lor \bar{a} \end{array} \\ \begin{array}{c} a \lor b \qquad b \lor \bar{a} \\\hline b \lor b \end{array} $$ We can now read off the truth assignment $a=F,b=T$.

Had we added $a \lor a$ instead, step 1 would still not do anything, and so we would add either $b \lor b$ or $\bar{b} \lor \bar{b}$ in step 3, and then read off one of the truth assignment $a=T,b=T$, $a=T,b=F$.
> 4 votes

---
Tags: algorithms, 2-sat
---


# Question
Title: Context free languages belongs to NTIME(n)?
As the question states, how do we prove that for every L ∈ L2 (context-free class of languages) is true that L ∈ NTIME(n)?

Can anyone point me to a proof or outline it here? Thanks!

# Answer
> 1 votes
Hint: Every context-free language is accepted by a pushdown automaton.

# Answer
> 0 votes
It is actually in P, the CYK algorithm deterministically parses any string of length $n$ in time $O(n^3)$

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


# Question
Title: Query on consequences of $\mathsf{P=BPP}$
We know $\mathsf{P=BPP} \implies \mathsf{NEXP\not\subseteq P/Poly}$ or permanent does not have polynomial sized circuits. However permanent needs superpoly circuits imply $\mathsf{NEXP\not\subseteq P/Poly}$ since $\mathsf{P^{\\#P}\subseteq PSPACE\subseteq NEXP}$. So why dont we just say $\mathsf{P=BPP} \implies \mathsf{NEXP\not\subseteq P/Poly}$?

# Answer
The conclusion is that the permanent does not have polynomial-size (constant-free) *arithmetic* circuits or $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$. Permanent not having polynomial-size constant-free arithmetic circuits is not known to imply $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$.

However, there are a couple more recent similar results whose conclusion is not a disjunction, but simply a lower bound on some polynomial family in $\mathsf{NEXP}$:

* Jansen and Santhanam showed that if PIT is in $\mathsf{NSUBEXP}$ then there is a family of polynomial whose integer evaluation problem is in $\mathsf{NEXP}$ but which do not have poly-size constant-free arithmetic circuits.
* Carmosino, Impagliazzo, Kabanets, and Kolokolova show that if PIT over a fixed finite field is in $\mathsf{NSUBEXP}$ then there is a multilinear polynomial whose evaluation problem over that same finite field is in $\mathsf{NE}$ that does not have poly-size arithmetic circuits. (This paper also has many other results of interest, including true hardness-to-randomness *equivalences*, avoiding many of the usual caveats.)
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Number of finite strings over a countably infinite alphabet
If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite?

# Answer
It's countable. The set $S\_\ell$ of strings of length $\ell$ is $\Sigma\times\dots\times\Sigma$, which is a finite product of countable sets, so is countable. Now, the set of all finite strings is $\bigcup\_{\ell\geq 0}S\_\ell$, which is a countable union of countable sets, which is countable.

Usually, you can only get an uncountable set from countable ones by taking the power set.
> 8 votes

# Answer
For a countably infinite alphabet A; AxN is also countably infinite...where Nis the set of natural numbers.(finite product of countable sets)

A finite string is a finite subset of AxN.( An ordered set of symbols)

Set of all finite subsets of a countably infinite set is countably infinite.(why)
> 0 votes

---
Tags: combinatorics, sets, uncountability
---


# Question
Title: Using Context free language to simulate regular expression in finite automata
Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n number of non-terminal to store n states in the NFA?

# Answer
> 6 votes
No such non-trivial bound can be obtained. Consider the language $L\_n = \\{ 0^{kn} : k \in \mathbb{N}\\}$. Any NFA for $L\_n$ needs at least $n$ states, but it can be generated by a context-free grammar with only one non-terminal: $S\to 0^nS|\epsilon$.

---
Tags: formal-languages, regular-languages, finite-automata, formal-grammars, lower-bounds
---


# Question
Title: Lower bound for number of nonterminals in a CFG
Let's say we have a context-free grammar for the language $a\mbox{\*}b\mbox{\*}c\mbox{\*}$. Is there a way to determine a lower bound for the number of nonterminals in this grammar? I'm pretty sure you need at least 2, but I haven't been able to prove it.

# Answer
You need at least two non-terminals here. For suppose not. A rule of the form $S \to \alpha$ cannot include two copies of $S$, since otherwise it would generate a word of the form $\cdots b \cdots a \cdots$ (since $S$ generates $b,a$). A rule of the form $S \to x S y$ (where $x,y$ are words) cannot mention the letter $b$ for similar reasons. The only rules mentioning $b$ are thus of the form $S \to w$ (where $w$ is a word). It follows that every word generated by the grammar has a bounded number of $b$s (since at most one rule of the form $S \to w$ can be applied when generating a given word), so it doesn't generate all of $a^\*b^\*c^\*$.

In contrast, you can generate the language using two non-terminals: $S \to aS|Sc|B$, $B \to Bb|\epsilon$. Therefore the minimum number of non-terminals needed to generate this language is two.
> 3 votes

---
Tags: formal-languages, context-free, formal-grammars, lower-bounds
---


title: *non-uniform* $ACC^0$ and above classes

text:
# Question
Title: *non-uniform* $ACC^0$ and above classes
$NEXP$ smallest class above $ACC^0$ that we know is separated from $ACC^0$.

We do not know if either $NP$ or $P/poly$ is in $ACC^0$.

Suppose every problem in $NP$ can be solved in polynomial time with polynomial sized advice string (that is $NP\subseteq P/poly$ holds) however the circuit that computes it needs only $ACC^0$ type structure?

Would that mean $NP$ is in *non-uniform* $ACC^0$ or *uniform* $ACC^0$?

# Answer
It would imply that NP is in non-uniform ACC0. While in some circumstances non-uniformity can be removed, this one doesn't seem to be one of them, though you never know...
> 1 votes

---
Tags: complexity-theory, circuits
---


# Question
Title: Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$
With the context-free grammar in Chomsky's form:$$S\to BA|AC|b\\A\to AA|AB|CC|a\\B\to AS|BB|CA\\C\to AB|SS|b$$

I need to:

> 1. run the CYK (Cocke-Younger-Kasami) algorithm and decide if I can derive the word $baabb$ from the context.
> 2. write the left derivation.

**My try:**

$1.$

$$ \begin{array}{c|lcr} i\bigg/j & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \text{C,S} & \text{B} & \square& \square &\square \\ 2 & \quad\blacksquare & \text{A} & \text{A} & \square & \square \\ 3 & \quad\blacksquare & \quad\blacksquare & \text{A} & \text{S,B} & \square \\ 4 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} & \text{A,C} \\ 5 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} \\ \end{array} $$

2. $S\Longrightarrow BA \Longrightarrow CAA \Longrightarrow bAA\Longrightarrow bAACC\Longrightarrow baabb$

I'm stuck here in the table construction. How should I fill in the empty squares?

# Answer
Watch this video and you should get:

$$ \begin{array}{c|lcr} i\bigg/j & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & \text{C,S} & \text{B} & \text{B,S} & \text{A,B,C} & \text{B,C,$\color{red}{\text{S}}$,A} \\ 2 & \quad\blacksquare & \text{A} & \text{A} & \text{B,C,A,S} & \text{A,B,C} \\ 3 & \quad\blacksquare & \quad\blacksquare & \text{A} & \text{S,B} & \text{A,S,C} \\ 4 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} & \text{A,C} \\ 5 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} \\ \end{array} $$

Since S is in the left and higher corner so we can derivate the word $baabb$ from the context
> 2 votes

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


title: Has connect 4 in 3D been studied in CS?

text:
# Question
Title: Has connect 4 in 3D been studied in CS?
Connect 4 is a classical game in computer science. Recently I found a web game where one could play the game on a 3d board. One version can be found here

https://www.mathsisfun.com/games/connect3d.html

I know Connect 4 has been completed, and developed algorothms for solving it. Like the minmax strategy.

Algorithms for Connect 4?

**My question is: Is there written any articles / done research on connect 4 in 3D before?** Has there been developed any algorithms etc?

# Answer
I couldn't find anything on that particular game, but I found an analysis of a similar game called qubic in Victor Allis' PhD thesis chapter 4: http://fragrieu.free.fr/SearchingForSolutions.pdf

It is essentially Connect 4 in 3D without gravity.
> 2 votes

---
Tags: reference-request, board-games
---


# Question
Title: What's this type of semantic analysis called in NLP?
I'm speculating that this is very much known in NLP, but as I've not studied NLP, I don't know what concepts are related to this:

Basically I have entities that are connected by some strings. I want to do semantic analysis using this kind of constructs. I.e. by checking whether a given sentence has entities (the yellow ellipses) connected with the right strings.

---

Notice that this is also basically describable as a a deterministic context-free language. But I'd like to understand the semantical aspect of this, rather than mere parsing (string matching).

# Answer
Given your example, **Lexical Semantics** may be what you are looking for. Things like WordNet provide hypernym (breakfast -\> meal), hyponym (meal -\> lunch), meronym (course -\> meal), holonym (water -\> oxygen) relationships. See chapter 19 of *Speech and Language Processing* by Jurafsky and Martin for more thorough set of details.
> 1 votes

---
Tags: terminology, natural-language-processing
---


# Question
Title: Calculating integral without quadratures
Is there any other options of calculating integral instead of using quadratures? I know that also we can calculate spline function or use monte-carlo method but do you know something else?

# Answer
> 1 votes
Another approach is to use a computer algebra to compute the integral exactly, symbolically.

See also Wikipedia's article on symbolic integration. Wikipedia also has a list of techniques and computational methods for integration.

---
Tags: numerical-analysis, numerical-algorithms
---


# Question
Title: Counting the number of permutations of string with given repeated interwoven subsequence
Given string $S$ of length $n$, count the number of distinct permutations $P\_n$ of a string of length $2n$ such that each of them contains $S$ twice as an interwoven subsequence.

Example. $S=abc$. There are 5 permutations: $abcabc$, $abacbc$, $ababcc$, $aabcbc$, $aabbcc$.

If each character of $S$ appears only once, the problem becomes easier. Consider all binary strings of length $2n$ with $n$ zeros and $n$ ones. Zeros represent the first subsequence and ones represent the second subsequence. Whenever there is a binary string with some prefix that contains more ones than zeros, we may repaint the binary string in a way that both the original binary string and the repainted binary string represent the same permutation, and that no prefix of the repainted binary string has more ones than zeros.

Therefore we may restrict ourselves to the binary strings where for each prefix the number of zeros equals or is greater than the number of ones. Because each character of $S$ appears only once, each such binary string represent a distinct permutation. There is a simple recursive method to generate such binary strings, and by applying dynamic programming it is possible to calculate $P\_n$ in $O(n^2)$ time. Apparently for this special case $P\_n$ eqals the n'th Catalan number $C\_n$, so it should be possible to get it done with $O(n)$ multiplications.

When some characters of $S$ appear more than once, or there are common substrings, $P\_n\<C\_n$. For $S=aaa$ the number is 1, for $S=aab$ it is 3, and for $S=aba$ it is 4. So now my questions are:

1. How to find $P\_n$ in a way that is faster than generating all $C\_n$ permutations and counting the unique ones?
2. The general case. Given $S$,$n$,$k$, count the number of distinct permutations of a string of length $kn$ such that each of them contains $S$ $k$ times as an interwoven subsequence. How to do this faster than generating all the plausible permutations and counting the unique ones?

# Answer
It's possible to count the number of such strings in something like $O(2^{n})$ time. This is faster than generating all permutations (as $n! \sim 2^{n \log n + O(n)}$), but it's still not polynomial time. I don't know if the number of such strings can be counted in polynomial time.

Here's how to do it. You can build a NFA that accepts all such strings of length $2n$, and only such strings. The NFA will have $O(n^2)$ states and be acyclic: it has $2n$ levels, and each level has $\le n$ states in it, and each transition goes from one level to the next level. Each state in the NFA is of the form $(i,j)$, representing that we've already consumed the first $i$ characters of the first copy of $S$ and the first $j$ characters of the second copy of $S$.

So now the task reduces to counting the number of strings accepted by this (acyclic) NFA. Unfortunately, counting the number of strings accepted by an (acyclic) NFA is #P-complete in the general case, so there's no polynomial-time algorithm that works for all (acyclic) NFAs. (This doesn't rule out the possibility of a specialized algorithm that somehow takes advantage of the special structure of this particular NFA, but personally, I don't see any way to construct such an algorithm.)

That said, there are two techniques that are available here:

1. We *can* count the number of strings accepted by this NFA in exponential time. First, convert the NFA to a DFA via the product construction. You obtain an acyclic DFA with at most $2n \times 2^n$ states. Since this DFA is acyclic, you can then count the number of words accepted by it in time linear in the number of states using dynamic programming. Therefore, the total running time will be something like $O(n \cdot 2^n)$.

See also https://cstheory.stackexchange.com/q/8200/5038.
2. Alternatively, you can compute an approximation to the number of such strings, much more efficiently -- but the approximation will be rather inexact. See Counting the number of words accepted by an acyclic NFA for details of how to do that.

I don't know if there are better techniques for your problem, or if there's any method to solve your problem in polynomial time.
> 2 votes

---
Tags: combinatorics, subsequences
---


# Question
Title: Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?
Consider a nondeterministic Mealy machine, $M$, defined as follows: $M = (Q, \Sigma, \Delta, \delta, \tau, q\_0)$ where

1. $Q$ is a finite set of states
2. $\Sigma$ is an input alphabet
3. $\Delta$ is an output alphabet
4. $\delta : Q \times \Sigma\_{\varepsilon} \to \mathcal{P}(Q)$ is the transition function
5. $\tau : Q \times \Sigma\_{\varepsilon} \to \mathcal{P}(\Delta)$ is the output function
6. $q\_0 \in Q$ is the start state

Let $M(x)$ for $x \in \Sigma^\*$ denote the set of all strings that $M$ could output on input $x$. Note that $M$ could fail to process the entirety of its input, and thus a string is output only if $M$ processes all of its input. Also, we define, for $L \subset \Sigma^\*$, $M(L) = \bigcup\limits\_{w \in L} M(w)$. Given this, if $L$ is regular, does it follow that $M(L)$ is regular?

I've attempted to solve this by first showing that for every non-deterministic Mealy machine, there exists an equivalent deterministic Mealy machine. By "equivalent" I mean that the input-output behavior of the two is identical. The problem, however, is that the output function for a deterministic Mealy machine can only output a single character at a time. How, then, could I get the simulating deterministic Mealy machine to output a set of strings?

# Answer
There is no reason to convert the Mealy machine to a deterministic one – indeed, this is not always possible. Suppose that the input alphabet is unary but the output is binary. A deterministic machine has one output of each length, but a non-deterministic machine can have many.

Instead, the idea is to construct an NFA which keeps track of both the Mealy machine $M$ and a machine $T$ accepting $L$. Denote by $w$ the (unknown) word in $L$ on which we run $M$. At each point in time we guess the next symbol in $w$ and transition in $T$, guess a corresponding transition in $M$, and "accept" the symbol output by the $M$-transition (if any). The accepting states of the NFA are those in which $T$ is at an accepting state.

I'll let you go over the details.
> 1 votes

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


# Question
Title: Find a regular language that is "infinitely between" two other regular languages
Suppose I have two regular languages $L\_{1}$ and $L\_{2}$ such that $L\_{1} \subseteq L\_{2}$ and $L\_{2} - L\_{1}$ is infinite. I want to find another regular language $L\_{3}$ such that $L\_{1} \subseteq L\_{3} \subseteq L\_{2}$ and both $L\_{2} - L\_{3}$ and $L\_{3} - L\_{1}$ are infinite.

My solution to this problem is choosing $L\_{1} = \\{a\\}$ (or some other single word in the language), $L\_{3} = \Sigma^{+}$, and $L\_{2} = \Sigma^{\*}$.

Are these choices valid? I think that $\Sigma^{+} - \\{a\\}$ is infinite, but I am unsure whether or not $\Sigma^{\*} - \Sigma^{+}$ is infinite.

# Answer
> 8 votes
Because regular languages are closed under complement and intersection, $L\_2 - L\_1$ is regular. Because it's also infinite, it contains words of arbitrarily large lengths.

Therefore, by the pumping lemma, there exist some words $x$, $y$, and $z$ such that the concatenation $x y^k z$ is in $L\_2 - L\_1$ for all $k \geq 0$.

Now consider the language $L'$ consisting of all words of the form $x y^{2k} z$ - that is, words where the $y$ is repeated an even number of times. Clearly, $L'$ is regular and infinite, and so is $L\_2 - L\_1 - L'$, since it contains all strings $x y^k z$ where $k$ is odd. Therefore, setting $L\_3 = L\_1 \cup L'$ satisfies the problem.

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


title: Sum of all products of subarrays

text:
# Question
Title: Sum of all products of subarrays
For any three-dimensional array $A$ of size $n\_1 \times n\_2 \times n\_3$ let $P(A)$ be the product of all its elements, i.e. $$P(A) = \prod\_{i\_1 = 1}^{n\_1} \prod\_{i\_2 = 1}^{n\_2} \prod\_{i\_3 = 1}^{n\_3} a\_{i\_1,i\_2,i\_3}.$$

A subarray (cf. submatrix) of $A$ is given deleting rows in any of the tree dimensions. For e.g. the $3 \times 3 \times 3$ array $B$ with elements $b\_{ijk}$: $$B = \left( \begin{array}{ccc} \left( \begin{array}{c} b\_{1,1,1} \\ b\_{1,1,2} \\ b\_{1,1,3} \end{array} \right) & \left( \begin{array}{c} b\_{1,2,1} \\ b\_{1,2,2} \\ b\_{1,2,3} \end{array} \right) & \left( \begin{array}{c} b\_{1,3,1} \\ b\_{1,3,2} \\ b\_{1,3,3} \end{array} \right) \\ \left( \begin{array}{c} b\_{2,1,1} \\ b\_{2,1,2} \\ b\_{2,1,3} \end{array} \right) & \left( \begin{array}{c} b\_{2,2,1} \\ b\_{2,2,2} \\ b\_{2,2,3} \end{array} \right) & \left( \begin{array}{c} b\_{2,3,1} \\ b\_{2,3,2} \\ b\_{2,3,3} \end{array} \right) \\ \left( \begin{array}{c} b\_{3,1,1} \\ b\_{3,1,2} \\ b\_{3,1,3} \end{array} \right) & \left( \begin{array}{c} b\_{3,2,1} \\ b\_{3,2,2} \\ b\_{3,2,3} \end{array} \right) & \left( \begin{array}{c} b\_{3,3,1} \\ b\_{3,3,2} \\ b\_{3,3,3} \end{array} \right) \end{array} \right)$$ one can form a subarray $B'$ of $B$ by deleting the first row in the first dimension, the second row in the second dimension, and keeping all of the third dimension: $$B' = \left( \begin{array}{cc} \left( \begin{array}{c} b\_{2,1,1} \\ b\_{2,1,2} \\ b\_{2,1,3} \end{array} \right) & \left( \begin{array}{c} b\_{2,3,1} \\ b\_{2,3,2} \\ b\_{2,3,3} \end{array} \right) \\ \left( \begin{array}{c} b\_{3,1,1} \\ b\_{3,1,2} \\ b\_{3,1,3} \end{array} \right) & \left( \begin{array}{c} b\_{3,3,1} \\ b\_{3,3,2} \\ b\_{3,3,3} \end{array} \right) \end{array} \right).$$

For a given three-dimensional array $A$ with elements only being $1$ or $-1$, I want to compute the sum of $P(A')$ for all subarrays $A'$ of $A$: $$\sum\_{A' \text{ subarray of } A} P(A').$$

Is there a clever way to do this? Can it be done in polynomial time?

In other words, I want to compute

$$\sum\_{S\_1,S\_2,S\_3} \prod\_{i\_1 \in S\_1} \prod\_{i\_2 \in S\_2} \prod\_{i\_3 \in S\_3} a\_{i\_1,i\_2,i\_3},$$

where $S\_i$ ranges over all non-empty subsets of $\[n\_i\] = \\{1,\dots,n\_i\\}$

Some observations I have made: A subarray is uniquely determined by which rows are kept from the original array. For example, in the case above $B'$ is determined by saying that we keep rows $2,3$ in the first dimension, rows $1,3$ in the second dimension and rows $1,2,3$ in the third dimension. So, for a $n\_1 \times n\_2 \times n\_3$ array $A$, we get one subarray for each triple of subsets $(l\_1,l\_2,l\_3)$, where $l\_1 \subset \\{1, \dots, n\_1\\}$ and so on. This gives a total of $(2^{n\_1} - 1)(2^{n\_2} -1)(2^{n\_3} -1)$ subarrays, so a naive approach is out of the question if we want to compute the sum in polynomial time.

If a subarray is given by $(l\_1,l\_2,l\_3)$ then another subarray is given by $(l\_1 \setminus \[n\_1\], l\_2 \setminus \[n\_2\], l\_3 \setminus \[n\_3\])$, so if you compute $P$ for one subarray, you get the other one "for free", if you know what $P$ for the whole array is. Maybe this can be used to do some clever thing, but I can't see it.

Here is a table of the products for the $2 \times 2 \times 2$ case, each row are the elements we want to multiply together in one product, and the result will be the sum of the products: $$\begin{array}{llllllll} b\_{1,1,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,1,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,2,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{2,1,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{2,1,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{2,2,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{2,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,1,1} & b\_{1,1,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,1,1} & b\_{1,2,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,1,1} & b\_{2,1,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,1,2} & b\_{1,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,1,2} & b\_{2,1,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,2,1} & b\_{1,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,2,1} & b\_{2,2,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,2,2} & b\_{2,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{2,1,1} & b\_{2,1,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{2,1,1} & b\_{2,2,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{2,1,2} & b\_{2,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{2,2,1} & b\_{2,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,1,1} & b\_{1,1,2} & b\_{1,2,1} & b\_{1,2,2} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,1,1} & b\_{1,1,2} & b\_{2,1,1} & b\_{2,1,2} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,1,1} & b\_{1,2,1} & b\_{2,1,1} & b\_{2,2,1} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,1,2} & b\_{1,2,2} & b\_{2,1,2} & b\_{2,2,2} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,2,1} & b\_{1,2,2} & b\_{2,2,1} & b\_{2,2,2} & \text{} & \text{} & \text{} & \text{} \\ b\_{2,1,1} & b\_{2,1,2} & b\_{2,2,1} & b\_{2,2,2} & \text{} & \text{} & \text{} & \text{} \\ b\_{1,1,1} & b\_{1,1,2} & b\_{1,2,1} & b\_{1,2,2} & b\_{2,1,1} & b\_{2,1,2} & b\_{2,2,1} & b\_{2,2,2} \end{array}$$

## The one-dimensional case

If we have a one-dimensional array $A$, we can just as well consider $A$ to be a set and compute: $$\sum\_{A' \subseteq A} \prod\_{x \in A'} x$$ which can be computed by considering the polynomial $$p(x) = \prod\_{a \in A} (x-a)$$ and if we expand this polynomial to $$p(x) = \sum\_{j=0}^n \alpha\_j x^j$$ the coefficient $\alpha\_j$ is the sum of all products of $n - j$ elements in $A$, so to get total sum we just need to sum the $\alpha$. Computing the coefficients $\alpha\_j$ can be done in polynomial time.

# Answer
> 4 votes
This is a partial solution for the case of a two-dimensional $A$ with entries in $\\{+1, -1\\}$.

First, some notation.

As above, for a given array $A$, let $P(A)$ denote the product of all the entries in $A$. Further, we'll define $S(A)$ to be the sum of all $P(B)$ where $B$ is a subarray of $A$.

For a given array $A$ with index sets $I\_1 \times I\_2 \times \ldots$, we identify a subarray $B$ of $A$ by a tuple of subsets $S\_1 \times S\_2 \times \dots$ where $\emptyset \neq S\_j \subseteq I\_j$. We will denote $B = A\[S\_1, S\_2, \ldots\]$.

**Lemma 1**: Let $A$ be a one-dimensional array (i.e.: vector) of length $n$ with entries in $\\{+1, -1\\}$. If $A$ consists solely of $+1$ entries, then $S(A) = 2^n-1$; otherwise if $A$ contains any $-1$ entries, then $S(A) = -1$.

**Proof**: Left as an exercise to the reader

Let $A$ be a $n\_1 \times n\_2$ two-dimensional array (i.e.: matrix) with entries in $\\{+1, -1\\}$. For a fixed $T \subseteq \[n\_2\]$, we can easily compute the sum

$$S\_T := \Sigma\_{S \subseteq \[n\_1\]} P(A\[S, T\])$$

by reducing the two-dimensional problem to the one-dimensional one. Note that $$S(A) = \Sigma\_{\emptyset \neq T \subseteq n\_2} S\_T$$ Let us treat $A$ as a set of $n\_2$ vectors, each of length $n\_1$. In this way, the subarray $A\[\[n\_1\], T\]$ (with $T \subseteq \[n\_2\]$) can be considered a set of vectors $\\{v\_i | i \in T\\}$. Consider the vector $u$ where $u\[j\] = \Pi v\_i\[j\]$, i.e.: the $j^{th}$ entry of $u$ is the product of the $j^{th}$ entries of all the $v\_i$. From Lemma 1, we know that if all the elements of $u$ are $+1$, then the required sum is $2^{n\_1}-1$; otherwise, it is $-1$. We'll call $T$ *degenerate* in the former case and *non-degenerate* in the latter.

Of course, this alone doesn't quite help us enough because there are still exponentially many subsets $T \subseteq \[n\_2\]$. So, lets try to understand exactly which subsets $T$ are degenerate. Evidently , $T$ is degenerate iff for all $1\leq j\leq n\_1$ there are an even number of $-1$s in $\\{v\_i\[j\] | i \in T\\}$. Now, when we see situations involving the parity of entries over an array, the first thing we should think about is translating things over to $\mathbb{Z}\_2$, the field over 2 elements.

**Define:** For an array $A$ with entries in $\\{+1,-1\\}$, we define the array $A'$ by mapping each entry in $A$ according to $+1\mapsto 0$ and $-1 \mapsto 1$. We will typically understand the entries of $A'$ to be elements of $\mathbb{Z}\_2$.

**Lemma 2:** A subset $T \subseteq \[n\_2\]$ is degenerate iff the vector sum $\Sigma\_{i\in T} v'\_i$ equals the zero vector (over $\mathbb{Z}\_2$).

**Proof:** This follows directly from the fact that an even number of $1$s in $\mathbb{Z}\_2$ sums to $0$.

**Corrollary 2:** If $T$ is such that the set of vectors $\\{v'\_i|i\in T\\}$ has full rank over $\mathbb{Z}\_2$ then $ \forall \emptyset \neq U \subseteq T$, $U$ is non-degenerate.

We see now that the degeneracy of a subset $T$ is intimately tied up with the rank of the associated matrix $A'\[\[n\_1\], T\]$. So, let us take $r$ to be the rank of $A'$ over $\mathbb{Z}\_2$. Let us re-order the vectors $\\{v\_1, v\_2,\ldots, v\_{n\_2}\\}$ so that $\\{v'\_1, v'\_2, \ldots, v'\_r\\}$ forms a maximal, linearly independent subset of $\\{v'\_1,v'\_2,\ldots,v'\_{n\_2}\\}$. By Corollary 2, we know that if $T \subseteq \[r\]$, then $T$ is non-degenerate.

Now, consider some non-empty subset $U$ of $\\{r+1, r+2, \ldots, n\_2\\}$. By some basic properties of linear algebra, we know that there is a unique (possibly empty) subset $V \subseteq \[r\]$ such that $\Sigma\_{j\in V} v'\_j = \Sigma\_{j \in U} v'\_j$. And, since we're operating in $\mathbb{Z}\_2$, we can re-arrange this equality into $\Sigma\_{j\in U \cup V} v'\_j = 0$. So, we conclude that for every non-empty subset $U$ of $\\{r+1, r+2, \ldots, n\_2\\}$ we can construct a unique degenerate subset $T \subseteq \[n\_2\]$. Conversely, we claim that every degenerate subset $T$ is accounted for in this manner (proof left to the reader).

**Theorem:** Let $A$ be a $n\_1 \times n\_2$ two-dimensional array with entries in $\\{+1, -1\\}$. Let $r$ be the rank of $A'$ over $\mathbb{Z}\_2$. Then,

$$ S(A) = (2^{n\_2-r}-1) * (2^{n\_1}-1) - (2^{n\_2} - 2^{n\_2-r})\*(-1) $$

**Proof:** The first summand corresponds to the $2^{n\_2-r}-1$ degenerate subsets formed by extended the non-empty subsets of $\\{r+1, r+2, \ldots, n\_2\\}$. The second summand corresponds to all the other (non-degenerate) subsets.

---
Tags: complexity-theory, time-complexity, arrays, arithmetic, matrices
---


# Question
Title: Proving that every derivation-tree has at most one leftmost-derivation in a context free grammar
I am trying to prove the following theorem:

---

For every derivation-tree in a context-free grammar $G=(V,T,P,S)$ there exists **at most** one leftmost derivation.

---

My partial proof by **contradiction** (I stucked at Cases (2) and (3)):

Let $G = (V,T,P,S)$ be a context-free grammar.

Suppose that for some derivation-tree there are two **distinct** rightmost derivations:

$S = \_0 ⟹\_{lm} \_1 ⟹\_{lm} \_2 ⟹\_{lm} … ⟹\_{lm} \_n = x$ $S = \_0 ⟹\_{lm} \_1 ⟹\_{lm} \_2 ⟹\_{lm} … ⟹\_{lm} \_m = x $
(x is the frontier of the tree)

It is clear that $\_1 = \_1$ since the first derivation uses a production rule of the form $S ⟶ Y\_1 … Y\_k$ where $Y\_1 … Y\_k$ are the children of the root node $S$.

Now since the derivations are distinct we get that there are **three** cases:

**(1)** $∃ i\_0 ∈ \\{2, … , min(m, n)\\}, (∀ k ∈ \\{ 0, … , i0 -1 \\}, \_k = \_k ) ⋀ \_{i\_0} ≠ \_{i\_0}$
(In other words: it says that the two derivations are identical till we reach some point in both derivations where they become distinct)

**(2)** $n \< m ⋀ ∀ k ∈ \\{ 0, … , n \\}, \_k = \_k$
(In other words: it says that the first derivation is a “sub” derivation of the second one)

**(3)** $n \> m ⋀ ∀ k ∈ \\{ 0, … , m \\}, \_k = \_k$
(In other words: it says that the second derivation is a “sub” derivation of the first one)

**Case (1):** If $∃ i0 ∈ \\{2, … , min(m, n)\\}, (∀ k ∈ \\{ 0, … , i0 -1 \\}, \_k = \_k ) ⋀ \_{i\_0} ≠ \_{i\_0}$ , We get that $∃w∈T^\*, ∈(V∪T)^\* , A∈V, \_{i\_0-1} = \_{i\_0-1} = wA$ , Since both derivations are in **the same** derivation-tree, The only possibility is that different production rules where used on **different** variables, but since the derivations are leftmost-derivations, we must use at the $i\_0$’th derivation the corresponding production-rule (in the derivation-tree) on $A$, since $A$ is the leftmost variable. Again, since the derivations are in **the same** derivation-tree, The production rule used on A must be the same rule $A ⟶ Z\_1 … Z\_k$ where $Z\_1 … Z\_k$ are the children nodes of the node $A$. Therefore we reached the contradiction $\_{i\_0} = \_{i\_0}$.

**Case (2):** If $n \< m ⋀ ∀ k ∈ \\{ 0, … , n \\}, \_k = \_k$ then we get that $\_n = \_n$ , Now since $\_n = x$ we get $\_n = \_n = x$, Since m \> n and since $x = \_n ⟹\_{lm} … ⟹\_{lm} \_m = x$, we get that $x ⟹\_{lm}^+ x$.

**Now I do not know how to proceed.**

**Case (3):** If $n \> m ⋀ ∀ k ∈ \\{ 0, … , m \\}, \_k = \_k$ then we get that $\_m = \_m$ , Now since $\_m = x$ we get $\_m = \_m = x$, Since n \> m and since $x = \_m ⟹\_{lm} … ⟹\_{lm} \_n = x$, we get that $x ⟹\_{lm}^+ x$.

**Now I do not know how to proceed.**

---

Maybe it got something to do with the fact that $x$ is the frontier of the derivation tree.

Thanks for any help.

# Answer
Here is a paraphrase of your proof. Suppose $$ S \Rightarrow \alpha\_1 \Rightarrow \cdots \Rightarrow \alpha\_n \Rightarrow w \\ T \Rightarrow \beta\_1 \Rightarrow \cdots \Rightarrow \beta\_m \Rightarrow w $$ are two leftmost derivations corresponding to the same derivation tree. Then the first step must be the same. *This is the point where you're stuck.*

What you want to do now is to say that $\alpha\_1 \Rightarrow \cdots \Rightarrow w$ and $\beta\_1 \Rightarrow \cdots \Rightarrow w$ are also leftmost derivations corresponding to the same derivation tree (obtained from the original one by taking into account the first step), and so by induction these derivations are the same.

There is a small problem – $\alpha\_1$ is now not a single symbol! You therefore have to *strengthen your induction hypothesis* and prove something more general which involves derivation trees starting from sentential forms (words which can involve both terminals and non-terminals).

---

Alternatively, if you prefer using frontiers of derivation trees, you should strengthen your induction hypothesis in a different (but equivalent) way. Now you are still given the original derivation tree, but some of the productions are marked as already having been performed. Your induction hypothesis now states that all leftmost derivations from this state are the same.

---

It's also possible to avoid strengthening the induction hypothesis, at the cost of a more complicated argument during the inductive step. Suppose that the first step is $S \to x\_1 A\_1 x\_2 A\_2 \dots x\_n A\_n x\_{n+1}$, where $A\_1,\ldots,A\_n$ are non-terminals and $x\_1,\ldots,x\_{n+1}$ are words. Any leftmost derivation must first completely derive $A\_1$, then completely derive $A\_2$, and so on, until $A\_n$ is completely derived. Induction shows that there is only one way to achieve any of these $n$ steps.

---

More generally, I suppose you focus first on *why* the result is true; only then focus on how to write the argument formally.
> 3 votes

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


# Question
Title: Generate a random graph with geometrical degree distribution
I'm working on graph generation, trying to implement the *RT-nested-Smallworld* network model described in this paper.

We are talking about generating an undirected graph in a slightly different way than what the Watts-Strogatz model does.

One of the very first steps of the algorithm is

> instead of selecting links to connect most immediate $\langle k \rangle / 2$ neighbors to form a regular lattice, our model selects a number $k$ of links at random from a local neighborhood $N\_{d\_0}$ with the distance threshold of $d\_0$, where $k$ comes from a geometric distribution. The local neighborhood is defined as the group of close-by nodes with mutual node number difference less than the threshold $d\_0$, that is $N^{(i)}\_{d\_0} = \\{j; |j-i| \< d\_0\\}$, for node $i$. It is worth noting that our model adopts a geometric distribution with the expectation $\langle k \rangle$ of for the initial node degree settings (i.e, for the link selection).

In other words, each node with index $i$ should have a (possibly different) random degree $k$, obtained by linking it with nodes with an index-distance $d\_0$.

First of all, I need to choose the parameter $p$ to generate the geometric distribution. If the average is $\langle k \rangle$, I choose $p = 1/\langle k \rangle$.

However, picking $n$ node degrees from a geometric distribution may not result in a feasible graph of $n$ nodes.

Moreover, Since this is an undirected graph we are talking about, going through each node and creating a random number $k$ of links will most likely **not** produce the desire average degree. E.g. during the *ith* iteration, the node *i* may already have more than $k$ links, created by the previous iterations of nodes randomly linking to it.

I tried to implement my own algorithm to distribute the node degrees as close as possible to the distribution outcome. Pseudocode

```
k_values = n values from the geometric distribution with p = 1/<k>
for each node in [0, n)
    if degree(node) < k_values[node]
        for each neighbor closer than d_0
            if degree(neighbor) < k_values[neighbor]
                if not link_exist(node, neighbor)
                    create_link(node, neighbor)

```

The problem is, this approach tends to consistently result in nodes having lower degrees than the output of the geometric distribution.

I know there are ways to generate an undirected graph with a given degree distribution. The biggest problem here seems to be the additional constraint on the potential neighborhood of each node (i.e. nodes within index-distance $d\_0$). Any ideas on how to solve that?

I would be happy getting a graph that is within a certain threshold from the outcome of the geometric distribution, and still quite close to the intended average degree $\langle k \rangle$.

# Answer
You can use the configuration model for this. Create a "stub" array where each of the $n$ vertices appears in the array $k\_i \sim \text{Geom}(p)$ times. Shuffle the array and then treat each adjacent pair in the array as an edge in the graph. Here's some python code to illustrate.

```
from numpy.random.mtrand import geometric
from random import shuffle
from _collections import defaultdict

if __name__ == '__main__':
    # Number of vertices
    n = 1000

    # Geometric distribution probability parameter
    p = 0.5

    stubs = []
    for i in xrange(0, n):
        # Sample the degree from the geometric distribution
        degree = geometric(p)
        # Insert into the stubs array the current vertex label degree times
        stubs += [i] * degree

    # Shuffle the values
    shuffle(stubs)

    # Build the graph
    G = {}
    for i in xrange(0, n):
        G[i] = []

    for i in xrange(1, len(stubs), 2):
        G[stubs[i]].append(stubs[i-1])
        G[stubs[i-1]].append(stubs[i])

    # Recover the degree distribution
    degrees = { i : len(neighbors) for i, neighbors in G.items() }

    dist = defaultdict(int)
    for (vertex, degree) in degrees.items():
        dist[degree] += 1

    print("Degree, empirical, theoretical")
    for (degree, freq) in dist.items():
        print("%d %f %f" % (degree, freq / float(n),  pow((1 - p), degree - 1) * p ))

```

Sample output:

```
Degree, empirical, theoretical
1 0.496000 0.500000
2 0.254000 0.250000
3 0.128000 0.125000
4 0.071000 0.062500
5 0.023000 0.031250
6 0.018000 0.015625
7 0.005000 0.007812
8 0.003000 0.003906
9 0.002000 0.001953

```

For more detailed description of the the configuration model, see Section 13.2 p. 435 of *Networks* by Newman.
> 3 votes

---
Tags: graphs, probability-theory, randomized-algorithms, sampling
---


title: Every AVL tree may be red black tree

text:
# Question
Title: Every AVL tree may be red black tree
I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof.

Induction for height.
Let's assume that it is truth for each AVL tree of height at most $h$.
Let's consider AVL tree $T$ of height $h+1$. Now, let's consider two subtree of $T$ - $L$ and $R$. We know that $height(R)\le h$ and $height(L)\le h$. Hence using induction hypothesis we conclude that $L$ and $R$ may be colored such that $L$ and $R$ will be red black tree. Then we may paint root - of course black color. Now $T$ is AVL and black tree.

# Answer
> 5 votes
Your proof produces a tree in which all nodes are colored black. It doesn't necessarily satisfy the "black height" rule:

> Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

Not every AVL tree satisfies this condition, for example the Wikipedia example doesn't.

---
Tags: data-structures, binary-trees, search-trees, balanced-search-trees, check-my-answer
---


# Question
Title: How to prove that 3-coloring is decidable?
In order to prove that 3-coloring is decidable, is it sufficient to say:

* Each node in the graph has 3 possible colors
* Therefore we can enumerate over all $3^n$ possibilities and then check that no two edges connect nodes with the same color

Does that prove that 3-coloring is decidable? Or do I need to construct a Turing machine for a proper proof?

By 3-coloring I'm talking about the graph coloring problem; i.e. assign one of 3 colors to each node in an undirected graph such that no two adjacent nodes have the same color.

# Answer
> 10 votes
It depends entirely on what level of formality you're aiming for. The informal description of an algorithm in your question is quite enough to convince *me* that 3-colourability is decidable. If you wanted to be a bit more formal, you could give pseudocode. If you wanted to be more formal still, you could describe a Turing machine in English. If you wanted to be even more formal, you could write down the full description of the Turing machine and prove that it really does decide 3-colourability.

Having said that, of the options I've listed, it's way more likely that there'd be an error in the description of the Turing machine or in its correctness proof! So it's not clear which proof would be the most believable.

# Answer
> -5 votes
All the non deterministical problems for TM are decidable, so from your description you demonstrated you needed $ 3^{n}$ turing machines to validate a solution. So your explanation is enough.

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


# Question
Title: Binary Integer Programming question - what graph problem is represented
I'm dealing with a BIP question, that represents a graph problem. The goal is finding the graph problem.

I've spend a lot of time trying to solving this question but I couldn't find the answer to that question.

All I'm given is the set of constraints and the objective function:

I'd really appreciate your help, no full answer needed, just a direction.

$$ \begin{align\*} \min & \sum\_{ijk} z\_{ijk} c\_{ij} \\ \text{s.t.}\\; & \sum\_j x\_{ij} = 1 \qquad \forall i=0\ldots n-1 \\ & \sum\_i x\_{ij} = 1 \qquad \forall j=0\ldots n-1 \\ & z\_{ijk} \geq x\_{ik} + x\_{j(k+1\\,\mathrm{mod}\\,n)} \qquad \forall i,j,k=0\ldots n-1 \\ & x\_{ij},z\_{ijk} \in \\{0,1\\} \end{align\*} $$

# Answer
This answer assumes that $c\_{ij} \geq 0$.

The first two sets of equations guarantees that $x\_{ij}$ is a permutation matrix. It defines a permutation $\pi$ on $\\{0,\ldots,n-1\\}$ in the following way: $\pi(j) = i$ if $x\_{ij} = 1$.

The set of inequalities is a logical implication: if $x\_{ik}=x\_{j(k+1)}=1$ then $z\_{ijk} = 1$. That is, if $\pi(k) = i$ and $\pi(k+1) = j$ then $z\_{ijk}=1$.

Since $c\_{ij} \geq 0$ and the objective is to minimize $\sum\_{ijk} z\_{ijk} c\_{ij}$, we want to have $z\_{ijk} = 0$ unless we are forced to take $z\_{ijk} = 1$. Therefore $z={ijk} = x\_{ik} \land x\_{j(k+1)}$. This means that the objective function is $$ \min\_\pi \sum\_{k=0}^{n-1} c\_{\pi(k)\pi(k+1)}. $$ This is the problem known as *minimum directed Hamiltonian circuit*.
> 1 votes

---
Tags: algorithms, linear-programming, integer-programming
---


# Question
Title: Transform $A\land B \Leftrightarrow B\lor A$ into conjunctive normal form
How do I transform the following formula into conjunctive normal form? $$ A \land B \Leftrightarrow B \lor A $$

# Answer
> 1 votes
I'll explain how to transform $A \Leftrightarrow B$ into disjunctive normal form; your case is very similar. You start with a truth table: $$ \begin{array}{c|c|c} A & B & A \Leftrightarrow B \\\hline F & F & T \\ F & T & F \\ T & F & F \\ T & T & T \end{array} $$ We now take all the lines in which the value is true, and for each of them construct the corresponding term. The line $F \\; F$ contributes the term $\lnot A \land \lnot B$, and the line $T \\; T$ contributes the term $A \land B$. Overall we get $$ (\lnot A \land \lnot B) \lor (A \land B). $$ There is a similar algorithm to construct CNFs, which you must have learned in class. (It can also be found in many online resources.)

---
Tags: propositional-logic
---


title: Ripple Carry Adder

text:
# Question
Title: Ripple Carry Adder
I'm new to computer science and came across an issue while learning about ripple carry adders. I'm trying to add binary 1+1+1 below (excuse the poor photoshopping). I know the answer should be binary 11, but my sums were 0 and 0 with a carry of 1. Shouldn't my sums be 1 and 1 with a carry of 0? What am I doing wrong?

# Answer
You're misinterpreting the action of a ripple-carry adder. Each of the two boxed circuits takes in two 1-bit numbers (the top two inputs) and a carry bit (the left input) and returns a sum bit (the lower output) and a carry (the right output). In this example, you are adding $a\_0+b\_0$ (the 1, 1 left pair of inputs) and $a\_1+b\_1$ (the 1, 0 right pair of inputs). In other words, reading from least significant bits on the left, you're adding $a=11$ to $b=01$, i.e., $11+01$ which gives you the sum bits $s\_0=0,s\_1=0$ and a carry of 1, as you observed. In decimal terms, your example adds $3+1$ and correctly produces $4$.
> 5 votes

---
Tags: computer-architecture, arithmetic, digital-circuits, cpu
---


# Question
Title: Why does the proof of undecidability of $A_{TM}$ require the universal TM to take input $\langle M,\langle M\rangle\rangle$?
I've read a proof explaining why $A\_{\mathrm{TM}}$ is undecidable, and I don't seem to understand why we need to give the opposite of $H$ function $D$ itself as input.

Here's the copy-paste of that proof (link: https://courses.cs.washington.edu/courses/cse322/04au/Lect10.pdf):

$A\_{\mathrm{TM}} = \\{\langle M,w\rangle\mid M\text{ is a TM that accepts }w\\}$ is undecidable! Proof (by contradiction):

1. Assume $A\_{\mathrm{TM}}$ is decidable there’s a decider $H$, $L(H)$ = $A\_{\mathrm{TM}}$.
2. $H$ on $\langle M,w\rangle = \mathrm{ACC}$ if $M$ accepts $w$ $\mathrm{REJ}$ if $M$ rejects $w$ (halts in $q\_{\mathrm{REJ}}$ or loops on $w$).
3. Construct new TM $D$: On input $\langle M\rangle$: Simulate $H$ on $\langle M,\langle M\rangle\rangle$ (here, $w = \langle M\rangle$). If $H$ accepts, then reject input $\langle M\rangle$; If $H$ rejects, then accept input $\langle M\rangle$.
4. What happens when $D$ gets $\langle D\rangle$ as input? $D$ rejects $\langle D\rangle$ if $H$ accepts $\langle D,\langle D\rangle\rangle$ if $D$ accepts $\langle D\rangle$; $D$ accepts $\langle D\rangle$ if $H$ rejects $\langle D,\langle D\rangle\rangle$ if $D$ rejects $\langle D\rangle$. Either way: Contradiction! $D$ cannot exist, so $H$ cannot exist. Therefore, $A\_{\mathrm{TM}}$ is not a decidable language.

So, I don't understand why we need to give $H$ the input of $\langle D,\langle D\rangle\rangle$, why not give it the input of $\langle D,w\rangle$? And give $D$ the same input, isn't that the same thing? Or what's the logic behind the second $\langle D\rangle$? For some reason it's very confusing for me. Thanks.

# Answer
The problem is that your proposed $D$ either isn't a TM or doesn't lead to a contradiction. Suppose we did as you suggested, defining a machine $D$ that required as input a pair $(\langle\\,M\\,\rangle, w)$ where $\langle\\,M\\,\rangle$ was the description of a TM $M$ and $w$ was an arbitrary word. Then, using $H$ as a subroutine we'd have $$ D(\langle\\,M\\,\rangle,w)=\begin{cases} \text{ACC} & \text{if $M$ doesn't accept $w$}\\ \text{REJ} & \text{if $M$ accepts $w$} \end{cases} $$ Now what happens if you give $D$ the input pair $(\langle\\,D\\,\rangle, w)$? We'd have the behavior $$ D(\langle\\,D\\,\rangle,w)=\begin{cases} \text{ACC} & \text{if $D$ doesn't accept $w$}\\ \text{REJ} & \text{if $D$ accepts $w$} \end{cases} $$ and here's where the problem crops up. The conditions "$D$ doesn't accept $w$" and "$D$ accepts $w$" make no sense, since $D$ was defined on inputs that were required to be *pairs*: a TM description and a word. It *might* happen that $w$ in the condition was interpretable as a (TM, word) pair, but the result would have nothing to do with the original input $(\langle\\,D\\,\rangle,w)$. In any case, we wouldn't get to the contradiction we needed, which is why the original construction needed to define $D$ with a single argument, $\langle\\,M\\,\rangle$.
> 2 votes

# Answer
> Why not give it the input of $\langle D,w\rangle$?

What's $w$? The machine $D$ is given some input, which it interprets as the coding of a Turing machine $M$. It's not given any $w$: only $\langle M\rangle$.

Imagine instead that you're given a function $f$ which is defined as $f(x)=x^x$. I ask you to calculate $f(10)$ and your question is a bit like asking, "Why does it have to be $10^{10}$? Why can't it be $10^y$?"
> 2 votes

---
Tags: computability, proof-techniques, undecidability, halting-problem
---


# Question
Title: What algorithm to apply when a graph have cycles ("circuits") and some negatives values in order to find the shortest path from $x1$ to all vertices?
What algorithm to apply when a graph have cycles ("circuits") and some negatives values in order to find the shortest path from $x1$ to all vertices? For instance in the following graph? I know I can't use Djikstra...

# Answer
The Floyd-Warshall algorithm gives costs between *all* pairs of vertices in reasonable time ($O(n^3)$ for $n$ vertices) as long as there are no negative cost cycles.
> 0 votes

---
Tags: algorithms, shortest-path
---


# Question
Title: Choosing nonzero entries from an array so no pair in same row or column
Suppose we have an $n\times n$ array $A$ of non-negative real numbers in which the sum of each row and each column is $1$. We want to find $n$ entries of the array $(x\_1,y\_1), \dots, (x\_n,y\_n)$ such that

* each $A\[x\_i,y\_i\]\>0$ and
* no pair $(x\_i,y\_i),(x\_j,y\_j)$ are in the same row or column (i.e., $i\neq j$ implies that $x\_i\neq x\_j$ or $y\_i\neq y\_j$ or both).

How can we prove that such a set of entries always exists?

Here is an example solution with a $3\times3$ table.

# Answer
The Birkhoff–von Neumann theorem states that a doubly stochastic matrix (a matrix with non-negative entries in which rows and columns sum to 1) can be written as a convex combination of permutation matrices (0/1 matrices which contain precisely one 1 in each row and column). This immediately implies your result.

---

If you don't want to assume this theorem, you can use Hall's theorem directly. Given your table $A$, define a bipartite graph by having $n$ row-vertices, $n$ column-vertices, and connecting row $i$ and column $j$ if the $(i,j)$th entry is non-zero. Your goal is to find a perfect matching in the graph.

According to Hall's theorem, the graph contains a perfect matching if for all subsets $S$ of row vertices, the number of neighbors of $S$ is at least $|S|$. That is, given a set $S$ of rows, we need to show that the set $$T = \\{ j : A\_{ij} \neq 0 \text{ for some $i \in S$}\\}$$ contains at least $|S|$ columns. Indeed, the sum of the entries in the rows in $S$ is exactly $|S|$, and the sum of the entries in the columns in $T$ is exactly $|T|$. Therefore the sum of entries in $S \times T$ is at most $|T|$. However, by definition this sum must equal $|S|$ (since all other entries in the rows in $S$ are zero), and so $|S| \leq |T|$, which is what we wanted.

This argument shows that you can use standard algorithms for finding maximum matchings in bipartite graphs to actually find your $n$ entries.

---

We are now at an excellent position to prove the Birkhoff–von Neumann theorem. The proof is by induction on the number of non-zero entries. The argument above shows that there are at least $n$ non-zero entries, and in that case it's not hard to see that the matrix must be a permutation matrix, completing the base case.

Now consider an arbitrary doubly stochastic $A$ with more than $n$ non-zero entries, and find a matching $(i,\pi(i))$ in $A$. This matching corresponds to sum permutation matrix $P$. Define $\alpha = \min\_i A(i,\pi(i)) \> 0$. The matrix $B = \frac{A - \alpha P}{1 - \alpha}$ is also doubly stochastic (since subtracting $\alpha P$ removes exactly $\alpha$ from each row and column), with at least one more zero entry. By induction, $B$ is a convex combination $\sum\_t \beta\_t P\_t$ of permutation matrices. Hence so is $A$: $$A = \alpha P + (1-\alpha) \sum\_t \beta\_t P\_t.$$

---

The Birkhoff–von Neumann theorem can be stated in many different ways. It states that the set of doubly stochastic matrices is the convex hull of the permutation matrices. It also states (with some more work) that the vertices in the polytope of doubly stochastic matrices are the permutation matrices.
> 7 votes

# Answer
As @YuvalFilmus says, this can be considered as the problem of finding a complete matching on a bipartite graph. The algorithm to do this is due to Hopcroft and Karp. Reference is Hopcroft and Karp, "An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs", SIAM Journal of Computing 2:4 (1973), pp. 225–231. DOI https://dx.doi.org/10.1137%2F0202019
> 2 votes

---
Tags: proof-techniques, matrices, search-problem
---


# Question
Title: Is There a Complete Problem for the Class of Turing Decidable Problems?
Languages such as $\text{HALT}\_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz \[1\] considers some classes inbetween $\text{ELEM}$ and $\text{REC}$. They present complete problems for these classes under specifically crafted reductions.

Are there complete problems for $\textsf{R} = \textsf{RE} \cap \textsf{co-RE}$ (aka $\textsf{REC}$) relative to weaker reductions? Turing reductions are inappropriate because they are capable of doing all the work. Should we expect such reductions to be contrived or not so (*e.g.* many-one reductions that are restricted to primitive recursion)?

---

\[1\] Sylvain Schmitz *Complexity Hierarchies Beyond Elementary* 2013 http://arxiv.org/abs/1312.5686

# Answer
Generally a class having a complete problem under a nice class of reductions implies that the class can be enumerated. $\mathsf{R}$ is not computably enumerable, therefore it does not have a complete problem with respect a nice class of reductions.

Here is the argument:

Assume that there is a complete problem $A$ for $\mathsf{R}$. Therefore for any problem in $\mathsf{R}$ can be obtained from a reduction (let's say polynomial time many-one reductions) combined with $A$. We can computably enumerate the reductions, therefore we can computably enumerate $\mathsf{R}$. But $\mathsf{R}$ is not computably enumerable (otherwise we could diagonalize).

In the literature look for the set of *total recursive/computable functions*.
> 8 votes

---
Tags: computability, reductions, turing-completeness, recursion-theory
---


title: Exponential analogue of NC?

text:
# Question
Title: Exponential analogue of NC?
Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors.

I want to know about the exponential analogue, which would cover problems that can be decided in polynomial time using an exponential number of processors.

What I'm looking for is a name for this class and any known relations between this class and other complexity classes, or any canonical problems for the class. It seems straightforward that it would contain NP and co-NP, and i think it is contained within PSPACE, but I'm not sure much else about it.

# Answer
Time in circuits corresponds to the depth. Therefore by polynomial time means polynomial depth.

The number of processors is the size of the circuit, i.e. number of the gates in the circuit. So by exponential number of processors you allow exponential size. This would be the class $\mathsf{DepthSize}(n^{O(1)}, 2^{n^{O(1)}})$. But *every* function is already in $\mathsf{DepthSize}(2, 2^{n^{O(1)}})$ (think of the CNF of the function you want to compute).

The take away is that exponential number of processors is too strong to be useful by itself.

One reasonable restriction to put is to limit the amount of communication between different processes. E.g. we each process can only communicate with only polynomially many other processes and the messages have polynomial size. That would be $\mathsf{PSpace}$ as explained in answers to Aterm's question on cstheory. Another way to see it to remember that $\mathsf{PSpace} = \mathsf{ATime}(n^{O(1)})$, problems computable by alternating Turing machines in polynomial time. Alternation in Turing machines is essentially forking new processes and then joining after they finish by taking the conjunction/disjunction of their return values.
> 1 votes

---
Tags: complexity-theory, reference-request, parallel-computing, complexity-classes
---


# Question
Title: How exactly MOV AX will load data from RAM?
Somewhere on Internet I read : **Whenever word size is greater than memory cell size, then there is a need for accessing multiple memory cell**
Example:
for 16 bit processor:
MOV AX \[2000\]
**To transfer memory content, we need to transfer 16 bit data , so we need to access 2 memory cells**
M\[2000 H\]
&
M\[2001 H\]
But I didnt get this. Why 2 cells ?
I interpreted as follows:
1) 8 bit binary code will be fetched which decoded as MOV AX.
2) From next memory location , (00 H ) will be fetched as memory is byte addressable.
3) From next memory location , (20 H ) will be fetched.
4) In IR register it is treated as ( 2000 H ) and data at (2000 H) memory location is fetched and moved to AX register.
So why to access M\[2001 H\] memory location ??

# Answer
> 8 votes
I am not sure if this is actually on-topic here, but anyway.

The main memory in x86 architectures is addressed byte-wise. If you want to retrieve 16 bits from address 2000h (note that AX is a 16 register), then you will need to read 8 bits from 2000h and 8 bits from 2001h. This is why the operation needs to read "2 cells". Note that the term "cell" is not the correct one, as it typically refers to individual 1-bit memory units without addressing logic.

Note that the processor actually doesn't read the two bytes separately. Rather, the content from bytes 2000h and 2001h are fetched at the same time as the data bus to cache and main memory is \>8 bits *and* the addresses you have here as examples are aligned, so the underlying architecture supports the parallel read.

# Answer
> 2 votes
I am assuming that you are talking about an Intel 8088 CPU. In that case, the CPU is a 16-bit processor, but it only has an 8-bit data bus. The 8086 has a 16-bit data bus. When a MOV AX, \[ADDR\] is encountered, the CPU must initiate two bus cycles to read in all 16-bits. Since Intel machines are little endian, it must read in the low byte then the high byte. See my answer on endiness here. So with a memory address of 1600h, the low byte is in 1600h and is loaded into the AL portion of the register while the high byte is in 1601h and is loaded into the AH portion of the register.

On a 8086, only one bus cycle is used because that CPU reads the entire 16-bit word in one go.

So, from a hardware standpoint, when the MOV instruction is decoded, it looks at the source and destination operands. MOV AX, \[2000h\] (from your example) is interpreted as "copy contents of memory location 2000h into the AX register using 16-bits." The microcode inside the execution unit makes this interpretation and initiates two bus cycles (one on a 8086 for the reasons already given). Because the lower 8 bits of the address bus is multiplexed with the 8 bit data bus, the CPU has some control signals that enable the address to be de-multiplexed from the data.

There are other control signals that goes to a separate decoder chip that decodes the bus cycle into one of the following operations: \*MEMR, \*MEMW, \*IOR, \*IOW which are Memory Read, Memory Write, I/O Read, and I/O Write (The * indicates an active low signal which means that the signal line is active when a logic 0 is present.). The address is latched onto the bus for the duration of the cycle so the memory decoding logic can select which memory chips are to be enabled. It uses the high order bits of the address for this (bit x to bit 19). The lower bits are sent to the actual memory chips to select which cell to access (bits 0 to x). The read and write signals tell the memory chips if they should transmit the contents of the cell onto the data bus, or to take the data that is on the data bus and place it into the cell. In the case of a read, the memory chip transmits the data in the cell, either a 1 or 0 onto the data bus and to the CPU that is waiting for it.

When the bus cycle ends, the CPU takes whatever is on the data bus and loads it into the appropriate register. It does this entire operation twice to load a 16-bit value into a register. Then the instruction is complete and the CS:IP register pair is incremented to the next instruction to be executed.

---
Tags: computer-architecture, memory-management, cpu-cache, memory-access
---


# Question
Title: Prove that every thin AVL tree may be converted to red-black tree
Let's define thin AVL tree as AVL tree $t'$ such that contains minimal possible number of nodes among all AVL tree $t$ such that $height(t)=height(t')$.

I am trying to prove that every thin AVL tree may be colored to be red-black tree. I would like to use induction. I tried to do induction by height - but as you could see Every AVL tree may be red black tree I didn't managed to (I have very similar problem).

Could you give me a hint ?

I can see following thing:
thin avl tree of height $h$ has exactly one vertex on height $h$ - contrary avl tree wouldn't be thin. Moreover this node must be red (property of black height).
Example:

# Answer
> 4 votes
Just a remark.

Your "thin" trees are sometimes know as Fibonacci trees. A Fibonacci tree $T\_h$ of height $h$ is recursively defined as root with two subtrees $T\_{h-1}$ and $T\_{h-2}$. Hence the name.

As the number of black nodes along each path from root to leaf must be equal, this means that the subtrees $T\_{h-1}$ and $T\_{h-2}$ must have the same black height in $T\_h$, although they differ in height.

---
Tags: proof-techniques, binary-trees
---


# Question
Title: The length of the smallest co-prime chain between any two integers
Consider the following statement:

> for any $a \< b \in \mathbb{N}$, one of the following holds:
>
> 1. $\gcd(a,b) = 1$.
> 2. there is a $a \< x \< b$ such that $\gcd(a,x) = \gcd(x,b) = 1$.
> 3. there are $a \< x \< y \< b$ such that $\gcd(a,x) = \gcd(x,y) = \gcd(y,b) = 1$.

Is this statement true?

---

### Motivation:

I found a variant of this problem in one of the recent algorithms competitions.

Consider the following problem:

**Input:** two integers $a$ and $b$ where $a \lt b$.

**Output:** smallest number $l$ such that there are integers $a = x\_0 \< x\_1 \< x\_2 \< \ldots \< x\_l \< x\_{l+1} = b$ such that all consecutive integers in the list are co-prime: $\gcd(x\_i, x\_{i+1}) = 1$ for $i=0,\ldots, l$.

Examples:

1. $a = 7, b = 13$: $\gcd(a,b) = 1$, therefore $l = 0$.
2. $a = 10, b = 12$: $\gcd(a,b) = 2 \neq 1$, therefore $l \geq 1$. Let the sequence be $10, 11, 12$. $\gcd(10, 11) = 1, \gcd(11, 12) = 1$.
3. $a = 2184, b = 2200$: There is no $a\< x \< b$ such that $\gcd(a,x)=\gcd(x,b)=1$. However, we can find $2$ integers that satisfy this problem.

There is a reference algorithm that algorithms are evaluated against. That algorithm assumes that

1. There is always an $l$ that satisfies the condition.
2. $l\leq 2$.

I don't see why they are true.

I have a polynomial time algorithm that does not assume either of them. I am not losing out on the asymptotic performance compared to the reference algorithm, but I could get the performance constants much lower if I can understand and prove the validity of the assumptions.

# Answer
> 1 votes
The conjecture $\ell \leq 2$ seems to be open. It is stated as Conjecture 3 in a paper of Dowe. Dowe does show that the Goldbach conjecture implies that $\ell \leq 3$, and mentions that Alan Woods showed in his PhD thesis that $\ell$ is bounded. Perhaps the recent proof of the odd Goldbach conjecture also implies a definite and small bound.

If $\ell \> 1$ then $b-a$ is an Erdős-Woods number. In particular, if $\ell \> 2$ then both $b-a$ and $b-a-1$ have to be Erdős-Woods numbers. A059756 lists the first few Erdős-Woods numbers. While all numbers on that list are even, there are also odd Erdős-Woods numbers, some of which are listed in A111042. The smallest values of $a$ corresponding to given differences are listed in A059757. While this list is not increasing, it does seem as if the numbers are growing pretty fast. Any counterexample to $\ell \leq 2$ would to be such that both $b-a$ and $b-a-1$ are Erdős-Woods numbers, and in particular $b-a \> 430$ (per A059756). This suggests (but does not prove) that any such counterexample will be huge, and so for all practical purposes we can assume that $\ell \leq 2$.

---
Tags: number-theory
---


title: Do "symbols" = terminals in CFGs?

text:
# Question
Title: Do "symbols" = terminals in CFGs?
Are the **"symbols"** of a context-free grammar the same thing as the terminals?

Are the set of symbols and set of terminals the same?

# Answer
In a context-free grammar there are two sets of symbols (two alphabets, if you will). One is the set of symbols that can be replaced by others: these are the non-terminal symbols. The other is the set of terminal symbols, which (you may have guessed) cannot be replaced.

At some point, a derivation is expected to produce a string of symbols that is immutable, and because it is immutable we tend to think of these strings in the same way we think of numbers (as opposed to arithmetic expressions), as elements of a language that is being **defined**. This is one game that we play.

You can still think of those two sets of symbols as partitions of a bigger set, the "set of all symbols". This would allow you to play other interesting games.
> 4 votes

---
Tags: context-free
---


# Question
Title: What is the difference between 'features' and 'descriptors' in computer vision / machine learning?
I've read multiple time sentences similar to

> Finally, for standard image classification bag-of-words features based on SIFT descriptors have been found critical for high performances. We first compute a standard SIFT discriptor at regular grid points over the whole image.

Source: "Multi-class image segmentation using Conditional Random Fields and Global Classification" by Nils Plath, Marc Toussaint, Shinichi Nakajima.

What is a descriptor? I thought SIFT is an algorithm which operates on images and gives features (vectors in $\mathbb{R}^n$, where $n$ is fixed for a fixed size of images and parameters of the SIFT algorithm)?

# Answer
The SIFT descriptor vector *is* a feature vector. "Descriptor vector" and "feature vector" are synonyms in this context. Most of the descriptions of SIFT I've seen use the phrase "descriptor vector", but occasionally they'll refer to it as a "feature vector" or refer it to as "SIFT features", perhaps to draw upon intuition from machine learning.

SIFT works by analyzing the image, identifying a set of keypoints (a set of points in the image that will be helpful for alignment), and then for each keypoint, it computes a descriptor vector (a feature vector). Then it uses the descriptor vectors for the keypoints in image $I\_1$ and the descriptor vectors for the keypoints in image $I\_2$ to try to align the two images to each other. The intuition is that if the descriptor vector for a keypoint in image $I\_1$ is "similar" to a descriptor vector for a keypoint in image $I\_2$, then maybe those two points should be aligned to each other. Here "similarity" is measured by the Euclidean distance between the two descriptor vectors.

Thus, a descriptor vector for a keypoint is a vector, e.g., in $\mathbb{R}^{128}$, chosen so that if the image is translated, scaled, rotated, etc., then the descriptor vector for that point won't be changed much by the transformation.

You can find a reasonable description of SIFT in Wikipedia: https://en.wikipedia.org/wiki/Scale-invariant\_feature\_transform
> 2 votes

---
Tags: machine-learning, computer-vision, features
---


title: Reduce Min-Cut to 0/1 Integer Program

text:
# Question
Title: Reduce Min-Cut to 0/1 Integer Program
Given an undirected, weighted graph $G=(V,E)$ and two nodes $s,t \in V$ and weight function $w: E \rightarrow \mathbb{N}$. The weight of a (s,t)-cut $ (U, U^C)$ is given by:

$$ w(U,U^C) := \sum\_{\\{i,j\\}\in V :i\in U \land j\in U^C} w(\\{i,j\\}) $$

Reduce $$ MinCUT:= \\{\<G,c,s,t,k\>\mid \text{There is a (s,t)-cut with weight} \leq k\\} $$ to $$ BinaryProgram:= \\{\<A,b\> \mid \text{There is a vector } y\in\\{0,1\\}^\* \text{ such that } Ay \leq b \\} $$

I know i have to find a matrix $A$ and a vector $b$ which implement the following constraints:

* The weight of the edges which cross the sets of the cut must be $\leq k$
* Node $s$ must be in set $U$ and node $t$ must be in set $U^C$
* Every node must either be in $U$ or $U^C$

Can somebody give me a hint how implement these constraints into a matrix ?

# Answer
> 1 votes
Hint: Let's try to encode the constraints using two types of variables: $a\_v$ for each vertex $v$, and $b\_{uv}$ for each edge $u,v$. The variable $a\_v$ encodes which part of the cut vertex $v$ belongs to. The variables $b\_{uv}$ equals 1 if the edge $(u,v)$ is cut.

We want to enforce the following constraints:

* $a\_s = 0$ and $a\_t = 1$.
* $b\_{uv} = 1$ if $a\_u = 1$ and $a\_v = 0$ or if $a\_u = 0$ and $a\_v = 1$.
* $\sum\_{uv \in E} w(u,v) b\_{uv} \leq k$.

Try to encode all these constraints as inequality constraints.

---
Tags: graphs, reductions, network-flow, integer-programming
---


# Question
Title: Algorithm for a list of best solutions to the Assignment problem
I am trying to brute force a classical substitution cipher. The problem is that there are $26!$ possible keys. So, I'd like to do frequency analysis to try likely keys first. Then, on the first $n$ tries I will use a dictionary to see if there are actual words in the decryption. That way, I don't need to try all possible keys.

So, as suggested here, I will use chi-squared testing. I was thinking of making a matrix, best illustrated with an example. Suppose in an alphabet {A,B,C} the letter frequencies are 50%, 30% and 20% respectively, and that in a ciphertext the frequencies are 10%, 50% and 40% respectively. Then the A-B cell in the matrix is $(0.1-0.3)^2=0.04$, which is the error rate when a B in plain is encrypted as an A.

```
   |  A   |  B   |  C                 | Use in plaintext | in ciphertext
---+------+------+------           ---+------------------+---------------
 A | 0.16 | 0.04 | 0.01             A |        0.5       |       0.1
 B | 0.00 | 0.04 | 0.09             B |        0.3       |       0.5
 C | 0.01 | 0.01 | 0.04             C |        0.2       |       0.4

```

The Hungarian algorithm then gives me a frequency-analysis-wise optimal key: $A \mapsto C, B \mapsto A, C \mapsto B$. This is because the sum of the errors (0.01+0.00+0.01=0.02) is minimal. This is useful, but what I need is the $n$ best keys.

The only thing I can come up with is to run the Hungarian algorithm, and then set one of the cells in the matrix above corresponding to the key found to a high value, so that if you run the algorithm again the key you find doesn't contain the mapping. So, in the example above, you could set A-C to 1 so that when you run the Hungarian algorithm again you find a different key that doesn't contain $A\mapsto C$.

However, this isn't guaranteed to find good keys in order. What would be a better way to extend the Hungarian algorithm to find the best $n$ keys?

---

**Epilogue**: after implementing this using D.W.'s approach below, it turned out that this method doesn't perform well enough to crack small-length (at least up to 1000 letters) cipher texts, because frequency analysis alone isn't enough. Performance may be improved by taking frequent digrams or trigrams into account, but I doubt this method can be as powerful as simple hill climbing.

# Answer
> 2 votes
Here's one technique to enumerate the best $n$ assignments, for any instance of the assignment problem. I suspect my approach isn't optimal, but it does run in polynomial time: it uses $O(nm)$ invocations of the Hungarian algorithm, where $m$ denotes the number of agents in the problem instance. In your example, $m=26$, so my approach requires $O(n)$ invocations of the Hungarian algorithm.

Let $A\_1,A\_2,A\_3,\dots$ denote the assignments, from best to worse. $A\_1$ is the best assignment; $A\_2$ is the next-best; and so on. Our goal want to enumerate $A\_1,\dots,A\_n$.

You can find $A\_1$ by solving the original assignment problem, e.g., with the Hungarian algorithm.

How can we find $A\_2$, the second-best assignment? The idea is to use a case analysis. Let $v\_1,\dots,v\_m$ denote the $m$ agents in the problem instance, and let $A(v)$ denote the task assigned to agent $v$ by assignment $A$. We'll break down the space $\mathcal{S}$ of possible candidates for $A\_2$ (i.e., the space of all assignments other than $A\_1$) into the disjoint union $\mathcal{S} = \mathcal{S}\_1 \cup \dots \cup \mathcal{S}\_m$, where $\mathcal{S}\_i$ is the space of assignments that agree with $A\_1$ for $v\_1,\dots,v\_{i-1}$ but disagree with $A\_1$ on $v\_i$. (In other words, we look at the first agent that receives a different assignment in $A\_1$ vs $A\_2$. Then there are $m$ possibilities for that agent; we let $i$ denote its index, i.e., the index of the first agent whose assignment in $A\_1$ is different from its assignment in $A\_2$. This breaks down the space $\mathcal{S}$ into subspaces $\mathcal{S}\_1,\dots, \mathcal{S}\_m$, as listed before.)

Now the approach will be to find the best assignment in each $\mathcal{S}\_i$, separately.

* $\mathcal{S}\_1$: We find the best assignment $A$ such that $A(v\_1) \ne A\_1(v\_1)$ using one invocation of the Hungarian algorithm, by changing the cost of the edge $(v\_1,A\_1(v\_1))$ to $\infty$ (or some very large positive number) and then re-running the Hungarian algorithm. This finds the best assignment out of all assignments that assign $v\_1$ to something different than $A\_1$ did.
* $\mathcal{S}\_2$: We find the best assignment $A$ such that $A(v\_1) = A\_1(v\_1)$ and $A(v\_2) \ne A\_1(v\_2)$ using one invocation of the Hungarian algorithm: change the cost of the edge $(v\_1,A\_1(v\_1))$ to $0$, and change the cost of the edge $(v\_2,A\_1(v\_2))$ to $\infty$.
* $\mathcal{S}\_i$: Similarly, for each $i$, we can find the best assignment $A$ such that $A(v\_j) = A\_1(v\_j)$ for all $j=1,2,\dots,i-1$ and such that $A(v\_i) \ne A\_1(v\_i)$, using one invocation of the Hungarian algorithm.

This gives us $m$ assignments, i.e., $m$ candidates for $A\_2$. By construction, each one of these assignments is different from $A\_1$. Also, by construction, this covers all the space of all assignments that are different from $A\_1$. Therefore, $A\_2$ will be the best of these $m$ candidates, so we can just compare these $m$ candidates and call it $A\_2$.

That find the second-best assignment. How can we find $A\_3$, the third-best assignment? Well, the same ideas apply: we'll use a case split, but now the case-split will be a little more involved. Suppose that $v\_i$ is the first agent where $A\_1$ and $A\_2$ disagree (i.e., $A\_1$ and $A\_2$ agree on $v\_1,\dots,v\_{i-1}$ but disagree on $v\_i$, so that $A\_2 \in \mathcal{S}\_i$). Then we can break down the space of possibilities for $A\_3$ by looking at the first agent that receives a different assignment from $A\_2$, or from $A\_1$.

In particular, let $\mathcal{T}$ denote the space of possible candidates for $A\_3$ (i.e., the space of all assignments other than $A\_1$ or $A\_2$). We can partition it into the disjoint union

$$\mathcal{T} = \mathcal{S}\_1 \cup \dots \cup \mathcal{S}\_{i-1} \cup (\mathcal{T}\_1 \cup \dots \cup \mathcal{T}\_m) \cup \mathcal{S}\_{i+1} \cup \dots \cup \mathcal{S}\_m.$$

In other words, since $A\_2 \in S\_i$ and we now want to exclude $A\_2$ from the space of allowable assignments, we partition $S\_i$ into $S\_i = \\{A\_2\\} \cup \mathcal{T}\_1 \cup \dots \cup \mathcal{T}\_m$ and remove $A\_2$. Here $\mathcal{T}\_j$ denotes the set of assignments that agree with $A\_2$ on $v\_1,\dots,v\_{j-1}$ but disagrees with $A\_2$ on $v\_j$ (and, if $j=i$, disagrees with $A\_1$ on $v\_j$ as well).

Now, we use the Hungarian algorithm to find the best assignment in each of $\mathcal{S}\_1, \dots, \mathcal{S}\_{i-1}, \mathcal{T}\_1, \dots, \mathcal{T}\_m, \mathcal{S}\_{i+1}, \dots, \mathcal{S}\_m$. This is doable using the techniques shown above, using one invocation of the Hungarian algorithm per subspace. Finally, we let $A\_3$ be best of all the solutions found.

We can continue in this way, at each step identifying the next-best by decomposing the space of remaining assignments into multiple subspaces and invoking the Hungarian algorithm on each subspace. At each step, we introduce at most $m$ new subspaces, and we can reuse the previously-obtained results for the other subspaces. Therefore, on each step we make at most $m$ invocations of the Hungarian algorithm, so the total number of invocations of the Hungarian algorithm is $O(nm)$.

There's probably a better way to do it, but if you can't find any other algorithm, this is one you could use. Note that this is a general technique for problem of enumerating the $n$ best assignments to any instance of the assignment problem. It's not specific to your substitution-cipher example.

---
Tags: algorithms, assignment-problem
---