# Question
Title: Looking for sources: Graph search in social media
I am looking for more information/references on how graph search is utilized in social media. Papers, books , anything really.

# Answer
Facebook graph search is a relatively new technology pioneered/announced by Facebook that attempts to search for relevant info based on social connections in a social media system (eg Facebook). ie it finds relevant info based on exploring information "nearby" on the "social graph".

in this way, basically every person on Facebook doing the same search with same search terms might come up with different results based on how it interrelates with what their friends are posting about. this also can be seen as part of a trend where the major online services are encroaching on each others prior territory, eg Google's recent introduction of Google+ social network. conversely Facebook is now encroaching on Google's lucrative and highly-developed search engine technology.

there is a huge amount of media coverage \[cited in the wikipedia article\] but mainly at a superficial level of a product introduction. in contrast to Googles pagerank algorithm, the Facebook algorithm did not appear to originate in open scientific research, but instead is a mostly proprietary technology developed within Facebook. Facebook is not going to want to release many details, but the following is useful for an overview, written by Xiao Li, an engineering manager on the natural language team for Graph Search, and Maxime Boucher a research scientist for Graph Search.

also it will be natural for Facebook to insinuate this algorithm as highly developed and competitive with Pagerank but because its in early stages of development, one would not expect highly advanced results competitive with Pagerank at least at first (because Pagerank has been highly developed over a decade etc) *with respect to mere semantic capability*. on the other hand Facebook has access to a social graph, and it would be expected to prove superior quality in some types of searches that best leverage/focus on ones personal social network.

there does not appear to be much open scientific research *outside of Facebook* related to this topic. however the following seems to be a publication of some of the principles in a previous prototype/experimental iteration/version called Unicorn which the new feature is probably originating from/growing out of.

* Unicorn: a system for searching the social graph

> Unicorn is an online, in-memory social graph-aware indexing system designed to search trillions of edges between tens of billions of users and entities on thousands of commodity servers. Unicorn is based on standard concepts in information retrieval, but it includes features to promote results with good social proximity. It also supports queries that require multiple round-trips to leaves in order to retrieve objects that are more than one edge away from source nodes. Unicorn is designed to answer billions of queries per day at latencies in the hundreds of milliseconds, and it serves as an infrastructural building block for Facebook's Graph Search product. In this paper, we describe the data model and query language supported by Unicorn. We also describe its evolution as it became the primary backend for Facebook's search offerings.
> 0 votes

---
Tags: graphs
---


# Question
Title: Why can't we derandomize the PCP theorem by iterating over all possible $\log n$ random strings?
Let's say I can solve problem $A$ in polynomial time using only $\log n$ bits of randomness, with a $\ge \frac{2}{3}$ chance of a correct answer. Then surely I can solve $A$ determistically by running my algorithm for $A$ over all random strings of length $\log n$ (of which there are a polynomial number) and take a popular vote of the outcomes.

I don't understand, then, why we would ever talk about $O(\log n)$ amounts of randomness in complexity classes that are closed under polynomial factors. More specifically, the PCP theorem says $NP = PCP\[O(\log n), O(1)\]$ - why isn't that the same as $PCP\[0, O(1)\]$?

# Answer
We can! However, the PCP theorem does not say that we can *solve* the problem using $\log n$ bits of randomness. It says that we can *verify* a solution with $\log n$ bits.

Recall that a standard definition of NP is the class of languages for which there is a deterministic, polynomial-time verifier: For each $x$ in the language, there is a certificate $y$ so that the verifier accepts $\langle x,y \rangle$, and there is no such $y$ if $x$ is outside the language.

The PCP theorem says that we could also define NP as the class of languages for which there is a randomized, polynomial-time verifier that uses $\log n$ bits of randomness and reads only a constant number of bits of the certificate $y$.

Notice that if you derandomize the $\log n$ bits of randomness by enumerating them all and running this verifier on each one, you end up with a deterministic algorithm that will read the entire certificate $y$, which matches the standard definition of NP above.
> 7 votes

# Answer
The PCP theorem states that every NP problem has a polynomial size certificates (for the YES instances) that can be checked (up to a small constant error) by reading only constantly many bits of the proof. This does not give you an algorithm to solve the problem since guessing the certificate would take exponential time. On the other hand, the fact that the certificate is only polynomial size, and that the verification consists of reading only constantly many bits, puts this proof system in NP.
> 3 votes

---
Tags: randomized-algorithms
---


# Question
Title: How are REGEXP implemented in programming languages?
Is there a good general paper about the interpretation or compilation of REGEXP in programming languages for pattern matching, with or without variables? I am not looking for a quick explanation about the construction of DFAs, but for a real paper on how it is actually done in programming languages implementation, and what is considered simple or difficult. I expect differences between languages may have an inpact. A formal paper on how REGEXP implementation should be done is useful too :-)

# Answer
I believe most interpreted regular expression matchers start with Thompson's construction algorithm to turn the regular expression into a non-deterministic finite automata. The article that first described these is: Ken Thompson, "Programming Techniques: Regular expression search algorithm", *Communications of the ACM*, 11(6):419-422, June 1968. But that paper is a little hard to read, since he was compiling to machine code.

My favorite tutorial on regular expression implementation is this series of blog posts by Russ Cox, the author of the RE2 regular expression library. He gives *lots* of historical discussion. He argues that the most efficient approach to simulating the NFA is to convert to DFA on the fly with caching of just the DFA states that you actually reach. (In contrast to, for example, the implementation of regular expressions in Perl, which use backtracking.) There are cases (e.g., when you get an extended regular expressions with backreferences) where you need to use backtracking, but Cox suggests that you should only use backtracking when you need to.

The other place you might look is Henry Spencer's regular expression library. According to that web site this was described in the book: Dale Schumacher (ed), *Software Solutions In C*, Academic Press, 1994.
> 5 votes

---
Tags: programming-languages, compilers, regular-expressions, matching, interpreters
---


title: A home assignment. C language

text:
# Question
Title: A home assignment. C language
Help would be much appreciated.

"Receive a number and reorder it from the largest to the smallest.
Input: 13252
Output: 53221
Cant use arrays... Only while, for, if/else ...

any idea? i'm clueless.
Thanks for the help.

# Answer
> 1 votes
Oh my word! Coding that did take a while. The logic however, is quite simple. Recall the number system.

* First, determine the length of the number entered by the user. You can do so by dividing the number repeatedly by 10 until the quotient becomes zero.
* Then, the maximum value of a digit in decimal number system is 9. So compare each digit in the number with 9. The modulo division operation comes handy in here. See if there's a match. If there's no match go to the next smaller digit, 8 and continue this until you get to zero.
* Multiply the first match found using this procedure with 10^(length-1) *i.e. you are making it your most significant digit (number systems)*
* Reduce the length *length--*
* Continue this procedure until length becomes zero
* A little tip for efficiency, note down the matched digit each time and make that the slab for comparing the remaining digits in the number i.e. if you found out 5 is the first match, and thus the greatest digit found in your number, there's no point starting your comparisons from 9 again for the next digit. Start at 5. Don't be overly smart and start at 4 though. Remember there can be multiple 5's in a number.

I wrote a working piece of code for this. So this algorithm works. Hope that helps. Ways to improvise the performance are appreciated. However, don't suggest the usage of arrays or strings as they are forbidden in the question.

---
Tags: algorithms, sorting
---


# Question
Title: Using humans as components to build a computer?
Ok before I start I realise this is on the fringe of on-topic (I have read the Questions help for this site), particularly as this is not a real-world problem. However:

1. I cannot find anything relevant on Google
2. From a purist point of view surely it must fall within Computer Science?

In any case, if I have overstepped a boundary then I apologise and welcome the Closure as I am an avid user of other SE sites so I understand the issues.

Caveats aside, here it is: I have long wondered if it would be possible to build a functioning computing system, using humans as discrete logic components, to solve problems that individual humans could not solve in a practical timesscale. For example, imagine a number of humans stranded on an island without any machines, that needed to crunch some complex numbers to escape.

I imagine arranging people so that they receive inputs from other groups within the system, make simple decisions (perhaps binary decisions, perhaps not) and pass the outputs to other groups.

Then I imagine some kind of programming language could be developed to control the data and computation flow and the language could be used to solve complex problems without individuals understanding the overall problem.

So I guess the above is not an answerable question- but **does anyone know of any research, books, papers or whatever** on what it would take to achieve, what kinds of of problems could be addressed and potentially solved, what kind of control language could be deployed and how the architecture could be scaled up to handled more complex problems?

I suppose, in essence, I am looking for anything on "idealised" atomic (as in self contained) and standard computing units that could be arranged at will- I am just thinking in human terms.

I find the idea fascinating and alluring. I'd love to try it out one day and see what performance could be achieved! Sorry for the tags I have used, as I was searching the tags here I quickly became aware I have no idea of the correct terminology for what I am thinking, though I am sure it exists within the field...

# Answer
Actually, until the 1950s the word *computer* was used to refer to a human who did arithmetic calculations. One (or more) of Richard Feynman's (many) autobiographies contains anecdotes about his time on the Manhattan project, where he ran the group of human computers. For arranging a group of humans to perform a complex computation they wouldn't start with discrete logic components, but rather have each human perform multiple arithmetic operations and then coordinate their results (along with some error checking.) How to organize these kinds of large computations may be covered in numerical methods books from the 1940s or early 1950s.

The first version of the Logic Theorist by Newell, Simon and Shaw was simulated using humans in 1956 (less expensive than computer time). They later won a Turing Award for basic contributions to AI, the psychology of human cognition and list processing (the Logic Theorist may have been the first program to use linked-lists to represent data structures.) And the experience influenced Simon's later ideas on emergent behavior (see his Sciences of the Artificial.)

As pointed out in the comments and other answers, there is now an emerging discipline of Human-Based Computation, where various incentives are used to get humans to do parts of a larger calculation, where those parts make good use of human problem solving or pattern recognition. One example of this is reCaptcha, where users need to enter two words to prove that they are not a bot, one a distorted image that is used for the actual "proof" and the second an actual word from a scanned book, which is used to produce a digitized version of the book. Another example is the Amazon Mechanical Turk where a business can outsource "microtasks" to human workers for small sums of money. The mechanical turk has been used, for example, to collect annotations on 250,000 images for image processing research. The key seems to be breaking the problem down into a pile of independent work items, with significant amounts of redundancy used to reduce errors. (E.g., you assign the same work item to 2 different humans, and then if they provide conflicting answers you assign the work item to a third human to resolve the difference.)
> 20 votes

# Answer
I would think that, in a way, current proof development technology, and possibly associated program synthesis techniques, rely on a symbiosis between humans and computers, wich is not far removed from the example of the Manhattan project human computers. The computer provides some steps of the reasonning and does all the tedious, though difficult book-keeping, while humans provide the Aha steps that the computer cannot (yet?) find.

I remember an old program transformation system, where transformations were programmed in a specific programming language. When the program identified a situation it could not handle, it could pass control to the user who was supposed to do whatever was needed by hand, with intepreted commands, and then pass control back to the transformation program.
> 1 votes

# Answer
as other answers point out, humans were used as computers before hardware-based computing (mainly for calculating large mathematical tables published as volumes), and that is the original literal meaning of the word "computer". in the history of computing, the trend has been exactly in the opposite direction away from human computing to hardware based computing because humans are essentially unreliable (and increasingly unnecessary) for nearly-mechanical tasks.

however, social networking has given rise to new forms of human-based computing aka "collective intelligence" (CI). there are many examples. for example on stackexchange the question "ratings" (positive minus negative votes) and "hot questions" are based on CI of stackexchange users (expressed via voting). algorithms to find similar items on eg Amazon based on user behavior are related to CI. similar algorithms run on Netflix to find similar movies based on user preferences (and user-submitted ratings).

google Pagerank is designed to work based on the CI encoded in link patterns (linking on web pages is ultimately based on human choices). Facebook is introducing a new Graph Search algorithm also tightly coupled with CI. note that even what friends a person has, as expressed in social networks, is related to CI.

examples of concepts related to human computing:

so, as far as long range trend, humans as digital or mechanical computers has been in decline for the entire 20th century continuing into the 21st, but collective intelligence is very much on the rise as well as cheap computing and computing clusters fueled by Moores law.
> 1 votes

# Answer
This is a real world challenge and closely relates to workflows. The idea of having a workflow is to have a queue or ordered or un-ordered list of tasks that people or computers have to pick up at any time to complete a bigger process in which they may or may not be concerned or know about at all.

In effect you will have a machine that can make something and usually this is the main challenge and/or goal for an entrepreneur, mostly because money can be made if you can automate something and then step away from it (like a machine).

The inherent problem with using humans is that they make more mistakes or get bored with the work. Basically, this is also the reason for entrepreneurs to try to replace the real people parts with mechanical or computers parts.
> -1 votes

---
Tags: reference-request, human-computing
---


# Question
Title: How can I prove $P \rightarrow (Q \rightarrow R)$ is equivalent to $(P \wedge Q) \rightarrow R$
I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have trouble comprehending what he's trying to tell me.

The question is:

Prove that: $P\rightarrow(Q\rightarrow R)$ is equivalent to $(P \wedge Q) \rightarrow R$

He wants us to prove it using math and goes on to tell me that $P \rightarrow (Q \rightarrow R) = \neg P \vee (\neg Q \vee R)$

From that point on, I was completely lost and unable to follow along.

# Answer
> 8 votes
1. You could just construct the truth tables for the two formulas: there are only three variables, so the tables are only eight lines.
2. Use de Morgan's laws, distributivity and so on to rearrange one formula into the other.
3. Use similar techniques to show that $\[P\rightarrow (Q\rightarrow R)\] \leftrightarrow \[(P\wedge Q)\to R\]$ is equivalent to true.
4. Use similar techniques to show that $\[P\rightarrow (Q\rightarrow R)\] \leftrightarrow \neg\[(P\wedge Q)\rightarrow R\]$ is equivalent to false.
5. Use one of the various propositional proof systems to accomplish one of 2–4, though that sort of thing will probably come up later in your course.

# Answer
> 4 votes
A very useful fact (especially for this problem) is that the following two expressions are logically equivalent $$ A\rightarrow B\quad\text{and}\quad \neg A\lor B $$ Then you could show that the two expressions you're given are equivalent, like this:

1. From $P\rightarrow (Q\rightarrow R)$, replace the right implication by its equivalent and then replace the left implication. You'll get something we'll call Exp 1.
2. From $(P\land Q)\rightarrow R$, replace the implication by its equivalent and then use deMorgan's law. You'll get something we'll call Exp 2.

Lo and behold, you'll find that Exp 1 and Exp 2 are the same, so you're done. It's worth noting that you were lucky in this problem: it's not always that simple.

# Answer
> 3 votes
There have been two good answers as to how you might prove it, depending on the logical system. But it might also help to think about exactly why it must be true.

Suppose you have a mathematical function $f : A\times B \rightarrow C$. That is, it takes an element of type $A$ and an element of type $B$, then it returns an element of type $C$.

Now consider a function $f' : A \rightarrow (B \rightarrow C)$. This is a function that takes an element of type $A$ and returns a function. This function, in turn, takes an element of type $B$ and returns an element of type $C$.

Can you see that these are, in a sense, equivalent? You might call the first function by passing a pair $f(a,b)$ and the second one by passing an element, then passing an element to the function returned, like $(f'(a))(b)$. Either way, you get an element of $C$ by passing in an element of $A$ and an element of $B$.

So the types $A \times B \rightarrow C$ and $A \rightarrow (B \rightarrow C)$ are isomorphic. For every function of one type, there is a function of the other type which does the same thing. Using set exponent notation makes this even more obvious: it's saying that $C^{A \times B}$ is isomorphic to $(C^B)^A$.

It may not be obvious what this has to do with logic, but actually the connection is extremely deep and completely rigorous. If you're interested, look up the Curry-Howard correspondence, or Curry-Howard isomorphism.

# Answer
> 1 votes
Though you are two steps from the solution:

¬P∨(¬Q∨R)

is also (associativity)

(¬P∨¬Q)∨R

is also (De Morgan's law)

¬(P∧Q)∨R

is also (definition of →)

P∧Q→R

---
Tags: logic, proof-techniques, propositional-logic
---


# Question
Title: If a thread containing main terminates, can another thread do anything?
I'm studying threads in C and I have this theoretical question in mind that is driving me crazy. Assume the following code:

```
1) void main() {
2)     createThread(...); // create a new thread that does "something"
3) }

```

After line 2 is executed, two paths of execution are created. However I believe that immediately after line 2 is executed then it doesn't even matter what the new thread does, which was created at line 2, because the original thread that executed line 2 will end the entire program at its next instruction. Am I wrong? is there any chance the original thread gets suspended somehow and the new thread get its chance to do something (assume the code as is, no sync between threads or join operations are performed)

# Answer
> 3 votes
While the details will depend on the actual thread model of your thread library (eg. pthreads, the POSIX thread library), some general observations hold.

1. Without explicit or implied syncing you have no guarantees about the serialization of threaded code. The platform running your code might execute some of the thread's code first before resuming the spawning (main) thread of the process.
2. The thread-creating code of your program itself is just a thread - it does not need to be distinguished from any thread it creates.
3. Automatic program termination after a thread ends will be most inconvenient in most settings (Imagine a multi-threaded program where one thread enters a non-recoverable error state while another thread performs a backup job). So while the code/language may lack *overt* syncing primitives, usually there still exist mechanisms to allow for a controlled thread termination.

---
Tags: parallel-computing, concurrency, threads
---


# Question
Title: Given a sorted array $A$, how can it be efficiently determined whether $\exists i . A[i] = i$?
Given an array $A$ of integers in ascending order, how efficiently can it be decided whether there exists an integer $i$ such that $A\[i\] = i$? How would an optimal algorithm for this problem work?

# Answer
> 7 votes
It can be done in $O(\log~n)$ for a $n$ element array $A$ by using a slightly modified version of binary search. This is possible because you stated that the input array is made of increasing integers and is therefore sorted. It does not matter what kind of integers your input actually contains: the integers may be negative, zero or positive as long as the array is sorted.

Your search for an index $i$ such that $A\[i\] = i$ is of course equivalent to searching for an index $i$ such that $A\[i\] - i = 0$ and the function $f(i) = A\[i\] - i$ is monotonically increasing so that the problem reduces to finding, if it exists, one point $i$ where the function value is zero. It follows that you are guaranteed that if a check fails you only have to explore one subarray, which leads to $O(\log~n)$ in the worst case.

Your algorithm starts by checking the middle element as usual. If the check succeeds (A\[middle\] - middle = 0), you have found the index you are searching for. If $A\[middle\] - middle \< 0$, then you need to check the right subarray; otherwise ($A\[middle\] - middle \> 0$), you have to check the left subarray.

# Answer
> 4 votes
Let $lb, ub \in \mathbb N$ denote the lower and upper bounds of $A$, resp.

You are testing for the existence of an $i \in \\{lb, \dots, ub\\}$ such that $A\[i\]=i$ (a 'fixpoint element'). Solve the task by recursive bisection, ie. repeatedly halving the size of the array portion within which a fixpoint element may reside.

The basic idea of the algorithm consists in finding a slice of contigous array elements where the first element is less than its index while the last element is greater than its index. Since the elements in the array are strictly increasing, this is a necessary condition for the array slice to contain a fixpoint element (it's not sufficient though, consider $A\[0..1\] = \<-a,a\>, a \> 1$).

In pseudocode

```
fn hasfix ( A: array int of int, lb: int, ub: int ): boolean =
    if lb = ub
        then return (A[lb] = lb)
        else if A[lb] > lb or A[ub] < ub
                 then false
                 else let m := floor ( (ub + lb) / 2 )
                       in if (A[m] < m)
                              then hasfix ( A, m+1, ub )
                              else hasfix ( A, lb , m  )
                          end if
             end if
    end if
end

```

the initial call

```
hasfix ( A, lb, ub )

```

will indicate whether there is a fixpoint element. Giving the index of such an element is an obvious extension.

Running time of the algorithm is $O(\log n)$ for $n$ being the number of array elements. Note that you abstract away from the magnitude of the array limits, ie. the size of their representation, and thus assume that access to any array element is $O(1)$.

---
Tags: algorithms, time-complexity
---


# Question
Title: kNN: how to improve Spam classification?
Currently I'm trying to classify spam emails with kNN classification. Dataset is represented in the bag-of-words notation and it contains approx. 10000 observations with approx. 900 features. Matlab is the tool I use to process the data.

Within the last days I played with several machine learning approaches: SVM, Bayes and kNN. In my point of view, kNN's performance beats SVM and Bayes when it comes to minimize the false positive rate. Checking with 10-fold Cross-Validation I obtain a false positive rate of 0.0025 using k=9 and Manhattan-Distance. Hamming distance performs in the same region.

To further improve my FPR I tried to preprocess my data with PCA, but that blow away my FPR as a value of 0.08 is not acceptable.

Do you have any idea how to tune the dataset to get a better FPR?

PS: Yes, this is a task I have to do in order to pass a machine learning course.

# Answer
You could consider querying the k-nearest neighbours and weight them following some schema like this one. There are quite a few in the literature. The general idea is to give more relevance to those neighbours lying closer to your sample. It has the effect of regularizing your classifiers (smooth out your decision surfaces).

You evaluated your algorithm using 10-fold CV. What is the dispersion of your measurements?. If you see wide dispersion, you could use bagging. It is very easy to implement. It is specially meaningful when overfitting is strong.
> 2 votes

# Answer
Try **stemming**.. words like *win, winner, winning* basically convey the same "essence" of meaning... so you can replace them all with *win*. this reduces your space and saves you time!

Also, If you really know your code, and since you are working on BoG model, i would suggest to have a "thesaurus" kind of relational model running behind your classifier .. the words "good" , "great", "superb", "excellent" are synonyms and maybe you could group them.

The LDA or PCA is always a smart thing to do.. anyway, a few more tips (you may already know these!)

* **ALWAYS NORMALIZE DATA**, when you can ! (i cannot stress this enough!)
* TRY a smart way for **feature selection**, although your classifier buddy will do it's best, but try to minimize its work.. you won't believe the type of speed ups you will see!
* **REMOVE redundant data** (they do no good, but "dimensions-explosions"!)

now, coming to part II of your problem... algorithmically speaking, the time for KNN and SVM (with no/linear classifier) is the same. The reason why your dataset behaves well with KNN is because 1. it has A LOT OF DATA! 2. it's a toy problem with "good data"... in the real world you WILL face a lot of nonlinear, weird and abysmally disorganized data, KNN won't be much of a use then..

Also, there's no silver bullet among classifiers, so you need to **understand your data** and then hit it with the classifier you think will work with it... try to make small plots of your data and try to visualize it.. the best guys in the business are the ones who understand DATA... try to getting in the habit of visualizing data.. at the end of the day, you need to understand your data.

All the best with your adventures ahead ! :)
> 2 votes

# Answer
You haven't said anything about exploration of the feature representation, which can be very important in this sort of problem. A bag-of-words representation will limit your accuracy and FPR. Can you extract features from the headers which would supplement bag-of-words? Are there bigrams which are commonly found in spam but no t non-spam (or vice versa)? Are spam emails unusually short, reference currencies, or unusually likely to contain an attachment of a certain kind? Adding features which help the algorithm distinguish between spam/not-spam is one of the most powerful things you can do to improve accuracy/reduce error.
> 1 votes

---
Tags: machine-learning, classification
---


# Question
Title: Error bound for minimum-degree spanning tree
I am reading *The Design of Approximation Algorithms* (Williamson and Schmoys; page 50 of this PDF) about solving the minimum-degree spanning tree problem of maximum degree 2 in polynomial time. The text states that we are going to find a tree $T$ with maximum degree at most $2\mathrm{OPT} +\lceil\log\_{2} n\rceil$ in polynomial-time. $n$ is the number of the vertices in the graph. Could someone clarify why $\log\_{2} n$ is placed there? The text gives no explanation what it is.

# Answer
It is $\sf NP$-complete to decide if a given a graph has a minimum-degree spanning tree of maximum degree 2. Because the problem is hard, we would like to compute an approximate solution (to the optimization problem).

What they do is that they show how to find a tree $T$ with $\Delta(T)$ being at most $2\text{OPT} + \log\_2 n$. The intuition is that the local search tries to make local improvements to a candidate tree, and when it can't make any improvements, it has found a *locally optimal tree*. It can then be shown that for any locally optimal tree, the maximum degree is at most $2\text{OPT}+\log\_2n$, where $n$ is the number of vertices. The explanation for the logarithmic term is given in Theorem 2.19; it results from a tight analysis.

The best we can hope to do assuming $\sf P \neq NP$ is to find a tree $T$ with $\Delta(T)$ being at most $\text{OPT}+1$. This in fact possible to do, and is shown in a later section of the book.
> 5 votes

---
Tags: algorithms
---


# Question
Title: Do all states in a DFA must be connected?
Could I construct (for some wired reason) a DFA that has a state that is not connected to anything, and it would still be legal?

I'm studying for a test, and I found a question that asks if an infinite DFA could represent a regular language, and I want to use a regular DFA and add all the infinite states not connected to the original. Can I do that?

# Answer
> 4 votes
As babou mentions, infinite deterministic automata are rather powerful. In fact, they can compute *all* languages. Consider the "universal deterministic automaton" which is a $|\Sigma|$-ary infinite tree, with one state per each string in $\Sigma^\*$. By choosing the set of accepting states to be $L \subseteq \Sigma^\*$, we obtain an automaton which accepts $L$.

Regarding connectedness, while a DFA need not be connected, every disconnected DFA is equivalent to a smaller one which is connected; the minimal DFA is always connected.

# Answer
> 4 votes
I suspect a trick question in the material you are studying - there are no DFAs with an infinite number of states in the first place.

in fact, the whole point of D/NFAs is their finiteness. if you could have an inifinite number of (reachable) states in your NFA you'd actually be able to recognize any language; just take for every word in your language the trivial deterministic recognizer and connect a global start state with $\lambda$-transitions to the start state of each of these automata.

# Answer
> 3 votes
You can certainly add as many disconnected states as you want. However, I think that the definition of DFA or NFA stipulates that the number of states is finite (that is what the **F** stands for). So it would not be a DFA. However, even with an infinity of states, it can certainly recognize a regular language, if appropriately built (as you suggest, for example).

The reason why the definition stipulates a finite number of states is that an infinite number of states will allow you to recognize about anything. After all, a Turing Machine is an automaton just like the DFA, but with an infinite number of states, that you can actually enumerate, as you can enumerate the transitions (also infinite in number).

I have not looked at it previously, but I believe that you can actually do much better than Turing Machine with a DIA (Deterministic Infinite Automaton). You have only countably many TM, but you have continuously many DIAs, as many as you have real numbers. So I should expect that they would do things one does not even expect from TM.

On the other hand, anything they do, they will do in finite number of steps, so that remains a limitation (as compared to Zeno machines, or machines using looping time-lines). I did not see anything in a fast look on the hypercomputation page of wikipedia.

I am sure someone has worked on continuous machines (I do not dare call them *real* machines, *real numbers* are enough of an abusive claim). Maybe looking at work on computable reals, and related literature can put some light on this.

They can solve the halting problem for ordinary TM. You just follow the usual diagonalization construction that describe a solution for the halting problem. Since you do not require that construction to be describable by an ordinary Turing Machine, there is no contradiction. Isn't this a happy world?

The only difficulty, albeit a minor one, is that we do not know how to implement them. Miracles are not of this world.. . yet.

---
Tags: automata, finite-automata
---


# Question
Title: Can you use a Bayes classifier to determine if something is NOT in a defined class?
I know I can use a Bayes classifier to determine if something is one of N classes, but can I also determine if something is NOT in any of the predefined classes? Or will a Bayes classifier only find the closest class?

# Answer
Create an extra class whose membership means "belongs to none of the predefined classes".
> 2 votes

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


title: Unification --- most specific unifier

text:
# Question
Title: Unification --- most specific unifier
In unification, given a set of equations, a standard problem is to compute a most general unifier (mgu). I am interested in a somewhat reversed problem. Imagine having a set of equations that do not have an mgu, like this one:

```
x = a
x = b

```

`x` here is a variable, whereas `a` and `b` are terms. I am interested are there any algorithms that could find a possible replacement for `a` and `b` such that the resulting equations have mgu? In the above example, that would be `a -> y, b -> y`, `y` being a variable. Lets call this a *fix*. I am particularly interested in most specific fixes. I could not find anything so far, but this seems like a natural problem, or not?

# Answer
> 4 votes
I found out that such a thing is called anti-unification. This problem was addressed by Plotkin and Reynolds. Here is a brief overview.

# Answer
> 3 votes
In rewrite theory, you often want confluence of your system: if $$ u\_1\leftarrow t\rightarrow u\_2$$

Then there is some term $v$ such that $$ u\_1\rightarrow v\leftarrow u\_2$$

It is possible to tell whether a set of rewrite rules is confluent by examining the critical pairs: pairs of rules $t\_1\rightarrow u\_1,t\_2\rightarrow u\_2$ and an instance $\theta$ such that

1. $t'\_1\theta = t\_2\theta$
2. $t'\_1$ is a subterm of $t\_1$ at position $p$.

You can then add the equation $u\_1\theta = t\_1\[u\_2\theta\]\_p$ to make the system confluent.

This suggest an approach to your problem: look at your equations as rewrite rules, then consider the critical pairs: they tell you which equations need to hold to make your system unifiable.

---
Tags: algorithms, logic, unification, equality
---


# Question
Title: How to get a base-3 representation of an integer using a stack?
Assuming that a stack data structure is available, how can this data structure be used to compute a representation of an integer in base three? For example, the algorithm for `printBase3` would return `12020` on input `141`.

# Answer
> -2 votes
ok I think I found the solution to my question

So if n = 141, 12020 would be printed to the screen.

Solution:

```
          public static void printBase3(int n){
           if (n/3 == 0)
           System.out.print(n);
          else{
          printBase3(n/3);
          System.out.print(n%3);
          }
        }

```

---
Tags: stacks
---


# Question
Title: Why does the following function distribute things in a binomial distribution?
I was reading the following FDS paper:

https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf

and it says that the the following hash function does not distribute things uniformly (instead it creates a binomial distribution):

$$i = (hash(g + t)) \pmod n$$

while the following did distribute things uniformly:

$$i = (hash(g) + t) \pmod n$$

Why does the above distribute things evenly while the other one doesn't?

g = is the global UID for a blob

t = tract number. (tract is the measure/units of reads and writes to a blob).

n = is the number of tract servers or a multiple of the tract servers.

hash = SHA-1 (according to the paper)

---

Paper Reference:

Title: Flat Datacenter Storage

Author(s): Edmund B. Nightingale, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, Yutaka Suzue

Institution(s): Microsoft Research, Univeristy of Texas at Austin

# Answer
The second function is easier to explain: it sends tract $t$ to position $t + h \pmod{n}$, where $h = hash(g)$. The function $t \mapsto t + h \pmod{n}$ is injective (one-to-one), and so every index $i$ gets mapped exactly once (in fact, by $i - h \pmod{n}$).

For the first function, we can think of $t \mapsto hash(g+t)$ as a random function (this is a common assumption whenever hash functions are involved; the fact that we use SHA-1 is completely irrelevant). Therefore for each fixed index $i$, the probability that $t$ is mapped to $i$ is $1/n$, and the total number of $t$s mapped to $i$ is distributed $\mathrm{Bin}(1/n,1) \approx \mathrm{Po}(1)$, that is it has binomial distribution which is approximated well by a Poisson distribution with mean $1$.
> 4 votes

---
Tags: distributed-systems, hash, hash-tables
---


# Question
Title: Why does appending permutations of servers at the end of hash table avoid bottlenecks?
I was reading the following FDS paper:

https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf

The paper has a TLT (tract locator table) for identifying where to write in each server. The table is basically a hash table where the index i maps to some (tract) server to do writes to or reads to.

Say that there are n (tract) servers. It says that if instead of just having index i mapping to server i, if instead we appended n more indexes mapping to some permutation of the servers (and having a table of size 2n in this example), we can avoid having a bottleneck at any specific server when doing reads or writes. Basically it claims that as we append more permutations the better. Why is this?

Why would this be?

Just for reference the index mapping function is:

$$i = (hash(g) + t) \pmod n$$

where:

g = is the global UID for a blob

t = tract number. (tract is the measure/units of reads and writes to a blob).

n = is the number of tract servers or a multiple of the tract servers.

hash = SHA-1 (according to the paper)

---

Paper Reference:

Title: Flat Datacenter Storage

Author(s): Edmund B. Nightingale, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, Yutaka Suzue

Institution(s): Microsoft Research, Univeristy of Texas at Austin

# Answer
> 4 votes
Adding permutations isn't about preventing slow servers from becoming bottlenecks, rather it's about dispersing a convoy once one forms behind a slow server. Because of the way tract locations are hashed, sequential reads of any blob always walk the tract locator table in the same order. Suppose you have six tract servers and your tract locator table looks like this

123456

and server 3 is slower than the others. Since sequential readers walk the table in the same order the slowness of server 3 will cause a convoy of sequential clients to form waiting for server 3. Once server 3 serves them, they all move on server 4 which may also become overloaded. Then 5, then 6, and before long the convoy is big enough to hammer each server in turn instead of spreading the load evenly across all of them.

If your tract locator table looks like this

643512623154125364213546

i.e. four permutations of 123456, events transpire differently if there is a slow server. If server 3 is slow, satisfied sequential readers will move from server 3 to servers 5, 1 or 6 depending on where they are in the table. This instead of all sequential I/O clients turning their attention to the same server after visiting server 3. The extra permutations have the effect of breaking up convoys if they form and lessening the likelihood of convoys forming at all.

---
Tags: distributed-systems, hash, hash-tables
---


# Question
Title: transformation of constraint satisfaction to SAT
How can any Constraint satisfaction problem be converted to an instance of Satisfiability? I have a CSP and i know its NP hard to solve it, but i would like to convert to an instance of k-SAT, but im not sure of any algorithm for transformation

# Answer
> 5 votes
I'm not sure what you mean by CSP, but suppose that you mean the following: there are $n$ binary variables and $m$ constraints. Each constraint is associated with a $k$-tuple of (distinct) variables, for some $k$ depending on the constraint, along with a subset of $\\{0,1\\}^k$ which is the allowed assignments for the $k$-tuple of variables.

For example, graph coloring, or rather, whether a given graph $G$ can be $\chi$-colored, can be viewed as a CSP. If there are $n$ vertices (we identify the vertex set with $\\{1,\ldots,n\\}$) then we have $n$ groups $x\_1,\ldots,x\_n$ of $\lceil \log\_2 \chi \rceil$ variables. For each $i \in \\{1,\ldots,n\\}$ there is a constraint on each group $x\_i$ stating that the assignment for $x\_i$ is the binary encoding of a number in the range $\\{0,\ldots,\chi-1\\}$. For any two connected vertices $(i,j)$ there is a constraint on both groups $x\_i,x\_j$ stating that $x\_i \neq x\_j$. This CSP is satisfiable iff $G$ is $\chi$-colorable.

In order to convert such a binary CSP to a SAT instance, we replace each constraint with the corresponding CNF. Continuing the example above, if $\chi = 2$ then for any $i,j$ there is a constraint $x\_i \neq x\_j$ which we realize as $$(x\_i \lor \lnot x\_j) \land (\lnot x\_i \lor x\_j). $$ The resulting CNF is satisfiable iff the CSP is. You can use the standard reduction to convert this CNF to a 3CNF if you wish.

We can also handle CSPs which are not binary, i.e., in which the variables are not binary but rather have some finite domain. The idea is similar to how I described coloring as a CSP above, and left to the reader.

---
Tags: satisfiability, constraint-programming
---


# Question
Title: Quantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?
In class last week, my professor commented and said that Turing machines are used as a standard measure/model of what is computable and are a helpful basis of discussion for that subject. She also said that all variants of Turing machines are proven to be computationally equivalent -- read, just as powerful -- as one another. W

I commented and said yesterday that, regarding computability power, I noticed that some turing machines can take incredibly large amounts of time to compute something very simple, while a turing machine with more tapes can compute something in a lower asymptotic complexity with respect to the number of steps needed.

She said that with respect to class discourse, the runtime of a particular algorithm on a turing machine does not change the definition of computability, or the power with which we measure computability. "We're concerned about what is computable, not what is efficiently computable at this point." So, it doesn't matter if the turing machines has more and more tapes, and more and more tapes implies that it can compute in lesser steps. Okay, I get that we're really focusing on what IS computable, not the speed at which we can compute it.

Something about that just bothers me, because up to this point, algorithms with abnormally large asymptotic time and space complexity really define the limits of what is, maybe I should say, practically, computable.

So, I have a couple of questions:

1. Suppose we have a model for a quantum turing machine, this must be equivalent to a "regular" turing machine, right?

So, the answer to that question I think really is going towards my reason for writing this post. Does quantum computing technology antiquate the classical definitions of what is computable via a turing machine?

2. Is this something above my head and should I delete this post? I don't mean to be precocious, I just didn't see a question similar to mine.

# Answer
You're mixing up *computability theory* (also known as *recursion theory*) and *complexity theory* (or *computational complexity*). Computability theory is a vast mathematical subject which studies the ramifications of the concept of *computation*. It does not deal with the complexity of computation. As your professor mentions, all (Turing-complete) computation models are the same from the point of view of computability theory. Computability theory, while an interesting mathematical subject, is not a good model for real-world computation for this reason, as you mention.

Complexity theory started its life as an attempt to address this issue. Complexity theory studies how difficult it is, in terms of time and space, to compute certain predicates and functions. From the point of view of complexity theory, not all computation models are the same, and Turing machines are taken as the reference model. However, even complexity theory is not very realistic, since it treats all computational models *polynomially equivalent* to Turing machines in the same way (two models are polynomially equivalent if any problem solvable in time $T(n)$ and space $S(n)$ in one model can be solved in time $T(n)^c$ and space $S(n)^c$ in the other, where $n$ is the input size and $c$ is some positive constant). For example, Turing machines are not good models for real computers since they do not support random access (accessing an arbitrary point in memory in time $O(1)$). Of course, random access can be simulated by a Turing machine, but the simulation can be slow. It is often said that sorting can be done in time $O(n\log n)$, but this is not the case for Turing machines, which probably require $\Omega(n^2)$ or move even for sorting integers. Therefore in the area of *algorithms*, other models such as the *RAM machine* replace Turing machines.

Finally, quantum computers can be modelled in several different ways, such as the quantum Turing machine. Everything computable using quantum computers is also computable using classical computers, and so from the point of view of computability theory, quantum Turing machines are just another equivalent model. However, quantum Turing machines are widely conjectured not to be polynomially equivalent to classical Turing machines: for example, factoring and discrete logarithm are "easy" for quantum Turing machines (solvable in polynomial time), while it is conjectured that they are "hard" for classical Turing machines (cannot be solved in polynomial time; though some people think that integer factoring might be solvable in polynomial time). So from the point of view of complexity theory, quantum Turing machines *are* different from classical Turing machines.
> 44 votes

---
Tags: turing-machines, quantum-computing
---


# Question
Title: Resizing and aliasing in computer science
If you resize an 1000x1000 raster image to 10x10 and resize it back to 1000x1000 is this considered to be an example of aliasing?

# Answer
When you resize to a lower resolution, there are several ways to do it. If you average values of the pixels that merge into a single one, you simply have a loss of resolution, which amounts to keeping only the lower spatial frequencies (counting frequencies relative to image size, not to pixel size). However, if you reduce resoution by sampling, i.e. replacing a bunch of pixels by the value of one of them, you may overplay high frequencies, not meaningful at the given sampling (spatial) frequency, leading to all kinds of artefacts such as moiré effects for images.

When you recreate the image at former resolution, you cannot in principle recreate lost information. But you try to make educated guess as to the effect most likely to occur or not to occur in most images. Hence, you apply some reprocessing to the image so as to eliminate unlikely phenomena, or play down phenomena that you know could not have survived the initial size reduction (they may or may not have been there, but you know that later presence is not due to original existence).

Typically, as you know that the image reduction has necessarily lost some higher spatial frequencies, or distorted their role, you can choose to eliminate or play doen those frequencies at the recreated higher resolution, as they do not originate from the initial image.

For example, if you had a large geometric image, reduction and back resizing will produce a staircase effect on most straight lines. These abrupt changes correspond to high spatial bandwith. By removing these high frequencies, you will recreate shaded areas that smooth down the staircase effect on the straight lines.

Aliasing has to do with the artefact due to the combined effect of sampling and reproducing back a sampled observation of a theoretically continuous phenomenon (or considered as such because its initial resolution is significantly greater than the sampling rate), may be an image, a sound, a film,etc. As seen above, the sampling technique does matter. Antialiasing consist of the techniques used to eliminate artefacts known as likely to occur. It cannot recreate lost information unless you knew separately that the processed information has to satisfy some constraints, which antialiasing can then use to improve the image. For example, you may know that geometric images use straight lines more often than small staircases.

Wikipedia has more technical information.
> 1 votes

---
Tags: terminology, image-processing, graphics
---


# Question
Title: Demonstrate that DPDA is closed under complement by construction
I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I got has something that at the end does not fit. Could you give me a hand?

The main problem happens with the **ε-moves**. A PDA could finish reading its input in a non-final (rejecting state) but can still move to a final (accepting) state through an **ε-move** and end up accepting the string. This means that just adding a dead state and complementing the states does not work. I already solved the problem of possible infinite sequences of **ε-moves**, so that is not a main part of my question.

**EDIT:** As far as I understand, if the DPDA reaches *end of input* and is in an accepting state and moves to a rejecting state through an **ε-move** it would still accept it (as it reached a final state with no input symbol left to read).

Please let me know if I can be more clear.

# Answer
> 5 votes
I didn't have time to write this before but I found an answer. Here is what I did:

Let $O$ be the original $PDA$. We will construct a new $PDA$, call it $M$ ($M$ stands for modified).

To find the complement of $O$, we can flip final states to be non-final states and vice-versa. It is the same procedure as for finite automatas. However, there is a subtlety. The main problem is that in the original PDA $O$ the input $w$ can lead to a state $S$ which is not a final state but could perform an $\epsilon-move$ and get to an accepting state $S'$. Flipping states as mentioned above, would make $M$ end in $S$ with the input $w$ which would be a final state (causing $M$ to accept accept the input) even though it will later make an $\epsilon-move$ to $S'$, a non-accepting state. Therefore, both $O$ and $M$ will accept $w$. Something similar happens if $S$ was a final state and $S'$ a non-final state reachable from $S$ through an $\epsilon-move$.

In order to overcome this problem, we must make sure that all $\epsilon$-moves happen before we read the next symbol. That is, we will enter a reading state only when a path of $\epsilon$-moves is followed and we reach a state which has no $\epsilon$-move available. We call these latter states **reading states**, as they need an actual symbol to perform a new transition.

Define $M$'s states to be tuples of the form $\<q, n\>$ where $q \in Q$ ($Q$ is the set of states of the original $PDA$) and $n \in \\{1, 2, 3, 4\\}$.

* If $\delta(q, \epsilon, X) = \<q', \alpha\>$ in $O$, let $\delta(\<q, 3\>, \epsilon, X) = \<\<q', 2\>, \alpha\>$ in $M$ if $q \in F\_O$.
* If $\delta(q, \epsilon, X) = \<q', \alpha\>$ in $O$, let $\delta(\<q, 3\>, \epsilon, X) = \<\<q', 3\>, \alpha\>$ in $M$ if $q \notin F\_O$.
* If $\delta(q, \epsilon, X) = \<q', \alpha\>$ in $O$, let $\delta(\<q, 2\>, \epsilon, X) = \<\<q', 2\>, \alpha\>$ in $M$.
* If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(\<q, 2\>, \epsilon, X) = \<\<q, 1\>, X\>$ in $M$
* If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(\<q, 3\>, \epsilon, X) = \<\<q, 4\>, X\>$ in $M$

In those definitions, we let states of the form $\<q, 2\>$ and $\<q, 3\>$ consume $\epsilon$-moves imitating $\epsilon$-moves of $O$ until there are no more. Then, perform an $\epsilon$-move to a reading state. Now for the reading states,

* If $\delta(q, a, X) = \<q', \alpha\>$ in $O$, let $\delta(\<q, 1\>, a, X) = \delta(\<q, 4\>, a, X) = \<\<q', 3\>, \alpha\>$ in $M$.

By making this definition, we consume a symbol of the input and move to a state of the form $\<q, 3\>$ to begin a new series of $\epsilon$-moves.

Finally, make states of the form $\<q, 4\>$ be accepting states of $M$ if $q \notin F\_O$. Also, make $\<q\_0, 3\>$ the initial state of $M$ if $q\_0$ is the initial state of $O$.

---

What we did is the following:

Create 4 "floors" of states (the second element of the tuple in states of $M$ determines in which floor we are). Floor 3 imitates $\epsilon$-moves of $O$ possibly reaching an accepting state $q$ of $O$. If that is the case, we move to floor 2; otherwise, we remain in floor 3. When there are no more $\epsilon$-moves to follow of $O$, we define $\epsilon$-moves of $M$ to reach a reading state. Floors 1 and 4 correspond to reading states. If we were on floor 3, we go to floor 4. If we were in floor 2, we reach floor 1. Only states $\<q, 4\>$ (states that are in floor 4) are accepting states of $M$, provided that $q$ is not an accepting state of $O$.

Please let me know if I made a typo at writing this. I could've easily mistaken. Also, my English is not very good so feel free to edit and rephrase things better.

# Answer
> 1 votes
There is a proof by construction in Sipser's *Introduction to the Theory of Computation* (3$^{rd}$ edition has a section on DCFLs) that identifies reading states of the automaton by splitting up any state that reads and pops at once. Only these reading states can be final states, and to get the complement DPDA you only reverse accepting behavior within the set of reading states.

# Answer
> -2 votes
You can assume the automaton to be free of $\varepsilon$-transitions without loss of generality.

This can be shown by using the standard construction from CFG to PDA applied to a Greibach normal form. In Silent Transitions in Automata with Storage, G. Zetzsche has recently presented a construction directly on automata.

**Potential caveat:** I kind of assume that said standard construction yields a DPDA if we apply it to a suitable, i.e. "deterministic", grammar and that this suitability survives transformation in Greibach normal form.

---
Tags: formal-languages, automata, closure-properties, pushdown-automata
---


# Question
Title: Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$
I need to find a context-free grammar for the following language which uses the alphabet $\\{a, b\\}$ $$L=\\{a^nb^m\mid 2n\<m\<3n\\}$$

# Answer
> 1 votes
**Hint**: Can you do $$L=\\{a^nb^m\mid m=3n\\}$$

Try it also for: $$L=\\{a^nb^m\mid m=3n-1\\}$$

Then you might want to be able not to always have that many $b$.

And there is a bit more to take care of.

# Answer
> 0 votes
Let's start with a grammar for the language $$ \\{ a^n b^m : 2n \leq m \leq 3n \\} $$ The idea is that if $c\_1,\ldots,c\_n \in \\{2,3\\}$ then $2n \leq c\_1 + \cdots + c\_n \leq 3n$. We can implement this idea in the following way: $$ S \to aSbb \mid aSbbb \mid \epsilon $$

Now we want to rule out $m = 2n$ and $m = 3n$. We can enforce this by requiring $c\_1 = 2$ and $c\_n = 3$ (note that when $n \leq 1$, no $m$ satisfies $2n \< m \< 3n$). This leads to the following grammar: $$ S \to aSbb \mid aSbbb \mid aabbbbb $$

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


# Question
Title: What are all the differences between the Gibbs phenomenon artefects and JPEG artefacts?
I thought the Gibbs phenomenom is the result of Fourier analysis estimation (but was it Fourier Series estimation or can it also be Fourier Transform estimation?)

JPEG uses the Discrete cosines Transform. A DCT is similar to a Fourier transform in the sense that it produces a kind of spatial frequency spectrum.

But what are the differences between the Gibbs phenomenom artefacts from Fourier and the artefacts from the Discrete Cosine?

# Answer
> 7 votes
There are three kinds of JPEG artifacts. The first and (arguably) most important one is described in Yuval's answer: To a first order the problem is that under high compression all the high frequency information is discarded, and the lowest frequency information remaining is the average color of each 8x8 square. When you take the inverse but leave out the high frequency information, the result is a square of a single color. A decoder can't perform any low-pass filtering to remove the blocky effect because that would cause significant error in the case that you used a high-quality setting to encode.

The second artifact is *exactly* the Gibbs phenomenon. Fine detail in the image will get "halos" if highly compressed. For example, here is a 64x64 image with a single dot at pixel 35,35:

Here's the same image saved by GIMP as a Jpeg with low quality (25%):

There is a halo around the pixel in the 8x8 block the pixel is in. (To make it easier to see, here is an image of that block scaled up by a factor of 8:

This effect is called *ringing*. (In audio processing it really produces a ringing noise.) This occurs because high levels of compression are chopping out the highest frequencies, which leaves ripples at the highest remaining frequency. (I.e., it's the Gibbs phenomenon.)

The third artifact is the inverse of the Gibbs phenomenon. The Gibbs phenom is because the multiplication of the brick-wall filter in the frequency domain is equivalent to convolution with the sinc function in the time domain. The inverse problem is using a box-car filter for downsampling in the time domain leads to a sinc function in the frequency domain, and thus a large amount of high-frequency noise gets aliased into the resulting downsampled image. This is essentially what JPEG is doing when it breaks the image into 8x8 blocks. The lowest-frequency component of each 8x8 block is the average (box-car) of the pixel values in that 8x8 block, so actually contains significant high-frequency aliasing. For example, consider the following image. (It is 64x64 with a horizontal stripe each third pixel. So has significant amount of high frequency information.

Now if I encode with jpeg at very low quality I get this:

The high frequency information from the original image is not being completely filtered by the box-car averaging, and thus gets aliased into a lower-frequency error in the image.

# Answer
> 4 votes
The artefact that you see in JPEG comes from the fact that JPEG divides the image into $8\times 8$ blocks of pixels and compresses them separately. The $8\times 8$ blocks are visible very clearly in the JPEG appearing in your question. When the image is decompressed, often there is no effort to smooth the boundary regions, and this results in a "blocking" effect.

(For the curious: in fact JPEG first converts your image into the YCbCr color space and downscales the Cb and Cr parts by 2 in one or two dimensions. Then each of the Y,Cb,Cr planes is compressed separately. So the effective blocks for Cb and Cr are even larger than $8\times 8$.)

---
Tags: image-processing, data-compression, graphics, signal-processing
---


# Question
Title: What does it mean that numbers are "totally ordered", in the Paxos Made Simple paper?
I was studying Paxos from the paper by Lamport called "Paxos Made Simple".

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

On page 3, it says

> Since all numbers are totally ordered, condition P2 guarantees the crucial safety property that only a single value is chosen.

where P2 is the following

> If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

What does it mean for numbers to be totally ordered? How is this property essential for condition P2 to guarantee safety?

# Answer
Totally ordered means that there exists an order relation such that given any two elements, one is greater than the other. In other words, there are no incomparable elements. For example, the real numbers are totally ordered: either $x \le y$ or $y \le x$. Counter-example: set inclusion $\subseteq$ is an order relation, but $\\{0\\}$ and $\\{1\\}$ are incomparable.

Intuitively, a total order is one where you can lay all the elements on a line, where moving along the line always increases the value. (This is not mathematically true because some orders are too “dense” to fit.)

Suppose that two proposals numbered $n\_1$ and $n\_2$ are chosen, with values $v\_1$ and $v\_2$ respectively. The desired safety property is that the values are in fact the same: $v\_1 = v\_2$. By condition P2, if $n\_1 \le n\_2$, then proposal $n\_2$ is higher-numbered than proposal $n\_1$, so its value $v\_2$ is equal to $v\_1$. Similarly, if $n\_2 \le n\_1$ then $v\_1 = v\_2$. The fact that the integers are totally ordered implies that at least one of the propositions $n\_1 \le n\_2$ and $n\_2 \le n\_1$ is true, and therefore either way $v\_1 = v\_2$.

What condition P2 means in some idealized way is that if a choice is made, all subsequent choices will be for the same value. However, “subsequent” doesn't quite work out, because the numbering of the proposals doesn't necessarily correspond with the order in which they are made in real time: different nodes in the network can make proposals before they are aware of each other, so numbers can't be assigned to proposals in chronological order. Solving this problem is a large part of working out a consensus algorithm.
> 4 votes

---
Tags: algorithms, algorithm-analysis, distributed-systems
---


# Question
Title: Why should leaf nodes in a red-black tree be black?
From the property of Red-Black Trees we know that:

* All leaves (NIL) are black. (All leaves are same color as the root.)(Comren et al "Introduction to Algorithms")

But what is the reason that we should enforce them as Black, even though they're NILL's?

# Answer
> 3 votes
Take a uncolored leaf node, now you can color it as either red or black. If you colored it as red then you may have chance that your immediate ancestor is also red which is contradicting(according to basic principle). If you color it as black then no problem even though the immediate ancestor is red. And also no change in the number of black nodes from root to leaf paths(i.e every path get +1). This may be the possible reason behind that.

# Answer
> 3 votes
It's simply a part of the definition of a red-black tree. It is also necessary to maintain one of the other rules associated with red-black trees: If a node is red, then both its children are black.

---
Tags: terminology, data-structures, search-trees, dictionaries
---


# Question
Title: Analysis of Algorithms: Applying Concepts
I believe I understand the concepts of algorithm analysis. However, I'm not fully confident in applying those concepts. I'd appreciate help in bridging the gap between concept and application.

I understand that if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$ then $f(n) \in \Theta(g(n))$

Essentially, when Big-O and Big-Omega form the upper and lower bounds of algorithmic performance, Big-Theta represents the optimal solution. But how does one determine those bounds and thus optimal performance?

How does/should one determine *Big-O, Big-Omega, Big-Theta* for the following algorithm?

```
int summation(int[] values)
{
  int sum = 0;
  for(int i = 0; i < values.length; i++)
  {
    sum += values[i];
  }
}

```

# Answer
Typically, when presented with a piece of code, your first step is to come up with a formula which gives the running time $T$ of your code as a function of the input size. In your example, the function takes an array, so a natural way to represent the input size is the number of elements in the array, `values.length`, which we can call $n$.

So, we now want an expression for $T(n)$. To get this, we should assign a "cost" to each statement, and then determine how many times each statement is executed. The costs are somewhat arbitrary and may vary across real computer hardware, but some assumptions can reasonably be made; in particular, we usually assume simple statements have a constant cost with respect to the input size. In your example, we might assign costs like this:

```
int summation(int[] values)
{
  int sum = 0;                       // cost = A, executed once
  for(int i = 0;                     // cost = B, executed once
      i < values.length);            // cost = C, executed n + 1 times
      i++)                           // cost = D, executed n times
  {
    sum += values[i];                // cost = E, executed n times
  }
}

```

Now, to get the expression for $T(n)$, multiply each statement's cost by the number of times it's executed. Here, we get $T(n) = A \times 1 + B \times 1 + C \times (n + 1) + D \times n + E \times n$. This comes out to $T(n) = (A + B + C) + (C + D + E) \times n = c\_0 + c\_1n$ for constants $c\_0, c\_1$.

In this example, happily, we have a closed-form expression for $T(n)$. As such, we can make an educated guess that this function is $\Theta(n)$, since $T(n)$ is a linear function. To prove this is true, we can try to prove it's both $\Omega(n)$ and $O(n)$.

By definition, $T(n) = \Omega(n) \iff \exists c \> 0, n\_0 \ge 0 \mid n \ge n\_0 \rightarrow T(n) \ge cn$. Our job now is to demonstrate that there is an $n\_0$ and $c$ such that $T(n) \ge cn$ for all $n \ge n\_0$. We have $c\_0 + c\_1n \ge cn$ for fixed constants $c\_0, c\_1$. We can solve this for $c$: $c \le c\_0/n + c\_1$. As long as we choose $c$ less than $c\_0/n + c\_1$, we have a valid choice for $c$; in particular, if we choose $c = c\_1$, we satisfy the inequality for all natural numbers, and can choose $n\_0 = 0$.

You can make a very similar argument for $O$; try choosing $c = c\_0 + c\_1$ in this case and complete the argument yourself. Once you know it's both $\Omega(n)$ and $O(n)$, you can conclude that it's $\Theta(n)$.

Of course, you don't really need to find the constants every time, but it can make an argument pretty convincing. If your $T(n)$ comes out to a expression which is the sum of powers of $n$, then you will always have that $T(n) = \Theta(n^x)$, where $x$ is the highest power to which $n$ is raised.

This gets significantly harder when $T(n)$ is recursive, i.e., when the expression for $T(n)$ involves $T$ itself; to solve problems like that, you'll often need to avail yourself of the Master Theorem or inductive proofs on the input size. Cross that bridge when you come to it, though.
> 1 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis
---


# Question
Title: Show that this algorithm does not work for determining convex polygons
**Context**

Consider this algorithm. If the set $\\{\angle p\_ip\_{i+1}p\_{i+2} : i=0,...,n-1\\}$ does not contain left and right turns, output "yes the polygon is convex"; otherwise, "no".

**My answer**

Consider this nonsimple polygon having 4 vertices; the algorithm above will output "yes" as the set of points does not contain both left and right turns, yet the polygon is not convex. Is this a good counterexample rendering the above algorithm incorrect?

Thanks in advance.

# Answer
> 3 votes
A simple counterexample is a pentagram (http://en.wikipedia.org/wiki/Pentagram). It contains right turns (if you go in clockwise direction) only, but it is not convex. The above algorithm will incorrectly say pentagram is a convex polygon. It's actually a complex polygon.

In other words, algorithm might fail if the input polygon is complex.

---
Tags: algorithms, graphs, computational-geometry
---


# Question
Title: Is subset sum with a fixed target sum NP-complete?
I've read that subset sum is NP-complete. What happens when I change the decision problem to look for a constant number? So the decision problem would look like this:

> Input: A collection of nonnegative integers A and a nonnegative integer b,
>
> Output: Boolean value indicating whether some subset of the collection sums to **10**

Would this still be NP-complete? I don't believe you would be able to reduce every other NP-complete problem to it.

# Answer
> 5 votes
We can throw away all zeroes in $A$. If a subset of $A$ sums to $10$, then this subset contains at most $10$ elements. There are at most $10|A|^{10}$ such non-empty subsets, so we can go over all of them in polynomial time.

# Answer
> -3 votes
Subset sum problem with only one number is probably not NP-complete, because there is a polynomial algorithm that solves this problem.
If it is NP-complete, then P=NP.

---
Tags: complexity-theory, np-complete, decision-problem
---


# Question
Title: Polynomial Hierarchy --- polynomial time TM
Consider, for example, the definition for $\Sigma\_2^p$ complexity class.

$$ x \in L \Leftrightarrow \exists u\_1 \forall u\_2 \\;M(x, u\_1, u\_2) = 1, $$

where $u\_1, u\_2 \in \\{0,1\\}^{p(|x|)}$, for some polynomial $p$. Here, $M$ must be polynomial time. But polynomial in the size of what exactly? For example, if we choose (guess) some $u\_1$, do I consider it to be fixed size when talking about time complexity of $M$? More precisely, should $M$ be polynomial only in the size of $x$?

An example. Consider the problem whether, given a graph $A$, there exists a graph $B$ such that $B$ is subgraph isomorphic to $A$.

$$A \in L \Leftrightarrow \exists B \\; \text{SubGraphIsomorphic}(A, B) = 1 $$

Now, subgraph isomorphism is NP-complete. If $B$ is fixed, then there is a TM that implements $\text{SubGraphIsomorphic}$ in deterministic polynomial time. If $B$ is not fixed, then I cannot claim such a thing unless I know $\sf P=NP$. Is this problem in $\Sigma\_{1}^{p}$, i.e. $\sf NP$? (Ok, this problem has trivial solutions, but I hope it helps to pinpoint my confusion.)

My confusion generalizes for all $\Sigma\_{i}^p$.

# Answer
Your definition of $\Sigma\_2^P$ is a bit misleading. Both $u\_1$ and $u\_2$ have to be bounded in length by some polynomial in $|x|$, and this usually forms part of the formula rather than part of the descriptive text. The predicate $M$ has to be polynomial time in the combined input length, which is the same as being polynomial time in $|x|$ since both $u\_1$ and $u\_2$ have length polynomial in $|x|$.

You have not described the predicate *SubgraphIsomorphic* correctly. You are given *two* graphs $A,B$, and you have to decide whether $B$ is isomorphic to a subgraph of $A$. We write it as an NP-predicate as follows: $$(A,B) \in \mathrm{SubgraphIsomorphic} \leftrightarrow \exists |P| \leq |(A,B)| \mathrm{Isomorphic}(A,B,P), $$ where $\mathrm{Isomorphic}(A,B,P)$ is true if $P$ encodes an injection from the vertex set of $B$ to the vertex set of $A$, and $(x,y)$ is an edge of $B$ iff $(P(x),P(y))$ is an edge of $A$. This is a polytime predicate. Moreover, the injection can be coded in length polynomial in the input $(A,B)$ (for simplicity, I'm assuming that the encoding is such that $|P| \leq |(A,B)|$).
> 3 votes

---
Tags: complexity-theory, time-complexity, complexity-classes, polynomial-time
---


# Question
Title: Why does left recursion have to be eliminated?
For example,

Let the Grammar be:

```
S->Sa|B

```

Thus, `S->Sa->Saa->...->Saa...aaa->Baa...aaa`

What's wrong with this?

Why is right recursion a solution to the problem?

```
S->BS'
S->aS'|e

```

# Answer
> 3 votes
I am assuming that you are talking about context free grammars.

There is no difference between the two grammars. They are a different representation of the same set.

What do you mean by a problem?

Left recursion is a problem for LL(k) parsers, but they can handle right recursion. LL(k) parsers are preferred because of they use less stack space and they tend to be faster (not always though).

---
Tags: context-free, formal-grammars, compilers, parsing, left-recursion
---


# Question
Title: proving that if $\{w\$w^R | w \in L\}$ is context-free then $L$ is regular
I am trying to prove this following theorem, can someone help please?

Let $L$ be a language over the alphabet $\Sigma = \\{ a,b \\}$. If $L' = \\{ w\\$w^R \mid w \in L\\}$ is context-free, then $L$ is regular.

# Answer
> 3 votes
Here is a proof sketch. The idea is to take a context-free grammar for $L'$ and come up with a regular grammar for $L$.

Start with a grammar for $L'$. Say that a language $M$ is *symmetric* if it is of the form $\\{w \\$ w^R : w \in P\\}$ for some $P \subseteq \Sigma^\*$. Prove that every non-terminal in $L'$ generates a language of one of the forms $w, wM, Mw$, where $w \in \Sigma^\*$ and $M$ is symmetric. Consider two cases: the non-terminal generates a word without $\\$$, or it generates a word with $\\$$. In the first case, it's easy to see that it must generate a unique word. In the second case, every word it generates must contain $\\$$, and the words need to be "compatible" in some sense, which implies that it generates a language of the form $wM$ or $Mw$.

For each non-terminal generating $wM$ or $Mw$, we can come up with a non-terminal generating the language $M$. This is because context-free languages are closed under this operation. So we can assume without loss of generality that each non-terminal either generates a unique word or a symmetric language.

Substitute all non-terminals generating unique words. All remaining productions must be of the form $A \to w B w^R$ or $A \to w \\$ w^R$. We can come up with an equivalent grammar in which $w$ is always a symbol in the first case and empty in the second, so that all productions are now either $A \to a B a^R$ or $A \to \\$$. If we replace these productions with $A \to a B$ and $A \to \epsilon$ then we get a right regular grammar for $L$.

For completeness, let me mention that the converse to the theorem also holds. You can see this by reversing the construction: from a right regular grammar for $L$, construct a context-free grammar for $L'$.

# Answer
> 2 votes
Since $L'$ is context-free, we consider a CF grammar $G=(V,T,P,S)$ for it, supposed to be reduced (all symbols are reachable and productive) and in Chomsky Normal Form (CNF).

We call *spine* any symbol that derives on a string containing $\\$$, including $\\$$ itself.

The start symbol $S$ is a spine. No right hand side of a rule contains more than one spine, since every string in $L$ contains exactly one $\\$$.

Other than the spine, if any, no rule contains a symbol deriving on a recursive symbol. Because of CNF, a recursive symbol can generate terminal strings of any length. Suppose a rule $\pi$ contains a symbol deriving on a recursive one on the left of the spine, and a word $w\\$w^R$ derived with that rule. Then the recursive symbol could be used to pump the length on the left side of the $\\$$ without changing the other part, thus getting out of the language $L'$. Similarly for the right side.

Hence, all the non-spine symbols generate only finite sets of strings.

Then consider the grammar $H$ obtained from $G$ by removing all symbols right of the spine in all rules that have a spine, and also the $\\$$ symbol itself. It clearly generate the language $L$ (by induction on derivation length). For every remainning non-spine non-terminal that derives on a set of $n$ terminal strings, replace each rule using it by $n$ rules, where it is successively replaced by each of the terminal strings. This does not change the language, and the grammar $H'$ for $L$, thus derived from $H$, is now right-linear. Hence $L$ is regular.

The converse is easily proved by building a PDA. It uses the finite control of a NFA for $L$ to check the first half of the string, while pushing it onto the stack. When it reads the $\\$$, it just goes in popping mode and only check that each symbol read is equal to the stack top, which is then popped. If the stack is empty when the string is read, it is accepted.

**Generalisation**: Reading Yuval Filmus' answer (which I did after writing this one), I realized that it was even simpler to show that non-spine non-terminal generate a single terminal string, though it is a stronger property than generating a finite set of strings. I though at first I had made a mistake, but it is not the case, and the proof does hold. Actually, the proof would also hold with an even weaker property, that each non-spine non-terminal generates a regular set of terminal strings.

Then, it occurred to me that if weaker properties are enough to carry the proof, then it should be possible to extend the proof to more complex situations were only a weaker property can actually be proved. Here is an example, based on my current proof asserting finiteness of the set of terminal strings generated by a non-spine non-terminal:

Let $L'$ be a language included in $\\{w\\$w'\mid w\in L \wedge |w|=|w'|\\}$and such that $\forall w\in L,\\;\exists\ w\\$w' \in L'$, then $L'$ is context-free implies that $L$ is regular

Note that this more general result implies trivially the result for the question asked by the OP.

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


title: "Minimum Stack"

text:
# Question
Title: "Minimum Stack"
I am now preparing for a test in my algorithms course and I have stumbled upon a question about a data structure which seems too trivial for me, but is probably not trivial at all.

The question is:

> Let a "minimum stack" be a data structure that supports the following functions:
>
> 1. Creating a new empty data structure.
> 2. Inserting element X.
> 3. Returning the newest element and removing it from the data structure.
> 4. Returning the minimal element (the element with the smallest value). (without removing it)
> 5. Changing the minimal element's value to k. (Hint: say T is the number of elements added after the minimal element).

Now, I have thought about using a linked list which is isomorphic to an actual stack, hence elements can be added and removed only from the tail, but scanning the list from head to tail is possible.

I've checked and all the functions except 4 and 5 turn out to be O(1), but 4 turns out to be O(n) at best, and 5 turns out to be O(T).

My question is: How can I do 4 in O(1) time, so that all the other functions are also O(1)? I am not looking for full answers, just hints that will guide me to a full answer.

# Answer
> 1 votes
The trivial approach would suggest a Fibonacci based data structure, but I presume that removing the newest element would be non-ideal. Therefore maybe a sorted-list would be better. The complexities would be:

> 1. Insertion: O(n)
> 2. Delete Newest: O(1)
> 3. Find Min: O(1)
> 4. Update Min: O(1)

Additionally, your only requirement is to modify the list in order to keep a pointer to the newest element so that you could remove it in O(1).

# Answer
> 1 votes
I don't think it's possible for all 5 to be $O(1)$. Consider sequence of operations 5 (setting the new value to be very large) -- 4 -- 5 (setting the new value to be very large) -- 4 -- etc. It will return all elements of the stack in sorted order in $O(n)$, and so it must effectively be stored in sorted order already. But then 5 can't find the proper place to insert the new value in $O(1)$! OTOH, if you just need 1-4 to be $O(1)$ (based on your question), you can just add a single piece of extra data to the linked list.

---
Tags: data-structures, priority-queues, stacks
---


# Question
Title: Proof that $A_{DFA}$ is decidable in Sipser
It seems like the proof that $A\_{DFA}$ is decidable in Sipser (2nd ed.) assumes the computation will halt... and hence only really proves that $A\_{DFA}$ is recognizable.

The language $A\_{DFA}$ is defined by $A\_{DFA} = \\{\langle B, w \rangle \mid B \text{ is a } \mathsf{DFA} \text{ that accepts input string } w \\}$.

Here is the passage (I've bolded the most relevant sentence):

> First, let's examine the input $\langle B, w \rangle$. It is a representation of a $\mathsf{DFA}$ $B$ together with a string $w$. One reasonable representation of $B$ is simply a list of its five components, $Q$, $\Sigma$, $\delta$, $q\_0$, and $F$. When $M$ receives its input, $M$ first determines whether it properly represents a $\mathsf{DFA}$ $B$ and a string $w$. If not, $M$ rejects.
>
> Then $M$ carries out the simulation directly. It keeps track of $B$'s current state and $B$'s current position in the input $w$ by writing this information down on its tape. Initially, $B$'s current state is $q\_0$ and $B$'s current input position is the leftmost symbol of $w$. The states and position are updated according to the specified transition function $\delta$. **When $M$ finishes processing the last symbol of $w$, $M$ accepts the input if $B$ is in an accepting state; $M$ rejects the input if $B$ is in a nonaccepting state.**

Am I missing something or is this proof bogus?

**EDIT**: Never mind, I think I see my problem. A Turing machine may move back and forth, never halting, but an automaton like $B$ given finite input $w$ finishes after $|w|$ steps, correct? So $M$ does halt. Feel free to post an answer explaining this yourself - I don't want anyone to miss out on a chance to answer by me deleting the question. If no one responds within a day, I'll post an answer myself.

# Answer
> 3 votes
The computation will always halt. If $M$ doesn't reject right away, then $B$ is an encoding of a DFA. DFA always halt on any finite input, so the simulation must halt too.

---
Tags: formal-languages, finite-automata, undecidability
---


# Question
Title: If a DFA can be simulated by a real program, can it be simulated by a TM
In proofs of decidability, we often want to simulate another model of computation by a Turing machine. But if I can simulate a $\mathsf{DFA}$ by, say, a C program, then is there some result which says that the $\mathsf{DFA}$ can be simulated by some $\mathsf{TM}$? Could a program be used in place of a $\mathsf{TM}$ in a proof of decidability?

I know that Java being Turing-complete would mean that it can simulate any $\mathsf{TM}$, so this is sort of the reverse of Turing-completeness I guess.

# Answer
> 3 votes
Assuming the same limited view on computation as Turing machines, then yes: typical programming languages are Turing complete and thus (for all we know) equivalent in power to TMs.

A simpler proof presents itself, too: if you look closely enough, finite automata are just Turing machines that don't use their tape.

Keep in mind, though, that Turing machines lack some features of modern real machines/languages: distributed computation (i.e. communication), user interaction, online algorithms and never terminating systems with continuous I/O (e.g. operating systems) are just some examples. If your simulation program uses such features, the simulation may not carry over to TMs.

# Answer
> 1 votes
The Church–Turing thesis states that every intuitive model of computation can be simulated by a Turing machine. This is not a theorem, just an informal principle, which holds in your case: every C program can be simulated by a Turing machine. Formally showing this would be tedious, but such facts are commonly assumed.

The fact that C is Turing-complete is in fact *stronger* than what you need: it states that C can be simulated by Turing machines and vice versa.

---
Tags: computability, simulation, turing-completeness
---


# Question
Title: What is the time/space complexity of $n!$? Can $n!$ has polynomial space complexity?
Given an integer $n$, calculate $n!=n\times(n-1)\times(n-2)\dotsc 3\times2\times1$.

What is the best time and space complexity of calculating $n!$?

P.S. I do not have any idea about this topic. I was using MATLAB and I needed to compute $200!$ but it said "Out of memory"!! That's why I am asking.

# Answer
Stirling's formula shows that $\log m! = \Theta(m\log m)$. In terms of the length $n = |m|$, we get $|m!| = \Theta(n2^n)$, and so $m!$ cannot be bounded by a polynomial in $m$. A reasonable algorithm for calculating $m!$ exactly is using the formula $m! = m \cdot (m-1) \cdots 1$. This algorithm uses quasilinear time and linear space (in the output size). For estimating $m!$, you can use the asymptotic series extending Stirling's formula.

Since $m!$ grows very large, there is no real need to calculate $m!$, you can just store all relevant values in a table (a value is relevant if it can be stored as a machine integer, though if you use bignums then more values become relevant). You can find the values in such a table on the web.

Things become more interesting when you're after $\log m!$, since now a table would be too big. Fortunately, MATLAB can compute the $\Gamma$ function which satisfies $\Gamma(m+1) = m!$ (it is the unique log concave function with this property) and its logarithm $\ln \Gamma$ — use the functions `gamma` and `gammaln`.
> 2 votes

---
Tags: time-complexity, space-complexity
---


# Question
Title: Proving that the continuation of a non-regular language is not ω-regular
I want to prove that a language is not $\omega$-regular.

The language I'm working with can be defined as:

$$L = \\{ a\_1 \dots a\_n x^\omega ~ | ~ n \> 0, a\_1 \dots a\_n \in L^\prime \\}$$

where $L^\prime$ is a specific non regular language (I omit the definition $L^\prime$ because I think it is of no help for my problem), $a\_i$ are symbols in $L^\prime$ alphabet and $x$ is any symbol not in $L^\prime$ alphabet.

I'm aware of several proof techniques for proving a language is not regular (see e.g. How to prove that a language is not regular? ).

Are there similar proof techniques for proving that a language is not $\omega$-regular?

# Answer
> 4 votes
If $L'$ is regular then it is easy to extend a DFA for $L'$ to a deterministic Büchi automaton for $L$. For the other direction, start with a (general) Büchi automaton for $L$. Call a state *winning* if the automaton accepts starting at the state upon reading $x^\omega$. Remove all $x$ transitions and make winning states accepting to obtain an NFA for $L'$.

---
Tags: formal-languages, regular-languages, proof-techniques, buchi-automata
---


# Question
Title: Regular language not accepted by DFA having at most three states
> Describe a regular language that cannot be accepted by any DFA that has only three states.

I'm not really sure where to start on this and was wondering if someone could give me some tips or advice. I understand that the pumping lemma can be used to prove a language is not regular, but in this case, it should be a regular language. If anyone has any thoughts it would be appreciated.

# Answer
The pumping lemma can be stated to take into account the number of states in the DFA. Every language $L$ accepted by a DFA with $p$ states satisfies the following pumping lemma:

> Each word $w$ of length at least $p$ can be broken up as $w=xyz$, where $|xy| \leq p$ and $|y| \geq 1$, such that $xy^iz \in L$ for all $i \geq 0$.

You can use this characterization to prove that the language $\\{0^p\\}$ requires $p+1$ states.

Another method is to use the Myhill--Nerode theorem. Two words $x,y$ are *inequivalent* (with respect to some language $L$) if for some word $z$, either $xz \in L$ and $yz \notin L$ or the other way around. The Myhill--Nerode theorem states that if there are $p$ pairwise inequivalent words, then every DFA for $L$ has at least $p$ states. For the example $L = \\{0^p\\}$, you can find $p+1$ pairwise inequivalent words, namely $\epsilon,0,\ldots,0^p$.
> 18 votes

# Answer
Yuval's answer is great. A simpler formulation of what he's described is that finite automata cannot count arbitrarily high, and the amount they can count to is bounded by the number states in the automata. More precisely, for an automata to count to $p$, it needs $p+1$ states (one state would be $0$).

This is, in essence, the entire idea behind the pumping lemma: if a string is really long, the finite automata must "forget" how high its counted and start all over again, allowing you to repeat a section over and over without it caring.

Therefore, any regular language that requires counting to 3 to validate a word in it, cannot be described by a finite automata of size 3.

Can you think of such a language? (Your professor may also expect you to prove this counting argument, though in my curriculum this understanding of the pumping lemma was taken for granted)
> 13 votes

# Answer
There is an algorithm to minimize DFAs. Just pick a language which has a minimal DFA of 4 (or more) states. Anything that has a minimal length of 3 symbols will do, i.e., the language of the regular expression $a^3 a^\*$, or (even simpler) $a^3$. To see why, take a peek at the proof of the pumping lemma for regular languages.
> 1 votes

# Answer
another idea, diagonalization! enumerate all 3-or-fewer-state DFAs, take the union of all of them, and then take the complement. this is a DFA by regular language operations closure. this could be *constructed* via an algorithm, but the question only asks for a *description*.
> -2 votes

---
Tags: formal-languages, regular-languages, finite-automata, pumping-lemma
---


# Question
Title: What determines the entropy of a program's source code?
a few days ago I asked a question about the limits of compression: Can PRNGs be used to magically compress-stuff?

The idea common to all the answers was that if you consider all programs of length \< k (Let's call this set $C\_k$), then there is only a finite number of possible outputs generated by programs in $C\_k$ (let's call that set $S\_k$).

In the comments, I asked a followup question roughly equivalent to "what determines which messages are possible outputs?" and have been thinking about this ever since.

It seemes clear that what determines that is the program that executes the program. If we ignore TM's and think in terms of source code, then the output of a piece of code depends only on the syntax and semantics of the programming language. So the language design determines the contents of $S\_k$. There are some interesting corollaries:

* All program transformations that do no affect the AST nor enlarge the program beyond k bits will produce programs that generate the same output.
* All refactorings, which might alter the AST but preserve all input/output relationships, will do the same if they do not inflate the size of the source code.
* a PL that provides multiple constructs ("There's more then one way to do it") for achieving the same result (control flow constructs, for example) will , generally speaking, have more programs of length \< k which generate the same output and so a smaller $S\_k$ then a similar but "slimmer" PL.

This brings me to the following question: If I consider all programs in $C\_k$ that generate the same output (it's an equivalence relation) and then proceed to compress them, what would be the results? Would the equivalent programs compress down to roughly the same size or not? Does the compressability depend on the meaning of the program (which is identical) or the bit sequence (which is not)?

A statement given in the answers to the previous question is that the entropy of a bit sequence determines how compressible it is. Is that entropy determined by the input/output relationships encoded in the program, or by it's bit-representation in language X? What's the right way to think of this?

**update** Since a program describes a computational process rather then merely output, the notion of equivalence suggested really doesn't indicate me much about the relative complexity of programs which are equivalent by that definition.

# Answer
> 5 votes
This is a classical question in the foundations of Kolmogorov complexity: does the programming language matter for the sake of defining minimal description length? It depends on your model, but in general the answer is "no" or "almost no".

Suppose that $P\_1,P\_2$ are two Turing complete programming languages. In particular, in $P\_1$ you can write an interpreter $I$ for $P\_2$. Therefore any program $\pi$ written in $P\_2$ can be converted in $P\_1$ by pasting together $I$ and $\pi$. What is the length of the combined program? In any reasonable programming language, it is $O(|\pi|)$, and so different programming languages only have at most a constant multiplicative advantage over each other. If we are more stringent in our requirements on the programming languages, the answer should be $|\pi| + O(1)$, which is what happens in Kolmogorov complexity. In this case different programming languages only have at most a constant *additive* advantage over each other.

The idea behind $\pi + O(1)$ is that you should be able to concatenate the code for $I$ with $\pi$. But in practice this is not quite possible. Suppose for example that $P\_1$ is $C$. We need to write $\pi$ as a string. If the character set of $\pi$ includes backslash or double quotes, then we will need to escape these, which could result in a multiplicative blow-up. Still, we get a $C$ program whose length is $O(|\pi|)$. If we are careful in our definitions then we can prevent this — check any introductory text on Kolmogorov complexity for the details.

---
Tags: data-compression, kolmogorov-complexity
---


title: Polynomial hierarchy intersection

text:
# Question
Title: Polynomial hierarchy intersection
While familiarizing myself with polynomial hierarchy, I have come across a problem of showing $NP^{\Sigma\_{k}^{p} \cap \Pi\_{k}^{p}} \subseteq \Sigma\_{k}^{p}$. By looking at the proof for $NP^{SAT} \subseteq \Sigma\_{2}^{p}$, I got the concept where we can guess the choices of the NTM and answers to SAT call and then encode the correctness of these answers. However, while I understand encoding correctness of answers for SAT calls, I have a problem of doing the same for the oracle $\Sigma\_{k}^{p} \cap \Pi\_{k}^{p}$, which has no known complete problems. It seems to me there is a cookbook way of proving this that I am missing?

# Answer
I will assume the following definition for $\mathit{NP}^{\Sigma\_k^p \cap \Pi\_k^p}$: it is the class of languages decided by polytime non-deterministic Turing machines with oracle access to a language in $\Sigma\_k^p \cap \Pi\_k^p$. Consider now some $L \in \mathit{NP}^{\Sigma\_k^p \cap \Pi\_k^p}$ which is decided by some NP machine $M$ with oracle access to a language $K \in \Sigma\_k^p \cap \Pi\_k^p$.

Since $K \in \Sigma\_k^p \cap \Pi\_k^p$, there are $\Sigma\_k^p$-witnesses to both $x \in K$ and $x \notin K$. Including all such witnesses, the NP machine $M$ becomes an absolute $\Sigma\_k^p$ machine (we fold the first $\exists$ quantifier).

In more detail, we can write $L$ as $x \in L \leftrightarrow \exists |y|\<|x|^C P(x,y)$ for some predicate $P$ which is polynomial time with oracle access to $K$. Since $P$ runs in polynomial time, it makes at most polynomially many queries to $O$. We construct a new predicate $P'$ which guesses the results $b\_1,\ldots,b\_T$ of these queries $q\_1,\ldots,q\_T$. Since $K \in \Sigma\_k^p \cap \Pi\_k^p$, if $b\_i = T$ ($b\_i = F$) then for some polytime $P\_+$ ($P\_-$) we have $$\exists |w\_{i,1}| \< |x|^{C\_1} \forall |w\_{i,2}| \< |x|^{C\_2} \cdots Q |w\_{i,k}| \< |x|^{C\_k} P\_{\pm}(q\_i,w\_{i,1},\ldots,w\_{i,k}).$$ By combining $P$ with the machines $P\_+,P\_-$ we can come up with a polytime predicate $P'$ such that $$ x \in L \leftrightarrow \exists |y| \< |x|^C \exists b\_1,\ldots,b\_T \exists |w\_{1,1}|,\ldots,|w\_{T,1}| \< |x|^{C\_1} \cdots Q |w\_{1,k}|,\ldots,|w\_{T,k}| \< |x|^{C\_k} \\ P'(x,y,\vec{b},\vec{w}). $$ Folding the first three existential quantifiers, we see that $L \in \Sigma^p\_k$.
> 2 votes

---
Tags: complexity-theory, time-complexity, polynomial-time
---