title: Space complexity of Horner's method

text:
# Question
Title: Space complexity of Horner's method
Following is the excerpt from wiki

> If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately $2n$ times the number of bits of $x$ (the evaluated polynomial has approximate magnitude $x^n$, and one must also store $x^n$ itself). By contrast, Horner's method requires only $n$ additions and $n$ multiplications, and its storage requirements are only $n$ times the number of bits of $x$.

I don't understand, how?

# Answer
Storing the output requires roughly $n|x|$ bits (where $|x|$ is the size of $x$ in bits); this is since the numbers involved have magnitude $\Theta(x^n)$. This is all that Horner's method requires, since it only keeps track of one value, the current "partial sum".

In contrast, the naive method keeps track of *two* values: the current partial sum, and also the current power of $x$. Each of these requires (towards the end of the process) roughly $n|x|$ bits to store, and both of them require $2n|x|$ bits in total.
> 2 votes

---
Tags: algorithm-analysis, space-complexity
---


title: Right linear grammar special case

text:
# Question
Title: Right linear grammar special case
According to the definition, the productions of a right linear grammar should have the form of $A\to xB$ or $A\to x$, does $A\to B$ or $A\to xy$ count as productions of a right linear grammar? $A\to B$ can be written as $A\to \epsilon B$ though...

# Answer
In your definition, $x$ must be a terminal symbol. In particular, it cannot be $\epsilon$, which is the empty string. The productions $A \to B$ and $A \to xy$ don't conform to the specifications you give, hence they don't belong in a right linear grammar according to the definition you provide.
> 1 votes

---
Tags: regular-languages, formal-grammars
---


title: compressed information = randomness?

text:
# Question
Title: compressed information = randomness?
Suppose I have a compressed file and it is not possible to compress it more without loss of information. We say that this file is random or pseudorandom.

So, if the randomness means not comprehensible and not compressible, I don't understand why ths file is, at the same time, information that my computer and I can understand.

This file could be a book that my computer can show to me and read, and I can read and sum it ...so, it is really randomness?

Note: I understand that if I can make a summary of a text or define it with less words, that not means that it could be possible to get all the information of this book again, of course but this book is not random for me.

Note II: I undesrtand ramdoness as something that is not possible to reproduce with an smaller algorithm. I mean a string is random when I can't find an other smaller string that is an algorithm that can reproduce the first one.

Note III: I want to thank you all for your help.

# Answer
okay, what you are talking about can be explained using the concept of Kolmogorov Complexity.

Let's understand the Kolomogorov complexity and randomness.

Suppose you have a string $A = HHHHH$ and $B = TTHTH$, now intuitively it seems $B$ has more randomness than $A$, however, statistically, both strings have an equal probability of being chosen. This troubled researchers for sometime untill Kolmogorov and Chaitin (independently) came up with a notion of randomness.

A string is said to be random if it cannot be compressed, that is it has no 'structure' in it. Formally, for any *word* $x \in (\Sigma\_{bool})^\*$, the Kolmogorov Complexity $K(x)$ of the word is the binary length of the shortest program generating it.

A word is said to be random if it is not compressible. i.e. $K(w\_n) \geq |w\_n| + c$

If you want to look up more on this, you can start with this wonderful survey note by Lance Fortnow

---

Now, as I understand your question, you are asking how is an a word that is incompressible be 'information' while we use the same notion for randomness.

So, this is a bit philosophical... well, randomness is always philosophical! anyway, What we call/define to random is actually information without a structure. The outcome of an unbiased coin toss is also random, i.e. it should not have any structure to it, and one should never be able to find any patterns or periodic repetitions in the string.

*Information* is basically a numerical measure of the uncertainty of an experimental outcome.

Now, let's use the K-Complexity... suppose we start writing down the outcomes of a coin toss. Now without the *information* you basically do not have an metric to evaluate randomness of the string. The randomness is more of a property associated with information. You can probably associate a certain degree of randomness to anything that's based on experiments.

The K-complexity is just a measure of randomness in information. For an completely 'random' string, the $K(w\_n) = |w\_n| + c$ and for a completely 'non-random' string, the $K(w\_n) = \delta + c$ where $\delta$ is some small quantity.
> 8 votes

# Answer
This question starts from faulty premises. Just because a particular file is not compressible does not mean it was necessarily generated randomly or pseudorandomly. Randomness is a property of the *source* where the data came from, not a property of the data itself (not a property of a single value emitted by that source). See, for instance, https://xkcd.com/221/ and http://dilbert.com/strips/comic/2001-10-25/ :

It doesn't make sense to say "a file is random"; sometimes if we're sloppy, we might say something like that, but everyone understands that what we really mean is "the file was generated by a source that is random". Randomness is a property of the source.

In comparison, compressibility is a property of the *data*, not the source. We can test whether a particular file is compressible by gzip by, well, running gzip and seeing if the compressed result is smaller than the original file.

Therefore, a statement like "if a file is not compressible, then it is random" represents a confusion. It confuses the difference between the source and an observation of a value from that source.

We could try to correct the statement to remove this confusion, to get something like "if a file is not compressible, then it was not produced by a random source" -- but that corrected version is simply false. It is not accurate. It is possible for a random source to produce an output that can be compressed by gzip (as illustrated by the Dilbert comic above). There is a result in information theory which guarantees that, *on average*, this doesn't happen -- but that's a very different statement. And if you make a correct statement of the true result, you'll find that your reasoning falls apart in the first or second sentence of your question.

Given a question that starts from faulty premises, the best answer is "mu", i.e., "un-ask the question" and ask a different one. My advice would be to start by studying the definition of randomness, the known links between randomness and compressibility, and then that might help you formulate your question a little more precisely (or might help you understand the relationship between these concepts).
> 2 votes

# Answer
The relationship between randomness and compressibility only exists when we talk about the source, or the hypothetically infinite string of outputs from the source. For instance, we know that a source that outputs either 0 or 1 with equal probability is random and that the stream it produces is "incompressible" (in the sense that, for any fixed compression algorithm, in the limit as the length of the stream goes to infinity, the stream cannot be compressed by that compression algorithm: the average compression ratio is $\le 1$).

Any finite string can be compressed down to nothing, if you let me pick a suitable compression algorithm; i.e., for any finite string $y$, there is a pair of algorithms $c$ and $d$ which compress the string to nothing, and decompress nothing to the string. These algorithms are easy: $c(y) = \epsilon$ and $c(x) = 0x$ for all $x \neq y$, whereas $d(\epsilon) = y$ and $d(0x) = x$. The compression ratio is bad for most strings, but you've just compressed any finite string -- including one generated by a random source -- down to nothing.

You can talk about compressibility for *specific* compression and decompression algorithms in the context of random finite strings, but not about limits of compressibility in general terms.

Another way to understand this is that there's no such thing as a random finite string.

As for how this addresses the question:

> Suppose I have a compressed file and it is not possible to compress it more without loss of information.

I demonstrate that this cannot hold for a finite string.

> We say that this file is random or pseudorandom.

Then we conclude that such a thing does not exist.

> So, if the randomness means not comprehensible and not compressible,

For producers and the potentially infinite streams they produce, I'd grant that this is a reasonable interpretation

> I don't understand why this file is, at the same time, information that my computer and I can understand.

Because the file isn't a potentially infinite random stream, and represents a discreet entity which still contains plenty of information.

> This file could be a book that my computer can show to me and read, and I can read and sum it ...so, it is really randomness?

It is not, as outline above.

> Note: I understand that if I can make a summary of a text or define it with less words, that not means that it could be possible to get all the information of this book again, of course but this book is not random for me.

Neither is any string, since what (I think) you are describing is a valid way to interpret the result of applying a compression algorithm to any finite string: it's a digest, or summary, for which there is indeed some algorithm that will losslessly convert it back to its original form.
> 0 votes

# Answer
Part of the problem with this question is that it gets two different groups talking past each other. The core issue is: There are TWO distinct intuitive interpretations of 'random bit string':

STATISTICS: A bit-string is 'random' if it is generated by an independent sequence of fair coin flips (or similar such process).

INFORMATION: A bit-string is 'random' if it is non-redundant, i.e contains essentially no internal sub-structure.

It happens to be the case that most bit-strings which are 'statistics-random' are also 'information-random' *\[of course, one cannot even consider the converse unless one knows how the bit-string came to be\]*. The conflict of intuition occurs when trying to apply both intuitions simultaneously to certain bit-strings. Consider, for example, a sequence of one hundred consecutive ones - is this 'random'? You get two answers:

STATISTICS: If each one in the sequence was generated by a separate, independent flip of a fair coin - then yes, it is just as random as any other string of one hundred bits.

INFORMATION: Obviously a string of one hundred ones is almost entirely redundant, so no, it is not at all random.

It is simply the case that the usual human 'gut reaction' is that real coin flipping should never generate one hundred ones in a row. More generally, people have a tendency to conflate 'sufficiently improbable' with 'impossible'. This is an underlying reason why 'information random' theory exists.

To resolve the confusion in this case, I argue thus: The phrasing of the submitter's question indicates that it is based on 'information random'. Any responder who presumes 'random' only means 'statistics random' in order to explain why the submitter is confused, is misguided in this case. Please stop.
> 0 votes

---
Tags: information-theory, data-compression
---


# Question
Title: Compression functions are only practical because "The bit strings which occur in practice are far from random"?
I would have made a comment, as this pertains to Andrej Bauer's answer in this thread; however, I believe it is worth a question.

Andrej explains that given the set of all bit strings of length 3 or less, a lossless compression function can only "compress" some of them. The others, for instance "01" would have to actually be compressed to a string such as "0001", with length 4. The compression ratio is simply the average compression across the input set.

This makes lossless compression seem impractical, but the important quote is this:

> The bit strings which occur in practice are far from random and exhibit a lot of regularity.

I have a hard time believing that, for instance, multimedia files are represented by anything other than random bit strings. Is there truly a pattern that compression functions leverage to make the algorithm useful in reality?

# Answer
> 11 votes
First of all, you're right: Multimedia files are represented (more or less) as random files. The reason for that is that those files *are already compressed* (lossy). Note that mp3, for example, is nothing but a compression algorithm!
A consequence is that further compression will not yield any noticeable compression (and indeed, lossless compression on already compressed (multimedia) files has never been a road to success).

You're also right on your other point: Lossless compression cannot compress on the average. To see that, say, your possible data set consists of $2^n$ different elements. How many bits do you need per file to always be able to distinguish elements from your set? Right, $n$. In total all files will be represented by no less than $n \cdot 2^n$ bits. Now if you represent some of those files by less than $n$ bits, some files will be represented by more than $n$ bits. That's about all there is to say.

In short, lossless compression works because text files are far from random (just consider the letter distribution of my answer and compare the number of *e*'s with the number of *z*'s!), and compressing random data (e.g. already compressed data or encrypted data) does not make any sense.

# Answer
> 10 votes
Multimedia *data* is very far from random, which is why it compresses so well. For example, a single second of video at 1920x1080 pixel resolution, with 24-bit colour and 24 frames per second is about 150MB of data uncompressed. Multimedia *files* have already been compressed so are hard to compress any farther.

However, even uncompressed multimedia data will probably look pretty random if you just consider it as a stream of zeroes and ones. (Having said that, GIFs are compressed using LZW, treating them as, essentially a stream of bits; that works decently well.) When you look at multimedia data knowing what it means, there's a lot of structure in there.

* Images have a lot of colour gradients and blocks of similar colours. JPEG uses something a lot like this.
* In video, almost every frame looks very similar to the one immediately before it, with some parts moved a little. MPEG uses this extensively.
* A lot of the sounds we're interested in are waveforms from resonating objects, not random frequencies.

I've mentioned JPEG and MPEG which are, of course, lossy. But I suspect you could use these ideas, in principle, to produce good lossless compression ratios of this non-random data. I doubt anyone would try to do that, though, as the time taken to compress would probably be impossibly huge.

# Answer
> 4 votes
Yes, lossless compression takes advantage of the fact that many files are not random. Yes, most multimedia files are not random.

Fax images are a good example of this effect. In their simplest form, a fax image is a 2-D black-and-white image, obtained by scanning a single page of some document. If you represent this image as a sequence of bits, one bit per pixel (0 = white, 1 = black), then you will discover that the resulting binary data is not at all random. For instance, here are some non-random patterns you will spot:

* Typically fax images have a lot more white pixels than black pixels.
* Also, each pixel is more likely to have the same color as the pixel to its left than to have a different color.
* For a more sophisticated pattern: Imagine scanning pixels horizontally, left to right, and counting the length of each "run" of consecutive pixels with the same color. Then long runs are more common than short runs, and long runs of white pixels are more common than long runs of black pixels.

Fax compression algorithms were designed to take advantage of these non-random aspects. Early fax compression algorithms are a particularly good example, because they are simple lossless compression schemes that very directly exploit these non-random properties of scanned images.

For instance, one early scheme for compressing fax images used run-length encoding combined with Huffman encoding. Run-length encoding replaces each run of same-color pixels with a single integer counting the length of the run. For instance, 00000110001 becomes "5 2 3 1". Run-length encoding exploits the fact that pixels tend to come in runs of the same color. The Huffman encoding further exploits the fact that some run-lengths are more common than others. See here for a detailed example of how one of these early schemes worked -- the scheme is simple and elegant, and directly exploits the patterns mentioned above.

These schemes would not offer any compression, on average, for random files. However, scanned fax images are not random, and as a result these compression schemes can offer substantial savings.

Similar comments apply to other multimedia files. The patterns present in other kinds of multimedia files can be more complex, but there are still many patterns present that make the data non-random.

# Answer
> 0 votes
A random audio file constitutes a kind of noise. Most people store audio files with music or speech, not noise.

---
Tags: information-theory, data-compression
---


title: Context free Grammar and regular set

text:
# Question
Title: Context free Grammar and regular set
I read a question and I don't understand it, is the set consisting of: production rules of Grammars that are CFGs, itself a regular set? The only thing I know is that the type 3 is under the type 2 in CNF.

# Answer
> 1 votes
A context-free grammar is just a string such as "$A\to 0A0\mid 1A1\mid 0\mid 1$". Forget for the moment that such a string happens to define a language (in this case, the set of all odd-length binary palindromes) and focus on the fact that it's a string over some alphabet.

Now, let $L$ be the set of strings that are regular grammars. A set of strings is a language. The question is asking if $L$ is a regular language.

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


title: Boolean function and real degree

text:
# Question
Title: Boolean function and real degree
Let $f$ be a boolean function with minimum degree real polynomial representing it be of degree $d$.

Is there a relation between number of zeros $f$ or $1-f$ and degree $d$?

# Answer
Exercise 12 (online version) in §1 of Ryan O'Donnell's *Analysis of Boolean functions* shows that all Fourier coefficients of a degree $d$ function are integer multiples of $2^{-d}$. In particular, the number of zeroes of $f$ is an integer multiple of $2^{n-d}$.

Moreover, for every integer $k \in \\{0,\ldots,2^d\\}$ there is a degree $d$ Boolean function having exactly $k2^{n-d}$ zeroes. This easily follows from the fact that a function on $d$ variables has degree at most $d$.
> 3 votes

---
Tags: complexity-theory, polynomials
---


# Question
Title: Compressing two integers disregarding order
Comparing an ordered pair (x,y) to an unordered pair {x, y} (set), then information theoretically, the difference is only one bit, as whether x comes first or y requires exactly a single bit to represent.

So, if we're given a set {x,y} where x,y are two different 32-bit integers, can we pack them into 63 bits (rather 64)? It should be possible to recover the original 32 bit integers from the 63 bit result, but without being able to recover their order.

# Answer
> 27 votes
Yes, one can. If $x\<y$, map the set $\\{x,y\\}$ to the number

$$f(x,y) = y(y-1)/2 + x.$$

It is easy to show that $f$ is bijective, and so this can be uniquely decoded. Also, when $0 \le x \< y \< 2^{32}$, we have $0 \le f(x,y) \< 2^{63} - 2^{31}$, so this maps the set $\\{x,y\\}$ to a 63-bit number $f(x,y)$. To decode, you can use binary search on $y$, or take a square root: $y$ should be approximately $\lfloor \sqrt{2 f(x,y)} \rfloor$.

# Answer
> 10 votes
As an addition to D.W.'s answer, note that this is a particular case of the Combinatorial Number System, which compactly maps a strictly decreasing sequence of $k$ non-negative integers $c\_k \> \cdots \> c\_1$ to $$ N = \sum\_{i=1}^k \binom{c\_i}{i}.$$

This number has a simple interpretation. If we order these sequences lexicographically, then $N$ counts the number of smaller sequences.

To decode, just assign $c\_k$ the largest value such that $\binom{c\_k}{k} \leq N$ and decode $N - \binom{c\_k}{k}$ as a $(k-1)$-sequence.

# Answer
> 4 votes
The total number of unordered pairs of numbers in a set of $N$ is $N(N+1)/2$. The total number of unordered pairs of *distinct* numbers is $N(N-1)/2$. It takes $2 \log\_2(N) = \log\_2(N^2)$ bits to represent an ordered pair of numbers, and if you have one less bit, you can represent elements of a space of up to $N^2/2$. The number of unordered not-necessarily-distinct pairs is slightly more than half the number of ordered pairs so you can't save a bit in the representation; the number of unordered distinct pairs is slightly less than half, so you can save a bit.

For a practical scheme that's easy to compute, with $N$ being a power of 2, you can work on the bitwise representation. Take $a = x \oplus y$ where $\oplus$ is the XOR (bitwise exclusive or) operator. The pair $\\{x,y\\}$ can be recovered from either $(a, x)$ or $(a, y)$. Now we'll look for a trick to save one bit in the second part, and give a symmetric role to $x$ and $y$ so that the order cannot be recovered. Given the cardinality computation above, we know this scheme will not work in the case where $x=y$.

If $x \ne y$ then there is some bit position where they differ. I'll write $x\_i$ for the $i$th bit of $x$ (i.e. $x = \sum\_i x\_i 2^i$), and likewise for $y$. Let $k$ take the smallest bit position where $x$ and $y$ differ: $k$ is the smallest $i$ such that $x\_i \ne y\_i$. $k$ is the smallest $i$ such that $a\_i = 1$: we can recover $k$ from $a$. Let $b$ be either $x$ or $y$ with the $k$th bit erased (i.e. $b = \sum\_{i\<k} x\_i 2^i + \sum\_{i\>k} x\_i 2^{i-1}$ or $b = \sum\_{i\<k} y\_i 2^i + \sum\_{i\>k} y\_i 2^{i-1}$) — to make the construction symmetric, pick $x$ if $x\_k=0$ and $y\_k=1$, and pick $y$ if $x\_k=1$ and $y\_k=0$. Use $(a,b)$ as the compact representation of the pair. The original pair can be recovered by computing the lowest-order bit that is set in $a$, inserting a 0 bit at this position in $b$ (yielding one of $x$ or $y$), and taking the xor of that number with $a$ (yielding the other element of the pair).

In this representation, $a$ can be any nonzero number, and $b$ can be any number with half the range. This is a sanity check: we get exactly the expected number of representations of unordered pairs.

In pseudocode, with `^`, `&`, `|`, `<<`, `>>`, `~` being C-like bitwise operators (xor, and, or, left-shift, right-shift, complement):

```
encode(x, y) =
  let a = x ^ y
  let k = lowest_set_bit_position(a)
  let low_mask = (1 << k) - 1
  let z = if x & (1 << k) = 0 then x else y
  return (a, (z & low_mask) | (z & ~low_mask) >> 1)
decode(a, b) =
  let k = lowest_set_bit_position(a)
  let low_mask = (1 << k) - 1
  let x = (b & low_mask) | ((b & ~low_mask) << 1)
  return (x, a ^ x)

```

# Answer
> 0 votes
A nonconstructive proof: there are $(2^{32}\times 2^{32} - 2^{32})/2 = 2^{31}(2^{32}-1)\<2^{63}$ unordered pairs of different 32-bit integers.

---
Tags: information-theory, data-compression
---


title: Known problems in BQP \ NP?

text:
# Question
Title: Known problems in BQP \ NP?
The introduction to Nielsen and Chuang has an Euler diagram of the suspected relationships between various complexity classes which shows $\text{BQP}$ extending slightly outside of $\text{NP}$. Is $\text{BQP} \not\subset \text{NP}$? Are there any specific problems known or suspected to be in $\text{BQP}$ but outside of $\text{NP}$? If so, what's the simplest known example?

# Answer
> 9 votes
If there was a problem known to be in $\text{BQP}$ but not $\text{NP}$, that would prove $\text{BQP} \not\subset \text{P}$. But $\text{BQP}$ vs $\text P$ is *also* still an open problem.

It is *suspected* that $\text{BQP} \not\subset \text{NP}$. In fact it's suspected that $\text{BQP} \not\subset \text{PH}$ via the "Recursive Fourier Sampling" problem. But proving separations between complexity classes is surprisingly hard. I don't think anyone's even managed to show that $\text{BQP} \not\subset$ $\text{LSPACE}$.

---
Tags: complexity-theory, complexity-classes, np, quantum-computing
---


title: CFL that runs in NP-time

text:
# Question
Title: CFL that runs in NP-time
What is an example of a context-free language that runs in NP-time? I've done searches but cant find one. Frankly, I do not know how to determine when a CFL is P or NP. Can someone tell me, please?

# Answer
All context free languages can be recognized in polynomial time:

https://en.m.wikipedia.org/wiki/CYK\_algorithm
> 3 votes

---
Tags: formal-languages, runtime-analysis, np
---


# Question
Title: How to calculate an accurate estimated reading time of text?
I suppose the calculation should not be done by only two factors (average reading speed/words per minute, and word count). But at least by a third parameter, that in my opinion should measure the difficulty of the used vocabulary with some kind of text analysis.

I suppose it would be something like this:

```
totalWordCount / (avgReadTimePerWord * textDifficulty)

```

Also I read somewhere that the average reading speed is 120 words per minute. But I have some questions regarding that:

1. Are people known wich existing algorithms that are capable of doing such accurate calculations considering those factors?
2. Is the average reading time equal in all languages and if not, how to add language as a factor also? What study shows average reading times per language?
3. Is it possible to add age as a factor? Or are there known studies on those factors?
4. If someone has dyslexia. Is their some research that suggest for example they take 30% longer to read? And can we just increase it by 30% in such case or are there other factors in such case?

Goal is to implement this as a function in a programming language like Python or PHP and to use the (personalised) result for creating an output like "this article can be read in approximately 12-14 minutes".

It would be nice if such information is publicly available.

# Answer
There is a similar question, so I will add a bit over the answer.

There are too many factors independent of language but solely based on individual reading abilities that such estimate would not be possible.
I assume perfect text without spelling errors and unclear grammar.

Giving it a try:
People can read 20, 50, 200, 2000... pages per hour, it depends on reading skills - only prescreening test will give you answer to that: give 2 pages, measure time, or use eye tracker and do the same.

This depends on language used, but the reading speed is measured in native language, so the differences are in the next point as for language (or decrease the speed for non-native by... proficiency at that language).

People use Cohorts imagine that the dictionary forms trie, and the speed of recognizing given word depends on amount of words with the same prefix.
*Cognitive Psychology: A Student's Handbook, fifth edition* by Michael W. Eysenck,Mark T. Keane, page 347.

For example: "Av..." What are possible words?
Average, Avalanche... Avengers if someone seen the movie, comics or ads.
"Ave.." - word on it's own, Average fits, Avengers also.
If person reads about statistics, "average" is already good choice, about Roman Empire - Ave it is, about movies played - Avengers.
But reading continues to the next syllabe.

It depends on mood, recent readings, coherence of text, familiarity with topic, recent topics seen (not only read).

About topic: reading novel is faster than technical text. Technical text for someone proficient will not decrease reading speed.
So the task given is important, if someone is checked for understanding text, reading speed decreases.

The language itself is not a factor, you should not take mean reading speed but median of your target group.
Yes age is factor, but not that usable as it gives fraction of other factors.

With dyslexia the decrease also vary per person, $30%$ decrease is very optimistic case.

*Theory and Research in Learning Disabilities* by J.P. Das, R.F. Mulcahy and A.E. Wall, page 179.

I would take into account understanding of text, with dyslexia simple, short statements are easier to cope than longer sentences.

In any case taking syllabes count, average sentence length, topic, statistical occurence of word in e.g. books, magazines, movies, spoken language, difficulty of text (taken as topic and uncommon words).

There are a lot more factors, but giving the general idea that it is not sufficient to just calculate it from text is presented.

The best estimate for personalised result - measure per person and store the result, honestly the best you can do.

You can try *The Psychology of Reading* by K. Rayner and A. Pollatsek.
> 2 votes

---
Tags: algorithms, natural-language-processing, counting, mathematical-analysis
---


# Question
Title: What are the most expressive, terminating languages?
I'm less interested in languages where you can write almost anything, but then are required to write an accompanying proof that what you wrote terminates.

I'm more interested in the design space of languages inherently confined to certain complexity classes by construction.

Is there any sort of theory hierarchy for sub-turing-complete languages?

# Answer
> 7 votes
There are plenty of classes of programming languages where all programs terminate. The most common form of enforcing termination is by way of types. The most well-developed theory of typing systems for terminating computation might be that of Barendregt's Lambda cube, which decomposes typing into three orthogonal axes:

Starting from a terminating languages such as the simply typed $\lambda$-calculus, one can add any combination of those three axes and retain termination.

This has close connections with logic, via the Curry-Howard correspondence.

There are many extensions and refinements, including types that capture complexity classes.

# Answer
> 5 votes
Following Bellantoni & Cook's foundational work in *A New Recursion-Theoretic Characterization of Polytime Functions*, there's been a lot of work on simple characterizations of complexity classes by means of total languages, with strong connections to linear logic as Martin Berger notes in the comments.

Building on this work, other complexity classes have been characterized: Leivant and Marion have given characterizations of PSPACE and ELEM (that last one is particularly nice).

There's also been work on LOGSPACE, again with Leivant and Ramyaa.

It's a pretty exciting field, with a yearly conference!

---
Tags: programming-languages, termination
---


# Question
Title: How to read out a double negation in propositional logic
How would one verbally say ~~R where R = my program is correct? The tildes are negation symbols. I'm not sure if it just cancels out and comes out as 'my program is correct' or if it's something else.

Thank you!

# Answer
> 13 votes
One way to pronounce "~" is as "not", so one could pronounce that as "not not R".

But frankly, pronouncing complex logic formulas can be ugly, and often it's better to just write it on a whiteboard or piece of paper and point.

Yes, ~~R is equivalent to R.

# Answer
> 22 votes
The answer by @D.W. is valid in classical logic, however if you are on the intuitionistic side, then you can't eliminate double negation (~~).

I'd read the formula as 'It is *not* true that my program is *not* correct'.

---
Tags: logic, propositional-logic
---


# Question
Title: Can an (extended) regular grammar have multiple nonterminals in its RHS?
Standard (right) regular grammars have three kinds of rules:

```
A <- ""
A <- "a"
A <- "a" B

```

This is OK for a theoretical point of view, but a big inconvenience to be usable in practice. A practical regular grammar should allow us to use commodity operators (`|`,`*`,`+`,`?`,`.`,`(`,`)`), character sets and group multiple rules in a single one. For example, the following regular grammar describes fractional numbers:

```
start <- digit+ dot digit* | digit* dot digit+
digit <- [0-9]
dot   <- '.'

```

The question is, what restrictions must be applied to RHS non-terminals to keep this grammars regular (if it is possible at all)?

**NOTE**

Q - *Why regular grammars instead of regular expressions?*

A - Regular expressions are OK for simple languages, but they are write-only for more complex ones. On the other hand, well written extended regular grammars are allot more readable and maintainable and allows us to extend them with captures and rule actions easily.

# Answer
Right regular grammars are very similar to NFAs. In fact, if we modify them slightly by forbidding productions of the form $A \to a$ but allowing ones of the form $A \to \epsilon$, they are completely equivalent to NFAs. As such, it's natural to allow rules of the form $A \to r B$, where $r$ is an arbitrary *regular expression*.

If we want to stay within the realm of grammars, we can allow instead (or additionally) rules of the form $A \to S'B$, where $S'$ is the starting symbol of a (nonterminal-)disjoint regular grammar (more generally, the regular grammars involved must form a DAG).
> 2 votes

---
Tags: regular-languages, formal-grammars, regular-expressions
---


# Question
Title: NP problems with exponentially complex average time solution?
Assuming $P \ne NP$, is there a problem such that is NP such that:

* There is always a solution
* On average, it takes exponential time to solve
* The probability distribution can be any distribution which can be sampled from in polynomial time.

Also, what would such a complexity class be called?

# Answer
We don't know. It's possible that $P \ne NP$ but still all problems can be solved in subexponential time, as Yuval states. The Exponential Time Hypothesis is a conjecture that a certain problem requires exponential time to solve, but it's a conjecture -- there's debate among researchers about whether we should expect it to hold or not.

Assuming the ETH, you can find problems that meet your requirements, at least for worst-case hardness: there is asymptotically almost surely a solution, and any deterministic algorithm must have worst-case running time that's exponential in the length of the input. In particular, ETH implies that every problem in the class SNP takes exponential time to solve. For instance, 3SAT would qualify.

It sounds like you really want average-case hardness. There are some natural candidate problems: 3SAT with an appropriate clause density would be one reasonable one.

You could also use cryptographic hardness assumptions from the crypto community, e.g., inverting $f(k) = AES\_k(0)$ probably takes exponential time yet is known to have a solution, as far as we can tell given our current state of knowledge. This gives you a problem with a concrete parameter size, but with standard techniques you can build something asymptotic if you prefer an asymptotic family of problems.
> 1 votes

# Answer
I'm not big on complexity classes and their definitions so this answer might not be correct. My suggestion is too long to fit in a comment, though.

Your description made me think about PPAD(-complete (?)) introduced by Papadimitriou.

The, as far as I'm aware, most associated problem with PPAD-complete is computing a mixed Nash equilibrium (NE) in two player games. Such NE is not efficiently computable and a problem instance can be generated in polynomial time.
> 0 votes

---
Tags: complexity-theory, np, randomness
---


# Question
Title: How do I stop "cheating" in reinforcement learning (MLP+Evo. Algorithm)?
I have a two hidden-layer MLP. I am trying to teach it classification of the sine function. For instance, if there is an \[x,y\] point above the sine function, the ANN should classify that point as a 1. Otherwise, it should be classified as a 0.

It should end up like this. Points above y=sin(x) should be blue. Points below should be red. The network is just outputting 1s or 0s, so we are plotting the point along with a binary value (0=red,1=blue).

Graphic done with Matplotlib.

I feedforwarded my ANN thousands of random points, calculated the error between desired and output, and used that as fitness for an evolutionary algorithm that would evolve the network weights. The lower the error, the more likely the weights would be bred and preserved for the next round.

Unfortunately, the algorithm found a way to "break" the network. It was able to minimize the error while outputting the wrong values. For instance, one network and weight iteration I evolved outputted 0 for all inputs I would give it, even though I got the error down to 0 when I evolved the weights. It's a beauty. The plot is below.

My Python code is pretty big, so I will spare how I wrote the MLP and show you just a few snippets of relevant code.

Here, we have lists of random points and are feeding them through the MLP. If it is trained properly, the error will be close to 0 because the MLP correctly classifies each point.

```
    i=0
    error = 0
    while i < 100:
        output1 = feedForward(neuralNet, [xValsAbove[i], yValsAbove[i]]) # feedforward a point that is above the sine function.
        output2 = feedForward(neuralNet, [xValsBelow[i], yValsBelow[i]]) # feedforward a point that is below the sine function.

        if output1 < 0.99:
            error += 1 - output1
        if output2 > 0.01:
            error += output2
        i+=1
    return error

```

So, let's start evolving. Generate a bunch of random weights. Feed them a few thousand random points each in a range of -50 to 50 on both axes. Select the ones with the lowest classification error. Continue. After 50 generations, my error is down to 2 or 3. Looks good. Let's feed it a bunch of test points and see how it did.

???

Can anyone help me here?

# Answer
You are minimizing the wrong loss function. In other words, you have picked a poor objective function.

Look up the standard objective functions that are used for training neural networks for boolean classification tasks: e.g., mean-squared error, or cross-entropy loss. This is covered in standard tutorials. They don't use the function you show. The function you picked looks... odd, so I suspect it is the source of your porblem.
> 1 votes

---
Tags: machine-learning, artificial-intelligence, evolutionary-computing
---


# Question
Title: How does Logical Block Addressing affect OS disk scheduling optimizations such as SCAN (Elevator Algorithm)?
If the OS is scanning from one edge of the disk to the other, doing so from behind the Logical Block Addressing (LBA) abstraction, although it may aim to service requests in an elevator-like way, what guarantee do we have that the physical mapping **correlates** to what we see as the OS?

i.e. Could it be that servicing requests in logical order would end up seeking to random physical sectors, or do logical addresses still approximately reflect physical locations?

# Answer
You are right, this could be a problem.

In older disks, the physical block number corresponds to the actual location of the block on the disk. So, that algorithm makes sense.

Newer disks do fancier stuff. They have firmware that might remap blocks around to different locations, so that the physical block number no longer corresponds to the actual location of the block on disk in all cases (two blocks with similar physical block number might be far apart in actuality). Because this can screw up OS scheduling algorithms, disk firmware generally tries to avoid this situation where possible, but it can happen.

It gets especially tricky with SSDs, which have very different performance properties than hard disks, but which must (for backwards compatibility) use an API originally designed for magnetic disks. So, modern SSD's do clever things to try to ensure that typical OS scheduling algorithms will still yield reasonable results, even though the physical block number doesn't necessarily correspond to the actual physical location of where the data is stored on the SSD.
> 1 votes

---
Tags: operating-systems, scheduling
---


# Question
Title: What ML methods exist to categorize signal from noise? Red noise? Spatially correlated noise?
Let's say we are given measurements of some sort.

In many cases, it is safe to assume that noise is white noise, serially uncorrelated, and zero mean with some finite variance.

But in other cases, "red noise" exists such that the noise is correlated in time. What does one do in this case? Perhaps a Gaussian Process could be used?

What methods exist to characterize spatially-correlated noise?

# Answer
The basic approach is to model the noise as an appropriate stochastic process (aka random process). There's an entire subfield of statistics that has studied different kinds of stochastic processes, and they each have different properties. It would be too much to try to summarize that entire subfield in a single answer here.
> 1 votes

---
Tags: machine-learning, statistics, bayesian-statistics
---


# Question
Title: Why Isn't This Outlier Score/Reconstruction Error Not Squared?
I was looking through a paper called "AI2 : Training a big data machine to defend", and saw this (http://people.csail.mit.edu/kalyan/AI2\_Paper.pdf)

$score(X\_{i}) = \sum\_{j=1}^{p} (|X\_{i} − R^{j}\_{i}|) × ev(j) $

Where $ev(j)$ is the percentage of variance.

I was wondering, why isn't the the term $(|X\_{i} − R^{j}\_{i}|)$ squared like other reconstruction error functions, or at least the ones I saw?

I believe the term $\sum\_{j=1}^{p} (|X\_{i} − R^{j}\_{i}|)$ is a mean absolute error and is used here because it is better than a mean square error because it is better for a time series and is more robust. If I am wrong, please correct me.

# Answer
there is a good explaination squarred vs flat.

But from the simple view squarred error aims at variance while flat at median.
Different outliers comes from both versions, this is task dependent - the choice has been made by authors.

In fact yes, it is called roboust (somehow missused term), but it is not "better" for time series, just gives better estimator for outliers in presented method, which from given equation uses neither mean error nor mean square error - it uses custom made estimator with variance calculated on it's own.
> 1 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: What is the difference between a R-tree and a BVH?
I've just read about R-Trees:

> The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R-tree is for rectangle.

This seems to be a Bounding Volume Hierarchy (BVH) with axis-aligned bounding boxes (AABBs):

> A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects are wrapped in bounding volumes that form the leaf nodes of the tree. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree.
>
> \[...\]
>
> One of the most commonly used bounding volumes is an axis-aligned minimum bounding box.

Both allow overlapping nodes.

I've learned about BVHs in a Computer Graphics lecture and about R-trees by a professor who is mainly working on databases. So it might be that different communities developed the same datastructure independently.

Is there any difference between R-Trees and BVHs?

# Answer
Note that we want to be able to retrieve, for any query range, the points that are inside, or sometimes the points that are closest to that query range. That's why a bounding-volume hierarchy is useful.

However, bounding-volume hierarchy is a very general notion. When designing a bounding-volume hierarchy data structure in practice, it is extremely important to decide **what kind of bounding volumes** to use. The bounding volume can be any geometric shape: circle, hexagon, square, trangle or rectangle. It is important to keep this bounding volume very simple (we want it to be easy to store, rather than a complicated geometrical shape) and easy to fit other objects in (we don't want to waste a lot of free space in the bounding volume, as it can cause exhaustive search.

Quote from \[1\],

> Below, I will first explain what a bounding-volume hierarchy is and how it is used. After that, I will explain what issues have to be addressed when designing a bounding-volume hierarchy. **I will then focus on a particular class of bounding volume hierarchies, namely R-trees**, and give an overview of our results on Rtrees.

R-tree is a class of BVH data structures that uses **rectangles** as **bounding-volume**. Rectangles are easy to store and they can cover other shapes easily. It is noted that R-tree is not the only class of BVH and there are other BVHs proposed using different shapes. Even among R-trees, there is a variety.

This data structure is important for different communities: computer graphics, computational geometry, database and others. All of them need to deal with situations where they need to query a set of geometrical objects (or vectors).

\[1\] Herman Johannes Haverkort, Results on geometric networks and data structures, 2004.
> 11 votes

---
Tags: data-structures, trees, databases, graphics
---


title: Perturbing trees

text:
# Question
Title: Perturbing trees
I have a collection of labelled directed trees, and from these input trees I would like to generate permuted trees that have the same node set but whose edges and labels have been permuted with some probability $p$, such that if $p=0$ the output trees are identical and if $p=1$ the trees are random. The string version of this would be that each character in the string is replaced with a random character with probability $p$. Is there an established algorithm for this task?

My current best effort is to traverse the nodes of the tree in either post order or reverse breadth-first order and for each node with probability $p$ find a new parent node for it, with the candidate set being the nodes that are not descendants of the node (they can't be the parent of the node as this would create a cycle), but I'm pretty sure both of these options are not the correct ones.

EDIT: More specifically, I would like the trees at $p=1$ to be drawn from the same distribution as if we draw a tree uniformly at random from the set of possible trees over the node set (I know this is problematic due to this number generally being bigger than the period of most random number generators, but let's leave that for now). My intuition here (which is likely overly simplistic, but might be useful) is that I'd like to create a kind of linear interpolation between the input tree and a tree drawn uniformly at random from the set of all possible trees over the node set. Of course, linear interpolation doesn't make an awful lot of sense between trees (as far as I can figure it out

The trees represent natural language syntactic analyses (dependency trees, for those familiar with NLP) where the nodes are the words of the sentence, and I am generating the perturbed trees as controlled simulations of errors made by human annotators when describing the syntactic structure of sentences to evaluate metrics for measuring annotator agreement. I know the permutation I have (post-order traversal, selecting a new parent uniformly at random from the set of non-descendants of the target) is wrong because if I assign new parents to every single node ($p = 1$) and create two trees, a bit more than 20% of nodes have matching heads whereas labels match lot of sense between trees (as far as I can figure it out, anyways), so the formulation as perturbation of the input tree has been more fruitful for me so far.

The trees represent natural language syntactic analyses (dependency trees, for those familiar with NLP) where the nodes are the words of the sentence, and I am generating the perturbed trees as controlled simulations of errors made by human annotators when describing the syntactic structure of sentences to evaluate metrics for measuring annotator agreement. I know the permutation I have (post-order traversal, selecting a new parent uniformly at random from the set of non-descendants of the target) is wrong because if I assign new parents to every single node ($p = 1$) and create two trees, a bit more than 20% of nodes have matching heads whereas labels on the edge to the parent match on only about 4% of nodes. So I'm clearly sampling less uniformly for tree structure than for labels, since the sample space for trees is far larger than for labellings.

# Answer
> 2 votes
What you need is a Markov chain on the set of labelled directed trees, whose stationary distribution is the uniform distribution. You might be able to find such a Markov chain in the literature. It is then natural to run this chain, starting from your given tree, for $T$ steps, where $T$ has Poisson distribution with expectation $-\log(1-p)$ (say). Notice that when $p = 0$ you just get your original tree back, and when $p \to 1$ you run the chain for many steps, and so you get an almost uniform sample.

Why use the specific distribution $\operatorname{Poisson}(-\log(1-p))$? The Poisson distribution here describes the outcome of a Poisson process with a certain rate. The parameter $-\log(1-p)$ interpolates between your two values, and is similar to the noise operator in analysis of Boolean functions. However, since you haven't defined semantics for $p$, this is an arbitrary choice.

---
Tags: algorithms, trees, randomized-algorithms
---


# Question
Title: Ford-Fulkerson algorithm with asymmetric adjacency matrix
Suppose that I have a bipartite graph $G=(A \cup B, E)$ and $A = \\{1, 2, \dots, n\\}$, $B = \\{1, 2, \dots, m\\}$. After a virtual sink $s = 0$ and a source $t = n+1$ is included into the graph, I want to implement Ford-Fulkersen max flow algorithm.

To the algorithm, we need a symmetric adjacency matrix, therefore $O((n + m)^2)$ space.

However, in a bipartite graph, it is enough to use an adjacency matrix with $O(nm)$ space. But I could not figure out how to modify the algorithm so that it works with an asymmetric adjacency matrix.

Is there any way that Ford-Fulkersen max flow algorithm works in above scenario?

# Answer
The algorithm doesn't need a symmetric adjacency matrix. It needs to keep track of a flow and a residual network. Both are supported on the edges of $G$ and their inverses. You can store them in roughly the same way you store your graph $G$, using the same amount of space (up to a multiplicative constant).
> 3 votes

---
Tags: graphs, max-flow
---


# Question
Title: Using pumping lemma to show $L = \{a^i b^j a^k \ | \ k > i + j\}$ cannot be accepted by an FA
> $L = \\{a^i b^j a^k \ | \ k \> i + j\\}$
>
> Use the pumping lemma to show that this language cannot be accepted by an FA.

**Proof:**

Suppose $L$ can be accepted by an FA.

Suppose a string $s = xyz \in L$, where

$$\begin{align} &x=a^n \\ &y=b \\ &z=a^{n+2} \end{align} $$.

Then a string $t = a^n b^i a^{n+2}$ should also be in $L$ for $i \ge 0$, $n+i\<n+2$ and should also be accepted by an FA. But if $i=3$,

$$\begin{align} n+i = n + 3 \\\\>n + 2 \end{align}$$

and $t \not \in L$, which is a contradiction. Thus, $L$ cannot be accepted by an FA.

---

Is this proof thorough? I am worried about the line $n+i\<n+2$, because it doesn't work for all values of $i$. Should I pick a string that works for all possible cases?

# Answer
> 6 votes
Your basic idea (in particular the choice of $t$) works, but there are some issues with the "proof" as such:

* What is $n$?
* Why do you have $y=b$ have to be pumped? You have to work against *all* allowed decompositions of $t$!
* $n+i \< n+2$ does indeed not work for all $i$, but that's kind of the point. Just drop that condition.

I suggest you read our reference posts about how to read and apply the Pumping lemma properly, and then browse our questions for more examples.

# Answer
> 0 votes
I'm assuming that *n* is the number of states in your FA and you chose your string so the length of *x* is equal to or greater than *n*

in Which case you have to remember that one of the conditions for the pumping lemma is that the length of the string *xy* is equal to or smaller than *n*.

this means that if you choose $t=\\{a^n b^i a^{2n}\\}$,
*y* cannot contain any *b*'s since $a^n$ has to be in *xy*.

---
Tags: formal-languages, regular-languages, pumping-lemma, check-my-answer
---


# Question
Title: Effect of Copy-On-Write on 2 processes sharing address space
I am studying operating systems and was going through Copy On Write mechanism. From Wiki:

> When one process modifies the memory, the operating system's kernel intercepts the operation and copies the memory; thus a change in the memory of one process is not visible in another's.

It says a particular virtual page is remapped if any of the processes that are sharing the address space tries to modify any data value. So, I tried testing it by writing following code :

```
#include<stdio.h>
#include<stdlib.h>

int main()
{
        pid_t pid;
        int a = 30;
        pid = fork();

        if(pid == 0)
        {
                printf("Parent\t %x\t %d\n",&a,a);
        }
        else
        {
                printf("Child\t %x\t %d\n",&a,a);
                a = 25;
                printf("Child\t %x\t %d\n",&a,a);
        }

        return 0;
}

```

Now when I run the program, the output I get is :

```
$ ./test
Child    ae9dfe3c        30
Child    ae9dfe3c        25
Parent   ae9dfe3c        30

```

I understand why the address in first and third line are same but my doubt is why is the memory location in second line same as the other two? It should be different because the child process is modifying the value of *a* ?

# Answer
The `fork` primitive makes a copy of the process. From within the processes, the parent and the child are almost identical; the few differences are the return value of the `fork` primitive and a few characteristics such as the process ID.

Copy-on-write is an implementation optimization. It isn't visible from inside the process. You'd need to look inside the kernel to see it, or use some reporting tools that expose this information. For example, you can observe it indirectly through memory usage statistics.

What you're printing out are the *virtual* addresses of the variables. They're the same: that's the whole point of `fork` — it creates a (near-)identical copy of the process.

Under the hood, when the child modifies the value of `a`, the kernel makes a copy of the page that contains it. Before that point, the variable `a` in the parent process and in the child process are stored in the same memory. After that point, they are stored in different memory: the parent and the child now each have their own page. But the two processes map their respective pages at the same address — the address of a variable doesn't change (it can't change, because that's how the code locates the variable).
> 4 votes

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


# Question
Title: How do I find the intersection of subgraphs in a directed acyclic graph efficiently?
I have a directory structure in which each directory can have multiple parents (IOW, a `cd ..` is ambiguous). AFAICS this means this is equivalent to a directed acyclic graph.

Now, a set of directories (aka vertices) is given. I need to know all directories which are below all of those given directories. Thus, I need the intersection of subgraphs.

In my case, getting the set of sub-directories is a rather costly operation. However, I can do it in parallel, i.e. I can do `ls` on multiple directories at the same time.

While one can easily think of a brute-force algorithm to do that (collect all vertices in sets, find the intersection of the sets) I wonder whether these is a more efficient algorithm.

# Answer
> 1 votes
The more efficient algorithm you're looking for is breadth/depth-first search.

---
Tags: graphs, parallel-computing
---


# Question
Title: How should i guide a program to perform correct things?
I want to make a small model of A.I. which can learn itself. I am inspired by 1000+ monkey theorem which states that if 1000+ monkey bangs a keyboard for enough long, then they will eventually produce a Shakespeare's play. So, if you give a banana to one monkey when he produce a correct word, then he would eventually learn to do correct things. I think it is related to neural network.

So, practically i want to start with basic alphabets and digits and then my program would permutate and combine those to form words. Now, if the words they form matches with those in English Dictionary, i want to reward the program. However i couldn't think of any possible approach to this. How could this be implemented?

# Answer
> 1 votes
The "Infinite Monkey Theorem" doesn't say that monkeys will learn. On the contrary: it says that if monkeys keep typing *random* stuff long enough (i.e. not using any sort of learning), the works of Shakespeare will eventually come out purely by chance. It is the Law of Truly Large Numbers.

So you're right: you need to build feedback into the system. The program should change its behavior based on your feedback. This is known as reinforcement learning and it is used a lot in AI. An overarching term for this, I believe, is machine learning.

# Answer
> 0 votes
A similar experiment (based on *cumulative selection*) is described in The Blind Watchmaker:

> Suppose that he \[a monkey\] has to produce, not the complete works of Shakespeare but just the short sentence *METHINKS IT IS LIKE A WEASEL*, and we shall make it relatively easy by giving him a typewriter with a restricted keyboard, one with just the 26 (capital) letters, and a space bar.
>
> CUT
>
> \[A computer program\] again begins by choosing a random sequence of 28 letters, just as before... it duplicates it repeatedly but with a certain chance of random error – *'mutation'* – in the copying. The computer examines the mutant nonsense phrases, the 'progeny' of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, *METHINKS IT IS LIKE A WEASEL*.

(for further details and a simulation you can take a look at http://www.evoinfo.org/weasel.html)

You can try something like that or experiment with evolutionary algorithms (especially ideas from evolutionary art).

---

By the way, real monkeys don't write Shakespeare.

---
Tags: artificial-intelligence, word-combinatorics
---


# Question
Title: Can every context free grammar be transformed into equivalent grammar of this form?
Show, that **every** context free grammar can be transformed into equivalent context free grammar ( with possible loss of $\lambda $ ) where $a \in V\_t$ and $A,B,C \in V\_n $ with rewriting rules of following **type**:

$ A \rightarrow a $

$ A \rightarrow aB $

$ A \rightarrow aBC $

My thoughts are that I need to show that every context free rule *i* can be written into set of context free rules that when applied generate same string as rule *i*.

Is that correct? If not, could you give me any hints on how to do it properly?

**EDIT:**

How I\`m trying to do it:

Greibach normal form has rules of type:

$A \rightarrow aA\_1A\_2...A\_n$

So I need to break long rules into shorter rules Chomsky normal form style.

# Answer
Yes, you can start with ordinary Greibach NF and replace the offending productions. The trick is the same that is usually used to turn a grammar into Chomsky Normal Form. Introduce new nonterminals that represent sequences of old nonterminals, for instance $\[A\_1A\_2\dots A\_k\]$ is a *single* symbol that represents the sequence $A\_1A\_2\dots A\_k$ when $k\ge 2$.

Then any production $A\to aA\_1A\_2\dots A\_n$ with $n\ge3$ is replaced by $ A\to a A\_1\[A\_2\dots A\_n\]$, leaving two nonterminals at the rhs of the production.

Remaining question: what are the productions for terminals $\[A\_1A\_2\dots A\_k\]$, in such a way that we get only a bounded number of those nonterminals? Well, if $A\_1 \to bB\_1\dots B\_m$ in the original grammar in GNF, then we add the production $\[A\_1A\_2\dots A\_k\] \to b\[B\_1\dots B\_m\]\[A\_2\dots A\_k\]$ in the new grammar. This can be done for all sequences of nonterminals that are suffixes of the sequences introduced by the original grammar.

Note that we have to take care of short sequences in the obvious way. If in the construction above we find an empty sequence $\[\ \]$ it should be omitted, and we write $A$ for the sequence $\[A\]$ of length one. These special cases occur if $m\le 1$ or $k\le 2$.
> 5 votes

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


# Question
Title: Time complexity of a problem inspired by palindromes
**This was inspired by Bradshaw's question originally posted on Math.SatckExchange**.

**EVEN PALINDROME**:

**Input**: Given a list of strings $\[v\_1, v\_2, ... ,v\_n\]$ where $\Sigma |v\_i| $ is even number.

**Question**: Is there a permutation $\sigma$ such that $w=v\_{\sigma(1)}v\_{\sigma(2)}... v\_{\sigma(n)}$ $\in \\{uu^R \in \Sigma^\* \\}$.

> Is it NP-complete to determine if a given set of strings can be ordered to form a palindrome (of even length as defined above)? If yes, Is it still NP-complete for $|\Sigma|=2$?

**EDIT**: Marzio has given an elegant reduction which shows that Even Palindrome is NP-complete for binary alphabets.

# Answer
> 4 votes
After a wrong polynomial-time attempt, this is a more robust idea to prove that the problem is indeed NP-complete.

The reduction is from the 3-PARTITION problem which is **strongly** NP-complete; i.e. it is still NP-complete even if the numbers are represented in unary.

The problem is to decide whether a given multiset $S = \\{a\_1,a\_2,...,a\_n\\}$ of $n = 3 m$ positive integers, can $S$ be partitioned into $m$ triplets $S\_1, S\_2, ..., S\_m$ such that the sum of the numbers in each subset is equal?

Let $p = (\sum\_i a\_i) / m$

Note that the problem remains strongly NP-complete even if $p/4 \< a\_i \< p/2$ (which forces each $S\_i$ to contain at exactly three elements); see the original definition of 3-PARTITION in Garey&Johnson, Computers and Intractability.

We can build an equivalent EVEN PALINDROME instance in this way:

We add the long string:

$$w = 1 \\, 0^p \\, 111 \\, 0^p 11111 \\, 0^p \\, ... \\, 0^p \\, 1^{2m+1}$$

Then we add $n$ more strings:

$$v\_i = 0^{a\_i}\\; , \\;i = 1...n$$

and $1 + 3 + 5 + (2m+1) = \sum\_{j=1}^{m+1} (2j-1)$ strings of length 1:

$$r\_k = 1 \\; , \\; k = 1...\sum\_{j=1}^{m+1} (2j-1)$$

Note that $|w| = \sum\_{i=1}^n |v\_i| + \sum\_k |r\_k|$

Proof:

By construction the $w$ contains substrings of odd increasing length $(1,111,11111, ...)$, so it cannot be "placed" in the middle of $u u^R$; but it must be placed entirely in $u$ or entirely in $u^R$ (without loss of generality suppose that it is placed in $u$.

Now the others $v\_i$ must be arranged in the opposite part $u^R$ and in such a way that every $p$ zeroes (that can be "totalized" using the $v\_i$) an odd number of the $r\_k$ can be placed (to reflect the corresponding $1^{2j+1}$ substring of $w$). Furthermore all elements must be placed, so exactly 3 $v\_i$ must be picked to reflect each of the $0^p$ substring of $w$. So if an EVEN PALINDROME can be found it induces a valid 3-partition of the $a\_i$ of the original problem.

The opposite direction (a 3-partition exists $\Rightarrow$ there is an EVEN PALINDROME is immediate by construction).

Example:

3-Partition instance: $S = \\{1, 1, 1, 2, 2, 3 \\}$, strongly NP-complete; so we can also represent the numbers in unary: $S' = \\{ 1\_1, 1\_1, 1\_1, 11\_1, 11\_1, 111\_1 \\}$

EVEN PALINDROME reduction:

$w = 1000001110000011111$

$v\_i = \\{ 0, 0, 0, 00, 00, 000 \\}$

$r\_k = \\{ 1,\quad 1,1,1,\quad 1,1,1,1,1 \\}$

Solution of EVEN PALINDROME:

$$uu^R = 1000001110000011111 \quad 11111 \\; 0 \\; 00 \\; 00 \\; 111 \\; 000 \\; 0\\; 0\\; 1\\}$$

which corresponds to the 3-partition:

$S\_1 = \\{ 1, 2, 2 \\}, S\_2 = \\{ 3, 1, 1 \\}$

---
Tags: complexity-theory, np-complete, strings
---


# Question
Title: How to use a CFG to restrict a subset of a*b*c*d* so that there are at most as many a's and b's as d's?
> Give Context-free Grammar for the language $\\{a^i b^j c^k d^h \mid i,j,h \ge 0, k\>0, i+j \le h\\}$

This is a training exercise, for which we don't get any answers, in a course I'm taking. I have found similar examples, but nothing that touches on the `i+j≤h` part of this. My biggest trouble is that it is ordered, so I have no idea how to add ***d***'s to the end when I add ***a***'s or ***b***'s to the front. I haven't gotten very far because of this, but my thinking looks like this at the moment:

```
S→ABcCD
A→aA | ϵ
B→bB | ϵ
C→cC | ϵ
D→dD | ϵ

```

I can't put things like `A→aAd` or `A→aBCD` because that would result in ***c***'s and ***d***'s before ***b***'s in the end word/string. My conclusion is that I am probably on the wrong track, but all examples I find use some sort of partitioning like this.

So could anyone point me in the right direction?

# Answer
There are lots of answers on this site about this subject. See, for example here and here. The underlying idea that often works for problems like this is to work from the inside out.

1. The $c^k$ part is easy: just use the production $V\rightarrow cV\mid c$.
2. The part surrounding the $c^k$ part consists of a bunch of $b$s followed by an equal number of $d$s. That's also easy; it can be generated by $U\rightarrow bUd$. Once we're finished with that, we switch to the $c$ part, so we have $U\rightarrow bUd\mid V$.
3. Keep going. Now you want to surround that part with a bunch of $a$s followed by the same number of $d$s. With what we've done so far, you should be able to do this part.
4. Finally, we want $i+j\le h$ so we concatenate the strings we've generated so far with zero or more extra $d$s. See hint (1).

As with many subjects, it gets easier the more examples you've done. Just keep at it.
> 2 votes

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


# Question
Title: Does a context-free grammar with multiple variables have a "starting" point?
So lets consider the following grammar

$$ \begin{align\*} S &\to 0 \mid 0A \\ A &\to 1 \end{align\*} $$

would the string "1" be accepted by the language or must the language start with $S$?

# Answer
No $1$ will not be a part of the grammar, as only those strings generated by starting from the start variable $S$ are part of the grammar.
> 5 votes

# Answer
What you have shown is technically not a grammar, only part of it. A grammar is formally defined as the tuple $(N, \Sigma, P, S)$, where:

* $N$ is a set of non-terminal symbols
* $\Sigma$ is a set of terminal symbols
* $P$ is a set of production rules
* $S$ is a start symbol

You have only provided $P$, but to have a grammar, you also need $N$, $\Sigma$ and $S$.

$N$ and $\Sigma$ are often omitted when defining a grammar, because they are clear from $P$ (like in your example, where $N = \\{ S, A \\}$ and $\Sigma = \\{ 0, 1 \\}$).

Explicitly specifying the start symbol (referred to as $S$ in the formal definition above) can be omitted when there is a clear convention for the name of the start symbol; naming it $S$ as you do in your example is a common convention.

What this all means for your example is that if you assume that $S$ is the start symbol, then $1$ is not a member of the language. If you instead assumed that $A$ is the start symbol, then $1$ would be a member of the language. Such grammar would be formally valid, but defining it like this wouldn't make sense from a human's point of view.
> 14 votes

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


# Question
Title: Defining the goal function in an optimization problem
I have an optimization problem. There are a few quantities, call them $a, b, c$, that describe how good a solution is. However, they all have different priority, from highest to lowest: $a, b, c$.

The goal is to minimize the values of $a, b, c$. The difference in priorities means that the solution with identical value of $a$, lower value of $b$ is lower than the other solution, no matter what the value of $c$ is. Similarly, if the value of $a$ is lower, then no matter what $b$ or $c$ is, the solution is better better than the other solution.

What's the best way to define a goal function for this problem? I don't know the range of those values. I was thinking about using some weight parameters, like multiplying $a$ by the greatest weight, $b$ by lower weight, and $c$ by the lowest weight value.

# Answer
> 3 votes
If you know the minimum and maximum values for $a,b,c$, you can use a weighted linear combination. e.g., if $a,b,c \in \[0,1000\]$ (they are all between 0 and 1000), then you can use the objective function

$$\Phi(a,b,c) = 10^6 a + 10^3 b + c.$$

Minimizing this function is guaranteed to be optimal under your partial order.

Sometimes, even when you don't have upper and lower bounds, you can still use an objective function like the one above, as a heuristic. It's not guaranteed to give optimal results, but it might be good enough in your particular application.

# Answer
> 1 votes
> think of a fitness function in genetic algorithm. Given a solution I need to be able to tell directly how good it is

You can use vectors instead of simple scalars.

Comparison of fitness values should be based on lexicographical order:

$$(a,b) ≤ (a′,b′) \iff a \< a′ \lor (a = a′ \land b ≤ b′)$$

The selection scheme is probably the main problem: tournament selection, truncation selection, ranking selection are not affected by this change; fitness proportionate selection (roulette wheel) can present difficulties.

The other steps of a classical genetic algorithm (recombination and, for steady state algorithms, replacement) stay the same.

---
Tags: optimization
---


title: Combinator equivalent to eta conversion

text:
# Question
Title: Combinator equivalent to eta conversion
In lambda calculus, one can prove that two expressions compute the same function if they are equivalent under both beta reduction and eta conversion, where eta conversion consists of eta reduction, $$ (\lambda x.A x) \to A \qquad\text{if $x$ is not free in $A$} $$ and eta expansion, $$ A \to (\lambda x.Ax) \qquad\text{where $x$ is not free in $A$.} $$ Thus, while one cannot computationally check whether two expressions compute the same function, one can computationally verify a proof that they do, if someone produces a sequence of beta reductions and eta conversions that takes one expression to the other. The reason that determining equality between expressions is undecidable has to do with the need to use eta expansions as well as contractions, so you have to backtrack to search for a proof.

My first question is: is the above characterisation correct? It seems to be from what I've read, but I haven't seen it explained in exactly that way and I might have misunderstood.

My second question is, does eta conversion exist in the combinator calculus, or is there an equivalent? In other words, is there a set of formal manipulations on combinator expressions that can be used to show that two are equivalent to one another?

As a simple example, the expressions $S\\,K\\,K$ and $S\\,K\\,S$ are equivalent. (They are both the identity function.) I can show this by explicitly evaluating both of them: $$ (S\\,K\\,K)\\,x = (K\\,x)\\,(K\\,x) = x, $$ whereas $$ (S\\,K\\,S)\\,x = (K\\,x)\\,(S\\,x) = x. $$ But this involves introducing variables (i.e. moving away from "pure" SK combinator expressions), and it doesn't proceed by starting from one expression and manipulating it to convert it into the other. Is there a set of syntactic moves that can be used to show this equivalence, analogously to eta conversions in lambda calculus?

# Answer
From the Barendregt lambda calculus book, we can find theory $CL$ (combinatory logic) defined as follows

$$ K P Q = P \qquad S P Q R = P R (Q R) $$

where $K,S$ are constant symbols (for the well known combinators), while $P,Q,R$ range over all the possible $CL$ terms (built from $K,S$, variables and application). The relation $=$ is postulated to be a congruence.

The $CL$ theory can be extended with the following $A\_\beta$ axioms:

$$ \begin{array}{ll} A.1 & K = S(S(KS)(S(KK)K))(K(SKK)) \\ A.2 & S = S(S(KS)(S(K(S(KS)))(S(K(S(KK)))S)))(K(K(SKK))) \\ A.3 & S(S(KS)(S(KK)(S(KS)K)))(KK)=S(KK) \\ A.4 & S(KS)(S(KK)) = \\ & \qquad S(KK)(S(S(KS)(S(KK)(SKK)))(K(SKK))) \\ A.5 & S(K(S(KS)))(S(KS)(S(KS))) = \\ & \qquad S(S(KS)(S(KK)(S(KS)(S(K(S(KS)))S))))(KS) \end{array} $$

(I have double checked these, but I can't swear I got them right.)

Corollary 7.3.15 states that $CL\ +\ A\_\beta$ is equivalent to $\lambda$ (the theory of the $\lambda$ calculus with $\beta$ conversion, but no $\eta$ or extensionality).

Hence, in principle one can use "only" the above laws to prove $SKK=SKS$.

The convenience of the above laws is self-evident, I think.

A similar set of axioms is found in the same book for $\lambda\eta = \lambda + \bf ext$. These are $A.3,A.4,A.5$ (hence no $A.1,A.2$) and

$$ \begin{array}{ll} A.6 & S(S(KS)K)(K(SKK)) = SKK \end{array} $$
> 5 votes

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


# Question
Title: Why isnt node checked for nil value in start when transplanting binary tree
Whilst I was reading CLRS I came across this:

> When TRANSPLANT replaces the subtree rooted at node u with the subtree rooted at node v, node u’s parent becomes node v’s parent, and u’s parent ends up having v as its appropriate child.

```
TRANSPLANT(T, u, v)
1  if u.p == NIL
2      T.root = v
3  elseif u == u.p.left
4      u.p.left = v
5  else u.p.right =  v
6  if v != NIL
7      v.p = u.p

```

> Lines 1–2 handle the case in which u is the root of T . Otherwise, u is either a left child or a right child of its parent. Lines 3–4 take care of updating u.p.left if u is a left child, and line 5 updates u.p.right if u is a right child. We allow v to be NIL, and lines 6–7 update v.p if v is non-NIL.

Why wasn't v was checked for nil value in the starting of the procedure and if it was not checked then why was it checked in line 6. If v is nil then its parent will be its original parent and u's parent will reference to v - wouldn't this cause inconsistency in tree ?

## Context

Transplant is the sub-procedure used in deletion of a node from a binary search tree. It is used in binary search tree not in RB Trees or B-Trees.

## Details about the book

Edition - 3rd

Print - 2nd

PageNo - 296

# Answer
If $v$ is NIL then transplanting $v$ just transplants an empty tree. This is fine. It is handled in the exact same way as transplanting an actual tree, the only difference being that we don't need to update $v$'s parent pointer.

Could the code be structured differently? Probably. Why, then, did the authors choose this particular implementation? No deep reason. They programmed the algorithm, and that's the code they came up with. You might have come up with a different code. There's no one right answer in programming.
> 1 votes

---
Tags: algorithms, data-structures, binary-trees, algorithm-design
---


# Question
Title: What happens after the accept state if there are still letters in the string in a Turing machine?
Lets say there is a turing machine $M$ where
\begin{align\*} M &= (Q, \Sigma, \Gamma, \delta, q\_1, q\_{accept}, q\_{reject}) \\ Q &= \\{q\_1, q\_2, q\_3, q\_{accept}, q\_{reject} \\} \\ Σ &= \\{0, 1\\} \\ Γ &= \\{0, 1, U\\} \end{align\*}

with transition functions \begin{align\*} \delta (q\_1, U) &= (q\_1, U, R)\\ \delta (q\_1, 0) &= (q\_1, 0, R)\\ \delta (q\_1, 1) &= (q\_2, 1, R)\\ \delta (q\_2, U) &= (q\_{accept}, U, R)\\ \delta (q\_2, 0) &= (q\_3, 0, R)\\ \delta (q\_2, 1) &= (q\_2, 1, R)\\ \delta (q\_3, U) &= (q\_3, U, R)\\ \delta (q\_3, 0) &= (q\_3, 0, R)\\ \delta (q\_3, 1) &= (q\_3, 1, R) \end{align\*}

If I input a string and it reaches the $q\_{accept}$ state while there are still letters remaining in the string, would it count as accepting the string, rejecting the string, something else?

# Answer
> 1 votes
As per the general definition Turing machine halts when it enters the reject or accept state.At this point there can be an arbitrary string present on the tape of the Turing machine. This is how you expect the Turing machine to compute a function of the type say $\\{0,1\\}^m \to \\{0,1\\}^n$.

# Answer
> 3 votes
In the nominal TM definition, the machine is a 7-tuple, $M=(Q,\Sigma,\Gamma,b,\delta,q\_0,F)$, where $F$ denotes a set of *final* states. Wheneven the TM transitions to a state in $F$ it immediately halts, no matter what it did or didn't do beforehand.

From the way you wrote your TM, I believe you meant that your final states are $F=\\{q\_{accept},q\_{reject}\\}$, thus once one of them is reached, the TM halts.

Once the above is clear, there is the question of "what happens if the input string isn't fully consumed". Well, this question is a bit misleading, since it implies that the TM consumes the input string symbol-by-symbol (like a DFA or PDA), which is **not** the case for the nominal TM.

In a Turing machine, the input string appears on the tape at the start of the computation. It is fully there, and needs not be "consumed". Besides of the input string, the tape is *empty*, i.e., it contains the blank $b$ symbol (where $b\in \Gamma \setminus \Sigma$, so the input cannot contain blanks). Since the input is already there on the tape, there is no question of "consuming" it. The alternative question is *reading* the input - it is perfectly fine if the TM moves to a final state ($q\in F$) before "reading" the entire input, i.e, when the head of the TM never visits all the tape slots in which the input resides. Again, this is perfectly allowed.

<sub>**A Note:** Sometimes the input is given on a separate tape (which is usually, a *read-only* tape). This helps to count the memory actually used for processing the computation without counting the space used to hold the input. Such machines are especially relevant for computations that take sub-linear space. Yet again, the machine is allowed to terminate without reading the entire input.</sub>

---
Tags: turing-machines
---


# Question
Title: Is language equality for linear context-free grammars decidable?
Let's consider two context-free grammars $G\_1$ and $G\_2$ and ask the following question: Is $L(G\_1) = L(G\_2)$, that is, are the two grammars equivalent?

In general, this problem is undecidable. However, if both $G\_1$ and $G\_2$ are left-linear (or right-linear) grammars, then the problem is decidable, because both grammars describe regular languages.

My question is whether or not the same problem is decidable when both grammars are linear. Also, if anybody can point to relevant literature, that will be highly appreciated!

# Answer
> 12 votes
Quoting from Amiram Yehudai, *The Decidability of Equivalence for a Family of Linear Grammars*, Information and Control 47, 122-136 (1980), page 1:

> The equivalence problem for various families of languages is of great interest in the theory of formal languages. This problem is decidable for regular languages (Rabin and Scott, 1959) and undecidable for context-free languages (Bar-Hillel et al., 1961). It is also undecidable for the family of linear context-free languages, as follows from Lemma 1 in (Baker and Book, 1974). The family of uniform linear languages is a natural and nontrivial subfamily of the linear languages for which equivalence is decidable.

This refers to Baker, B. S. and Book, R. V. (1974), Reversal-bounded multipushdown machines, J. Comput. System Sci. 8, 315-332, which, in the proof of that Lemma 1, presents a subset of linear context-free languages such that deciding whether a member of the set is equal to $\Sigma^\*$ is equivalent to deciding the Post Correspondence Problem.

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


# Question
Title: Recurrence: space complexity to Tournament Method
Tournament method have this structure to found min and max (function `getMinMax`):

```
  mid = (low + high)/2;
  mml = getMinMax(arr, low, mid);
  mmr = getMinMax(arr, mid+1, high);

  /* compare minimums of two parts*/
  if (mml.min < mmr.min)
    minmax.min = mml.min;
  else
    minmax.min = mmr.min;

  /* compare maximums of two parts*/
  if (mml.max > mmr.max)
    minmax.max = mml.max;
  else
    minmax.max = mmr.max;

```

Time complexity is , but how can I found the space complexity? You stack values, plus values, plus values... until values. So (log n times). . That's right?

# Answer
First of all, when talking about space complexity, we need to make sure what exactly we are counting. There are two main issues:

1. Are we counting the space taken by the input?
2. How much space does a variable like `mid` or `mml` take? How much space does the return address take?

Regarding the first issue, usually we're not counting the space taken by the input; this space should be accounted for in the procedure creating the array. This convention is important in complexity theory for handling space complexity classes with small working space, and also makes practical sense.

Regarding the second issue, we actually have two kinds of variables here:

1. Addresses – the return address, `mid`, and perhaps other temporary values.
2. Array elements – the two components of `mml` and `mmr`.

The usual convention counts machine words rather than bits. Without explaining what exactly machine words are, it is usually assumed (and practically justified) that addresses take $O(1)$ machine words.

Regarding array elements, it depends on the type of the array. Here presumably the array elements are machine integers of machine floating points, and so they also take $O(1)$ machine words.

---

Having clarified these issues, let us get back to the algorithm. When analyzing the time or space complexity of an algorithm, we usually measure the complexity with respect to the input size $n$ (in machine words). In this case, we can identify the input size with the size of the array (measured in number of elements), although the input is actually a bit larger.

Suppose for simplicity that $n$ is a power of 2, say $n = 2^m$. When we trace the execution of the algorithm, we discover recursive calls for the following subarrays are made:

* $A\[0,2^m)$
* $A\[0,2^{m-1})$
* $A\[0,2^{m-2})$
* $\ldots$
* $A\[0,1)$

(Here $A\[a,b)$ consists of the elements $A\[a\]$ up to $A\[b-1\]$.) After the call on $A\[0,1)$ executes, we get another call to $A\[1,2)$, and so on and so forth.

At the particular point in time illustrated in the call stack above, the call stack is $m+1$ levels deep, and so the stack consists of $\Theta(m)$ machine words. That already shows that the algorithm requires $\Omega(m)$ space. Since the space taken by local variables is part of the call stack, the memory usage at any point in time is big Theta of the depth of the call stack (since each level requires $\Theta(1)$ machine words). It's not hard to check that the call stack never gets more than $m+1$ levels deep, and so the space is $\Theta(m)$.

When $n$ is not a power of 2, a very similar analysis shows that the space usage of the algorithm is $\Theta(\log n)$.
> 3 votes

---
Tags: algorithm-analysis, space-analysis
---


# Question
Title: Utility of D latch/flip-flop and how it differs from an SR latch/flip-flop
I understand that in a D latch, whenever the clock signal is high, Q matches D, and while the clock signal is low, it holds the previous state of D. For a D flip-flop, Q will hold whatever value D is at the exact moment C goes high, and will hold that same state until C goes high again. I am able to draw the clock diagram and identify these circuits. But I am not understanding the purpose of these components in a high level context.

1. What exactly does the D latch and D flip-flop do? (Differences and similarity)
2. From my understanding, it is to be able to "store" a bit value, but if that's the case, why not use an SR latch?

Edit: I have seen the following post. However, my question is a little more specific. I am asking specifically about a D latch/flip-flop. I also want to be able to differentiate how this is different from a SR latch, since it seems that their descriptions seem to do the same thing.

# Answer
One big difference is that while the SR flipflop has a "not-allowed" state (i.e., inputs S=1, R=1), the D flipflop has no such condition.

Another difference, is that the D flipflop just mirrors the input into the output, while SR has two inputs: one for setting the ouput to 1, and one for resetting the output into a 0.
> 0 votes

---
Tags: circuits
---


title: Constant problem for discrete functions

text:
# Question
Title: Constant problem for discrete functions
Is there an algorithm to decide whether a closed-form expression over integer variables using, say, $\\{+,-,\times,\div,\text{^},\lfloor\text{lg}\rfloor,!,()\\}$, or some other useful set of operators, is everywhere zero?

For example, is $(jk)^2 +k!-2j$ always 0 when $j,k$ are integers (obviously not)? If some of the operators make it impossible, is it possible with just a subset, for example if one removes factorial?

# Answer
> 1 votes
To decide if a particular diophantine equation (i.e., an expression in integers using multiplication and addition/subtraction equated to zero) has any solutions is undecidable. This is essentially the answer to the negative to Hilbert's tenth problem, which asks for an algorithm to determine if a diophantine equation has a solution.

# Answer
> 0 votes
p=q has a solution if and only if 0^((p-q)\*(p-q)) is *not* identically zero.  Thus, by undecidability of Diophantine equations, there is no such algorithm.

0^0 = 1 ≠ 0  and for all positive x,  0^x = 0 .    (p-q)*(p-q) is a square, and thus never negative, so 0^((p-q)*(p-q)) can be non-zero is and only if (p-q)\*(p-q) can be zero.    Therefore

p=q has a solution
if and only if
p-q = 0  has a solution
if and only if
p-q can be zero
if and only if
p-q can be zero
if and only if
(p-q)*(p-q) can be zero
if and only if
0^((p-q)*(p-q)) can be non-zero

.

---
Tags: computer-algebra
---


# Question
Title: Terminology - machine code and byte code
Do "machine code" and "byte code" terms refer to the available instruction set to the CPU and virtual CPU and their encoding (the language specification) or do they refer to the "encoding" of the current program's instructions after compilation?
The definitions I found in wikipedia seem to lean towards the notion of "instruction set":

# Answer
Both are sequence of instructions encoded as binary data. The difference being that "Machine code" is executed by the CPU whereas "byte code" is executed by a software (which itself is made up of machine code and executed by CPU).
> 4 votes

# Answer
Machine code is the set of machine instructions that make up the program. For instance, in ARM, this would be instructions like LDR, ADD, SUB, etc... Byte code is the code after compilation and is in bits. The format is usually 1-2 bytes representing the instruction and then more bytes representing the params passed into the instruction.

Note: there are many variations to this definition. Machine code to some may mean the hexadecimal representation of the code. It's definitely subjective.

Edit: When you open a file that has machine code inside it, it will have assembly instructions such as ADD, SUB, MUL, etc. Differs for different architectures. When you open a file with byte code, you will just a long list of just bits.
> 0 votes

# Answer
I think machine code and byte code are languages in their own. Compilation translates the source code from a high language to a lower level language (byte code or machine code).
> 0 votes

---
Tags: terminology
---


# Question
Title: Predicting next action to take to reach a final state
Does anyone know of an algorithm that could be used to determine the next action to take to reach a desired state when trained on time-series data?

For example, a robot starts at a certain state, then takes an action to get to another state. This occurs continuously for many iterations (imagine the robot is randomly exploring a room). If the robot is at a specific starting state, and I desire the robot to end up in a different state, is there an algorithm that could recommend the best next action (or set of next actions) to take to reach that final desired state?

One approach I've tried is to use a neural network with the current state and the next state being the input and the action to get from the current state to the next state being the output. The network would know for a single state how to get to a next desired state that is one action away. The issue is, what if the desired state is many actions away?

# Answer
> 1 votes
You can represent the problem as a directed graph where the nodes are the states and the edges are the action that signifies the transition from one state to another if the action is performed. Once this is done you can use various graph path finding algorithms to find the sequence of actions to reach a specific state from a starting state.

---
Tags: algorithms, artificial-intelligence, neural-networks, neural-computing, time-series-analysis
---


# Question
Title: Runtime of this function: $T(n) = 8T(n/3)+nlogn$
I need to find the runtime of this function: $$T(n) = 8T(n/3)+nlogn$$

I try to use the "Master Theorem" when $$a=8,b=3$$ $$n^{log\_ba}=n^{log\_38}$$ $$f(n)=nlogn$$ And I define: $$\varepsilon = -1.5+log\_3 8$$ the first option in "Master Theorem" it\`s that (when $\varepsilon \>0$): $$f(n)=nlogn=O(n^{log\_3 8-\varepsilon})$$ So: $$f(n)=nlogn=O(n^{log\_3 8-(-1.5+log\_3 8)})$$ $$f(n)=nlogn=O(n^{1.5})$$

And its ture! So I can say that the runtime it\`s: $$T(n)=\Theta (n^{log\_3 8}) $$

That\`s true? and why I can say that $\varepsilon=-1.5+log\_3 8\>0 $ I dont have calculator in the exam!

Thank you for help :)

# Answer
You only need to make sure that $\log\_{3}8 \> 1$ which is easy to see.

Let $\log\_3{8} = 1 + \delta$, $\delta \> 0$. Set $0 \< \epsilon \< \delta$. We have $n^{\log\_3{8} - \epsilon} \> n^1$.

So $n \log n = O(n^{\log\_{3}8 - \epsilon})$.
> 0 votes

---
Tags: runtime-analysis
---


title: Supercomputer Configuration

text:
# Question
Title: Supercomputer Configuration
I think I understand how supercomputers work in general, but I would like to know how they are configured. It seems to me that supercomputers have a separate computers at each node, each with it's own processor, memory, storage, networking and operating system. It's all that really necessary? Why isn't each node given a processor and memory and a way to communicate with a master node, which is a real computer. Each with be provided with binary ready to run. Why does each node need to be able to run it to own operating system.

# Answer
> 2 votes
It is pretty hard to come up with a specific definition of a supercomputer. From what you described I think you have clusters in mind, which is basically a network of computers with some task-division possibilities. Every node in a cluster is a computer itself and they might (or should) communicate with each other.

I think your question indicates a slight lack of understanding what computers are and what operating systems do (what do you mean by *real computer*?) If you have a processor and a memory you need some operating system to use them effectively. For example, you mentioned "a way to communicate" between machines - that is pretty tough to implement reasonably without an operating system.

I would recommend checking wikipedia page on computer clusters and taking it from there.

---
Tags: parallel-computing
---


# Question
Title: Finding the Regular Expression of a language
I'm trying to find a regular expression for the language $$L = \\{w\mid n\_a(w)+n\_b(w)\equiv 2\pmod3\\}\\,,$$ where $n\_a(w)$ is the number of $a$s in $w$.

I can see that this would generate strings of length $3n-1$ and I can write the expression for a string of whose length is a multiple of three: $(( a + b )^3)^\*$. But that's not quite what I need.

The alphabet is $\\{a,b\\}$

# Answer
> 2 votes
It's better to think of $L$ as strings of length $3n+2$. You already have an expression for strings whose length is a multiple of 3, so use that and append all strings of length 2.

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


# Question
Title: Is every countably infinite language recursive?
We'll say the alphabet for the languages is finite, say {0,1}.

# Answer
Every language over a finite alphabet is countable so your question is just "is every language recursive?" The undecidability of the halting problem shows that there are non-recursive languages.
> 5 votes

---
Tags: formal-languages, uncountability
---


title: Quantum CNot algorithm problem

text:
# Question
Title: Quantum CNot algorithm problem
I have a very simple quantum algorithm:

Let's start with two qubits in the state $|00\rangle$. I apply a Hadamard gate to the first one. Then I apply a CNot gate, with the first one as a control. Then I apply a Hadamard gate to both of them.

I think I should end up with with two qubits 100% in the $|00\rangle$ state. However, I tested this algorithm on two different simulators (QuantumPlayground and Davy Wybiral's), and the output of both was:

$$ 0.707\\,|00\rangle ;\ 0.707\\,|11\rangle\\,. $$

Where did I go wrong?

# Answer
(For convenience I'm omitting the normalization factors like $1/\sqrt2$ and $1/\sqrt4$.)

The state after applying CNOT is $$\left|E\right\rangle=\left|00\right\rangle + \left|11\right\rangle.$$ This is **not** the same as $$\left|S\right\rangle=(\left|0\right\rangle+\left|1\right\rangle)(\left|0\right\rangle+\left|1\right\rangle)=\left|00\right\rangle+\left|01\right\rangle+\left|10\right\rangle+\left|11\right\rangle.$$ Only $(H\otimes H)\left|S\right\rangle=\left|00\right\rangle$, but $(H\otimes H)\left|E\right\rangle$ is something else.

Physically we say $\left|E\right\rangle$ is an **entangled** state and $\left|S\right\rangle$ is a **separable** state. Being entangled means you cannot consider each qubit independently.

Instead, to compute $(H\otimes H)\left|E\right\rangle$ you need to consider each **possibility** (linear component) separately:

\begin{align} (H\otimes H)\left|00\right\rangle &= (\left|0\right\rangle+\left|1\right\rangle)(\left|0\right\rangle+\left|1\right\rangle) &&= \left|00\right\rangle+\left|01\right\rangle+\left|10\right\rangle+\left|11\right\rangle \\ (H\otimes H)\left|11\right\rangle &= (\left|0\right\rangle-\left|1\right\rangle)(\left|0\right\rangle-\left|1\right\rangle) &&= \left|00\right\rangle-\left|01\right\rangle-\left|10\right\rangle+\left|11\right\rangle \\ \hline \therefore\\;(H\otimes H)\left|E\right\rangle &&&= \left|00\right\rangle \phantom{\\,-\left|01\right\rangle-\left|10\right\rangle} + \left|11\right\rangle. \end{align}
> 1 votes

# Answer
The other answers explain how the circuit behaves. This answer will explain how to directly manipulate the circuit into a simpler form.

Here's a surprising fact: surrounding a CNOT with Hadamards flips the CNOT.

(I get that checking this on paper requires already understanding the solution to your question. You can confirm it for yourself in a circuit simulator such as Quirk at least.)

Your CNOT circuit is surrounded by 3 Hadamards. By flipping the CNOT, and using the fact that H is its own inverse, we can turn that into a single Hadamard:

Leaving us with the standard make-an-entangled-bell-pair circuit. So, when the input is $|00\rangle$, the output is $\frac{1}{\sqrt 2}|00\rangle + \frac{1}{\sqrt 2}|11\rangle$.
> 2 votes

# Answer
Your circuit is equivalent to first applying a Hadamard gate on the second qubit followed by a CNOT gate where the control is the second qubit. This cannot result in state $|00\>$ after execution.

To help you further, why do you think it should end up in state $|00\>$?
> 0 votes

---
Tags: quantum-computing
---


# Question
Title: What do we mean when we say an edge (u,v) connects some component to other component in forest G = (V,A)
Let H = (V,E) be a connected, undirected graph. Let A be a subset of E. Let C = (W , F) be a connected component (tree) in the forest G = (V,A). Let (u,v) be an edge connecting C to some other component in G.

Now doesnt it imply that (u,v) must belong to A since it is in forest G and it doesnot matter which component it connects? Is this proof wrong:

For purpose of contradiction lets assume that it does not belong to A. As (u,v) connects two components of graph it must be an edge. As Set of edge is given by A in graph G it must belong to A which contradict our assumption.

# Answer
Here's a simple example. Let $H$ have vertices $V=\\{1,2,3,4\\}$ and edges $E=\\{(1,2),(2,3),(3,4),(4,1),(1,3)\\}$, so $H$ is a square plus one diagonal.

Now let $A=\\{(2,3),(4,1)\\}$, so these are the edges of $G$ and hence $G$ will have two components, each consisting of one edge of $A$. Let's pick $C$ to be the component consisting of $\\{2,3\\}$, so the other component will be $(4,1)$.

There is an edge **of $H$** connecting these two components, namely $(1,3)$. Your mistake was assuming that the $(u,v)$ edge was in the forest $G$. If it were, then it would have to lie in a single component so couldn't connect two components of $G$.
> 1 votes

---
Tags: formal-languages, graphs, reductions, proof-techniques
---