# Question
Title: How to prove that a language is not regular?
We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a given language is regular.

How do I show the opposite, though? My TA has been adamant that in order to do so, we would have to show for all regular expressions (or for all finite automata, or for all left-linear grammars) that they can not describe the language at hand. This seems like a big task!

I have read about some pumping lemma but it looks really complicated.

*This is intended to be a reference question collecting usual proof methods and application examples. See here for the same question on context-free languages.*

# Answer
Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular. The following properties can be used:

1. The pumping lemma, as exemplified in Dave's answer;
2. Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
3. A regular language has a finite number of prefix equivalence class, Myhill–Nerode theorem.

To prove that a language $L$ is not regular using closure properties, the technique is to combine $L$ with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, e.g., the archetypical language $I= \\{ a^n b^n \mid n \in \mathbb{N} \\}$. For instance, let $L= \\{a^p b^q \mid p \neq q \\}$. Assume $L$ is regular, as regular languages are closed under complementation so is $L$'s complement $L^c$. Now take the intersection of $L^c$ and $a^\star b^\star$ which is regular, we obtain $I$ which is not regular.

The Myhill–Nerode theorem can be used to prove that $I$ is not regular. For $p \geq 0 $, $I/a^p= \\{ a^{r}b^rb^p\mid r \in \mathbb{N} \\}=I.\\{b^p\\}$. All classes are different and there is a countable infinity of such classes. As a regular language must have a finite number of classes $I$ is not regular.
> 75 votes

# Answer
Based on Dave's answer, here is a step-by-step "manual" for using the pumping lemma.

Recall the pumping lemma (taken from Dave's answer, taken form Wikipedia):

> Let $L$ be a regular language. Then there exists an integer $n\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $n$ ($n$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:
>
> 1. $|y| \ge 1$
> 2. $|xy| \le n$ and
> 3. a "pumped" $w$ is still in $L$: for all $i \ge 0$, $xy^iz \in L$.

Assume that you are given some language $L$ and you want to show that it is not regular via the pumping lemma. The proof looks like this:

1. Assume that $L$ **is** regular.
2. If it is regular, then the pumping lemma says that there exists some number $n$ which is the pumping length.
3. Pick a **specific** word $w\in L$ of length larger than $n$. The difficult part is to know which word to take.
4. Consider **ALL** the ways to partition $w$ into 3 parts, $w=xyz$, with $|xy|\le n$ and $y$ non empty. For **each** of these ways, show that it cannot be pumped: there always exists some $i\ge 0$ such that $xy^iz \notin L$.
5. Conclude: the word $w$ cannot be "pumped" (no matter how we split it to $xyz$) in contradiction to the pumping lemma, i.e., our assumption (step 1) is wrong: $L$ is not regular.

Before we go to an example, let me reiterate Step 3 and Step 4 (this is where most of the people go wrong). In Step 3 you need to pick one specific word in $L$. write it down explicitly, like "00001111" or "$a^nb^n$". Examples for things that are *not* a specific word: "$w$" or "a word that has 000 as a prefix".

On the other hand, in Step 4 you need to consider more than one case. For instance, if $w=000111$ it is not enough to say $x=00, y=01, z=00$, and then reach a contradiction. You must also check $x=0, y=0, z=0111$, and $x=\epsilon, y=000, z=111$, and all the other possible options.

---

Now let's follow the steps and prove that $L= \\{ 0^k1^{2k} \mid k\>0 \\}$ is not regular.

1. Assume $L$ is regular.
2. Let $n$ be the pumping length given by the pumping lemma.
3. Let $w = 0^n 1^{2n}$.
(sanity check: $|w|\gt n$ as needed. Why this word? other words can work as well.. it takes some experience to come up with the right $w$). Again, note that $w$ is a specific word: $\underbrace{000\ldots0}\_{n \text{ times}}\underbrace{111\ldots1}\_{2n \text{ times}}$.
4. Now lets start consider the various cases to split $w$ into $xyz$ with $|xy|\le n$ and $|y|\>0$. Since $|xy|\<n$ no matter how we split $w$, $x$ will consist of only 0's and so will $y$. Lets assume $|x|=s$ and $|y|=k$. We need to consider ALL the options, that is all the possible $s,k$ such that $s\ge 0, k\ge 1$ and $s+k \le n$. *FOR THIS $L$* the proof for all these cases is the same, but in general it might be different.
take $i=0$ and consider $xy^iz = xz$. this word is NOT in $L$ since it is of the form $0^{n-k}1^{2n}$ (no matter what $s$ and $k$ were), and since $k \ge 1$, this word is not in $L$ and we reach a contradiction.
5. Thus, our assumption is incorrect, and $L$ is not regular.

---

A youtube clip that explains how to use the pumping lemma along the same lines can be found here
> 43 votes

# Answer
From Wikipedia, the pumping language for regular languages is the following:

> Let $L$ be a regular language. Then there exists an integer $p\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:
>
> 1. $|y| \ge 1$
> 2. $|xy| \le p$ and
> 3. for all $i \ge 0$, $xy^iz \in L$.
> $y$ is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in $L$).
>
> (1) means the loop y to be pumped must be of length at least one; (2) means the loop must occur within the first p characters. There is no restriction on x and z.
>
> In simple words, For any regular language L, any sufficiently long word $w\in L$ can be split into 3 parts. i.e $w = xyz$, such that all the strings $xy^kz$ for $k\ge 0$ are also in $L$.

Now let's consider an example. Let $L=\\{(01)^n2^n\mid n\ge0\\}$.

To show that this is not regular, you need to consider what all the decompositions $w=xyz$ look like, so what are all the possible things x, y and z can be given that $xyz=(01)^p2^p$ (we choose to look at this particular word, of length $3p$, where $p$ is the pumping length). We need to consider where the $y$ part of the string occurs. It could overlap with the first part, and will thus equal either $(01)^{k+1}$, $(10)^{k+1}$, $1(01)^k$ or $0(10)^k$, for some $k\ge 0$ (don't forget that $|y|\ge 1$). It could overlap with the second part, meaning that $y=2^k$, for some $k\>0$. Or it could overlap across the two parts of the word, and will have the form $(01)^{k+1} 2^l$, $(10)^{k+1} 2^l$, $1(01)^k 2^l$ or $0(10)^k 2^l$, for $k\ge0$ and $l\ge1$.

Now pump each one to obtain a contradiction, which will be a word not in your language. For example, if we take $y=0(10)^k2^l$, the pumping lemma says, for instance, that $xy^2z=x0(10)^k2^l0(10)^k2^lz$ must be in the language, for an appropriate choice of $x$ and $z$. But this word cannot be in the language as a $2$ appears before a $1$.

Other cases will result in the number of $(01)$'s being more than the number of $2$'s or vice versa, or will result in words that won't have the structure $(01)^n2^n$ by, for example, having two $0$'s in a row.

Don't forget that $|xy| \le p$. Here, it's useful to shorten the proof: many of the decompositions above are impossible because they would make the $z$ part too long.

Each of the cases above needs to lead to such a contradiction, which would then be a contradiction of the pumping lemma. Voila! The language would not be regular.
> 30 votes

# Answer
For a given language $L \subseteq \Sigma^\*$, let

$\qquad \displaystyle S\_L(z) = \sum\limits\_{n \geq 0} |L \cap \Sigma^n|\cdot z^n$

the (ordinary) generating function of $L$, i.e. its sequence of word counts per length.

The following statement holds \[FlSe09, p52\]:

$\qquad \displaystyle L \in \mathrm{REG} \quad \Longrightarrow \quad S\_L \text{ rational}$

That is, $S\_L(z) = \frac{P(z)}{Q(z)}$ with $P,Q$ polynomials.

So any language whose generating function is *not* rational is not regular. Unfortunately, all linear languages also have rational generating functions¹ so this method won't work for the simpler non-regular languages. Another drawback is that obtaining $S\_L$ (and showing that it is not rational) can be hard.

**Example:** Consider the language of correctly nested parentheses words, i.e. the Dyck language. It is generated by the unambiguous grammar

$\qquad \displaystyle S \to \[S\]S \mid \varepsilon$

which can be translated into the equation

$\qquad \displaystyle S(z) = z^2S^2(z) + 1$

one solution (the one with all positive coefficients) of which is

$\qquad \displaystyle \mathcal{S}(z) = \frac{1 - \sqrt{1 - 4z^2}}{2z^2}$.

As $S\_L = \mathcal{S}$ \[Kuic70\] and $\mathcal{S}$ is not rational, the Dyck language is not regular.

---

1. The proof for the statement for regular languages works via grammars and transfers to linear grammars immediately (commutativity of multiplication).

---

$\ \ $ \[FlSe09\] *Analytic Combinatorics* by P. Flajolet and R. Sedgewick (2009)
$\ \ $ \[Kuic70\] *On the Entropy of Context-Free Languages* by W. Kuich (1970)
> 17 votes

# Answer
This is an expanded version of my answer from here Using Pumping Lemma to prove language $L = \\{(01)^m 2^m \mid m \ge0\\}$ is not regular since this is supposed to be a reference question.

So, you think the pumping lemma looks complicated? Don't worry. Here's a slightly different take approach, which is hidden in @Romuald's answer as well. (Quiz: where?)

Let's start by remembering that every regular language is accepted by a deterministic finite state automaton (DFA). A DFA is a finite directed graph where every vertex has exactly one out-edge for each letter in the alphabet. Strings give you a walk in the graph based at a vertex labeled "start", and the DFA accepts if this walk ends at a vertex labeled "accept". (The vertices are called "states" because different areas of math like to make up their own terminology for the same thing.)

With this way of thinking it is easy to see that: *If strings $a$ and $b$ drive the DFA to the same state, then for any other string $c$, $ac$ and $bc$ drive the DFA to the same state.* Why? Because the stating point of a walk and the string defining it determine the end completely.

Put slightly differently: *If $L$ is regular and strings $a$ and $b$ drive a recognizing automaton to the same state, then for all strings $c$, either $ac$ and $bc$ are both in $L$ or neither is.*

We can use this to show languages aren't regular by imagining it is and then coming up with $a$ and $b$ driving an DFA to the same state, and $c$ so that $ac$ is in the language and $bc$ isn't. Take the example language from @Dave's answer. Imagine it is regular, so it has some recognizing DFA with $m$ states. The Pigeon Hole Principle says that at least two of $\\{(01)^i : 0\le i\le m+1\\}$ send the DFA to the same state, say $a=(01)^p$ and $b=(01)^q$. Since $p\neq q$, we see that $a2^p$ is in the language and $b2^p$ is not, so this language can't be regular.

The nice thing is that the example is really a template for proving that languages aren't regular:

* Find a family of strings $\\{a\_i :i\in\mathbb{N}\\}$ with the property that each of them has a "tail" $t\_i$ so that $a\_it\_i$ is in the language and $a\_it\_j$, for $i\neq j$ is not.
* Apply the argument above verbatim. (This is allowed, since there are always enough $a\_i$ to let you invoke the Pigeon Hole Principle.)

There are other tricks, but this one will work easily on most of your homework problems.

**Edit:** An earlier version had some discussion of how this idea relates to the Pumping Lemma.
> 15 votes

# Answer
Following the answer here, I will describe a method of proving non-regularity based on Kolmogorv complexity.

This approach is discussed in "A New Approach to Formal Language Theory by Kolmogorov Complexity", by Ming Li and Paul M.B. Vitanyi (see section 3.1).

Let $K(x)$ denote the Kolmogorov complexity of a string $x$, i.e. the length of the shortest encoding of a Turing machine $M$, such that $M(\epsilon)=x$ (any of the usual definitions will do). One can then use the following lemma to prove non regularity:

> **KC-Regularity**: Let $L\subseteq \Sigma^\*$ be a regular language, then there exists a constant $c$ which depends only on $L$, such that for all $x\in\Sigma^\*$, If $y$ is the $n'th$ string (relative to the lexicographic ordering) in $L\_x=\left\\{y\in \Sigma^\*|xy\in L\right\\}$, then $K(y)\le O(\log n)+c$.

One can understand (and prove) the above lemma as follows, for any $x\in\Sigma^\*$, to describe the $n'th$ string in $L\_x$ one needs to specify:

* The automaton which accepts $L$
* The state in the automaton after processing the prefix $x$
* The index $n$

Since we only need to remember the state after processing $x$, and not $x$ itself, we can hide this factor in the constant depending on $L$. The index $n$ requires $\log n$ bits to describe, and we get the above result (for completeness, one needs to add the specific instructions required to generate $y$, but this only adds a constant factor to the final description).

This lemma shows how to bound the Kolmogorov complexity of all strings which are members of $L\_x$ for some regular language $L$ and $x\in\Sigma^\*$. In order to show non regularity, one can assume $L$ is regular, and prove that the bounds are too restrictive (e.g. bounded Kolmogrov complexity for an infinite set of strings).

The answer linked above contains an example of how to use this lemma to show $L=\left\\{1^p | \text{p is prime}\right\\}$ is not regular, several more examples are given in the paper. For completeness, we show here how to prove $L=\left\\{0^n1^n| n\ge 0\right\\}$ is not regular.

Given some $x\in\left\\{0,1\right\\}^\*$, we denote by $y\_i^x$ the $i'th$ word in $L\_x$. Note that $y\_1^{0^i}=1^i$. Using the above lemma, focusing on prefixes $x$ of the form $x=0^i$ and fixing $n=1$, we obtain $\forall i\ge 0 : K(y\_1^{0^i})\le c$. Since $y\_1^{0^i}=1^i$, this means that we can bound the Kolmogorov complexity of all strings of the form $1^i$ by a constant, which is obviously false. It is worth mentioning that we could have examined a single $x$, e.g. $x=0^n$ for large enough $n$ which satisfies $K(0^n)\ge \log n $ (we start with a high complexity prefix). Since $y\_1^x=1^n$, we get $K(1^n)\<c$, contradiction (suppose $n\>2^c$).
> 10 votes

# Answer
In the case of unary languages (languages over an alphabet of size 1), there is a simple criterion. Let us fix an alphabet $\\{ \sigma \\}$, and for $A \subseteq \mathbb{N}$, define $$ L(A) = \\{ \sigma^n : n \in A \\}. $$

> Theorem. Let $A \subseteq \mathbb{N}$. The following are equivalent:
>
> 1. $L(A)$ is regular.
> 2. $L(A)$ is context-free.
> 3. There exist $n\_0,m \geq 1$ such that for all $n \geq n\_0$, it holds that $n \in A$ iff $n+m \in A$. (We say that $A$ is *eventually periodic*.)
> 4. Let $a\_i = 1\_{i \in A}$. Then $0.a\_0a\_1a\_2\ldots$ is rational.
> 5. The generating function $\sum\_{i \in A} x^i$ is a rational function.

The theorem can be proved in many ways, for example using the pumping lemma, Myhill–Nerode theory, Parikh's theorem, the structure of DFAs on unary languages (they look like a "$\rho$", as in Pollard's $\rho$ algorithm), and so on. Here is a useful corollary.

> Corollary. Let $A \subseteq \mathbb{N}$, and suppose that $L(A)$ is regular.
>
> 1. The limit $\rho = \lim\_{n\to\infty} \frac{|A \cap \\{1,\ldots,n\\}|}{n}$ exists. (This is the *asymptotic density* of $A$.)
> 2. If $\rho = 0$ then $A$ is finite.
> 3. If $\rho = 1$ then $A$ is cofinite (that is, $\overline{A}$ is finite).

As an example, the language $L(\\{2^n : n \geq 0\\})$ isn't regular, since the set has vanishing asymptotic density, yet is infinite.
> 8 votes

# Answer
Use Myhill–Nerode theory.

Let $L$ be a language. We say that two words $x,y$ are *inequivalent* modulo $L$ (or: with respect to $L$) if there exists a word $z$ such that exactly one of $xz,yz$ is in $L$. In any DFA for $L$, $\delta(q\_0,x) \neq \delta(q\_0,y)$ (exercise). This implies the following criterion:

> Let $L$ be a language. Suppose that there exists an infinite set of pairwise inequivalent words (that is, an infinite set $S$ such that any two non-equal $x,y \in S$ are inequivalent modulo $L$). Then $L$ is not regular.

Here is a simple example of applying this criterion:

> The language $L = \\{a^nb^n : n \geq 0\\}$ isn't regular.
>
> **Proof.** Let $S = \\{ a^n : n \geq 0 \\}$. We claim that any two different words in $S$ are inequivalent modulo $L$. Indeed, let $a^i,a^j \in S$, where $i \ne j$. Then $a^ib^i \in L$ but $a^ib^j \notin L$.

An important feature of this method is that it is guaranteed to succeed: if $L$ is not regular then there exists an infinite set of pairwise inequivalent words. This is a consequence of the Myhill–Nerode theorem. Briefly, equivalence modulo $L$ (the negation of inequivalence modulo $L$ defined above) is an equivalence relation, and a language $L$ is regular iff the number of equivalence class of equivalence modulo $L$ is finite. If $L$ is not regular, taking one word out of each equivalence classes would constitute an infinite set of inequivalent words.
> 5 votes

# Answer
The class of regular languages is closured under various closure operations, such as union, intersection, complement, homomorphism, regular substitution, inverse homomorphism, and more. This can be used to prove that a given language is not regular by reduction to a language which is already known to be non-regular.

As a very simple example, suppose that we know that the language $\\{a^nb^n : n \geq 0\\}$ is not regular. Then we can prove that the language $\\{w \in \\{a,b\\}^\* : \\#\_a(w) = \\#\_b(w)\\}$ (the language of all words with equally many $a$s and $b$s) is not regular as follows:

> Suppose that $L = \\{w \in \\{a,b\\}^\* : \\#\_a(w) = \\#\_b(w)\\}$ were regular. Then $L \cap a^\*b^\*$ would also be regular. But $L \cap a^\*b^\* = \\{a^n b^n : n \geq 0\\}$, which is known not to be regular.

Here is a more complicated example. Let us show that the language $L' = \\{(0+1)^n2(0+1)^n : n \geq 0\\}$ is not regular.

> Let $h$ be the homomorphism mapping given by $h(0) = 0$, $h(1) = 1$, $h(2) = \epsilon$. If $L'$ were regular then so would the following language be: $h(L' \cap 0^\*21^\*) = \\{ 0^n 1^n : n \geq 0 \\}$. However, we know that the latter isn't regular.

Finally, here is an example using inverse homomorphism. Let us show that the language $L'' = \\{0^n10^n : n \geq 0\\}$ isn't regular.

> Let $k$ be the homomorphism given by $k(0) = 0$, $k(1) = 0$, $k(2) = 1$. If $L''$ were regular then so would $k^{-1}(L'')$ be, but that is just the language $L'$ from the preceding example.
> 5 votes

# Answer
Given a language $L$, for every string $x$ there is a set of strings $y$ such that $xy \in L$. Each such set could be used as a state in a state machine.

All you need to do is to show that the number of such sets is not finite.

As an example, let $L = {a^nb^n: n ≥ 0}$. Given $x = a^nb$ for some $n ≥ 1$, the only string $y$ such that $xy \in L$ is $y = b^{n-1}$. So for every $n$ we have a different set, which means $L$ is not regular.

So in general, if you find an infinite set of strings $x$ such that each $x$ gives a different set $\\{y: xy \in L\\}$ then the language cannot be recognised by a finite state machine, and therefore is not regular.
> 3 votes

---
Tags: formal-languages, regular-languages, proof-techniques, reference-question
---


# Question
Title: Reducing CLIQUE to Super Connector problem
I am trying to show that our problem is NP-Complete by reducing the known problem CLIQUE to our problem.

Regular CLIQUE problem:

> **Input:** An undirected graph $G$ and a positive integer $K$.
>
> **Goal:** Does $G$ have a clique of size at least $K$?

Our problem:

> **Input:** An undirected graph $G$ and a positive integer $K$.
>
> **Goal:** Is there a group of size $K$ of super connectors in $G$?

A *super connector* is a node with at least $C$ (i.e., a fixed number of) edges. A group $S$ of super connectors is a set of super connectors all connected to each other.

A group of super connectors is thereby a clique and a return value of TRUE from our problem will result in TRUE in the CLIQUE problem as well.

My idea to solve this is that I modify the graph by removing all nodes that aren't super connectors. We are then left with a graph where every node is super connectors and can then input the graph in the CLIQUE problem to see if there exists a clique and thereby get a solution for our problem. By modifying the graph like this both of the problems will give the same outputs with the same inputs. Am I on the right path or completely wrong?

# Answer
> 3 votes
The simplest NP-hardness reduction is as follows. Suppose we are given an instance $(G,k)$ of CLIQUE. If $k \leq c$ then we solve CLIQUE by brute force in time $O(n^c)$. Otherwise, $G$ has a $k$-clique iff it has a $k$-clique consisting of super-connectors. This is because any vertex in a $k$-clique must have degree at least $k-1 \geq c$, and so is a super-concentrator.

---
Tags: np-complete, clique
---


# Question
Title: context-free grammar for comma-separated list with comments
I'm trying to write a context-free grammar for a comma-separated list of statements with comments. It is trivial if the comma appears at the end of a statement. It is trivial if the comment is ignored. But I don't know how to include a comma in the middle of a statement (before the comment).

This Python / Lark CFG:

```
start: def+

def: "{" statement ("," statement)* "}"

!statement: NAME "=" (
    | "Foo"
    | "Bar" "(" NAME ")"
    | "Tomato"
    | )

NAME: /[A-Z][a-z-]{0,15}/

COMMENT: "//" /.*/

%import common.WS
%ignore WS

```

parses this text:

```
{
    Mike = Foo,
    Fred = Bar(Chocolate),
    Joe = Tomato
}

```

producing this AST:

```
start
  def
    statement
      Mike
      =
      Foo
    statement
      Fred
      =
      Bar
      (
      Chocolate
      )
    statement
      Joe
      =
      Tomato

```

I want to parse the content of comments into the AST, not just ignore it:

```
{
    Mike = Foo,
    Fred = Bar(Chocolate),      // Yummy!
    Joe = Tomato
}

```

======= EDIT =========

The problem from which the question was distilled requires an optional description tied to each assignment. Arbitrary comments (such as on the lines with braces) aren't needed. So Yuval's answer (with the addition of a trailing comment) works like a charm. For completeness, the working grammar is:

```
start: def+
def: "{" statement ("," COMMENT? statement)* COMMENT? "}"

statement: NAME "=" (foo | bar | tomato)
foo:    "Foo"
bar:    "Bar" "(" NAME ")"
tomato: "Tomato"

```

and produces the AST:

```
start
  def
    statement
      Mike
      foo
    // Stuff
    statement
      Fred
      bar   Chocolate
    // Yummy!
    statement
      Joe
      tomato
    // aaaargh

```

# Answer
Define a non-terminal `COMMENT` which generates comments (in your case, `//` followed by arbitrary non-newline characters and then newline), as well as the empty string. In the definition of `def`, add `COMMENT` after `,`.
> 1 votes

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


title: Reduce 4-SAT to 5-SAT

text:
# Question
Title: Reduce 4-SAT to 5-SAT
given is a reduction from 4-SAT to 5-SAT. How is it possible to describe such a function? I found some informations about reduction 3-SAT to 4-SAT here, but it can't help me so much.

# Answer
Here is a translation of the answer how to prove 4-SAT CNF is NP-complete to the current situation.

---

Suppose an instance of 4-SAT over variables $x\_1,x\_2,\cdots, x\_m$ is given as a boolean formula $$f=c\_1\land c\_2\land \cdots\land c\_m,$$ where $c\_i$ is a disjunction that has exactly 4 literals for all $i$.

Introduce a new variable $s$. Suppose $c\_i=w\lor x \lor y \lor z$ for some literal $w,x,y,z$. Let $$\begin{aligned} c\_{i+}&=w\lor x \lor y \lor z\lor s\\ c\_{i-}&=w\lor x \lor y \lor z\lor \neg s. \end{aligned}$$

* If $c\_i$ can be satisfied by an assignment, then $c\_{i+}\land c\_{i-}$ is satisfied by the same assignment plus $s=0$ (or $s=1$).
* If $c\_{i+}\land c\_{i-}$ can be satisfied by an assignment, the same assignment without considering $s$ must satisfy $c\_i$ since one of $s$ and $\neg s$ must be false.

Construct an instance of 5-SAT over variables $x\_1,x\_2,\cdots, x\_m, s$, $$g=c\_{1+}\land c\_{1-}\land c\_{2+}\land c\_{2-}\land\cdots\land c\_{m+}\land c\_{m-}.$$

Because of the relation between $c\_i$ and $c\_{i+}\land c\_{i-}$,

* If $f$ is satisfied by an assignment, then $g$ is satisfied by the same assignment plus $s=0$.
* Conversely, if $g$ is satisfied by an assignment, then $f$ is satisfied by the same assignment without considering $s$.

The above means the transformation from $f$ to $g$ is a reduction from 4-SAT to 5-SAT. It runs in polynomial time.

---

For simplicity of explanation, the above restricts $k$-SAT to CNF formulas with exactly $k$ literals without duplicates. Thanks to a similar simple padding technique, it is does not matter to the construction of reduction above whether we allow at most $k$ literals with or without duplicates when we define $k$-SAT.
> 3 votes

# Answer
Since you did not specify exactly the two languages, let us suppose that 4-SAT is a CNF of this type: *(A ∨ B ∨ C ∨ D) ∧ (A¯ ∨ C¯ ∨ F ∨ S) ∧ (E ∨ G ∨ H¯ ∨ Q) ∧ ....* A way to reduce this instance of k-SAT into an instance of (k+1)-SAT is this: you can add inside every clause a further literal (for example Z) so the first clause will become **(A ∨ B ∨ C ∨ D ∨ Z)**, the second clause will become **(A¯ ∨ C¯ ∨ F ∨ S ∨ Z)**, the third clause will become **(E ∨ G ∨ H¯ ∨ Q ∨ Z)** and so on. It is easy to observe that by assigning the value 0 to the variable Z, you get an instance of 5-SAT which is verified if and only if the starting 4-SAT instance is verified.
> 0 votes

---
Tags: time-complexity, np-complete, np-hard, satisfiability, polynomial-time
---


# Question
Title: What is an array that can be iterated circularly an infinite amount of times called?
I have a feeling that the answer is either a "circular linked list" or a finite state machine, but the answer is probably a circular linked list.

# Answer
The answer is circular buffer.
Such structure could be implemented using array or linked list, but you cannot call explicit array-based circular buffer as linked-list.

FSA cannot be "executed" infinitely (type 3 machine only uses fixed input and reads it ones), unless your FSA definition covers Turing Machines.
> 2 votes

---
Tags: arrays, loops, lists
---


title: What is a Meta algorithm?

text:
# Question
Title: What is a Meta algorithm?
I am currently reading a survey paper on the multiplicative weight update meta-algorithm. I am not quite sure what they mean by "meta-algorithm". Is it simply a general algorithm that can be used for different purposes?

I couldn't find any exact definition for this term, though I have found examples of meta-algorithms such as Boosting in machine learning.

# Answer
I interpret it as meaning "algorithmic technique". It's a general framework that can be used to solve a number of problems.

Don't worry too much about the meaning of that phrase. It's not something with an accepted definition, and you don't need to understand it to gain the value from that survey paper; it's just a passing phrase. Instead, focus on understanding the ideas and technical results in the survey paper.
> 13 votes

# Answer
The term "meta-algorithm" has a fairly well-accepted meaning in the context of learning theory, which is the field of research from which multiplicative weights originates.

Specifically, a meta-algorithm, in the context of learning theory, is an algorithm that decides how to take a set of other (typically, though not necessarily non-meta) "algorithms" (which might be as dumb as a constant output, for example), and constructs a new algorithm out of those, often by combining or weighting the outputs of the component algorithms. (Don't take this to be a canonical definition though.) Typically those component algorithms are viewed as black-boxes taking input and producing their output, with the inner workings hidden/irrelevant.

There are a number of examples of meta-algorithms. The referenced Multiplicative Weighting algorithm is one example. A particularly simple example is majority voting for an ensemble of binary classifiers: Suppose you have a bunch of binary classification algorithms, and you don't know how to pick a good one. You can just compute them all, and let them vote. Voting in this case is the meta-algorithm. Of course, this may not work very well, and you might want to do something like weighted voting, where the weight somehow scales with observed performance.

Just a few examples of meta-algorithms that I can think of at the moment:

* multiplicative weights
* weighted majority
* boosting
* bagging
* ensemble averaging, voting
* "Follow the Leader"

As always, you can find examples that blur the line between meta and not meta. For example, K-nearest neighbors could be considered a weighted voting/averaging of component algorithms, where every potential neighbor (i.e. the labeled points in the dataset) is its own component algorithm, having a constant output, and the weighting is a function of distance from the algorithm input.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Is every X3SAT instance with no cycles satisfiable?
Exactly 1 in 3 SAT (X3SAT) is a variation of the Boolean Satisfiability problem. Given a set of clauses, where each clause has three literals, is there an assignment such that in each clause exactly one literal is true? X3SAT is NP-hard even if we assume all literals are positive (monotone) and no two clauses have more than one literal in common (linear).

A cycle is a set of clauses such that each clause has one free literal and two backbone literals. A literal is free if it appears in only one clause in the cycle. A backbone literal appears in exactly two cycle clauses.

My question: Is a linear and monotone X3SAT instance with no cycles always satisfiable?

---

*Background:* We can think of linear monotone X3SAT as the following problem: we are given a set of clauses, where each clause has three positive literals and no two clauses have more than one literal in common; the goal is to determine whether there is a set of literals such that each clause contains exactly one literal from the set.

I have generated a number of unsatisfiable linear monotone X3SAT instances and they all have large numbers of cycles, so I'm wondering if every unsatisfiable linear monotone X3SAT instance will have at least one cycle.

The smallest linear and monotone cycle has three clauses:

$\quad$ 3-cycle: $(a,x\_1,x\_2)(b,x\_2,x\_3)(c,x\_3,x\_1)$
$\quad$ Free: $a,b,c$
$\quad$ Backbone: $x\_1,x\_2,x\_3$

A cycle can have more than three clauses. A cycle with $k$ clauses has $2k$ distinct literals, $k$ free literals, and $k$ backbone literals. A $k$-cycle has $\lceil F\_{k+3} / 2\rceil$ satisfying assignments, where $F\_i$ is the $i$-th Fibonacci number.

The smallest unsatisfiable linear and monotone X3SAT instance has six 3-cycles, but only five clauses:

$\quad (a,x\_1,y\_1)(a,x\_2,y\_2)(a,x\_3,y\_3)(x\_1,x\_2,x\_3)(y\_1,y\_2,y\_3)$

It contains the following 3-cycles:

$\quad(x\_1,x\_2,x\_3)(a,x\_1,y\_1)(a,x\_2,y\_2)$
$\quad(x\_1,x\_2,x\_3)(a,x\_1,y\_1)(a,x\_3,y\_3)$
$\quad(x\_1,x\_2,x\_3)(a,x\_2,y\_2)(a,x\_3,y\_3)$
$\quad(y\_1,y\_2,y\_3)(a,x\_1,y\_1)(a,x\_2,y\_2)$
$\quad(y\_1,y\_2,y\_3)(a,x\_1,y\_1)(a,x\_3,y\_3)$
$\quad(y\_1,y\_2,y\_3)(a,x\_2,y\_2)(a,x\_3,y\_3)$

X3SAT can be converted into a max weight independent set problem. Let each literal be assigned a vertex. Two vertices have an edge iff the two literals appear together in a clause. The weight of each vertex is the number of clauses the literal appears in (one half the degree of the vertex). The X3SAT instance is solvable only if there is an independent set with weight equal to the number of clauses. If the instance is satisfiable then the graph can be made bipartite by removing exactly one edge from each clause.

# Answer
The graph below is a positive answer without words.

---

Here is the detailed proof.

### Definitions

Let $X$ be an instance of **X3SAT**.

* $X$ is linear if any two clause shares at most one variable.
* $X$ is monotone if all literals in all clauses are positive.
* A walk in $X$ is a sequence of clauses where each clause is not disjoint with the clause following it. The length of the walk is the number of its clauses. A walk starts with variable $v$ if its first clause contains $v$. A walk ends with variable $v$ if its last clause contains $v$. A walk is said to connect two variables if it starts with one of the variables and ends with the other variable. In particular, any clause connects all variables in it.
* A trail is a walk in which all clauses are distinct.
* $X$ is connected if there is a walk between any two variables.
* A cycle is a walk whose first clause is its last clause. A simple cycle has no repeated clauses except the first and last clause. $X$ is acyclic if $X$ has no simple cycles, i.e., there is at most one trail between any two variables,
* For any two variables, the distance between them is the minimum length of a walk that connects them. The distance between a variable and itself is 0.

### A linear monotone acyclic instance of X3SAT is always satisfiable.

Let $X$ be a linear monotone acyclic instance of X3SAT whose set of variables is $V=\\{v\_1,v\_2, \cdots, v\_n\\}$. Because of monotonicity, we will use variable and literal interchangeably. Each clause in $X$ is also treated as the set of three variables in it.

Assume $X$ is connected. Otherwise, $X$ is the union of two disjoint linear monotone acyclic instances of X3SAT that can be treated independently.

Let $d(u)$ denote the distance from $v\_1$ to variable $u$.

**Claim 1. For any clause $c=(t,u, w)$, $\\{d(t), d(u), d(w)\\}=\\{\ell, \ell, \ell-1\\}$ for some $\ell\ge1$.**

**Proof**: If $c$ contains $v\_1$, then it is easy to see that $\\{d(t), d(u), d(w)\\}=\\{1, 1, 0\\}$. Now assume $c$ does not contain $v\_1$.

WLOG, let $d(w)=\ell-1 \> 0$ be the minimum among the three distances. Let $c\_1, \cdots, c\_{\ell-2}, c\_{\ell-1}$ be the unique trail from $v\_1$ to $w$. The shared variable between $c\_{\ell-2}$ and $c\_{\ell-1}$ cannot be $t$ or $u$, since $d(t)\ge \ell-1$ and $d(u)\ge\ell-1.$ That means $c\_{\ell-1}\not=c$. Suppose there is a trail $b\_1, b\_2, \cdots, b\_{\ell-1}$ from $v\_1$ to $t$. Then for the same reason, $b\_{\ell-1}\not=c$. We can reduce the walk $c\_1, \cdots, c\_{\ell-2}, c\_{\ell-1}, c, b\_{\ell-1}, b\_{\ell-2}, \cdots, b\_1, c\_1$ to a simple cycle, which is a contradiction, which implies that there is no trails of length $\ell-1$ from $v\_1$ to $t$, i.e., $d(t)\gt\ell-1$. Since $c\_1, c\_2, \cdots, c\_{\ell-1}, c$ is a walk of length $\ell$ from $v\_1$ to $t$, $d(t)=\ell$. Similarly, $d(u)=\ell.$ QED.

Fix a total order $\prec$ on $V$. For example, we can let $v\_p\prec v\_q $ if $p\<q$.

Let $A\_0=\\{v\_0\\}$. For all $\ell\ge 1$, define $A\_{\ell}$ recursively by
$$A\_\ell= \\{t\in V: d(t)=\ell \text{ and the last clause of the shortest trail}\\ \text{ from } v\_1\text{ to }t\text{ is }(t,u, w)\text{ for some }u,w\in V \text{ such that }\\ d(t)=d(u)=\ell\text{ and }d(w)=\ell-1\text{ and } w\not\in A\_{\ell-1}\text{ and }t\prec u\\}$$ Let $A=\cup\_{\ell=0}^{\infty}A\_\ell$. Note that if $d(t)=\ell$, then $t\in A$ iff $t\in A\_\ell$.

**Claim 2: $A$ shares exactly one variable with each clause.**

Proof. Let $c$ be a clause in $X$. By claim 1, $c=(t,u,w)$ where $d(t)=d(u)=\ell$, $d(w)=\ell-1$ and $t\prec u$. The last clause of the shortest trail from $v\_1$ to either $t$ or $u$ is $c$.

* $w\in A\_{\ell-1}$. By definition, $t$ and $u$ are not in $A\_\ell$.
* $w\not\in A\_{\ell-1}$. By definition, $t\in A\_\ell$ and $u\not\in A\_\ell$.

QED.

### Exercises

Let X be a linear monotone acyclic instance of X3SAT with $n$ variables and $m$ clauses.

**Exercise 1.**.(One minute or two) Explain that $A\_1$ is empty. Give an example where $A\_3$ is not empty.

**Exercise 2.**. Show that $n= 2m+1$.
> 4 votes

# Answer
I have extended this proof to show a linear, monotone X3SAT instance with any number of non-intersecting cycles is always satisfiable. Two cycles intersect if they have a variable in common

Cases to consider include cycles with an even number of clauses, cycles with an odd number of clauses, a cycle that contains the origin, and cycles that don't contain the origin. Since the algorithm described sometimes chooses literals lexicographically, the way a cycle is labeled can change the satisfying assignment found. The following algorithm handles all of these cases. The basic idea is to totally order the clauses and then satisfy each clause in order while doing the X3SAT equivalent of unit clause propagation.

Assume every literal can be lexicographically ordered. Create a graph by assigning a vertex to each literal. Two literals are connected by an edge if the two literals appear together in a clause. The X3SAT instance is satisfiable if the graph can be made bipartite by removing one edge from each clause.

Choose the lexicographically lowest order literal and make it the origin of the graph. Assume this literal is assigned true. The distance between a literal and the origin is the smallest number of edges connecting the literal to the origin. The distance of a clause from the origin is the distance from the origin to the closest literal(s) in the clause.

At this point I want to define several types of literals. A cycle has two types of literals: "Backbone" literals are literals that appear in two of the cycle's clauses. "Free" literals appear in only one of the cycle's clauses.

Apass Jack proves every clause has one literal that is "closest" to the origin and two "furthest" literals in a linear, monotone X3SAT instance with no cycles. In a linear, monotone X3SAT instance with no intersecting cycles it is possible for a clause to have two closest literals, but, no clause can have all three literals the same distance from the origin. For a clause to have two closest literals, both literals must be backbone literals in a cycle. If all three literals in the clause are the same distance from the origin then all three literals must be backbone literals in a cycle. This would require the clause to be in three intersecting cycles and we are assuming the instance has no intersecting cycles. This shows every clause must have at least one literal "closest" to the origin and at least one "furthest" literal.

Order the clauses by their distance from the origin. We will "impose" an order on furthest literals based on the order of the clauses that are the same distance from the origin.

Clauses that are the same distance from the origin should first be ordered by the imposed order of their closest literals and then ordered by the lexicographically lowest ordered furthest literal. This determines a total order of the clauses and imposes a total order on the literals. Here is an example:

$\quad(a,b,z)(a,c,e)(c,f,g)(f,h,i)(b,x,y)(z,j,k)$

$a$ is the origin.

$\quad(a,b,z)$ and $\quad(a,c,e)$ are distance-$0$ from the origin.

We order them first by the closest literal which is $a$ in both clauses. Then we order them by the lexicographically lowest ordered furthest literal. $b$ comes before $c$, so,

$\quad(a,b,z)$ comes before $\quad(a,c,e)$.

This imposes the order $a,b,z,c,e$ on the literals in distance-$0$ clauses. The clauses

$\quad(c,f,g), (b,x,y), (z,j,k)$

are distance-$1$ from the origin. We first order these clauses by the closest literals using the imposed order:

$\quad(b,x,y)(z,j,k)(c,f,g)$.

This is enough to order the clauses and imposes the order $a,b,z,c,e,x,y,j,k,f,g$.

$\quad(f,h,i)$ is the only distance-$2$ clause from the origin.

Clausal order: $\quad(a,b,z)(a,c,e)(b,x,y)(z,j,k)(c,f,g)(f,h,i)$

Imposed literal order: $a,b,z,c,e,x,y,j,k,f,g,h,i$

Process each clause in order. Note that as each clause is processed the literal(s) closest to the origin already have an assignment from a previous step. For example, in distance-$0$ clauses, the origin has already been assigned to true. This means all other literals in distance-$0$ clauses must be false. The closest literal in distance-$1$ clauses must be one of those literals assigned false in distance-$0$ clauses. Similarly, the closest literal(s) in each clause will have been assigned a truth value in an earlier step.

When a clause is processed in order, all of the assigned literal(s) will be false, Choose the lowest order unassigned literal in the clause and assign it true. All other literals in the clause are assigned false. Propagate these assignments to other clauses. In particular, when an unassigned literal is assigned to true then process all clauses with this literal immediately and set all other literals in these clauses to false (unit clause propagation).

An example. The instance is listed in clausal order.

4-Cycle that contains the origin:

$\quad(a,b,c)(b,d,e)(c,f,g)(d,f,h)$

$\quad(a,b,c)$ : $A$ is the origin and assigned true so $b$ and $c$ must be false: $\quad(A,b,c)$

$\quad(b,d,e)$ : $b$ is false so choose the lowest order unassigned furthest literal, $D$, to be true: $\quad(b,D,e)$

$\quad(d,f,h)$ : Propagate $D$ is true and set $f$ and $h$ to false: $\quad(D,f,h)$

$\quad(c,f,g)$ : $c$ and $f$ are false so the lowest order unassigned furthest literal, $G$, is set true: $\quad(c,f,G)$

$\quad(A,b,c)(b,D,e)(c,f,G)(D,f,h)$

Proof of the correctness of the algorithm.

Every clause will be either processed in order or processed out of order.

A clause is processed out of order when a previous step sets a literal in the clause to true (unit propagation step). All other literals in the clause are set to false and the clause will always be satisfied if it is processed out of order.

When a clause is processed in order then all of the closest literals will have been set to false in a previous step. If the clause is part of a cycle then it is possible one of the furthest literals may have been set to false in a previous step. This can only happen if the furthest literal is a backbone literal. This happens in the example above. When $\quad(b,D,e)$ is processed, $D$ is set to true and this propagates to $\quad(D,f,h)$ forcing $f$ to be false. $f$ is a backbone literal in the $4$-cycle and a furthest literal in $\quad(c,f,g)$. I have already shown that all three literals in a clause can't be backbone literals because this would require intersecting cycles. This means when a clause is processed in order there must be at least one unassigned furthest literal in the clause. This literal can be set to true satisfying the clause (this is literal $G$ in $\quad(c,f,G)$ in the example).

This proves the algorithm will satisfy all clauses in a linear, monotone X3SAT instance with no intersecting cycles.

---

I want to correct this answer. This proof shows a linear, monotone X3SAT instance is solvable unless there exists a clause where all three literals in the clause are backbone literals. This is not the same as saying the instance has no intersecting clauses as I mistakenly claimed. In some ways, this is a stronger claim since an instance can have intersecting cycles and still have no clause where all three literals are backbone literals.

This is an example of an instance that has no intersecting cycles, yet, there is a clause with three backbone literals:

$\quad(a1, x1, x2) (a2, x2, x3) (a3, x3, x1)$

$\quad(b1, y1, y2) (b2, y2, y3) (b3, y3, y1)$

$\quad(c1, z1, z2) (c2, z2, z3) (c3, z3, z1)$

$\quad(x1, y1, z1)$

x1, y1, and z1 are backbone literals even though the clause (x1, y1, z1) is not part of any cycle.

The algorithm does find satisfying assignments for this instance. Choosing a1 to be the origin gives the solution where a1, a3, y1, a2, c1, c3, b2, and c2 are true and all other variables are false.

$\quad(A1, x1, x2)(A2, x2, x3)(A3, x3, x1)$

$\quad(b1, Y1, y2)(B2, y2, y3)(b3, y3, Y1)$

$\quad(C1, z1, z2)(C2, z2, z3)(C3, z3, z1)$

$\quad(x1, Y1, z1)$
> 1 votes

---
Tags: satisfiability, boolean-algebra, 3-sat, constraint-satisfaction, bipartite-graph
---


# Question
Title: How does one know what statements in Coq require Induction?
I was trying to learn Coq using the famous book Software Foundations. In it I found the following:

```
Theorem mult_0_r : forall n:nat,
  n * 0 = 0.
Proof.
  induction n as [| n IHn].
  - simpl. reflexivity.
  - simpl. rewrite -> IHn. reflexivity.
Qed.

```

which I understand perfectly but find rather unintuitive. I understand perfectly how each step works but it would have never occurred to me to use induction to prove such a trivial fact. In fact in the mathematical proof I had in mind that would have been a fact/property (or I guess an axiom) of `0`. i.e. $\forall n \in N, n \cdot 0 = 0$ is true by definition. I guess in Coq (or the way we set up numbers? thats not true).

My biggest complaint or worry is that if such a trivial thing requires induction I feel now I am unable to recognize what needs induction (at least in Coq). I know it needs it here because I am in the induction chapter. But in normal maths its usually quite obvious because the problem is obviously recursive. But I wouldn't have really thought of that proposition as recursive. For example it goes on to prove more things as exercises:

```
Theorem plus_n_Sm : ∀n m : nat,
  S (n + m) = n + (S m).
Proof.
  (* FILL IN HERE *) Admitted.
Theorem plus_comm : ∀n m : nat,
  n + m = m + n.
Proof.
  (* FILL IN HERE *) Admitted.
Theorem plus_assoc : ∀n m p : nat,
  n + (m + p) = (n + m) + p.
Proof.
  (* FILL IN HERE *) Admitted.

```

which I am sure are not too difficult, but my worry is that in isolation I would have never thought such trivial statements required something as sophisticated as induction. I didn't even learn induction until last 2 years of highschool and didn't really do it seriously until college. So now I see trivial statements requiring what seems to me, sophisticated mathematics.

I just feel my intuition got really lost. When I do Coq proofs (in isolation), how do I know when to use induction and on what? I doubt there is a general procedure (of course) but proofs do exist. So there must be something guiding us to use induction in Coq.

# Answer
> 6 votes
Coq allows one to prove mathematical theorems in a completely formal way. At first, this copes with our experience of doing maths, which is far more informal.

Most of the time, people doing maths are not exposed to mathematical logic. They do not know, for instance, how to define the set of real numbers. Or even the set of natural numbers. Numeric sets are simply taken for granted, together with their operations and related properties. On top of these "basic facts" people build more complex theorems. Essentially, the "basic facts" are used as if they were axioms.

Note that one could work at a similar level in Coq, if one wishes. One can import the `Arith` Coq library, which provides the basic facts of arithmetics, and exploit those.

However, the underlying logic of Coq does not take those properties for granted. The type of natural numbers, for instance, is not a primitive concept in the logic, but rather something which is defined using induction. Since that makes `nat` an inductive type, virtually every proof about naturals will require induction. (This also holds in set theory, e.g. Zermelo-Fraenkel, where naturals are also defined in a sort-of inductive way.)

Arithmetical operators are also defined using induction. Using a simplified syntax, one could define multiplication as

```
x * 0     = 0
x * (S y) = x + (x * y)

```

or, alternatively,

```
0 * x     = 0
(S y) * x = x + (y * x)

```

Both definitions are equivalent. However, using the first one will result in us being able to prove `x * 0 = 0` "without induction" -- it follows by definition. In Coq, we can simply write `reflexivity` and let the system expand the definition for us.

By comparison, `0 * x = 0` is not a trivial equation which follows from the definition: to expand the definition we need to know what is the second argument of the multiplication, but here it's merely an unknown `x`. Hence, for this we do need induction over `x`. There's no way around that.

Note that, if we used the second definition instead, we would prove `0 * x = 0` immediately, and instead require induction for `x * 0 = 0`. So, no definition is strictly better than the other one.

# Answer
> 5 votes
As the others have mentioned, in Coq's standard library (or typical presentations of naturals in Coq), naturals are defined inductively, usually a la Peano. We could make other choices, e.g. one could imagine defining naturals as the free semiring on one generator which would give you many of the "axiomatic" facts for "free". (Well, you'd have to prove them about general rings...)

For *any* inductively defined type, `T`, whenever you want to prove a statement of the form `forall x:T, P(x)` you will need to use induction on `T` unless the proof doesn't actually depend on `T`, i.e. it is parametric, e.g. `forall x:T, x = x`. In fact, all proofs of this form can be written as an induction, they may just be a trivial induction. Often the induction will be hidden away in some lemma.

However, the key concept it seems you are unfamiliar/uncomfortable with is the notion of definitional equality in intensional dependent type theories like Coq. Let's say you state that $2$ means $1+1$. If you then ask whether $2=1+1$ there are no steps of proof required. You simply substituted the meaning of $2$ and see that $1+1=1+1$ which is true by reflexivity. More generally, (closed) terms in Coq have normal forms, and Coq treats any two terms with the same normal form as identical. This is definitional equality. Reducing to that normal form may involve large amounts of computation, but there is no proof rule that to tell Coq to reduce a term to normal form. It just does it in the background as necessary to perform type checking. Definitions, such as the one for multiplication reproduced below:

```
Fixpoint mul n m :=
  match n with
  | 0 => 0
  | S p => m + p * m
  end
where "n * m" := (mul n m) : nat_scope.

```

introduce new (non-normal) terms and new computational rules for normalizing them. In this case, it adds a rule that says `0 * x = 0`. These follow from the generic rules for `Fixpoint` and `match` for the Coq type theory. If you were to ask whether `forall x:nat, 0 * x = 0`, Coq sees `forall x:nat, 0 = 0` since `0` is the normal form of `0 * x`. There is no computational rule saying how `x * 0` should be reduced when `x` is a variable, so the "normal" form of `x * 0` is `x * 0`. With this understanding, it is much easier to see why and how induction helps in this particular case. When we do induction, we get two new problems: `0 * 0 = 0` and `(S p) * 0 = 0` which allows steps of computation to be performed. In the latter case, we get `0 + p * 0` which then leans on the computation rules induced by the definition of natural number addition, but also leaves us with `n * 0` which requires the induction hypothesis to resolve.

At more advanced levels of proof engineering, it is common to try to set up definitions so that a decent amount of work can be done by this implicit computation mechanism. Extreme forms of this are reflection principles where we prove an implementation of a decision procedure correct after which we can simply run it and appeal to this result to prove other results. Techniques like this are behind things like the `ring` solver and `ssreflect`.

# Answer
> 3 votes
To see how you can prove something about natural numbers, you must know what you know about natural numbers. Usually, we learn all sorts of 'basic facts' about numbers in high school that are pretty much given without further proof, which we can use later to prove more interesting statements about numbers.

In most mathematical disciplines, this 'naive' approach to numbers is fine. However, when we care about the formalization of numbers, we want a 'minimal definition' of what a number (and related concepts such as successors, predecessors and arithmetic) is and prove all 'basic facts' from them.

So, in the book you're reading, all we know about numbers is the following definition:

```
   Inductive nat : Type :=
     | O
     | S (n : nat).

```

That is, natural numbers are an inductive type, defined as either the natural number O or the successor of a natural number. This is the reason why we do proofs by induction: it is all we know about the natural numbers in this setting.

---

So, where did your intuition let you get lost? When learning mathematics, you get taught that 'basic facts' about numbers early on, which therefore seem easy and get taught induction fairly late (and when you actually have to prove things!) which makes it seem hard.

What is actually the case is that, from a viewpoint of formalisation, induction is the one fundamental property of natural numbers! The best way to see this is that, in fact, all other properties of natural numbers follow from it.

My final advice is not to worry. The fact that all 'basic facts' are suddenly not as basic as they may have seemed so far can be intimidating, but this is simply what formalisation is about: having rigid constructions for 'basic facts'. Once you have these in place, you can prove more complicated statements as usual, by relying on the 'basic facts' just proven.

# Answer
> 3 votes
I want to share my own experience of learning Coq and theorem proving in general.

Most of the time, the proof of a statement largely depends on the recursive structure of the *function* or *operation* at hand. IMHO it is even more important than the recursive structure of *data types*.

Again, let's look at multiplication of natural numbers.

```
Fixpoint mul n m :=
  match n with
  | 0 => 0
  | S p => m + p * m
  end
where "n * m" := (mul n m) : nat_scope.

Theorem mult_0_r : forall n, mul n 0 = 0.

```

(Before you write a proof, just focus on the definition of the function, and ignore what it means as a number operation.)

The definition of `mul` matches on the structure of `n`, then, if `n = S p`, recursively calls itself with `p`. The structure is the strong sign that you'll need induction on the first argument of `mul`. On the other hand, you won't need to do `induction` on the second argument, or even `destruct`, simply because it's not pattern-matched inside `mul`.

This applies to more complex statements as well. Say we were to prove distributivity of multiplication over addition:

```
Theorem mult_distr_plus_r : forall n m p, (n + m) * p = n * p + m * p.

```

And suppose that we know both `plus` and `mult` are recursive on the first argument. In this case, the natural choice to do induction on is `n` because, by its positions, destructing `n` gives the largest amount of expansion (three times in total):

```
(S n + m) * p = S (n + m) * p = p + (n + m) * p
S n * p + m * p = (p + n * p) + m * p

```

It's easy to see that you can complete this proof by IH and `plus_assoc`.

In contrast, destructing `m` gives just one, and `p` gives none, so you'll need more lemmas to complete the proof (e.g. `plus_n_Sm`, `plus_comm` if you destruct `m`, `mult_n_Sm` in addition if you destruct `p`).

```
(n + S m) * p = ?
n * p + S m * p = n * p + (p + m * p)

(n + m) * S p = ?
n * S p + m * S p = ?

```

---

Here's another example to show that proof by induction depends on the function structure. Suppose we have the Fibonacci function:

```
Fixpoint fib n :=
  match n with
  | 0 => 0
  | 1 => 1
  | S (S p) => fib p + fib (S p)
  end.

```

Then we want to prove some property on it, say it gives the same result as another definition of Fibonacci.

```
Theorem fib_is_fib' : forall n, fib n = fib' n.

```

Now, the recursive structure of `fib` is more complicated than `mul` above. It has two base cases, and the result of `fib (S (S p))` depends on both `fib p` and `fib (S p)`. If you try good ol' induction (with tactic `induction n.`) on it, you immediately fail.

In order to prove a property of `fib`, you actually need a stronger induction principle:

* Given a property P on natural numbers, if all of the following holds:
    + P holds for 0.
    + P holds for 1.
    + If P holds on `n` and `S n`, it holds on `S (S n)`.
* Then P holds on all natural numbers.

In Coq:

```
Theorem nat_ind_fib :
  forall P : nat -> Prop, (* For a given property P, *)
  P 0 ->                  (* if P holds for 0 *)
  P 1 ->                  (* and 1, *)
  (forall n : nat, P n -> P (S n) -> P (S (S n))) ->
                          (* and `P n` and `P (S n)` implies `P (S (S n))` *)
  forall n : nat, P n.    (* then P holds for all n. *)

```

Now we can prove a property on `fib` by induction using tactic `induction n using nat_ind_fib.`

---
Tags: induction, coq
---


# Question
Title: In which reference can I find a definition for the equivalence of DFAs?
How is the equivalence of DFA defined? I found the equivalence of states --- James Hein, section 5.3, page 301. But he doesn't define equivalence between entire automata. (Ullman and Hopcropft seem to define neither.)

# Answer
You can find a definition in Automata Theory, Languages and Computation by Hopcroft, Motwani, Ullman, in the fourth chapter.

Here's a link : HMU, the section begins at page 171 of the pdf

Two DFA are said to be equivalent if they accept the same language, and (an equivalent proposition) if they have the same minimal automaton (which is unique).
> 2 votes

---
Tags: finite-automata, reference-request
---


# Question
Title: Why run -time of N-Queens using backtracking algorithm fluctuates?
I have tested and measured the running time of a backtracking algorithm for solving the $N$-Queens problem. When $N=7$, the run time is $0.773$, but for $N=8$, the run time is $0.492$.

I think the run time should grow exponentially with the size of $N$. Why is the algorithm slower for $7$ than for $8$? This case also happens between $20$ and $21$ ,$28$ and $29$. This is my pseudocode.

`Function BACKTRACKING-SEARCH(csp)returns a solution,or failure
 return BACKTRACK({},csp)
Function BACKTRACK(assignment, csp) returns a solution, or failure
begin
if assignment is complete then return assignment
var = SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)
for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
if value is consistent with assignment then
add {var = value} to assignment
Result ←BACKTRACK(assignment,csp)
If Result ≠ failure then
return Result
Remove {var=value} and inferences from assignment
End if
End for
Return failure
end`

# Answer
> 3 votes
Consider that there might be something wrong with your experimental setup. The theoretical running time of an algorithm is based on an ideal model of a computer, but in practice there are lots of non-ideal behaviours. The running time of an experiment can vary based on lots of factors, and will be different from run-to-run.

You should repeat the experiment a number of times, and take the average running time of those runs to get a reliable reading. You could also compute the standard deviation of the running time, so you can get a good idea of whether the observed difference is statistically significant.

I implemented a straightforward backtracking approach to enumerate all solutions to the $n$-queens problem. The running time, *taken as an average over 10,000 runs*, was 0.045 ms for $n=7$, and 0.22 ms for $n=8$. This nicely fits with the fact that the number of (partial) solutions explored was 552 for $n=7$, and 2057 for $n=8$ (we have that $\frac{2057}{552}\times0.045\times\frac{8}{7}=0.19\approx 0.22$). So, based on my data, there is nothing that suggests $n=8$ is faster than $n=7$ -- if we want to enumerate all solutions.

Keep in mind that it is really hard to measure very low running times. There are other processes running at the same time, and how these are scheduled may affect the running time of your process. Your operating system may preempt your process for a while to run another process. For best accuracy, you should measure CPU time rather than "wall time", so that the time that your process is preempted is not taken into account.

If you're doing only a single run, the 0.773 or 0.492 (seconds?) you are measuring probably isn't the time required to do the backtracking (since that takes less than a millisecond), it's the time required to launch the process and load the executable from disk. The magnitude of the thing you're measuring is very small compared to the magnitude of the noise.

For completeness, here are my results for $n=1$ to $14$, giving the *total* number of valid partial solutions, the number of *valid* complete solutions (with $n$ queens), the *first* time (i.e., after how many partial solutions) a complete solution was found, average running time in *ms*, number of *runs* the average was taken over and the *minimum/maximum* number of timer ticks for a single run (to show how wide the spread in measured running times is).

```
n=1     total: 2        valid: 1        first: 2        0,0003ms        runs: 10000     min/max: 0/868
n=2     total: 3        valid: 0        first: -1       0,0006ms        runs: 10000     min/max: 0/55
n=3     total: 6        valid: 0        first: -1       0,0006ms        runs: 10000     min/max: 0/45
n=4     total: 17       valid: 2        first: 9        0,0009ms        runs: 10000     min/max: 1/96
n=5     total: 54       valid: 10       first: 6        0,0018ms        runs: 10000     min/max: 3/167
n=6     total: 153      valid: 4        first: 32       0,0071ms        runs: 10000     min/max: 15/286
n=7     total: 552      valid: 40       first: 10       0,0492ms        runs: 10000     min/max: 131/765
n=8     total: 2057     valid: 92       first: 114      0,2412ms        runs: 10000     min/max: 703/3107
n=9     total: 8394     valid: 352      first: 42       1,1385ms        runs: 2635      min/max: 3393/7416
n=10    total: 35539    valid: 724      first: 103      5,5285ms        runs: 543       min/max: 16869/29597
n=11    total: 166926   valid: 2680     first: 53       30,03 ms        runs: 100       min/max: 91033/116218
n=12    total: 856189   valid: 14200    first: 262      172,61ms        runs: 18        min/max: 543521/593573
n=13    total: 4674890  valid: 73712    first: 112      1037,2ms        runs: 10        min/max: 3379429/3490449
n=14    total: 27358553 valid: 365596   first: 1900     6736,1ms        runs: 10        min/max: 21845050/23117728

```

If we consider purely the time until finding the *first* solution, then the running time no longer is strictly increasing, but certain $n$'s are \`\`easier'' to solve in the sense that the backtracking strategy used happens to come across a valid solution earlier:

```
n=1     total: 2        0,0005ms        runs: 10000     min/max: 0/1199
n=2     total: 3        0,0005ms        runs: 10000     min/max: 0/50
n=3     total: 6        0,0004ms        runs: 10000     min/max: 0/50
n=4     total: 9        0,0004ms        runs: 10000     min/max: 0/56
n=5     total: 6        0,0004ms        runs: 10000     min/max: 0/44
n=6     total: 32       0,0016ms        runs: 10000     min/max: 2/64
n=7     total: 10       0,0006ms        runs: 10000     min/max: 1/54
n=8     total: 114      0,0089ms        runs: 10000     min/max: 21/232
n=9     total: 42       0,0033ms        runs: 10000     min/max: 7/199
n=10    total: 103      0,0107ms        runs: 10000     min/max: 29/140
n=11    total: 53       0,0052ms        runs: 10000     min/max: 14/77
n=12    total: 262      0,0533ms        runs: 10000     min/max: 138/2867
n=13    total: 112      0,0192ms        runs: 10000     min/max: 51/228
n=14    total: 1900     0,4925ms        runs: 6091      min/max: 1375/3820
n=15    total: 1360     0,3772ms        runs: 7953      min/max: 1072/3057
n=16    total: 10053    3,1402ms        runs: 956       min/max: 8997/17103
n=17    total: 5375     1,7544ms        runs: 1710      min/max: 5040/13332
n=18    total: 41300    14,813ms        runs: 203       min/max: 45021/60028
n=19    total: 2546     0,9637ms        runs: 3113      min/max: 2753/8341
n=20    total: 199636   83,5  ms        runs: 36        min/max: 264863/288246
n=21    total: 8563     3,9   ms        runs: 770       min/max: 11193/18734
n=22    total: 1737189  953,3 ms        runs: 10        min/max: 2900112/3477819
n=23    total: 25429    15,342ms        runs: 196       min/max: 41098/116394
n=24    total: 411609   251,833ms       runs: 12        min/max: 803905/970462
n=25    total: 48684    31,6211ms       runs: 95        min/max: 92880/133684

```

The *total* column reports the number of partial solutions considered before a valid complete solution is found (or the total number of partial solutions considered if there do not exist valid complete solutions). You can see that (for instance) when $n$ goes from 20 to 21 there is a large drop in number of solutions that need to be considered (and consequently a large drop in running time).

In this case, my backtracking algorithm (which uses the most obvious approach of starting at the top left, recursing, and moving the queen in each row from left to right), contrary to yours, takes longer to find a solution for $n=8$ than it does for $n=7$. However, the spread in running times (even though the algorithm is completely deterministic) is large: the fastest $n=8$ solution is more than twice as fast as the slowest $n=7$ solution.

It is difficult to quantify why a certain $n$ is more \`\`lucky'' than another, because this requires a deep understanding of the structure of the search space and how it interacts with a particular backtracking strategy.

One interesting fact is that if $n$ is odd, there always exists a solution placing a queen in the top left corner. This leads to the observation that the time to find the first solution for $2n+1$ is always much faster than that for $2n$, because the algorithm's guess (in the $2n+1$ case) for the first queen (top left corner) is always correct and the problem then reduces to solving a restricted version for the $2n$ case where no queens can be placed on the diagonal.

# Answer
> 2 votes
The exponential running time of backtracking for the$N$-queens problem is an *upper bound*, which means that the algorithm may do better sometimes. If the algorithm is 'lucky' and tries good positions for the queens first, it can find a solution with doing less backtracking compared when trying bad positions first.

Whether the algorithm is lucky or not depends both on how the position for a new queen is chosen and on the input instance. Likely, your algorithm is lucky for $N=8$, but not so lucky for $N=7$.

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


# Question
Title: Quicksort where element comparison outcome is random. Probability of element being in a certain position
So we have this block of pseudocode:

```
Monsters = [M1,M2,M3,M4,M5,M6,M7,M8];
qsort(Monsters,rand_compare);

```

> `qsort()` sorts the array via quicksort where we use the last element as pivot. To compare two elements it uses `rand_compare`, which, with equal probability (i.e., 1/2 either way), will return either "1. element is bigger" or "2. element is bigger" and never "both are equal". What is the probability that M8 appears in position 0, 1 or 2, respectively, after applying `qsort` ?

I'm really not sure how to tackle this question. Intuitively it should be 1/8 for every position. Does it depend on what implementation of quicksort you use?

# Answer
> 2 votes
In quick sort, after a partition, you have placed every element smaller than your pivot p below p and every element larger than p above it. Therefore after a partition you know the pivot is in the correct position and therefore it will not be moved again. Since you choose the last element (M8) as your pivot, this simplifies the process, since you only have to go through one iteration.

When you compare each element to M8, you will randomly be told that M8 is greater or the other element is "greater" each with 1/2 odds, and if the other element is "greater" it will be placed to the right of M8. Therefore, for M8 to end up in position 0, 1, or 2 it will have to have 2 or less elements that are determined to be "smaller" than M8. We can determine this probability through a geometric sequence:

0: (0.5^7)(0.5^0)(C(7,7)) = (0.5^7)(1) = .0078125

1: (0.5^6)(0.5^1)(C(7,6)) = (0.5^7)(7) = .0546875

2: (0.5^5)(0.5^2)(C(7,5)) = (0.5^7)(21) = .1640625

# Answer
> 1 votes
Let us first recall how quicksort works. We start by choosing a pivot — in your case $M\_8$. We then partition the array into elements smaller than the pivot and larger than the pivot (breaking ties arbitrarily), and reorder the array in the following way:

> elements smaller than the pivot; the pivot; elements larger than the pivot

We then recursively sort the elements smaller than the pivot, and the elements larger than the pivot.

The location of the pivot is the same as the number of elements smaller than the pivot. In your case, each of the elements $M\_1,\ldots,M\_7$ is smaller than the pivot $M\_8$ with probability $1/2$.

You take it from here.

---
Tags: sorting, probability-theory, quicksort
---


# Question
Title: Mapping reducibility from recursive to recursively enumerable language
I want to find out whether, assuming a language $L\_1$ being mapping reducible (i.e., $L\_1$ maps to $L\_2$ and the complement of $L\_1$ maps to the complement of $L\_2$) to a language $L\_2$ and $L\_2$ being recursively enumerable, $L\_1$ is recursive or not.

I tried creating a recursive Turing machine for $L\_1$ by using the recursively enumerable machine of $L\_2$, but if the input belongs to the complement of $L\_1$, its mapping will also be in the complement of $L\_2$ and we cannot say anything about it.

So I tried proving by contradiction instead: Assuming $L\_1$ is recursive, show that our assumption that $L\_2$ is recursively enumerable is wrong. However, this will require an inverse mapping. Alternatively, we could also try assuming $L\_1$ is recursive and show that such a mapping cannot exist, but I can't think of any approach to it.

Can someone help me?

---

*Mapping reducibility* of two languages $L\_1$ and $L\_2$ is defined as a function which, when given a string in $L\_1$, gives as output a string in $L\_2$ and, when given as input a string in $L\_1$ complement, gives as output a string in $L\_2$ complement.

# Answer
> 2 votes
If $L\_1 \le\_m L\_2$, that is, $L\_1$ is many-one (i.e., mapping) reducible to $L\_2$ and $L\_2$ is recursively enumerable (r.e.), then $L\_1$ must also be r.e. This is because an acceptor for $L\_1$ can be derived by reducing any instance $w$ of $L\_1$ to an instance $w'$ of $L\_2$ and then simulating the acceptor for $L\_2$ (which exists on grounds of $L\_2$ being r.e.) on $w'$.

However, in general, $L\_1$ does not have to be *recursive* (which is strictly stronger than r.e.). In fact, any language $L$ is (trivially) many-one reducible to itself, so just take your favorite r.e. but not recursive language $L$ and note that $L \le\_m L$ holds despite $L$ not being recursive.

---

Honestly, I believe your confusion arises from your unnecessarily complex view of many-one reducibility (i.e, on the basis of $L\_1$, $L\_2$, and their complements). Note that you can think of a reduction of $L\_1$ to $L\_2$ instead as mapping any instance $w$ of $L\_1$ to an instance $w'$ of $L\_2$ under the condition $w \in L\_1 \iff w' \in L\_2$. Stating this based on the equivalence sign "$\iff$" avoids having to think about the complements of $L\_1$ and $L\_2$, thus avoiding unnecessary "clutter" in your thought process.

---
Tags: computability, reductions
---


# Question
Title: Karp-Rabin - what is the input for the worst case time complexity?
I'm trying to determine the input for the worst case time complexity of Karb-Rabin regardless of the used hash function. However, I'm seeing both of these answers on the Internet:

* String "AAAAAAAA" and pattern "AAA"
* String "AAAAAAAB" and pattern "AAB"

Which of these inputs would have the worst running time in Karp-Rabin? Or are they both providing the worst case running time? Thanks!

# Answer
It all depends on what hash function you are using for your strings. The worst case for Rabin-Karp would be a case in which every single substring of the text has an equal hash to the pattern, therefore every single substring would be compared and the algorithm is equivalent to brute force.

The first example would be an example of this since the pattern matches in every case, therefore the algorithm would have to individually compare every substring (Assuming you are looking for every match and don't break out on the first one).

The second example would only be an example of a worst case if the hash of "AAB" matches the hash of "AAA," which is unlikely unless you have a really bad hash function. The algorithm would compare the hash of each substring of "AAA" and "AAB" and determine them to be non equal and bypass them until reaching the end where it hits "AAB" and finds and equal hash, comparing the substrings and determining them to be equal.
> 2 votes

# Answer
Worst case for Rabin-Karp string search is hash collision, i.e when you look for "ABCD" and other string "XXXX" has the same length and hash, and then the text consists purely of 'X' chars :)
> 0 votes

---
Tags: time-complexity, runtime-analysis, search-algorithms
---


# Question
Title: Quicksort Algorithm with Pivot element as Median
I have read that when pivot element is choosen as Median, then QS Algorithm gets nearly balanced splits and have time complexity of O(nlogn), but my doubt is what if all the elements of the input are same like (2,2,2,2,....,2) and pivot is still the median element, then what type of partitions QS will get as left and right subarray and what will be the time complexity. O(nlogn) or O(n^2)

This is not a homework question, I'm not in school/college anymore.

# Answer
> 1 votes
It depends on the partition algorithm used. Some might be $O(n^2)$ if they put all equal elements on the same side while others remain $O(n \log n)$ if they split the equal elements.

# Answer
> -1 votes
Writing a Quicksort implementation where n equal items take $O(n^2)$ is just stupid.

A good implementation will split the array into items less than the median, equal to the median, and greater than the median. That will sort an array of all equal elements in O(n).

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times
I am trying to prove that language $E\_{DFA}$ is decidable using multiple executions of $A\_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation").

Can I just use the given $M$ as a decider?

> $M =$ "On input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is an empty string ($L(w)=\emptyset$):
>
> 1. Mark the start of the DFA as $q\_0$.
> 2. Simulate B on input w a finite number of times:
>     1. First check if the encoding is correct, if $L(w)=\emptyset$, if not - reject.
>     2. Recursively: mark states that can be obtained within a finite $δ$ operations from any marked states.
> 3. If no accept state marked - accept. else, reject."

Is this correct?

Definitions: $$\begin{align\*} A\_{DFA} &= \left\\{ \langle B,w \rangle \mid \text{$B$ is a DFA that accepts input string $w$} \right\\} \\ E\_{DFA} &= \left\\{ \langle A \rangle \mid \text{$A$ is a DFA and $L\left(A\right) = \varnothing$} \right\\} \end{align\*}$$

Emphasis: I am trying to prove $E\_{DFA}$ by running the proof of $A\_{DFA}$ several times (finite), so I thought the correct thing would be to use the input $w$ as empty set.

# Answer
> 2 votes
If you want to reduce $E\_{DFA}$ to $A\_{DFA}$, you should use the following theorem:

> If a DFA with $n$ states accepts some word, then it accepts some word of length less than $n$.

But a much more efficient algorithm would just run DFS from the initial state, and check whether some accepting state is reachable from it.

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


# Question
Title: Non-recursivity of language of TMs which have equivalent TMs of smaller and larger description length
Prove that the language

$$ L=\\{\langle M \rangle \mid \exists M\_1, M\_2 : L(M\_1)=L(M\_2)=L(M) \text{ and } |\langle M\_1 \rangle| \< |\langle M \rangle| \< |\langle M\_2\rangle| \\}$$

is not recursive.

# Answer
First, let us notice that in the definition of $L$, a machine $M\_2$ accepting the same language as $M$ but having a longer description always exists, so only the condition on $M\_1$ is pertinent.

Suppose that $L$ were computable. Consider the following Turing machine $T\_\ell$. The machine enumerates all Turing machines of size at least $2^\ell$, until it finds a machine $M$ such that $\langle M \rangle \notin L$ (such a machine must exist, since there are infinitely many computable languages but only finitely many Turing machines of size less than $2^\ell$). Then it transfers control to the machine $M$, i.e., it runs $M$ on the input.

By construction, $L(T\_\ell) = L(M)$. Since $\langle M \rangle \notin L$, necessarily $|\langle T\_\ell \rangle| \geq |\langle M \rangle| \geq 2^\ell$. However, by hardcoding $\ell$ into a Turing machine in which $\ell$ is an additional input, we see that $|\langle T\_\ell \rangle| = O(\ell)$. We obtain a contradiction for large enough $\ell$.
> 1 votes

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


# Question
Title: Why is the period of Mersenne Twister prng $2^{19937}-1$ and not $2^{19968}$?
For the Mersenne Twister prng, wikipedia, I feel the period exponent should be the size of the MT array, $32\cdot 624 = 19968$.

How come the exponent is 19937 instead?

# Answer
> 4 votes
Here is the one-line explanation.

The number of effective bits in MT19937 is 624\*32-31=19937. They cannot be all 0. So the period of MT19937 is $2^{19937}-1$.

---

All notations if not introduced below come from this Wikipedia article. The parameters for MT19937, (w, n, m, r) = (32, 624, 397, 31) will be used from time to time.

### Explanation from the recurrence

> The series $x$ is defined as a series of w-bit quantities with the recurrence relation: $$x\_{k+n}:=x\_{k+m}\oplus \left(({x\_{k}}^{u} \mid\mid {x\_{k+1}}^{l})A\right)\qquad \qquad k=0,1,\ldots$$

Note the lower part of the lowest term $x\_k$, ${x\_k}^l$ is not used in the recurrence relation. Hence the number of effective bits used by the recurrence is $(k+n-k)w-r=nw-r$. Since 0 is excluded, the theoretical limit of period of Mersernne Twister is $2^{nw-r}-1=2^{19937}-1$.

### Detailed explanation.

The above explanation is not rigorous enough because of a lack of proper reference. To convince myself, I followed the established pseudocode implementation.

```
// Generate the next n values from the series x_i
function twist() {
  for i from 0 to (n-1) {
    int x := (MT[i] and upper_mask)
              + (MT[(i+1) mod n] and lower_mask)
    int xA := x >> 1
    if (x mod 2) != 0 { // lowest bit of x is 1
         xA := xA xor a
    }
    MT[i] := MT[(i + m) mod n] xor xA
  }
  index := 0
}

```

The code above shows that the internal state of a Mersenne Twister is kept in MT\[0\], MT\[1\], ..., MT\[n-1\], which is an array of n values of w bits each. It seems that the period of a Mersenne Twister should be $2^{nw}=2^{19968}$.

Let us check the situation closely.

Every call to `twist()` will update the internal state. After each call to `twist()`, `function extract_number()` will be called $n$ times, each time extracting from `MT[index]` one word of w bits to output where `index` is one of 0, 1, ..., n-1.

How does `twist()` update the internal state?

* the upper w-r bits of MT\[0\], the lower r bits of MT\[1\], and all bits of MT\[317\] are used to update MT\[0\].
* the upper w-r bits of MT\[1\], the lower r bits of MT\[2\], and all bits of MT\[318\] are used to update MT\[1\].
* the upper w-r bits of MT\[2\], the lower r bits of MT\[3\], and all bits of MT\[319\] are used to update MT\[2\].
* ...
* the upper w-r bits of MT\[306\], the lower r bits of MT\[307\], and all bits of MT\[623\] are used to update MT\[306\].
* the upper w-r bits of MT\[307\], the lower r bits of MT\[308\], and all bits of the updated MT\[0\] are used to update MT\[307\].
* the upper w-r bits of MT\[308\], the lower r bits of MT\[309\], and all bits of the updated MT\[1\] are used to update MT\[308\].
* ...
* the upper w-r bits of MT\[622\], the lower r bits of MT\[623\], and all bits of the updated MT\[315\] are used to update MT\[622\].
* the upper w-r bits of MT\[623\], the lower r bits of updated MT\[0\], and all bits of the updated MT\[316\] are used to update MT\[623\].

Note that **all bits in the array MT at the start of `twist()` are used except the lower r bits of MT\[0\]**. So an effective internal state of MT is r bits less than all bits in array MT. Since an effective internal state can never be all 0, the number of effective internal states is at most $2^{nw-r}-1=2^{19937}-1$, which is the theoretical limit of the period for a linear-feedback shift register like Mersenne Twister.

It is another level of interesting mathematical reasoning how MT19937 attains that theoretical limit of its period.

### Another explanation by pseudocode

The following pseudocode is another implementation of Mersenne Twister.

Note the code `MT[0] := MT[0] and upper_mask` and `MT[0] := MT[1] and upper_mask`, which limits the number of effective bits in MT\[0\] to w-r. There are (n-1)w bits in MT\[1\], MT\[2\], ..., MT\[n-1\]. In total, there are (w-r)+(n-1)w = nw-r bits in the (effective) internal state of a Mersenne Twister.

```
// Adapted from https://en.wikipedia.org/w/index.php?title=Mersenne_Twister&oldid=896072298#Pseudocode by Apass.Jack

// Create a length n array to store the state of the generator
int[0..n-1] MT
int index := n+1
const int lower_mask = (1 << r) - 1 // That is, the binary number of r 1's
const int upper_mask = lowest w bits of (not lower_mask)

// Initialize the generator from a seed, which must be done once before repeated calls to next().
function seed_mt(int seed) {
    index := n
    MT[0] := seed
    for i from 1 to (n - 1) { // loop over each element
        MT[i] := lowest w bits of (f * (MT[i-1] xor (MT[i-1] >> (w-2))) + i)
    }
    MT[0] := MT[0] and upper_mask
}

function temper(int y) {
    y := y xor ((y >> u) and d)
    y := y xor ((y << s) and b)
    y := y xor ((y << t) and c)
    y := y xor (y >> l)

    return lowest w bits of (y)
}

function twist() {
    int x := MT[0]
              + (MT[1] and lower_mask)
    int xA := x >> 1
    if (x mod 2) != 0 { // lowest bit of x is 1
        xA := xA xor a
    }
    x := MT[m] xor xA

    MT[0] := MT[1] and upper_mask
    for i from 1 to (n-2) {
      MT[i] := MT[i+1]
    }
    MT[n-1] := x
}

// Generate the next value from the series MT[]
function next() {
    twist()
    return temper(MT[n-1])
}

```

---
Tags: pseudo-random-generators, random-number-generator
---


# Question
Title: Subset with modified condition, is it still NP-complete?
So I know the conditions required for a problem to be NP-Complete is that it has to lie within NP and has to be NP-hard.

The given problem I have is subset sum.

However, the conditions have been change to sum ≤ M and sum ≥ M from sum = M. To be more specific:

1. "If we ask if there is a subset with sum ≤ M, is the problem still NP- Complete?"
2. "If we ask if there is a subset with sum ≥ M, is the problem still NP- Complete?"

My initial reaction is that the two problems are no longer NP-complete since they can both be solved within polynomial time.

1. Check each element and see if there exists at least one smaller than M.
2. Add all positive integers and see if the sum of all elements is larger than M.

Since it isn't NP Hard, it cannot therefore be NP-complete.

Am I thinking/approaching this correctly?

# Answer
> 2 votes
What precisely are the problems? I may be missing something (and cannot do comments yet). Are they

(1) Given a set $A \subseteq \mathbb{Z}$ of $n$ elements, does there exist some subset $S \subseteq A$ with $\sum\_{x \in S} x \le M$.

(2) Given a set $ \subseteq \mathbb{Z}$ of $n$ elements, does there exist some subset $S \subseteq A$ with $\sum\_{x \in S} x \ge M$.

If so these problems seem clearly in $\mathbf{P}$, basically by the reasoning you described -- we just want the minimum/maximum possible subset sum, and then we compare that with $M$. Assuming empty $S$ is allowed:

* for (1), add up all the negative numbers in $A$ and see if it's $\le M$. If Yes, then return yes. If not, return No.
* for (2), add up all the positive numbers in $A$ and see if it's $\ge M$.

Again I may be missing something, but it seems like the other answer's reduction might not be addressing the possibility that $SS\_\le$ and $SS\_\ge$ would return yes based on different sets? Like consider input $A = \\{1, 3\\}$ and $M=2$.

---
Tags: np-complete, np-hard, decision-problem
---


# Question
Title: Union of regular languages that is not regular
I've come across that question : **"Give examples of two regular languages which their union doesn't output a regular language. "**

This is pretty shocking to me because I believe that regular languages are closed under union. Which means to me that if I take two regular languages and union them, I **must** get a regular language.

And I think I understand the proof of that : In my words, if the languages are regular, then there exist automatas that recognize them. If we take all the states (union), and we add a new state for the entry point, and we modify the transition function for the new state with epsilon, we are ok. We also show that there exist a path from every state etc.

**Can you tell me where I'm wrong, or maybe another way to approach the question.**

Source of the question, exercise 4, in french.

Also, the same question is asked with the intersection.

# Answer
There's a significant difference between the question as you pose it and the question posed in the exercise. The question asks for an example of a set of regular languages $L\_{1}, L\_{2}, \ldots$ such that their union $$ L = \bigcup\_{i=1}^{\infty}L\_{i} $$ is not regular. Note the range of the union: $1$ to $\infty$. Regular languages are closed under *finite* union, and the proofs runs along the lines that you sketch in the question, however this falls apart under *infinite* union. We can show this by taking $L\_{i} = \\{0^{i}1^{i}\\}$ for each $i$ (with $\Sigma = \\{0,1\\}$). The infinite union of these languages of course gives the canonical non-regular (context-free) language $L = \\{0^{i}1^{i}\mid i \in \mathbb{N}\\}$.

As an aside, we can see easily where the normal proof fails. Imagine the the same construction where we add a new start state and $\varepsilon$-transitions to the old start states. If we do this with an infinite set of automata we have build an automata with an infinite number of states, obviously contradicting the definition of a *finite* automata.

Lastly, I'm guessing the confusion may arise from the phrasing of the original question, which starts "Donner deux exemples des suites de langages...", which is (~~roughly~~, my French is a bit rusty, but externally verified!) "Give two examples of *sequences* of languages...", rather than "Give two examples of languages...". An incautious reading may mistake the second for the first though.
> 30 votes

# Answer
For your second question, consider the languages defined by $$ M\_n = \\{a^{k^2}\mid 1\le k \le n\\}\cup\\{a^j\mid j\ge(n+1)^2\\} $$ Observe that for any $n\ge 1$, $M\_n$ is regular, since (1) the left set is finite and hence regular, (2) the right set is denoted by the regular expression $a^naa^\*$ so is regular, and (3) regular languages are closed under finite unions, as you already know.

It's not too difficult to show that for any integer $n\ge 1$ we have $M\_{n+1}\subseteq M\_n$ and hence $M\_n\cap M\_{n+1} = M\_{n+1}$ so inductively we have $$ \bigcap\_{i=0}^n M\_i = M\_n $$ (which we don't actually need here, but it's too pretty to leave out).

Now observe that $M\_n$ doesn't contain $a^{n^2+1},a^{n^2+2}, \dotsc, a^{(n+1)^2-1}$, so none of these strings will be in the full intersection. As a consequence we'll have $$ \bigcap\_{i=0}^\infty M\_i = \\{a^{n^2}\mid n\ge 1\\} $$ which is known not to be a regular language. (If you didn't know this fact, it's in many theory texts and the proof is well worth the effort of reading.)
> 3 votes

# Answer
If you do the Union of infinitely many Unit Sets, you can make *any* language (well, at least, any r.e. language, because if it is undecidable, you cannot specify the list of all its strings). For example, the union of unit sets where each contains a different palindrome string over {a, b}, gives as result the palindrome language (context-free): this is $\\{\epsilon\\} \bigcup \\{a\\} \bigcup \\{b\\} \bigcup \\{aa\\} \bigcup \\{bb\\} \bigcup \\{aaa\\} \bigcup \\{aba\\} \bigcup \\{bab\\} \bigcup \\{bbb\\} \bigcup \ ... $

You can do something similar with intersection, making infinitely many sets where each is $ \Sigma^\* - \\{ p\_i \\}$ , where $p\_i$ is the $i$th palindrome word, resulting the language of all not palindromes words (complement of palindrome language, non-regular).
> 2 votes

# Answer
Why choose complicated regular languages to show that regular sets are not closed under infinite union? Singleton languages are enough to show that any RE language is an infinite union of regular sets.

Take any recursively enumerable language $L$. Each string $w\in L$ has an enumeration index $i=index(w)$. Let $L\_i=\\{w\mid i=index(w)\\}$. Every $L\_i$ is a singleton set, hence regular. But $L =\bigcup\_{i=1}^{\infty}L\_i\\;$ is RE.

Similarly, defining $M\_i=\Sigma^\*\setminus L\_i$, we have the sets $M\_i$ which are regular as complements of a singleton set. Then $\bigcap\_{i=1}^{\infty}M\_i= \Sigma^\*\setminus L\\;$ which is the complement of $L$, hence co-RE. And that can be achieved with any co-RE set.

Hence any recursive language is an infinite union of regular sets, and also an infinite intersection of regular sets (not the same ones, but their complements:).

Infinity is full of surprises, and what is true for arbitrarily large values may not be true at infinity.
> 1 votes

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


title: Lazy streams and infinite series

text:
# Question
Title: Lazy streams and infinite series
I just started Unix System Programming with Standard ML and starting on page 22 Shipman begins to explain a pure functional way of avoiding the constant state changes of typing at a keyboard:

> A lazy stream is an infinite list of values that is computed lazily. The stream of keystrokes that a user presses on the keyboard can be represented as an infinite (or arbitrarily long) list of all of the keystrokes that the user is ever going to press. You get the next keystroke by taking the head element of the stream and saving the remainder. Since the head is only computed lazily, on demand, this will result in a call to the operating system to get the next keystroke. What’s special about the lazy stream approach is that you can treat the entire stream as a value and pass it around in your program. You can pass it as an argument to a function or save the stream in a data structure. You can write functions that operate on the stream as a whole. You can write a word scanner as a function, `toWords`, that transforms a stream of characters into a stream of words. A program to obtain the next 100 words from the standard input might look something like `apply show (take 100 (toWords stdIn))` where `stdIn` is the input stream and `take n` is a function that returns the first `n` elements in a list. The `show` function is applied to each word to print it out. The program is just the simple composition of the functions. Lazy evaluation ensures that this program is equivalent to the set of nested loops that you would write for this in an \[imperative\] program. This is programming at a much higher level than you typically get with \[imperative\] languages.

I take it he doesn't mean just a list of the 26 letters of the alphabet, rather, something more like every possible word and combination thereof, i.e., similar to the theoretical possibility of finding yours and everyone's birthday if you look hard enough in the irrational never-repeating infinite stream of $\pi$ places. That is, somewhere in the infinite series of $\pi$ decimal places is your birthday mmddyyyy-style. Is this in fact what is meant here? Also, is this in any way related to infinite recursion?

In a similar vein, I once was told that no functional language is truly pure, and he gave the example of a function that "goes out" and gets the exact time from an atomic clock. Is this the same sort of issue, where, e.g., an infinite list of possible times is available for a list operation?

# Answer
> 1 votes
No, that's not what the author means. The author means the *specific* sequence of characters the user will *actually* type. If the user is about to write a letter to Al that might be:

```
'D'::'e'::'a'::'r'::' '::'A'::'l'::rest

```

The point is that you conceptually have "all" of the characters, and you can (with a bit of care) process this list like any other list.

---
Tags: computability, functional-programming, lists
---


# Question
Title: Minimum distance of nodes from a set of two nodes
In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) \< dist(x,w)$). The solution that comes to my mind is running two BFS, which gives us $\mathcal{O}(V + E)$ running time.

---

Is there any better way to do this? possibly with one BFS?

**EDIT:** We can start two BFS from $w$ and $v$ simultaneously and one step at a time. First we find the nodes in distance 1 of the $w$ then the nodes in distance 1 of $v$ and then nodes at distance 2 of $w$ and so on. by the time there is no node in the queue of BFS of node $v$, we can end the search. any node which is first visited with $v$ BFS is closer to $v$ than $w$.

But again I suppose there is a more efficient way to do this.

# Answer
You can do this with only one BFS and the solution is very simple.

I will assume that you have as input a graph $G = (V, E)$. Let $dist$ be a vector which stores the distance of all nodes of your graph to node $v \in V$.

You must run a BFS algorithm starting on node $v$ and store the distance from each node to $v$ in $dist$. This value can be simply obtained during the BFS execution. Then, you can iterate through this vector marking (or deleting) all nodes $i$ such that $dist\[i\]$ \< $dist\[w\]$.

The overall complexity of this algorithm is $\mathcal{O}(V + E + V)$. In a tree, we have that $|E| = |V|-1$. Thus, the complexity is $\mathcal{O}(3 V) = \mathcal{O}(V)$.
> 0 votes

---
Tags: graphs, trees, shortest-path
---