# Question
Title: What are appropriate isomorphisms between formal languages?
A *formal language* $L$ over an alphabet $\Sigma$ is a subset of $\Sigma^\*$, that is, a set of words over that alphabet. Two formal languages $L$ and $L'$ are equal, if the corresponding sets are extensionally equal as subsets of $L\cup L'$. One can use languages in complexity theory to formalize the concept of a "problem." One could complain that "in general" extensional equality is undecidable, but I believe this would be misguided.

I'm pondering the following problem since some time: Two languages $L$ and $L'$ over alphabets $\Sigma=\\{a,b\\}$ and $\Sigma'=\\{c,d\\}$ (where $a$, $b$, $c$ and $d$ are distinct letters) can never be equal, even if they describe "exactly" the same "problem." But they should be isomorphic, if they really describe "exactly" the same "problem." What I would like to know are possible notions of isomorphism appropriate for complexity theory. I initially thought a computationally weak "translator" like a finite-state machine could be used to define the allowed isomorphisms, but this already seems to break down for trivial syntactic translations between equivalent logical formulas. (See for example this table with the syntactic definition of the **dual** $A^\bot$ in linear logic.)

Today I had the following idea: A definition of the language corresponding to a certain "decision problem" often has two parts: (1) An encoding of the allowed problem instances as finite strings of symbols, and (2) a definition of the "accepted" problem instances which belong to the language. If the checking whether a given finite string of symbols is an encoding of an allowed problem instance already requires a machine computationally stronger than a finite-state machine, then this stronger machine should also be used for the definition of the allowed isomorphisms.

> Questions: Has this line of reasoning any chance of "resolving" my problem? Has my problem already been solved, so that I just need to read the right references? Does my problem itself makes any sense, or is this just as misguided as complaining about undecidability of extensional equality?

---

**Edit (not an answer yet)** I noticed that "(1) An encoding of the allowed problem instances as finite strings of symbols" already contains the (hidden) assumption of a normalized input. Without this assumption, two different finite strings might correspond to the same problem instance. Instead of checking whether a given finite string is valid, the checking might produce a normalized input (and map invalid strings to a special string).

This setting has the advantage that the machine doing the checking/normalization is already equipped with means to transform finite strings to other finite strings. The allowed machine (complexity class) for this task could be part of the problem definition, and the (iso)morphisms would use the same machine (complexity class). (The suggestion of "poly-time many-one reductions" from Raphael's comment would then indeed be one possibility for problems in $\mathsf{P}$.)

A drawback is that this way of specification might only be appropriate for deterministic machines. Non-deterministic machines might require more flexible ways to specify/decide whether two input strings correspond to the same problem instance.

# Answer
> 6 votes
> Has my problem already been solved, so that I just need to read the right references?

The theory of abstract family of languages is relevant. For example, the morphisms defined by finite state transducers lead to the cone family. Eilenberg's short ICM talk from 1970 nicely explains this framework, see also chapter 11 "Closure properties of families of languages" from *Introduction to Automata Theory, Languages, and Computation (1st ed.)* by J. Hopcroft and J. Ullman from 1979. However, only nondeterministic languages fit into this framework1. In the end, the book *Theory of codes* by J. Berstel and D. Perrin from 1985 helped me to come up with reasonable solutions for my problem. *Codes and Automata* by J. Berstel, D. Perrin and C. Reutenauer from 2009 is a major revision of this book with a much broader coverage.

> Has this line of reasoning any chance of "resolving" my problem? Does my problem itself makes any sense, or is this just as misguided as ...?

The assumption that there is one correct category for modeling isomorphisms between languages to "formalize the concept of a problem" is misguided. There are many different categories which can be interesting in the context of formal languages.

Here are three interesting categories related to many-one reductions, which will be referred to as **total**, **partial**, and **relational**. The objects of the categories are pairs $(\Sigma, L)$ of a finite alphabet $\Sigma$ and a language $L\subset\Sigma^\*$ of words over $\Sigma$. For **total**, the morphisms between the source object $(\Sigma, L)$ and the target object $(\Sigma', L')$ are total functions $f : \Sigma^\* \to \Sigma'^\*$ with $L=f^{-1}(L')$. For **partial**, the morphisms are partial functions $f : \Sigma^\* \to \Sigma'^\*$ with $L=f^{-1}(L')$, where two partial functions $f$, $g$ are considered equal (as morphisms) if $f(x)=g(x)$ for all $x\in L$. For **relational**, the morphisms are relations $R\subset \Sigma^\* \times \Sigma'^\*$ with $L=R^{-1}(L')$, and any two morphisms between the same source and target are considered to be equal. The set of allowed functions or relations can be restricted to various simple "translators" to get categories with interesting isomorphisms.

* The monoid homomorphisms from $\Sigma^\*$ to $\Sigma'^\*$ give a very basic **total** category. The isomorphisms of this category are basically just the bijections between $\Sigma$ and $\Sigma'$. Any reasonable family of languages should better respect these isomorphisms, i.e. be closed under inverse homomorphisms.
* The partial functions defined by deterministic log-space Turing machine translators give a quite natural **partial** category. It is able to perform many trivial syntactic transformations (like applying De Morgan's laws to move negations to the atoms), includes the morphism defined by functional finite state transducers1, and also can sort. Still it won't identify two completely unrelated languages as isomorphic, because equality of the composition of two morphisms to an identity morphism is a much stronger requirement than just existence of many-one reductions in both directions.
* The relations defined by nondeterministic log-space Turing machine translators give an interesting **relational** category. SAT is isomorphic to HORNSAT in this category, but it is an open question whether TAUTOLOGY or any other co-NP-complete problem is isomorphic to HORNSAT.

> Two languages $L$ and $L'$ over alphabets $\Sigma=\\{a,b\\}$ and $\Sigma'=\\{c,d\\}$ (where $a$, $b$, $c$ and $d$ are distinct letters) can never be equal, even if they describe "exactly" the same "problem." But they should be isomorphic, if they really describe "exactly" the same "problem."

The very basic **total** category described above solves this problem.

The problem becomes more interesting if "exactly the same" is replaced by "nearly the same for most practical purposes": Let $L$ be a language over $\Sigma=\\{U,C,A,G\\}$ and let $L'$ be the language over $\Sigma'=\\{0,1\\}$ obtained from $L$ by the substitution $U \to 00$, $C \to 01$, $A \to 10$, and $G \to 11$. Note that in any **total** category, $L$ and $L'$ are not isomorphic for $L=\Sigma^\*$. The same would be true for **partial** categories, if the part "where two partial functions $f$, $g$ are considered equal (as morphisms) if $f(x)=g(x)$ for all $x\in L$" were omitted from the definition.

The quite natural **partial** category described above is sufficient for making $L$ and $L'$ isomorphic. It would be nice to have a more basic (i.e. more restrictive) category that makes them isomorphic. The following (successively more restrictive) categories look reasonable to me:

* The partial functions realized by unambiguous finite state transducers2 where the only accepting state is the initial state. The isomorphisms of this **partial** category are (a subset of the) bijections between recognizable variable length codes.
* The partial functions realized by deterministic finite state transducers where the only accepting state is the initial state. The isomorphisms of this **partial** category are (a subset of the) bijections between prefix codes.
* The partial functions realized simultaneously by both a forward and a backward deterministic transducer where the only accepting state is the initial state. The isomorphisms of this **partial** category are (a subset of the) bijections between bifix codes.
* Further restriction of the partial functions such that the isomorphisms are (a subset of the) bijections between block codes could also make sense.

> One can use languages in complexity theory to formalize the concept of a "problem."

Even before I learned about category theory, I have wondered about whether there are "more faithful" ways to formalize the concept of a "problem". After becoming familiar with category theory, I sometimes tried to come up with possible solutions, but always quickly gave up at the first stumbling block (because nobody cares anyway). I know that Yuri Gurevich has solved some related questions, but his solutions are practically applicable, whereas I was looking more for something nice and abstract, independent of practical applicability.

Most of my spare time for the last three weeks went into finally making some progress on this problem. Most often the time was spend finding annoying issues in the possible solutions I had in mind. The sense of making progress arose from reading (old) books and articles, and learning many basic concepts and facts about transducers and rational sets. Finally I learned the notions of a prefix code and a bifix code (formerly *biprefix code* in Berstel's book), which allowed me to come up with the reasonable3 categories described above.

It may be hard to appreciate those (code related) categories, without having seen some issues of the more obvious categories. A general issue is that closure under composition can make it hard to define a nicely restricted class of partial functions. Another issue is related to the fact that addition of one (or multiplication by a constant) is an "easy to compute function" if the digits of the number are given in low-endian order, but not if the digits are given in big-endian order.

---

1  A functional finite state transducer is a nondeterministic finite state transducer that realizes a partial function. These partial functions cannot be realized by deterministic finite state transducers. They can be realized by deterministic bimachines, but those may need $O(n)$ forward and backward scans over the input, if they want to operate in $O(1)$ space.

2  An unambiguous finite state transducer is a nondeterministic finite state transducer with at most one accepting path for each input. It realizes a partial function, hence it is also a functional finite state transducer. It is decidable whether a given finite state transducer is unambiguous.

3  I'm not sure how reasonable the **total** and the **relational** categories introduced above really are. I just wanted to show straightforward alternatives to the **partial** category. More alternatives are easy to come up with, for example **co-relational**, where the morphisms are relations $R\subset \Sigma^\* \times \Sigma'^\*$ with $L=R^{-1}(L')-R^{-1}(\Sigma'^\*-L')$, and any two morphisms between the same source and target are considered to be equal.

---
Tags: complexity-theory, formal-languages, reference-request
---


# Question
Title: Locally finite graph without an optimal path
If I have a locally finite graph (every node has finite number of neighbors) with positive edge weights, is it possible for there to be a path between some start node and goal node but no shortest path between them?

I think that it can only happen if the goal node is somewhere in the infinity, but then we wouldn't be saying that the goal node actually exists, right?

Could anyone help me on this?

# Answer
It can happen. Let $P\_0,P\_1,\ldots$ be a one-way infinite path, where $P\_0$ is the start node, and the edge from $P\_i$ to $P\_{i+1}$ has weight $1/2^{i+1}$. Let $Q\_0,Q\_1,\ldots$ be a one-way infinite path, where $Q\_0$ is the goal node, and the edge from $Q\_i$ to $Q\_{i+1}$ has weight $1/2^{i+1}$. Connect $P\_i$ to $Q\_i$ with an edge of weight $1/2^{i-2}$. The weight of the path $P\_0-\cdots-P\_i-Q\_i-\cdots-Q\_0$ is $$(1/2+\cdots+1/2^i)+1/2^{i-2}+(1/2^i+\cdots+1/2) = \\ (1+\cdots+1/2^{i-1})+1/2^{i-2} = \\ (2-1/2^{i-1})+1/2^{i-2} = \\ 2+1/2^{i-1} \\, . $$ So for each $\epsilon \> 0$ there is a $P-Q$ path of weight $2+\epsilon$, but there is no path of weight $2$.
> 6 votes

---
Tags: graphs
---


# Question
Title: Prove/ Disprove: For every nontrivial $A,B \in R (RE)$, $A\le_m B$
> Prove/ Disprove:
>
> * For every nontrivial $A,B\in R$, $A\le\_m B$
> * For every nontrivial $A,B\in RE$, $A\le\_m B$
>
> trivial set is the empty-set or $\Sigma^\*$.

So basically the question is if for every two nontrivial sets there is a computable function from $A$ to $B$.

I'd be glad to get hint/guidance since I'm kinda stuck and not sure how to attack this problem.

Thanks.

# Answer
> 3 votes
HINT:

Go again over the definition of reductions. The many-one reduction from $A$ to $B$ is a function $f: \Sigma^\* \to \Sigma^\*$ that satisfies:

1. $f$ is complete (=defined on any input)
2. $f$ is computable (hint, hint).
3. $f$ is valid: $x\in A$ if and only if $f(x) \in B$.

The "non trivial" part means there exists $x \in A$ and $x' \notin A$, and more importantly - the same holds for $B$. Now it should be fairly easy for you to complete the answer of your question.

---
Tags: computability
---


# Question
Title: What does feedforward inversion mean in the context of convolution and catastrophic codes?
i'm reading the article of J. L. Massey and M. K. Sain, "Inverses of Linear Sequential Circuits" (Date of Publication - April 1968) (here) and i cannot understand - what is "feedforward inversion"?

They give a short description of circles in convolution codes and a little bit description about catastrophic codes (codes that makes an infinite amount of errors on decoding if there was a couple of errors in channel).

Can anyone explain the term "feedforward inversion", and what do they mean by delay in that regard?

P.S. i'm interested in this theme because i want to understand the proof of Theorem 1 in that article, no more.

# Answer
The paper deals with sequential encoding and decoding of codes. Maybe you have heard of "block codes": these codes take a message $M\in \\{0,1\\}^k$, perform some computation, and then output a code-word $c\_M \in \\{0,1\\}^n$.(1). A main drawback of encoding systems for such codes is that need to know **the entire** message $M$ in order to output $c\_M$.

This is not the case in convolution code.

### Sequential circuits

Convolution codes are usually designed so that there is a very simple and *sequential* encoding algorithm. By "sequential" I mean that the system reads $M$ bit by bit, and immediately(2) outputs some part of $c\_M$. Say, if the rate is $k/n=1/2$, then for every bit of $M$ given as an input to the encoder, the encoding system outputs the next $2$ bits of the codeword (even without knowing the rest of $M$). After the entire input $M$ is fed into the encoder, we will get the entire codeword $c\_M$.

This sequential nature of encoding is what the paper means by "feed-forward": you always input the next part of the data, and that's enough for the system to proceed and give output, as a function on the current state of the encoder. This is/was crucial in memoryless implementations (those can't hold the past bits of the message $M$), or implementations that could not wait to have the entire $M$ due to the large delay incurred (those don't know the future bits of the message $M$).

Thus, a "feedforward inverse" is simply a **sequential** decoding algorithm. ("inverse" is the algorithm that inverses the code, that is, the decoding system).

### Delay

The delay $L$ is explained in the first paragraph of the paper: (below, not a precise quote)

> An inverse with delay $L$, for a sequential circuit with $k$ inputs and $n$ outputs *\[= a decoder for the encoder\]*, is a sequential circuit with $n$ inputs and $k$ outputs, that cascaded with the encoder, yields an overall sequential circuit with delay $L$.

That is, take the encoder, and connect the decoder immediately to the output of the encoder. Now start feeding the input into the encoder. $L$ is the amount of "clocks" until you see the same bit at the output of the decoder.

---

(1) The alphabet needs not be binary, this is just for simplicity.

(2) Or after a fixed number of clocks.
> 1 votes

---
Tags: terminology, coding-theory, error-correcting-codes
---


title: $\lambda$-calculus with reflection

text:
# Question
Title: $\lambda$-calculus with reflection
I'm looking for a simple calculus that supports reasoning about reflection, namely, the introspection and manipulation of running programs.

> Is there an untyped $\lambda$-calculus extension that enables one to convert $\lambda$-terms into a form that can be syntactically manipulated and then subsequently evaluated?

I imagine that the calculus has two main additional terms:

* $\mathtt{reflect}\ v$: takes $v$ and produces a representation of $v$ amendable to syntactic manipulation.
* $\mathtt{eval}\ v$: takes a syntactic representation of a term and evaluates it.

In order to support reflection, a syntactic representation of terms is required. It would look something like:

* $\lambda x.e$ would be represented as a term $(\mathsf{LAM}\ R(e))$, where $R(e)$ is the reflected version of $e$,
* $e\ e'$ would be represented as term $(\mathsf{APP}\ R(e)\ R(e'))$, and
* $x$ would be represented as $(\mathsf{VAR}\ x)$.

With this representation, pattern matching could be used to manipulate terms.

But we run into a problem. $\mathtt{reflect}$ and $\mathtt{eval}$ need to be encoded as terms, as does pattern matching. Dealing with this seems to be straightforward, adding $\mathsf{REFLECT}$, $\mathsf{EVAL}$ and $\mathsf{MATCH}$, but will I need to add other terms to support the manipulation of these?

There are design choices that need to be made. What should the $R(-)$ function alluded to above do with the body of $\mathtt{reflect}$ and $\mathtt{eval}$? Should $R(-)$ transform the body or not?

As I am not so much interested in studying reflection itself -- the calculus would serve as a vehicle for other research -- I do not want to reinvent the wheel.

> Are there any existing calculi that match what I have just described?

As far as I can tell, calculi such as MetaML, suggested in a comment, go a long way, but they do not include the ability to pattern match and deconstruct code fragments that have already been built.

One thing I would like to be able to do is the following:

* $\mathtt{let}\ x=\lambda y.y\ \mathtt{in}\ \mathtt{reflect}\ x \to (\mathsf{LAM}\ (\mathsf{VAR}\ y)\ (\mathsf{VAR}\ y))$

And then perform pattern matching on the result to build a completely different expression.

This is certainly not a conservative extension to the $\lambda$-calculus and the meta-theory is likely to be ugly, but this is kind of the point for my application. I want to break $\lambda$-abstractions apart.

# Answer
> 16 votes
Jean Louis Krivine introduced an abstract calculus which extends the "Krivine Machine" in a very non-trivial way (note that the Krivine machine already supports the call/cc instruction from lisp):

He introduces a "quote" operator in this article defined in the following manner: if $\phi$ is a $\lambda$-term, note $n\_\phi$ the image of $\phi$ by some bijection $\pi: \Lambda \rightarrow \mathbb{N}$ from lambda terms to natural numbers. Note $\overline{n}$ the church numeral which corresponds to $n\in\mathbb{N}$. Krivine defines the operator $\chi$ by the evaluation rule: $$ \chi\ \phi \rightarrow \phi\ \overline{n\_\phi}$$ I believe Kleene wizardry will show that this is sufficient to do what you wish: i.e. define a quote and eval operators, if $\pi$ is computable.

Note that Krivine is notoriously challenging to read (please don't get mad if you read this, Jean-Louis!), and some researchers have done the charitable act of trying to extract the technical content in a more readable manner. You might try to take a look at these notes by Christophe Raffali.

Hope this helps!

---

It occurs to me that there is another reference that may be relevant to your interests: the Pure Pattern Calculus by Jay and Kesner formalizes a variant of the $\lambda$-calculus which extends simple abstraction over a variable to an abstraction over a pattern representing a pattern calculus itself. This is phenomenally expressive and in particular allows one to deconstruct an application itself: if I am not mistaken, the term:

$$ (\lambda (x\ y). x)((\lambda x.x\ x)\ (\lambda y.y)) $$

reduces to $\lambda x.x\ x$. Again, I belive that this is more than enough to implement the **quote** and **eval** operators.

# Answer
> 7 votes
Doing so is very difficult, if not imposible, without giving up confluence. Which is to say, I suspect you are right about a hairy meta-theory. On the other hand, it is possible to design a combinator calculus that can express all turing computable functions, and that has full ability to inspect its terms: see Jay and Give-Wilson.

I believe that having this ability does some bad things to your equational theory, however. In particular you will tend to only be able to prove two values are equal if the the are equal up to alpha equivalences.

I have not yet read the Krivine paper cody linked to, but I should note that in Classical logic you essentially have only two things: true, and false. Everything is equivalent to one of those. That is, you tend to have a collapsed equational theory anyways.

# Answer
> 4 votes
In the theory of programming languages the feature you speak about is usually referred to as "quote". For instance, John Longley wrote about it in some of his work, see this paper.

If you are just after theoretical considerations (as opposed to an actualy useful implementation) then you can simplify things by stating that `quote` (or `reflect` as you call it) maps into the type of integers `nat` by returning a Gödel code of its argument. You can then decompose the number just as you would an abstract syntax tree. Furthermore, you do not need `eval` because that can be implemented in the language – it is essentially an interpreter for the language.

For a concrete model which has these features you can consider Kleene's first combinatory algebra: interpret everything as a number (think of them as Gödel codes) and define Kleene application $n \star m$ to mean $\varphi\_n(m)$ where $\varphi\_n$ is the $n$-th partial function. This will give you a model of $\lambda$-calculus (with partial maps) in which `quote` is simply the identity function. No further features need to be added to the language.

If you tell me what you're after, I may be able to give you more specific references.

By the way, here is an *open problem:*

> Enrich $\lambda$-calculus (typed or untyped) with `quote` which is a congruence in such a way that you preserve the $\xi$-rule.

The $\xi$-rule $$\frac{e\_1 \equiv e\_2}{\lambda x \\,.\\, e\_1 \equiv \lambda x \\,.\\, e\_2}$$ says that $\lambda$-abstraction is a congruence. It allows us to reduce under $\lambda$ so to speak. In combination with `quote` this becomes problematic, since `quote` is supposed to be a congruence as well, $$\frac{e\_1 \equiv e\_2}{\mathtt{quote}\\,e\_1 \equiv \mathtt{quote}\\,e\_2},$$ so for instance we see that it must be the case that $$\mathtt{quote}\\,((\lambda x \\,.\\,x) y) \equiv \mathtt{quote}\\, y.$$ So somehow this `quote` is supposed to calculate "very canonical" Gödel codes – but even assuming we have a typed $\lambda$-calculus without recursion this seems to be hard to do.

# Answer
> 4 votes
Here is an alternative answer, instead of using my nominal approach which is still experimental there is some more established approach that goes back to the paper:

LEAP: A language with eval and polymorphism
Frank Pfenning and Peter Lee
https://www.cs.cmu.edu/~fp/papers/tapsoft89.pdf

The paper starts with:

> This then led us to the question, first posed by Reynolds, of whether strongly typed languages admit metacircular interpreters. Conventional wisdom seemed to indicate that the answer was "No". Our answer is "Almost".

Please note that LEAP is much stronger than what the OP wants. First of all it is typed. And second it asks for metacircularity, which means for example that eval can execute its own definition. In Prolog you get metacircularity for solve/1:

```
solve(true).
solve((A,B)) :- solve(A), solve(B).
solve(H) :- clause(H,B), solve(B).

```

If you add the following clause to solve/1:

```
solve(clause(H,B)) :- clause(H,B).

```

And if you see to it that clause/2 also returns the clauses of solve/1. You can then call solve(solve(...)) and see how solve executes itself.

Questions of self representatio still spurr some research, see for example:

Self representation in Girards System U
Matt Brown, Jens Palsberg
http://compilers.cs.ucla.edu/popl15/popl15-full.pdf

# Answer
> 3 votes
The problem is identified in vincinity of proof assistants such as Coq and Isabelle/HOL. It goes under the acronym HOAS. There are some claims around λ-Prolog that through the new ∇ quantifier such things can be done. But I couldn't get a grip yet of this claim. I guess the main insight I got so far is that there is no definite approach, there are a couple of possible approaches.

My own take, not yet finished, is inspired by a recent paper by Paulson on proving Gödels incompletness. I would use the object-level binders in connection with some data structure that has the meta-level names. Basically a similar yet distinct data structure as the one from the OP, and with Church coding since I am interested in dependent types:

```
datatype Expr = var Name                 /* written as n */
              | app Expr Expr            /* written as s t */
              | abs Name Expr Expr       /* written as λn:s.t */

```

The meta level expressions can be distinguished from the object level expressions in that we use the variable names n, m, .. etc.. to denote names. Whereas we use the variable names x, y, .. etc.. on the object level. The interpretation of a meta term in the object logic would then work as follows. Lets write \[t\]σ for the interpretation of the nominal term t in the nominal context σ, which should give an object term. We would then have:

```
 [n]σ = lookup σ n
 [s t]σ = [s]σ [t]σ
 [λn:s.t]σ = λx:[s]σ.[t]σ,n:x

```

The above would define what the OP calls an EVAL function. Small difference to Paulson, σ is only a finite list and not a functional. In my opinion it would be only possible to introduce an EVAL function and not a REFLECT function. Since on the object level you might have some equality so that different lambda expressions are the same. What you have to do would be to use eval to reason possibly also about reflection if you feel the need.

You would need to go to extremes like Prolog where nothing is expanded, if you want to tear down the wall between nominal and non-nominal. But as the λ-Prolog system example shows, in the higher-order case there are luring additional problems which can for example only be overcome in logical way by introducing new means such as a ∇ quantifier!

---
Tags: logic, lambda-calculus, semantics, reflection
---


# Question
Title: How much bits need to add to 100bit of data in order to correct up to 10bits?
I'm trying to calculate how much **minimum** bits need to be added to data of 100bits, in order to correct 10 bits that are messed up by:

1. bits that deleted (Erasure Correcting)
2. bits that corrupted (Error Correcting)

I tried Hamming code and Reed-Solomon codes but didn't figured out the answer of 1 or 2.

There are some other more-efficient algorithm for that problem ? Thanks in advance !

# Answer
> 2 votes
This seemingly innocent question, is actually quite difficult to answer. Let me try to give some more information on the parameters that get into the game here, and give a partial survey of common results and bounds.

As mentioned in Qalnut's answer, to deal with $10$ bits of errors (in the worst case) we must have distance at least $d=2\cdot 10+1$. This is given. Another parameter that is implied by your question is that the basic unit is a bit. You ask, what is the minimal length $n$ of a (binary) code that has distance $d$ and contains, at least $2^{100}$ codewords.

### The lower Bound

Let's first try to ask a slightly more general question:

> Given an alphabet of size $q$, what is the maximal number of codewords in code of length $n$ that has minimal distance $d$. \[Let's denote this number by $A\_q(n,d)$\].

The answer to this question is not simple at all, but there are several well known bounds. One very useful bound is the **singleton** bound, which states that $$ A\_q(n,d) \le q^{n-d+1}$$

This immediately tells us that in order to have $2^{100}$ codewords with distance $d=21$, you must take $n\>120$, that is, to add at least 20 bits. But this is only a bound, it never says that such a code (with length 21) actually exists, or how to find it.

More generally, this bound tells us that the relation between the *rate* of the code $R=n/k$ and the relative distance of the code $\delta=d/n$ behaves, for $n\to \infty$, as $$ R \le 1-\delta + o(1)$$

Since you wished the relative distance of your code to be $d/n =0.175$, the maximal rate is $\approx 0.825$, which is exactly what we got ($k/n = 100/120 = 0.833 = 0.825 + 1/n)$. The moral of this story is: if you aim for distance $\delta$ (which can correct $\approx \delta n /2$ errors), you will have to add at least $$(n-k) = n-Rn \approx \delta n $$ more symbols. This is a nice rule of thumb. In the asymptotic case (that is, when $n$ is very very large) that would be approximately the answer.

As said, this bound is, in many cases, not really tight. For other lower bounds, look for the Plotkin bound (for binary codes) and the Johnson bound.

### The upper bound

So we know we can't get $n$ smaller than, say, 120. But this is not very helpful from a practical point of view, since we don't even know if a code with $n=120$ exists, or maybe in this case the first code with $d=21$ and $k=100$ shortest $n=137$??

Gilbert and Varshamov come to our help, and show that there always exists a code for which $$ A\_q(n,d) \ge \frac{q^n}{\sum\_{j=0}^{d-1}\binom{n}{j}(q-1)^j}$$

So now you just need to plug in $A\_q(n,21)=2^{100}$ and find $n$. Let me WolframAlpha this for you, it gives $n\<189$ (actually, a tighter version of the GV bound for binary code will gives $n\le 185$. The GV bound even tells you how to find this code, in a greedy way (thus, doesn't expect it to be efficient).

### The "answer"

As I said, the real answer may be difficult to find, and depend on $q$ (why are you so fixed on binary codes? maybe considering the message as symbols of a larger alphabet would give a better code? But then the noise pattern need to be properly defined, so I'll skip this explanation here), and on $k$ (why 100 bits? ain't 127 bits make much more sense?), and on efficiency (which you asked, but I will not get into), etc.

The bottom line, is that many people thought on such questions over the last century, for various parameters. The problem is to find the code you need. For this purpose you can look at some Code tables that aggregate codes of various parameters.

For instance, for short binary codes, there is this work, "Bounds for binary codes of length less than 25" (*IEEE Trans. Inform. Theory* 24:81-93, 1978). A more extensive list can be found, for instance, at Code Tables: Bounds on the parameters of various types of codes. Searching in Table of Nonlinear Binary Codes for a code with the parameters you gave in your question, I found that the shortest code for distance 21 that has at least $2^{100}$ codewords has length $n=191$. The reference is H. J. Helgert and R. D. Stinaff. "Shortened BCH codes", *IEEE Trans. Inform. Theory*, 19:818--820, 1973. Damn, this is worse than the GV bound, but it allows you to code messages of up to $k=116$ bits! instead, If you are willing to settle with messages of length $k=91$ bits, you will be able to do that with $n=173$ bits. (M. Kasahara, Y. Sugiyama, S. Hirasawa, and T. Namekawa., *IEEE Trans. Inform. Theory*, 22:462--468, 1976). Using this table for linear binary codes, there is a *constructive* code with $k=100$ and $n=176$. There references are inside this link.

So back to you innocently looking question: the answer(1) is **76**.

---

(1) At least, the best answer I was able to google. (**ADDENDUM**, found a better one:) and re-google.

# Answer
> 1 votes
A block code $\mathcal{C}$ with minimum distance $d$ can detect up to $d-1$ errors, correct up to $d-1$ erasures, and correct up to $\left\lfloor\frac{d-1}2\right\rfloor$ errors. In general, these error detection/correction capabilities are theoretical maximums and cannot be achieved simultaneously. A proper answer to your question would require *at very least* information about the family of codes you want to use and about your decoding scheme.

In any case, here's a reasonable scenario using Hamming codes. Hamming(7, 4) encodes 4 bit messages of data ($k=4$) with 3 parity bits ($m=3$) for a block length of $n=7$. It allows for single error correction if there is only one error in the received block (SEC) **or** double error detection (DED), but not both.

We can do better. How about a code that can distinguish between single/double bit errors and simultaneously correct a single bit error (SEC-DED)? We'll use an extended Hamming code. To determine how many parity bits $m$ we need, we can use this inequality: $2^m \geq m + k + 1$

We want to send 100 bits and correct up to 10 errors, Hamming codes can correct at most 1 error per block, so we must 10 messages each of length $k=10$. From the above inequality, we need at least $m = 4$ parity bits. That suffices for SEC but we need one more bit, $m=5$, for SEC-DED. That's 15 bits per block ($n= k + m = 15$) and 10 blocks for a total of 150 bytes -- 50 more than the original message. If we know the sender's clock speed, we can determine the position of any erased bits and correct/detect them just as we would corrupted bits.

Do note: if more than one error per 10-bytes block occurs, the sender will have to resend it. For codes that work on streams rather than blocks, see convolutional codes. For optimal error correction rate with block codes, see Hadamard code.

Aside: the code we've used is Hamming(15, 10). It's a variant of Hamming(15, 11), and it is used in the Bluetooth spec to encode data for transmission. It offers the highest possible ratio of message length to block length for an SEC-DED code with 5 parity bits.

---
Tags: information-theory, encoding-scheme, error-correcting-codes
---


# Question
Title: Machine learning algorithm(s) for recognizing simple graph patterns
I generate some simple graphs based on usage stats of a website, and they may look like these:

I call the 'pattern' on the left 'convergence', and the 'pattern' on the right 'divergence'. The terms 'convergence' and 'divergence' are loosely and visually defined, and they simply means that the two curves either become closer and intersected (decreasing difference in `Y` while increasing in `X`) or become apart (increasing difference in `Y` while increasing in `X`)

Of course, the curves may neither converge nor diverge. An extreme case of such case is they may evolve more or less parallel to each other.

My problem is to recognize the convergence and the divergence patterns. This may be trivial as done visually by human, but I want to automate the task using an algorithm, and likely a ML algorithm. "Pattern recognition' comes to mind as a (broad) area relating to this kind of problem.

I have some very high-level idea about a possible approach: first manually label some existing graphs as 'convergence', 'divergence', or 'other', and then use a set of these categorized graphs/images to 'train' the ML algorithm in the hope that the algorithm can recognize the patterns on its own after proper training.

My specific questions are:

1. What are the recommended ML algorithm(s) for this problem? And any pointer to the theory and implementation of such algorithm(s) is appreciated.
2. I may be terribly ignorant, but: does such a ML algorithm operate on the graph/image directly or does it operate on the underlying data points that make up the graph? In other words, what would be the input to the algorithm? A series of images or a bunch of numbers?

# Answer
I suspect machine learning is the wrong approach. Instead, I suspect you will do better to define a metric and measure the metric, or define a hypothesis and use hypothesis testing. You are not trying to predict the future evolution of these values; that's something that ML might be suitable for, but that's not what you're trying to do, so ML doesn't seem like the right tool for the job.

Let me suggest an approach. If $f(t),g(t)$ are the values of the measurements at time $t$, define $D(t) = |f(t)-g(t)|$ (the absolute value of the difference). $D(t)$ measures how close they are. Then, you want to test whether $D(t)$ is increasing or decreasing. If $D(t)$ is decreasing, then you have a situation of "convergence"; if $D(t)$ is increasing, then you have a situation of "divergence".

How can you test whether $D(t)$ is increasing vs decreasing, over some time period? Here's one simple approach. You could separate your time window into two halves, the first half and the second half. Calculate the average value of $D(t)$ over the first half, say $\mu\_0$, and the average value of $D(t)$ over the second half, say $\mu\_1$. Now you can compare $\mu\_0$ to $\mu\_1$, to determine whether it is increasing or decreasing.

Alternatively, another approach would be to use simple linear regression on $D(t)$ to fit a linear model $D(t) \sim \alpha t + \beta$, and then test whether the slope $\alpha$ is greater than zero or smaller than zero.

However, one problem with this is that your conclusion might be confounded by noise: it might be that $D(t)$ is neither increasing nor decreasing, but all you're seeing is statistical noise. So can you separate out the case where $D(t)$ is increasing from the case where $D(t)$ is decreasing?

The answer is yes: you can test for statistical significance using hypothesis testing. If you observe $\mu\_0 \> \mu\_1$, you can use a hypothesis test to test whether this difference is statistically significant (e.g., using a permutation test). Or, if you fit a linear model and find $\alpha \> 0$, you can use a hypothesis test to test whether the difference from zero is statistically significant (this is covered under standard textbooks on linear regression).

There's lots more one can say about hypothesis testing, but this should give you the general approach. The short version is: don't use machine learning; using an appropriately chosen statistical measure or statistical hypothesis test.
> 5 votes

# Answer
I think the key is to abstract your problem by finding appropriate features. For example a feature could be the minimal distance between the two curves. Or how many times do they cross over. Or how many steps do they stay less than K units away from each other. Think about features that will capture convergence and divergence. Once you have the right features you can throw them into your favourite machine learning algorithm like a Support Vector Machine, Neural Network or Decision Tree. I would give the learning algorithm a set of numbers, because it will make the learning much easier than giving it the whole image.
> 3 votes

---
Tags: machine-learning, artificial-intelligence, pattern-recognition, hidden-markov-models
---


title: Proof of Trakhtenbrot's theorem

text:
# Question
Title: Proof of Trakhtenbrot's theorem
In the proof of Trakhtenbrot's theorem (as given in "Elements of Finite Model Theory" by Leonid Libkin), for every Turing machine $M$, author constructs a FO sentence $\Phi\_M$ of vocabulary $\sigma$ such that $\Phi\_M$ is finitely satisfiable iff $M$ halts on the empty input. Then he says that as the latter is known to be undecidable so the theorem holds.

My doubt is, the vocabulary $\sigma$ that was constructed depends on the Turing Machine $M$. But the theorem holds for any relational vocabulary with at least one binary relation symbol and also it should not depend on the machine $M$. Perhaps the claim of author is enough to imply the theorem for arbitrary vocabulary, but I am unable to see how.

# Answer
> 6 votes
I'm a bit late, but the only answer does not address the question.

You state that the vocabulary $\sigma$ depends on the choice of turing machine $M$. If this were the case, then indeed the claim would only follow for arbitrary vocabularies. But - as the index of $\Phi\_M$ and the missing one of $\sigma$ hint at - only the formula depends on $M$, the vocabulary is fixed for all turing machines.

Now all this shows, is undecidability for this particular vocabulary $\sigma$. To get the desired undecidability for all vocabularies with at least one binary relation, we have to do the reduction using only a single binary relation. We do this by encoding all of $\sigma$ into a single binary relation. The specifics are a popular exercise (and indeed the first exercise in the chapter), and go back to techniques first used by Kálmar.

# Answer
> 5 votes
They perform a *reduction*: given an arbitrary Turing machine, they construct a specific formula equivalent to the question "Does this machine halt on $\varepsilon$?". If validity could be decided in the target logic, so could the halting problem, which contradicts its undecidability.

So yes, the formula can depend on the machine as much as it wants. See here to read more about this, and browse questions for more examples.

---
Tags: turing-machines, logic, reductions, undecidability, finite-model-theory
---


# Question
Title: FSM + state data is Turing complete abstraction?
I'm playing with Akka FSM. The declaration of a an Akka FSM consists of states + data mantained during the states (the akka doc is more clear than me) + events that trigger transitions between states. Can we say that such a formalism is Turing-complete? I can't think of a problem that can't be solved this way.

# Answer
Maybe your questions should be more self-contained, but let's assume that your description together with the documentation from Akka amounts to the following description:

* The input consists of events, and the output consists of actions.
* Even so output actions may trigger further input events, this relation is neither fully deterministic, nor part of the machine model itself.
* There are a finite number of states that determine which **rules** will be applied to the input event and the internally stored data, *for determining the output action, the new state, and the modification of the internal data*.
* After an output action is performed, the machine transitions into a new state, and waits for further input events.

Under these conditions, the machine model is only Turing complete if already the **rules** *for determining the output action, the new state, and the modification of the internal data* were Turing complete.

What you have in mind is probably some mechanism for triggering input events as part of the output action. So the FSM is supposed to have some sort of first-in, first-out event queue, and the output action can post input events to this queue. In this case, this machine model would be more powerful than a queue automation, which is known to be Turing complete.
> 1 votes

---
Tags: finite-automata, turing-completeness
---


# Question
Title: Programming a genetic algorithm with a non-fixed size
I am trying to write a genetic algorithm for a program. Most examples for genetic algorithms use something like this as the input:

```
aaaaaaaaaa

```

and mutate/crossover until they get

```
helloworld

```

or similar. This requires however that you start with something of length N, but my search space doesn't have a fixed length. How should I alter the mutation/crossover steps to allow for changes in unit size?

# Answer
> 2 votes
There are plenty of possibilities:

* Add/remove a symbol at the end with probability $c$.
* Add/remove $k$ symbols at the end with probability $c \cdot 2^{-k}$.
* For every symbol, remove it with probability $c\_1$;
for every gap, insert a symbol with probability $c\_2$.
* For every symbol $a$, convert it to $a^k$ with probability $c \cdot 2^{-k-1}$.

And so on and so on. Basically, whatever works for you is good. Without any knowledge about the function you are trying to optimise, it is impossible to guess which strategies make more sense than others.

# Answer
> 0 votes
Another idea is to start with a very large genome, enough that it will cover any possible target. During evaluation you only check whether the start of your genome matches the target. For example, start with

```
aaaaaaaaaaaaaaaaaaaaaaaaaaa

```

end with

```
helloworldsdfkjiojerpweorke

```

As long as the first part matches we are happy and we ignore the junk in the end.

---
Tags: algorithms, optimization, genetic-algorithms
---


# Question
Title: How to identify and find navels from human pics
I have a specific question and not sure what tools I can use to finish my projects. I know this may has been well solved, but I am quite new to the image recognition and detection area and don't know what tools I can use to productionize this work.

We are trying to find, for example, navels in humans pics:

1. I have 10000 body pics from different persons as the training set. All pics have shown their navels, but we don't resources to label them in these pics.
2. Given a pic of a different person, trying to find this person's navel in this pic within a very short time (e.g., less than 1 second). The accuracy must be very high.

I am wondering what tools I can use to do this work (the best is that has c++ implementation because we may want to productionize this project).

# Answer
> 0 votes
I don't know why you would want to find navels, sounds like a strange problem. Anyway, I would approach it using standard computer vision detection methods. Create a labelled dataset of navels. Then train a sliding window detector based on some visual features eg., Haar, SIFT, HOG. Now use your detector to find more examples of navels and add them to your dataset.

---
Tags: machine-learning, image-processing, pattern-recognition
---


title: d-ary heapsort analysis

text:
# Question
Title: d-ary heapsort analysis
I need to find a tight bound on the number of comparisons in a d-ary heapsort, in terms of `d` and `n` (the length of the array we want to sort).

Since inserting `n` items to a heap takes `O(n)` , and each delete-min takes `O(d log n/ log d)`, I was thinking the bound is `O(n d log n / log d)`. Am I right? If so, how do I prove that it is indeed a tight bound?

Thanks.

# Answer
> Inserting $n$ items to a heap takes $\Theta(n)$.

You probably mean that "building" a heap takes $\Theta(n)$.

> Each `delete-min` takes $\Theta(d \lg n/ \lg d)$, I was thinking the bound is $\Theta(n d \lg n / \lg d)$.

I agree with you.

> How do I prove that it is indeed a tight bound?

How tight do you want to prove it is? Do you want to show that the worst-case running time of $d$-ary heap-sort is $\Omega(n d \lg n / \lg d)$? If so, I tend to think it is indeed tight.

For a hint, this paper: The Analysis of Heapsort mentions that (in Abstract)

> The number of keys moved during $2$-ary heap-sort when sorting a random file of $n$ *distinct* elements is $n \lg n + O(n)$ in the worst case.

It even further proves that (Notice that it is for the ***best case***)

> Theorem 1 (Page 7): Heap-sort ($2$-ary) requires at least $\frac{1}{2} n \lg n- O(n)$ data moves for any heap composed of *distinct* keys.

Maybe you can adapt it to $d$-ary heap-sort.
> 1 votes

---
Tags: data-structures, runtime-analysis, sorting, heaps
---


# Question
Title: Using the pumping lemma to prove that a language is context-free
I am new to automata theory.

Could you give me a little hand with the correct use of the pumping lemma? I understand now how to proof a language is not context-free, but how do I use the pumping lemma to proof it is?

Do I find one way to break the word into: uvwxy so that v and x can be pumped? Is that enough and can I pick it in such a way that u or w or y are empty. I understand from the lemma that as long as v or x are not empty it is good. But can only w be empty and the rest be at least one character?

I did read on this topic, but I am just trying to make sure that what I understood is correct and there aren't other not so obvious things I should consider. Please help.

# Answer
I read How to prove that a language is not context-free? and it has a very detailed example of a demonstration using the pumping lemma. But you are looking for some general understanding of the method so I will tell you the steps I follow when I use pumping lemma to prove that $L$ is not CFL:

1) You suppose that $L$ is CFL. The idea is find a contradiction using the pumping lemma.

2) By pumping lemma exists a constant $N\>0$ associated to $L$. Use a generic constant because if you use a fixed one like $N=1$ for example, and don't find a contradiction you have to try with $N=2,3,4,...$.

3) You have to choose a word $\sigma \in L$ such that $|\sigma|\geq N$. You have to use your creativity to choose a word that allows you to easily reach a contradiction in the next steps.

4) By the pumping lemma exists a factorization of your word $\sigma=uvwxy$ and the following always complies: $$|vwx|\leq N$$ $$|vx|\geq 1$$ $$\sigma\_i=uv^iwx^iy \in L \forall i\in\mathbb{N}\_0$$

5) So the next step is to prove that the factorization does not exists. Your job if to check that all possible factorizations in the form $uvwxy$ don't complies with the 3 points of the pumping lemma. This generate a contradiction in your initial assumption then $L$ can't be CFL.

6) If you find a factorization of your particular word this mean nothing! Remember that the pumping lemma says:

If $L$ is CFL $\Rightarrow$ exist a factorization$\dots$

So you have two options at this point. The first is suspect that maybe your language is CFL and try to write a context-free grammar or draw a push-down automaton that denotes $L$. In second option you can assume that the word $\sigma$ was bad pick and try with another word to find a contradiction.

This is the general mechanics of the pumping lemma. I recommend you to try to understand the theory behind it or you will probably make mistakes in your test.

**You can't use the pumping lemma to show that a language $L$ is context-free.**. If you want to prove that $L$ is CFL the standard way is to write a CFG or draw a PDA like I said before.
> 3 votes

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


# Question
Title: Issue in comparing classifiers for pattern recognition
I have designed a classifier M which recognizes gestures and classifies it under any category always. A gesture is classified based on the hamming distance between the sample time series y and the training time series x. The result of the classifier are probabilistic values. There are 3 classes/categories with labels A,B,C which classifies hand gestures where there are 100 samples for each class which are to be classified (single feature and data length=100). The data are different time series (x coordinate vs time). The training set is used to assign probabilities indicating which gesture has occured how many times. So,out of 10 training samples if gesture A appeared 6 times then probability that a gesture falls under category A is

> P(A)=0.6 similarly P(B)=0.3

and

> P(C)=0.1

Now, I am trying to compare the performance of this classifier with Bayes classifier, K-NN, Principal component analysis (PCA) and Neural Network.

1. On what basis,parameter and method should I do it if I consider ROC or cross validate since the features for my classifier are the probabilistic values for the ROC plot hence what shall be the features for k-nn,bayes classification and PCA?
2. Is there a code for it which will be useful.
3. What should be the value of k is there are 3 classes of gestures?

Please help. I am in a fix.

# Answer
There isn't an easy way to do this. In fact a recent paper by Charles Parker explains some of the problems with using ROC curve measurements (there's a friendly overview at my blog \- self promotion alert!!). His paper does make some recommendations on the best ways to compare different classifiers, so you will find something useful there.
> 7 votes

# Answer
1. The general way to compare classifiers is to compare them using ROC. For a fixed range of false alarm rates you check which classifier has achieved the highest accuracy. If you want a single measure then you can use Area Under ROC (AUC). There are many other measures too, look them up. For a fair comparison you need to compare all classifiers on an even footing, this means the same features and the same training conditions.
2. The value of k is something that you will need to find out by trying different values. Pick the value that performs best on your validation set, but only report results on your test set, which you haven't used during parameter tuning.
> 0 votes

---
Tags: machine-learning, pattern-recognition
---


# Question
Title: $k$-Multiset intersection efficient algorithm
Given a collection of sets $C= \\{S\_1,S\_2,\cdots,S\_n\\}$ such that each set $S\_i \in C$ is sorted and has at least $k$ elements.

What is the most efficient algorithm for finding the intersection of these sets: $\bigcap\_{S\_i \in C}{S\_i}$

# Answer
> 1 votes
If the least elements in all $S\_i$ are equal then pick it for final set else pick least element among all $S\_i$ and remove (remove minimum among all sets and not minimums of all sets). This works in $O(n\*|C|\*log |C|)$, where $|C|$ is the total number of elements in $C$ (not it's cardinality). This works since all your $Si$ are sorted and removal of element will maintain the sorted order.

---
Tags: algorithms, sets
---


# Question
Title: Given asymptotic bounds, what can we say about small n?
I am trying to wrap my head around these asymptotic notations. Given $f(n)$ and $g(n)$, one can write $f(n) = \Omega(g(n))$ as shorthand for $f(n) \geq c\*g(n), n\geq n\_0$. But what happens when $n\<n\_0$. What can we then say about $f(n)$ and $g(n)$? Do we just assume that $f(n)$ is a constant and the relation still works? Or does the question not even make sense to ask?

# Answer
> 2 votes
Nothing. If all you know about two functions is their $O$/$\Omega$ relations, you know *nothing* about how they relate to each other on *any* finite prefix.

Yes, this makes asymptotics of, say, runtime functions absolutely useless in terms of questions like, "which algorithm should I use in scenario X?" On first sight, that is.

Luckily, we usually *do* analyse with more detail but throw them away when formulating the theorem with coarse notation like Landau symbols. Many results about "practical" algorithms implicitly say, "and this behaviour can be observed for reasonable $n$".

Sometimes you get better theorems which use Landau notation for "error terms" only; authors like Knuth do not say "algorithm A runs in time $O(n \log n)$", but rather "algorithm A takes $2n\log n - 2n + O(1)$ comparisons". This does not completely do away with your issue, but mitigates it to some extent. If you know that that $O(1)$ stands for $\leq 1377$, you can make informed decisions based on that result.

Some of our reference material discusses facets of this issue.

---
Tags: asymptotics, landau-notation
---


# Question
Title: Computing a boolean function with a small formula
Suppose that $x = (x\_1,\ldots,x\_n)$ is a binary vector and $f(x)$ is a boolean function. Furthermore suppose $y = (y\_1,\ldots,y\_m)$ is a binary vector and that $F(x,y)$ is a binary formula of size $k.$ Here by *size* I mean the number of leaves in $F.$

Suppose I have vectors $S = \\{s\_1,\ldots,s\_n\\}$ such that for any $x \in \\{0,1\\}^n$ there is a $s \in S$ such that we have $$ F(x,s) = f(x).$$

I need to prove that in this case I can express $f(x)$ as a boolean formula of size $O(n\cdot k).$

What would be the idea about this?

Since for every input $x$ we have an $s \in S$ one could encode the specific $s$ for every one of the $2^n$ possible inputs but this would give a too large formula.

**Edit.** The original text as it appears in the book "Extremal combinatorics with applications to computer science 2ed."

# Answer
> 2 votes
Something has gone wrong in the way you applied Adleman's theorem: it has led you to try to prove something that isn't actually true.

The statement the book asks you to prove *is* true. There *is* a good deterministic algorithm for $f$. Adleman's theorem, applied properly, immediately gives you a good deterministic algorithm for $f$. Just make sure you pick the definition of "good point" correctly. Hint: A good point for $a$ is a value $y$ such that $F(a,y)=f(a)$. What can you conclude about $f(a)$, if you observe a point $y$ such that $F(a,y)=1$? Now an application of Adleman's theorem immediately leads to a simple deterministic algorithm for computing $f$ and a small boolean formula for $f$. In particular, we get the following boolean formula for $f$:

$$f(x) = F(x,s\_1) \lor F(x,s\_2) \lor \dots \lor F(x,s\_n).$$

Why does this work? Well, if $f(x)=0$, then we're guaranteed that $F(x,y)=0$ for all $y$ (this comes directly from the exercise in your book), so in particular every term of the above disjunction is 0, so this formula gives the correct answer for $f(x)$. On the other hand, if $f(x)=1$, then Adleman's theorem guarantees that there exists at least one $s\_i \in S$ that's a good point for $x$, i.e., at least one $s\_i$ such that $F(x,s\_i)=f(x)=1$, which means that the above disjunction is 1, so this formula gives the correct answer for $f(x)$ in this case, too.

In contrast, the claim you're trying to prove isn't true. Here's an explicit counterexample. Let $F(x,s)=s$ (so $m=1$), $s\_0=0$, $s\_1=1$ (so $S=\\{0,1,\dots\\}$), and let $f$ be any function with no small formula. Then it is easy to verify that for all $x$ there exists $s \in S$ such that $F(x,s)=f(x)$: in particular, you can take $s=f(x)$. Notice that we didn't use anything about $f$, so we were free to choose $f$ any way we want. It is also easy to see that $F$ has a small formula, for this choice of $F$. Therefore, this choice of $F,S,f$ satisfies all the preconditions of your claim. However, (by assumption) $f$ doesn't have a small formula, so this is a counterexample for your claim.

There's a crucial difference between "there exists at least one $s$ for which (blah) is true" vs "(blah) is true for a large fraction of $s$".

I don't know how you got to your claim or what went wrong in your translation from the book's exercise to your claim, but I suspect you didn't apply Adleman's theorem quite right, or the way you applied it didn't give you strong enough conclusions/assumptions about the properties that $F$ has.

---
Tags: circuits, boolean-algebra
---


# Question
Title: Random uniform sampling of position restricted permutations
Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions?

Consider $N \times N$ *restriction matrices* $R$, that is matrices over $\\{0,1\\}$. Each such $R$ defines a set of permutations $\Pi\_R$ according to

$\qquad\displaystyle \pi \in \Pi\_R \iff \forall i \in \[1..n\].\ \pi(i) = j \implies R\_{i,j} = 1$.

Note that $R$ is not permutation matrix but a general restriction matrix. I want to sample *uniformly* from $\Pi\_R$ given $R$.

So far I am using Hungarian's assignment algorithm to produce random permutations consistent with restriction matrix $R$, but these permutations are significantly non-uniformly sampled.

Examples:

* Every $R$ that has one one per row and column admits only a single permutation.
* For

$\qquad\displaystyle R = \left( \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right) $

there are only two permutations: $\pi\_1 = (2 1 3)$ and $\pi\_2 = (2 3 1)$.
* If $R$ contains only ones, $\Pi\_R$ is the set of all permutations.

# Answer
> 1 votes
I'll answer both the question as it currently stands, and the original version of the question.

## The current question

Your question is basically asking for a way to sample uniformly at random from the set of perfect matchings of a given bipartite graph. In particular, we have $N$ nodes on the left side corresponding to the $N$ rows of $R$, and $N$ nodes on the right side corresponding to the $N$ columns of $R$. Draw an edge between node $i$ (on the left) and node $j$ (on the right) when $R\_{i,j}=1$. This gives a bipartite graph $G$. Now there's a bijection between the perfect matchings of $G$ and the permutations in $\Pi\_R$, so we want to sample uniformly at random from the perfect matchings of $G$.

The following question refers to algorithm for exactly that problem: Sampling perfect matching uniformly at random. In particular, there are existing algorithms that approximate sampling from the uniform distribution (i.e., their distribution is almost uniform).

## The original question

Originally, the question imposed the stronger restriction that $\pi(i)=j \Longleftrightarrow R\_{i,j}=1$. Here's the solution to that version of the problem.

**Theorem.** If $R$ is a permutation matrix, there is a single permutation $\pi$ that is compatible with $R$. If $R$ is not a permutation matrix, there is no permutation $\pi$ that is compatible with $R$.

Recall that a permutation matrix is a matrix that has exactly one 1 in every row and every column.

*Proof of theorem.* Consider any row, say row $i$. If it is all zeros (has no $1$), then there's no matching permutation ($\pi(i)$ has to equal something). If it has two or more $1$'s, there is no matching permutation (you can't have $\pi(i)=j$ and $\pi(i)=k$ where $j\ne k$). So for there to be a matching permutation, the row must have exactly one $1$. Since the row $i$ was arbitrary, this must be true of all rows. By symmetric, the same is true for all columns. QED.

---

You can easily recognize whether a matrix is a permutation matrix or not. Given a permutation matrix you can easily recover the corresponding permutation. Therefore, an algorithm to do what you want is trivial. The algorithm either outputs nothing (if $R$ is not a permutation matrix) or always deterministically outputs a single permutation (if $R$ is a permutation matrix).

---

For the example $3 \times 3$ matrix you gave in your question, there is no permutation that is consistent with that matrix. Your matrix has $R\_{2,1}=1$ and $R\_{2,2}=1$. By your conditions, this implies the requirements that $\pi(2)=1$ and $\pi(2)=2$. However, $1\ne 2$, so it is impossible to have a permutation $\pi$ that satisfies both of these requirements.

---
Tags: combinatorics, randomized-algorithms, permutations, sampling
---


# Question
Title: Selecting k-1 items that divide a sorted array to k equal parts
Given an unsorted array of $n$ integers, I need to find an $O(n \log k)$ algorithm that finds the $k-1$ items that divide the sorted array to $k$ equal (up to $\pm 1$ items) parts.

For example, if $k=3$, the items we want would be at indices $n/3$, $2n/3$ in the array *after we sort it*.

I know that you can select those items in $O(nk)$ but I can't think of how to improve that $k$ to $\log k$. I'd appreciate any help.

# Answer
I assume that $k = 2^m$ ($m \in \mathbb{N}$) and $k \le n$.

Here is a recursive (divide-and-conquer) algorithm:

1. Select the median of the array $A$ and use it to partition the array into $A\_l$ and $A\_r$
2. Do the same thing above recursively on $A\_l$ and $A\_r$.

It is easy to see that the depth of the recursive is $O(\lg k)$. Unfolding the recursive tree, you will find that at each depth (i.e., recursion), the non-recursive cost is $O(n)$ for median-selection and partition.

---

Note that if $k = n$, the algorithm above is the QuickSort algorithm with medians as pivots.
> 2 votes

# Answer
Initially assume that k is odd.

Algorithm:

1. Find the median of the unsorted array. This can be done using Selection Algorithm in O(n) time.
2. Recursively find the median of the two partition thus obtained.

Time complexity: O(nlog(k))

Analysis:

In each recursive step, you double the items obtained so far. So the number of steps would be log(k). Also in each recursive step time taken is O(n). Thus total time taken would be O(nlog(k))

The case in which k is even can be solved in similar fashion.
> 2 votes

---
Tags: algorithms, selection-problem
---


# Question
Title: Forward Error Correction for streaming data
I am very familiar with error correcting codes. However, it is not obvious how to apply them to adaptive streaming data. There also doesn't seem to be much literature on the problem.

The naive approach might be to take small codewords of data and use forward error correction until there is a statistically significant chance that the client has received them. Then, move to the next codeword.

My question is whether there are known pitfalls with the naive approach and whether there exists a more comprehensive or performant solution (let's ignore the use of locally decodeable codes for now).

# Answer
> 1 votes
tl;dr: This solution is quite good for random noise, but fails for bursty noise, or if you wish to get extremely low failure probability.

## Random Noise

Assume the average noise (across the entire stream) is 10%, that is, each symbol is flipped with probability 0.1. The naive approach you suggest can be summarized as taking small chunks of data ("small" with respect to the size of the stream), and encoding each chunk individually via some ECC. For instance, a single chunk may be of length $\log N$, while the stream is of length $N$. Then, if you use ECC on that chunk (and expand it into length $C\log N$, for some large constant$~C$), there is a probability of $\approx 2^{-C\log N}$ that it will be decoded incorrectly. Taking a union bound over the entire stream, there is only a polynomially small probability that some chunk of data will fail.

If polynomially-small failure probability is good for you - you are golden. Otherwise, you will have to take ECC with larger redundancy, and this may be impractical. There's also an issue of delay, but that is secondary here.

### Bursty noise

A different problem arises when the noise is not random, but adversarial, or even simpler, just bursty. Here again we can assume that 10% of the transmissions are noise, however they can come as a single burst of noise, corrupting $N'/10$ consecutive transmissions. Clearly, the above naive solution will fail, since there are many codewords that will be completely noisy. Note that even if you increase the redundancy of each encoding, this will not help. The only solution is to increase the chunk size (that is, to send at most 10 encoded chunks), but this is terrible in terms of delay.

One solution to the bursty noise is send the information in a random order. If the transmission is long enough and the information is spread across this transmission quite evenly, then even a burst of noise "behaves" like a random noise with high probability (i.e., it will corrupt the codewords in balanced manner, and will have low probability to completely corrupt a single codeword). This might not be enough.

Using stronger codes (that have an "online" property) can help resisting more noise, improve the delay and reduce the failure property to be exponentially small. See Franklin et al., "Optimal Coding for Streaming Authentication and Interactive Communication" (*IEEE Trans. Info. Theory.* 61:133-145, 2015). There is also a similar encoding scheme that works for sliding windows rather than unbounded streams, see "Efficient Error-Correcting Codes for Sliding Windows".

# Answer
> 0 votes
Techniques based on rateless codes can work better for correcting erasures on streaming data, especially when you do not have a good sense of the channel properties, or the channel varies significantly. The coded-datagram protocol, for example, handles this case.

If you are really interested in arbitrary errors, take a look at convolutional codes.

---
Tags: streaming-algorithm, error-correcting-codes
---


# Question
Title: How to make the standard DP algorithm for 0/1 Knapsack make larger steps?
The standard knapsack problem solution is O(nW) where we will increment the weight +1 at a time to get to the solution.

Is there any approach to the knapsack problem that does not require incrementing weight +1 at a time.

e.g. One way that I can think of is to divide all the numbers by its common

`Capacity = 100 weights = [5, 10, 20] -> Capacity = 20 weights = [1, 2, 4]`

# Answer
Your assumption is wrong; the dynamic programming algorithm does *not* do that. It computes $m(n,W)$ according to the recurrence

$\qquad\displaystyle m(i,w) = \begin{cases} 0, &i=0 \lor w=0; \\ m(i-1,w), & w\_i \> w; \\ \max \\{ m(i-1,w), m(i-1, w - w\_i) + v\_i \\}, &w\_i \leq w . \end{cases} $

Here, $(w\_1, v\_1), \dots, (w\_n, v\_n)$ are the weight-value pairs and $W$ is the knapsack size. Note how $m(i,w)$ is the maximum value that can be achieved with items $1, \dots, i$ and up to weight $w$; prove that by induction.

You can note two things:

1. The algorithm does not "move towards" $W$ in a straight fashion; it investigates many "paths" from $0$ to $W$ in an interleaved fashion, optimizing locally.
2. When it makes a stept, it does not have to be by $1$; all steps correspond to a $w\_i$.
> 3 votes

---
Tags: algorithms, optimization, dynamic-programming, knapsack-problems
---


title: Context free grammar for this language

text:
# Question
Title: Context free grammar for this language
Is this language Context Free?

$L=\\{a^{n+3} b^{2m} \mid n \neq m \\}$

I think that I could split the languages into $L\_1$ and $L\_2$ with the conditions $n\<m$ and $n\>m$, provide 2 CF grammars and then to make the union. But I don't know how to put the condition $n\<m$ to the grammar or how to think about the conditions. Thank you!

# Answer
> 2 votes
Idea: Construct a Grammar fragment for `$a^nb^(2n)$`. Complement it with rules that break the symmetry.

```
1: L -> aaaX

2: X -> aXbb   // So far, the subsequence of terminals does not belong to L.
               // The next two rules break the symmetry.
3: X -> aP
4: X -> Qbb

5: P -> aP  | epsilon
6: Q -> Qbb | epsilon

```

**Proof sketch**

The grammar is clearly context-free.

The correctness can be proven eg. by induction over possible derivations. The intuition is simple:

* Each derivation starts with applying rule 1 followed by an arbitrary number of. applications of rule 2. At each step of this derivation, the current item matches `a^3a^nXb^(2n); n >= 0`. In particular, `n=m`in the nomenclature of the problem statement.
* After application of any one of the rules 3 and 4, non-terminals will only ever expand into sequences of either `a` or `b`.
* At least on application of rule 3 or 4 is necessary to complete a derivation.

The very first application of 3/4 introduces the imbalance between `a` and `bb` in the terminal string. After passing that 'trapdoor', this imbalance will never be offset, since only the 'right' terminals will be produced henceforth.

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


# Question
Title: Algorithm for queue with multiple repeated different interval events
I have N events, each repeats after some time ti. I want a queue where I can pop out next event.

For example, I have events A,B,C with intervals 2,3,5 At the beginning they all are in the queue with values:

A-2, B-3, C-5

When I take out event, it should be A, after that I put it back, but add +2.

B-3, A-4, C-5

Next is B. I add +3

A-4, C-5, B-6

Next is A, I add +2

C-5, B-6, A-6

and so on.

What could be the best algorithm for that?

# Answer
> 2 votes
Use an efficient implementation of priority queues, such as binary heaps. Then, your algorithm would look like this:

```
proc triggerEvents(events : Array[(String, Integer)]) {
  q = new MinHeap()
  for ( i=0; i<events.size; i++ ) {
    // use event index as key, interval as priority
    q.add(i, events[i][2])
  }

  while ( true ) {
    (i, p) = q.popMin()
    trigger(events[i][1])
    q.add(i, p + events[i][2])
  }
}

```

With $n$ the number of events, this will take time $\Theta(n \log n)$ for the initialisation¹ and then $O(\log n)$ time for each iteration of the `while` loop plus whatever `trigger` does.

In practice, be mindful of overflows.

You can not be asymoptotically faster than that; otherwise we could sort² in time $o(n \log n)$ which is not possible (for unrestricted inputs).

---

1. Can be sped up to $O(n)$; see e.g. here.
2. Add one event per element with its value as time interval. Drop the re-adding from the algorithm and execute $n$ iterations of the `while`-loop. Trigger just prints the element.

---
Tags: algorithms
---


title: Are these two algorithms the same?

text:
# Question
Title: Are these two algorithms the same?
An algorithm is a finite sequence of operations on an abstract machine. (Correct me, if I am not correct).

If two algorithms can take the same set of inputs, and for each input, they generates the same sequence of intermediate and final results/output, are they the same algorithm?

What I am thinking is if an algorithm can be thought of just as a mapping from the set of inputs to the set of sequences of intermediate and final results/output.

Thanks.

# Answer
Starting with a vague definition of algorithm, you won't get a clear-cut answer. Here are two possible ways to look at it.

* **Algorithms are high-level constructs**, that is we distinguish idea from implementation. In that sense,

```
for ( i=1; i<n; i++ ) {
  print i
}

```

and

```
i = 1
while ( i < n ) {
  print i
  i++
}

```

are *implementations of the same algorithm*, but clearly not the same program. And while this simple example may actually translate to the same machine code for many real languages, it's clear that they don't *have* to. So whether the programs create the same sequence of states depends on your machine model.

This is a hint that tying your notion of algorithm to a specific machine model is probably not useful.
* **Algorithms are specific sequences of instructions for fixed machine models**. Then, the answer depends on your machine model.

1. If there is exactly one statement for every possible state change, then a sequence of states induces a unique sequence of statements. Hence, if all inputs cause identical state sequences, the algorithms/programs are the same.
    2. If multiple statements can cause the same state change, then the opposite is true.
> 2 votes

---
Tags: algorithms, terminology
---


# Question
Title: Minimal length of a string that contains two strings
We have two strings $a,b$. I want to find string $c$ that includes $a$ as a subsequence and includes $b$ as a subsequence and the length of $c$ is minimal. Is there an efficient algorithm for this problem?

For example, if $a=1011$ and $b=0100$, the minimal string that include both: $c=101100$. As you can see string $c$ includes both $a$ and $b$ (with the characters of $a$ appearing in the same order in $c$, possibly with other characters interspersed, and the same for $b$).

I think it can be solved by a dynamic programming algorithm.

# Answer
> 3 votes
Following the explanation on Wikipedia,

Note that the result of neither step is necessarily unique.

Writing actual (pseudo)code, correctness proof and runtime analysis are easy exercises.

# Answer
> 1 votes
Hint: assume $a$ starts with a 1st letter $x$, hence is some $xa'$. Similarly, assume $b$ is some $yb'$.

Now what is the shortest word that contains $a$ and $b$ when $x=y$ (when $a$ and $b$ start with the same char)? And what if $x\not=y$? Finally, what if $a$ is the empty word $\epsilon$? Or if $b$ is $\epsilon$?

Solving all these cases will lead you to a dynamic programming solution.

PS: what you call "a string $s$ that includes all characters of $a$" is formally called a supersequence. Write it $a\leq s$. In particular, the *number of occurrences* of the symbols in $a$ and *their left-to-right order* must be accounted for in $s$ but not necessarily at contiguous positions.

---
Tags: algorithms, optimization, dynamic-programming, strings
---


# Question
Title: Construct Turing Machine which accepts the language $ww$
I try to construct a TM that accepts the language $\\{ ww \mid w \in \\{a,b\\}^\* \\}$.

Between the words $w$ is no delimeter, so I don't know, how my TM can know where the first $w$ ends and the second $w$ begins.

Is there a trick for this?

# Answer
Here is a sketch for how a deterministic machine might work:

1. place a marker in front of the input.
2. go through the input, checking if the length is even. If not, reject.
3. place a marker behind the input.
4. going back and forth, move the markers towards each other until they meet in the middle.
5. as long as the halves are nonempty, compare and erase their first letters and reject if not equal.
6. accept.
> 5 votes

# Answer
One way I have read of is to first check the length of the string, and if it is odd, reject the string.

Then We could put some special character (e.g. `c`) at the end of the entire string and copy the entire string to the other side of the special character and then apply the algorithm for checking $a^nb^n$.

I also found another method explained as a pseudo code in this pdf, which changes the first half of the string to some other substitute variables and then compares them.
> 1 votes

# Answer
An important thing to recognize is that you are only concerned with deciding if your input $x$ can be written as $ww$. That is, you want if decide $\exists w (x=ww)$.

There are many ways you can go about this, and honestly, there is even a large variety of easy ways to go about it. If you just have to describe the Turing machine in words (like, you don't have to construct a detailed diagram), then pretty much any of them would be sufficient. If you have to draw a diagram, here are some things you might want to consider:

If you are allowed to use nondeterminism, as was commented, you should take advantage of this. You can nondeterministically guess where there half-way point of your input is, and then check to see if the first segment matches the second segment. Likewise, you can always just guess what $w$ is and then check to see that your input tape looks like $ww$.

If you can't use nondeterminism, you can always emulate it by trying all possible middle points or writing down all possible $w$'s, stopping at a provably reasonable time, of course. You can, as a previous answer mentions, count the length of your input $x$, then use that to compute the middle point.

Some other considerations that are typical when one is a assigned problems like these deals with how many tapes your machine has. If you Turing machine only has one tape, guessing $w$ might be foolish, and you would be much better off guessing or finding the middle.

I hope this is sufficient. The tricky thing about this kind of question is, either you don't have to fully describe the Turing machine, in which case, there are lots of nice and short answers, or you do have to fully describe the Turing machine, in which case, you will have to do a nice little bit of work to convert one of these short descriptions into a diagram.
> 1 votes

---
Tags: formal-languages, turing-machines, automata
---


# Question
Title: What is the difference between cyber security ontologies and scenario ontologies in this system?
I have been reading the paper Towards a Cognitive System for Decision Support in Cyber Operations. And I have been trying to understand the role of two ontologies proposed here, **cyber security ontologies** and **scenario ontologies**.

I have asked a question on CGS SE, What are the practical uses of ontologies? and the role of the **ACT-R** architecture in this system have become clear to some extent, but the question about the ontologies is that:

Does the cyber security ontologies make the ideas in the TENA's Repo understandable for ACT-R or the ideas that are in the repo has to be represented by an ontology called **cyber security ontologies** in order to be understandable for the **ACT-R** architecture?

**The Cognitive System realized in the TENA framework:**

Questions raising from this Figure can be:

1. What is the difference between the **cyber security ontologies** and the **scenario ontologies**?
2. What kind of knowledge the **scenario ontologies** represent?
3. And of course what is the reason that the scenario ontologies are connected to **Event data management** module instead of TENA's Repo?

**ACT-R Architecture:**

**TENA Architecture:**

# Answer
> 1 votes
Some more detail can be found p97. Here "ontologies" are basically encodings of database contents (which represent cyber attacks, incidents, and malicious/ impacted software programs) parseable by external sources, e.g. ACT-R. The event data management system keeps track of (real) attacks/ incidents, or possibly simulated ones. TENA is a Testing and Training Enabling Architecture. In a sense the Cyber Security Ontologies are all the "Nouns", and the Scenario Ontologies are "Verbs" that operate on the Nouns. ACT-R takes these inputs and attempts to create a conceptual linking or model. In a sense the ACT-R is a machine learning system for cyber-attack-related events and entities. It is a framework for outputting a (maybe statistical) analysis that could be used to predict future attacks from the structure of past ones.

> The need for controlled vocabularies, taxonomies, and ontologies to make progress toward a science of cyber security is recognized in \[26\] and \[27\] as well. In the domain of cyber security, the ontologies would include, among other things, the classification of cyber attacks, cyber incidents, and malicious and impacted software programs. From our point of view, which seeks to accurately represent the human-side of cyber security, we also expand our analysis to: (i) the different roles that system users, defenders and policy makers play in the context of cyber security; (ii) the different jobs and functions that the members of cyber defender team play and the knowledge, skills and abilities needed to fulfill these functions. In order to reduce the level of effort, we will reuse existing ontologies when possible6 and only create new ontologies that support the use cases we select.

---
Tags: terminology, knowledge-representation, ontologies
---


# Question
Title: Necessities for two undirected graphs being isomorphic
As far as I know, for two undirected graphs $G = (V, E) $ and $H = (V', E')$, the following criteria is necessary for them to be isomorphic:

1. $|V| = |V'|$
2. $|E| = |E'|$
3. $G$ has $j$ nodes of degree $k$ $\Leftrightarrow $ $H$ has $j$ nodes of degree $k$

Are there more that are that obvious? Thanks in advance for your help!

# Answer
For two graphs $G$ and $H$ it is necessary for literally *every* property that holds of $G$ to also hold of $H$ and vice-versa. There's no point making a list because everything is in that list.
> 1 votes

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


title: RAW Data Hazard resolution

text:
# Question
Title: RAW Data Hazard resolution
Let's consider the following MIPS (using pipelined arch.) assembly code:

```
lw r1,0(r2)
sub r4, r1, r6
and r6, r1, r7
or r8, r1, r9

```

the r1 value used in the second and third instruction will not be ready to use until the end of the 4th cycle of the pipeline, while the 2nd and the 3rd instruction need it at the 4th and 5th cycle respectively, i think for the 3rd instruction the problem can be resolved using bypass but for the 2nd instruction i am not sure ?? can anyone tell me how to avoid the RAW data hazard in this case ??

# Answer
It depends on the context. From a computer architecture perspective, you can insert a hazard detection unit that inserts a bubble in the pipeline when it detects this condition. It's shown top/left-ish in this picture from Patterson&Hennessy:

The logic doesn't do anything unexpected, it detects the case that an instruction in the ID wants to read a register that a memory read in the EX stage will write to, the instruction from the ID stage is then killed and PC is "held" so the instruction will re-execute.

From a programmer perspective, suppose there is no hazard detection unit, just insert the NOP yourself.
> 0 votes

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


# Question
Title: Is the set of all strings over a finite alphabet finite?
Suppose $Σ=\\{0,1\\}$; then $Σ^\*$ is the set of all strings over $Σ$.

Is $Σ^\*$ over $Σ$ finte?

# Answer
> 2 votes
The star operator is a unary operator known as Kleene star (or Kleene closure) and the result of its application on $\Sigma$ (an arbitrary set of strings) is another set that contains all possible finite strings constructed using only strings from $\Sigma$.

Assuming that the set contains at least one non-empty string, the cardinality of the set produced by the Kleene star operator is infinite since we can always generate a new unique string by appending one of the non-empty strings.

---
Tags: formal-languages, word-combinatorics, kleene-star
---


# Question
Title: Prove that $S_2$ is closed under union and complement
I'm having trouble proving that $S\_2$ is closed under union and complement, even though in this Wikipedia article it says that:

> It is immediate from the definition that $S\_2$ is closed under union and complement.

I think that my problem is due to the fact that $S\_2$ is defined slightly differently in my assignment. Here's the definition I must work with:

> $S\_2$ is the complexity class of all languages $L$ for which there exists a polynomial bound verifier $V$ and a polynomial $p$ such that for all $x \in \\{0,1\\}^\*$:
>
> $x \in L \Rightarrow \exists y \in \\{0,1\\}^{p(|x|)} \forall z \in \\{0,1\\}^{p(|x|)} : V(x,y,z)=1$ $x \notin L \Rightarrow \exists z \in \\{0,1\\}^{p(|x|)} \forall y \in \\{0,1\\}^{p(|x|)} : V(x,y,z)=0$

Let's look first at union. Let $A,B \in S\_2$. I thought of defining a new verifier $V\_{A \cup B} = V\_A \lor V\_B$ which should return a correct answer. However, my problem is defining the new polynomial $p$. Let's say that the polynomials that exist for languages $A,B$ are $p\_A,p\_B$ and that $p\_A \< p\_B$. Now let's look at some $x \in A \cup B$.

The problem is that if $x \in A$ all I know is that there exists a $y$ s.t. $|y|=p\_A(|x|)$ and that if $x \in B$ there exists a $y$ s.t. $|y|=p\_B(|x|)$. But how do I define a polynomial $q$ such that I can be sure that there exists a $y$ s.t. $|y|=q(|x|)$ for any general $x$?

As for the closure under complement, if $A \in S\_2$, all I know is that if $x \in \overline A$, then $x \notin A$, therefore $\exists z \in \\{0,1\\}^{p(|x|)} \forall y \in \\{0,1\\}^{p(|x|)} : V(x,y,z)=0$. However I do not see how we use this in order to conclude that $\exists y \in \\{0,1\\}^{p(|x|)} \forall z \in \\{0,1\\}^{p(|x|)} : V(x,y,z)=1$.

# Answer
> 3 votes
As you mention in your post, you can define a new verifier $V=V\_A \vee V\_B$ however, you missed the point that the input of $V$ need not be the input of $V\_A$ or $V\_B$: **it can be the concatenation of their inputs**

So the new $V$ can be written as $$ V(x, y\_A\circ y\_B, z\_A \circ z\_B )$$ where it "runs" $V\_A(x,y\_A,z\_A)$ and $V\_A(x,y\_B,z\_B)$ and decides accordingly.

It then immediately follows that $q = p\_a +p\_b +1$ (the +1 is just to separate the prefix from the suffix, you can ignore it).

---
Tags: complexity-theory, closure-properties, complexity-classes
---


title: MU0 instruction set

text:
# Question
Title: MU0 instruction set
As i know the MU0 processor instruction format is as follows:

so the opcode is 4 bit, can anyone explain why it has only 8 instructions, if it could have 16 instructions, 2^4 = 16 ??

# Answer
The mu0 microprocessor was designed for teaching purposes. As such, it was deliberately designed to be extremely simple. Having a simple instruction set is a benefit for teaching: it enables you to focus on core concepts, without being distracted by unnecessary complexity. Thus, presumably the designers of the mu0 designed their instruction set to have as few as instructions as possible, given their teaching goals. In this case, it doesn't need more than those 8 instructions; those are more than enough to illustrate the primary concepts.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Chomsky Normal Form-remove unit production
In the step of removing unit productions when converting a grammar to Chomsky normal form, I sometimes found that the variables may end up having the same production bodies. Is this possible? If so, can we consider these variables identical? For example, given:

```
S->aAA|aA|A|a
A->bBBB|bBB|bB|B|b
B->bSSS|bSS|bS|S|b

```

So

```
S-derivable set is {A, B}
A-derivable set is {B, S}
B-derivable set is {S, A}

```

If I add all the non-unit productions from A and B to S, and from B and S to A, and from S and A to B, then the resulting new productions of S, A and B will have exactly the same production bodies.

```
S->aAA|aA|A|bBBB|bBB|bB|bSSS|bSS|bS|a|b
A->same as above
B->same as above

```

Is this correct??

# Answer
Yes it is correct. This happened because in your original grammar the non-terminal symbols formed a cycle with the following productions: $$S\to A$$ $$A\to B$$ $$B\to S$$

So by transitivity all non-terminals can produce the same things.
> 1 votes

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


title: How to get samples of different paths?

text:
# Question
Title: How to get samples of different paths?
Say I have a "semi" directed, weighted, graph (some edges are undirected, some are directed).

Consider two nodes, A and B. Consider the set of all paths that take me from node A to node B.

I essentially want X samples of all these paths. I don't want these samples to be "too close" to the ideal path. Essentially, I want them relatively spread out over the space of solutions. I do want to include cyclic paths, which I know makes the set of possible paths infinite. Therefore, I want the paths to be relatively close to the ideal path, but still not too close. This is obviously a very vague, non-rigourous description of this aspect of the problem, which is why if possible, I would like to be able to specify some parameter that lets me control how close to the ideal my samples are.

These are the solutions I have thought of so far:

1) Use some kind of algorithm that gives me the X shortest paths. The problem with this is the samples are all too similar to the ideal path in terms of length.

2) Do the following:

```
     a) Run A*/Dijikstra's to find the ideal path.
     b) Remove X% of the edges that form the ideal path.
     c) Run A*/Dijistra's again to find the second sample. The fact that a portion of the edges have been removed from the ideal path, should mean that this second sample should be quite different.
     d) Remove X% of the edges that form the second sample.
     e) Repeat.

```

The problem with this is that I'm worried that for a large number of samples (10000+), a very large number of edges will be removed, making the samples taken later on to be very different from the ideal path.

Does anyone have any ideas on how to better approach the problem?

The graph is quite big (100000+ nodes and edges). The algorithm's speed and performance is very important, however I can do a very large amount of preprocessing beforehand, if necessary.

# Answer
I can think of two approaches. Each generates a *single* sample at a time; any modifications to the graph are undone before generating the next sample.

1. Compute the shortest path, then remove `r` of the edges you take and generate the next-shorted path. This can be used to generate `nCr` samples, though many will coincide. For better quality, you probably want to also apply this to its own output: find the initial shortest path, remove 2 edges, find the intermediate shortest path, remove 2 edges, find the final shortest path. For a reasonably large graph, I would just calculate the edge(s) to remove at random in each step. Variant: instead of removing a single edge, remove both that edge and all other edges that go in/out of either vertex (I would consider the graph undirected for this step).
2. Randomize the weights as you pass them to A\*. That is, when you advance from one node to the next, multiply that edge's weight by a number between 0.9 and 1.1 (probably with a Gaussian distribution actually). On rare occasions this might generate loops, especially if you widen the random range.
> 1 votes

---
Tags: algorithms, graphs, enumeration, sampling
---