# Question
Title: Runtime analysis of sorting an array with known number of inversions
I'm having difficulties with analyzing the worst-case runtime of this following case:

I'm given an array that has $n$ natural numbers. Out of all $\binom{n}{2} = \frac{n(n-1)}{2}$ possible pairs there are $\frac{n(n-1)}{2} - 5n$ inversions. Inversion is defined like this: $a\[i\] \< a\[j\],\ i\>j$.

So of course you can sort the array in $O(n \log n)$ time but can you do any better than this? I've looked online and saw that inversion sort time is in $\Theta(n+I)$ where $I= \text{# inversions}$ but then I get that $I=\Theta(n^2)$ so it doesn't really help me.

# Answer
Hint: Make use of the following facts:

* Each pair $i,j$ that forms an inversion for sorting in ascending order, does not form an inversion when sorting in descending order (and vice versa).
* Reversing the complete list can be done in $\Theta(n)$.
> 4 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: What exactly is the difference between supervised and unsupervised learning?
I am trying to understand clustering methods.

What I I think I understood:

1. In supervised learning, the categories/labels data is assigned to are known before computation. So, the labels, classes or categories are being used in order to "learn" the parameters that are really significant for those clusters.
2. In unsupervised learning, datasets are assigned to segments, without the clusters being known.

Does that mean that, if I don't even know which parameters are crucial for a segmentation, I should prefer supervised learning?

# Answer
The difference is that in supervised learning the "categories", "classes" or "labels" are known. In unsupervised learning, they are not, and the learning process attempts to find appropriate "categories". In both kinds of learning all parameters are considered to determine which are most appropriate to perform the classification.

Whether you chose supervised or unsupervised should be based on whether or not you know what the "categories" of your data are. If you know, use supervised learning. If you do not know, then use unsupervised.

As you have a large number of parameters and you do not know which ones are relevant, you could use something like principle component analysis to help determine the relevant ones.
> 24 votes

# Answer
Note that there are more than 2 degrees of supervision. For example, see the pages 24-25 (6-7) in the PhD thesis of Christian Biemann, Unsupervised and Knowledge-free Natural Language Processing in the Structure Discovery Paradigm, 2007.

The thesis identifies 4 degrees: supervised, semi-supervised, weakly-supervised, and unsupervised, and explains the differences, in a natural-language-processing context. Here are the relevant definitions:

* In **supervised** systems, the data as presented to a machine learning algorithm is fully labelled. That means: all examples are presented with a classification that the machine is meant to reproduce. For this, a classifier is learned from the data, the process of assigning labels to yet unseen instances is called classifi- cation.
* In **semi-supervised** systems, the machine is allowed to additionally take unlabelled data into account. Due to a larger data basis, semi-supervised systems often outperform their supervised counterparts using the same labelled examples. The reason for this improvement is that more unlabelled data enables the system to model the inherent structure of the data more accurately.
* Bootstrapping, also called self-training, is a form of learning that is designed to use even less training examples, therefore sometimes called **weakly-supervised**. Bootstrapping starts with a few training examples, trains a classifier, and uses thought-to-be positive examples as yielded by this classifier for retraining. As the set of training examples grows, the classifier improves, provided that not too many negative examples are misclassified as positive, which could lead to deterioration of performance.
* **Unsupervised** systems are not provided any training examples at all and conduct clustering. This is the division of data instances into several groups. The results of clustering algorithms are data driven, hence more ’natural’ and better suited to the underlying structure of the data. This advantage is also its major drawback: without a possibility to tell the machine what to do (like in classification), it is difficult to judge the quality of clustering results in a conclusive way. But the absence of training example preparation makes the unsupervised paradigm very appealing.
> 13 votes

# Answer
In supervised learning the classes are known in advance and also their types, for instance, two classes good and bad customers. When new object(customer) comes on the basis of its attributes the customer can be assigned to bad or good customer class.

In unsupervised learning the groups/classes are not already known, we have objects (customers), so group the customers having similar buying habits hence different groups are made of the customers i.e. not known already on the basis of similar habits of buying.
> 0 votes

# Answer
In supervised learning the output(dependent variable) depends on the input variable(independent variable).In some set of given supervisions the responder tries to compute the desired objective.

In unsupervised learning there is no supervision so system tries to adapt itself to the situation and learns manually based on some measure.

eg: Teacher in a class -supervision -supervised learning An self study elective in class-No supervision Unsupervised Learning
> 0 votes

---
Tags: machine-learning, data-mining, clustering
---


title: Transition coverage for a DFA

text:
# Question
Title: Transition coverage for a DFA
Let $G$ be a directed graph, with a single source node $s$. I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where each path must start at $s$. The cost of a collection of paths is the sum of the lengths of the paths.

Is there an efficient algorithm to find the minimum-cost collection of paths? This smells like it might be NP-hard to me (it sounds like a set cover problem), so I'm guessing not. If it is NP-hard, are there any good approximation algorithms or heuristics for this problem?

This sounds a bit like some kind of network-flow problem. Every collection of paths from $s$ to $t$ is an integral flow from $s$ to $t$, and every integral flow from $s$ to $t$ can be expressed as a union of paths from $s$ to $t$. The difference is that (1) the objective function we are trying to minimize is different from the standard network flow problem, and (2) the starting point of each edge is fixed to $s$, but the ending point is not fixed. So, I don't know if network flow like techniques would help.

---

Motivation: Suppose I have a DFA, and I want to find a testsuite that achieves full edge coverage. A test is a word over the alphabet of the DFA; a testsuite is a collection of tests. A transition is covered by this testsuite if there exists at least one test in the testsuite that causes the DFA to follow that transition at some point. Suppose the cost of a test is its length, and the cost of a testsuite is the sum of the costs of the tests.

Then we can ask whether there is an efficient algorithm that, given a DFA as input, outputs a minimum-cost testsuite that achieves full transition coverage. That's exactly the graph problem outlined above.

# Answer
This is related to a well known problem with a conjecture due to Karpovsky and Moskalev \[1\] (I still believe is open) that at most V-1 paths are needed. It is tied to conjector of Erdos, Goodman, and Posa \[2\].

If you want the state of the art today, I suggest doing a thorough reverse-citation search on \[1\].

---

\[1\] Karpovsky, M. G., and E. A. Moskalev. "Covering of edges of graph by a minimal set of paths." Discr. Math 58.2 (1986): 214. (This is in the "research problems" section)

\[2\] Erdos, Paul, Adolph W. Goodman, and Louis Pósa. "The representation of a graph by set intersections." Canad. J. Math 18.106-112 (1966): 86.
> 2 votes

---
Tags: graphs, finite-automata, optimization, software-testing, set-cover
---


# Question
Title: Composition of combinators with arities greater than one
In combinatory logic, the axiom of composibility asserts that for any two combinators, $A$ and $B$, there exists a combinator $C$ that composes $A$ and $B$. That is, for all $A,B,x$ there exists a $C$ such that: $CABx = A(Bx)$.

But what if $A$ and $B$ have arities other than 1? In particular, suppose that $A$'s arity is greater than $B$'s. Say $A$ has arity 4 and $B$ has arity 2. Presumably, this would mean that their composition should be $CABvwxyz = A(Bvw)xyz$, so that $A$ would then operate on the four combinators $(Bvw), x, y$ and $z$. Is this correct? Surely not $CABvwxyz = A(Bv)wxyz = (A(Bv))wxyz$.

I believe what I am confused about is the use of the 'variable combinator' notation (e.g., $Axy$). It doesn't seem to me to be syntactically strict. I believe it is a meta-notation, intended to express the arity of a combinator; which is fine, except that, given the subtleties of reasoning with combinators (at least for my humble comprehension :-) ), I would very much appreciate having an explicit re-write rule to transform one sequence of combinators into another. Is my thinking mis-guided?

# Answer
> 2 votes
One methodical way of accomplishing this is to construct a corresponding lambda term and to then convert it to a CL term using pseudoabstraction.

First some definitions. You want to compose two combinators $A$ and $B$ with arities $p$ and $q$, respectively. Let $C^\lambda\_{p,q}$ represent the lambda term accomplishing this.

$C^\lambda\_{p,q}$ must first accept $A$, then $B$, then the $q$ arguments $b\_1,\ldots,b\_q$ of $B$, and then $p-1$ remaining arguments $a\_1, \ldots, a\_{p-1}$ of $A$ (*note*: '$p-1$' because the argument $B(b\_1\ldots b\_q)$ has already been accepted). So $C^\lambda\_{p,q}$ must accept $ p + q + 1$ arguments in total, and it must satisfy:

$$C^\lambda\_{p,q} A B b\_1 \ldots b\_qa\_1\ldots a\_{p-1} \rhd\_\beta A(Bb\_1\ldots b\_q)a\_1 \ldots a\_{p-1}$$

This easily works for:

$$C^\lambda\_{p,q} \equiv \lambda xyb\_1 \ldots b\_q a\_1 \ldots a\_{p-1}.x(yb\_1 \ldots b\_q)a\_1 \ldots a\_{p-1}$$

So in your example with $p = 4$ and $q = 2$, we get:

$$C^\lambda\_{4,2} \equiv \lambda xyb\_1b\_2 a\_1 a\_2 a\_3.x(yb\_1 b\_2)a\_1 a\_2 a\_3 $$

Now for the conversion. To this end we introduce the notion of pseudo-abstraction, as defined below by Hindley & Seldin in *Lambda-calculus and Combinators*:

**Definition 1. (Abstraction)** For every CL-term $M$ and every variable $x$, a CL-term called $\[x\].M$ is defined by induction on $M$, thus:

1. $\[x\].M \equiv \mathsf{K}M$ $\hspace{29.8mm}$if $x \not\in FV(M)$
2. $\[x\].x \equiv \mathsf{I}$
3. $\[x\].Ux \equiv U$ $\hspace{33mm}$if $x \not\in FV(U)$
4. $\[x\].UV \equiv \mathsf{S}(\[x\].U)(\[x\].V)$ $\hspace{3mm}$if neither (1) nor (3) applies

Here, $\equiv$ denotes syntactical equivalence, and $\[x\]$ is not really part of the language of combinatory logic itself. Intuitively, a term $\[x\].M$ is just a *name* for a valid CL term which we can recover using the above definition. The definition will eliminate all bound variables. For example:

$$\[xy\].xyx$$ $$\[x\].(\[y\].(xy)x)$$ $$\[x\].(\mathsf{S}(\[y\].xy)(\[y\].x))\text{(Def. 1.4)}$$ $$\[x\].(\mathsf{S}(\[y\].xy)(\mathsf{K}x))\text{(Def. 1.1)}$$ $$\[x\].(\mathsf{S}(x)(\mathsf{K}x))\text{(Def. 1.3)}$$ $$\[x\].(\mathsf{S}x)(\mathsf{K}x)$$ $$\mathsf{S}(\[x\].\mathsf{S}x)(\[x\].\mathsf{K}x) \text{(Def. 1.4)}$$ $$\mathsf{S}(\[x\].\mathsf{S}x)(\mathsf{K}) \text{(Def. 1.3)}$$ $$\mathsf{S}(\mathsf{S})(\mathsf{K}) \text{(Def. 1.3)}$$ $$\mathsf{SSK}$$

So $\[xy\].xyx \equiv \mathsf{SSK}$, i.e. when we write $\[xy\].xyx$, we really mean $\mathsf{SSK}$. You can verify that $\mathsf{SSK}$ captures the intended functionality:

$$\mathsf{SSK}xy \rhd\_{1w} (\mathsf{S}x)(\mathsf{K}x)y \rhd\_{1w} xy(\mathsf{K}xy) \rhd\_{1w} xyx$$

similarly, the CL term $C^{CL}\_{p, q}$ for $C^\lambda\_{p, q}$ is simply:

$$\[xyb\_1 \ldots b\_q a\_1 \ldots a\_{p-1}\].x(yb\_1 \ldots b\_q)a\_1 \ldots a\_{p-1}$$

Of course, to do the elimination of variables manually even for $C^{CL}\_{4,2}$ is tedious, but the point is that the meaning is fixed (and the process of elimination could easily be automated).

# Answer
> 0 votes
You are right that $Axy$ is not a syntactically strict. In strict combinatory logic, each term is either (0) an atom (i.e. a variable), (1) a combinator (or a $\lambda$ expression) or (2) a pair $(f g)$, read "$f$ applied to $g$". The expression $Axy$ is really shorthand for $((Ax)y)$. We see two conventions in play here:

1. The application operator can also be expressed by just juxtaposition. Compare with the usual notation for multiplication: $ab$ stands for $(a \times b)$.
2. Function application associates to the left. So the correct way of parenthesizing $Axy$ is $((Ax)y)$ rather than the other way around, $(A(xy))$. Compare subtraction and division: $3-2-1 = ((3-2)-1)$.

The combinator $K$, to take an example, satisfies the equation $Kxy = x$. What that really means is that $(Kx)$ is the function $\lambda y.x$, and so $((Kx)y) = ((\lambda y.x)y) = x$. Here $x,y$ are variables or atoms, if we allow the latter.

How should you simplify an expression like $Kx$? The usual convention in combinatory logic, to the best of my knowledge, is not to simplify. So only simplify a combinator if it has enough "arguments". This way you never get to see the intermediate $\lambda$ expressions.

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


# Question
Title: A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP
Wikipedia states on sparse languages that

> There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from a NP-complete language to a sparse language iff NP $\subseteq$ P/poly.

Is that correct in that it is so far proven for an *arbitrary* Turing reduction and not a limited P-time reduction? (Could it be true for P-time reductions also, but maybe not proven so far?) It cites this without reference. What is a reference for this?

# Answer
> 3 votes
No, what you suggest would be meaningless. The Turing reduction is also polytime. For a proof, see Theorem 3.2 in Oded Goldreich's lecture notes.

---
Tags: complexity-theory, reference-request, np-complete, reductions, p-vs-np
---


# Question
Title: Why is the transform in Schönhage–Strassen's multiplication algorithm cheap?
The Schönhage–Strassen multiplication algorithm works by turning multiplications of size $N$ into many multiplications of size $lg(N)$ with a number-theoretic transform, and recursing. At least I think that's what it does because there's some other cleverness and I really don't understand it well enough to summarize accurately. It finishes in $O(N \cdot lg(N) \cdot lg(lg(N)))$ time.

A number-theoretic transform is exactly like a Discrete Fourier Transform, except it's done in the finite field $F\_{2^N+1}$ of integers modulo $2^N+1$. This makes the operations a lot cheaper, since the Fourier transform has a lot of multiplying by roots of unity, and $F\_{2^N+1}$'s roots of unity are all powers of 2 so we can just shift! Also, integers are a lot easier to work with than floating point complex numbers.

Anyways, the thing that confuses me is that $F\_{2^N+1}$ is very large. If I give you a random element from $F\_{2^N+1}$, it takes $O(N)$ bits to specify it. So adding two elements should take $O(N)$ time. And the DFT does a *lot* of adding.

Schönhage–Strassen splits the input into $\frac{N}{lg(N)}$ groups with $lg(N)$ bits. These groups are the values of $F\_{2^N+1}$ that it will transform. Each pass of the DFT will have $O(\frac{N}{lg(N)})$ additions/subtractions, and there are $O(lg(\frac{N}{lg(N)}))$ passes. So based on addition taking $O(N)$ time it seems like the cost of all those additions should be $O(N \frac{N}{lg(N)} lg(\frac{N}{lg(N)}))$, which is asymptotically the same as $O(N^2)$.

We can do a bit better than that... because the values start out so small, the additions are quite sparse. The first pass' additions really only cost $O(lg(N))$ each, and the second pass' cost $2^1 O(lg(N))$ each, and the i'th pass' cost $O(min(N, 2^i \cdot lg(N)))$ each, but that still all totals out to a terrible $\frac{N^2}{lg(N)}$.

**How is Schönhage–Strassen making the additions cheap? How much do they cost overall?**

Is it because the algorithm actually uses $F\_{N+1}$ (with $N$ guaranteed to be a power of 2)? There's enough stacked $2^{2^{n}}$ and german in the paper that I'm really not sure. On the other hand, I don't think that guarantees enough roots of unity for things to work out.

# Answer
According to the Wikipedia article, at each step the length of the integers is reduced from $N$ to (roughly) $\sqrt{N}$, and there are (roughly) $\sqrt{N}$ of them, and so the additions only cost $O(N)$. There is a detailed analysis of the running time in the final paragraph of the linked section, copied here in case it changes:

In the recursive step, the observation is used that:

* Each element of the input vectors has at most $N/2^k$ bits;
* The product of any two input vector elements has at most $2N/2^k$ bits;
* Each element of the convolution is the sum of at most $2^k$ such products, and so cannot exceed $2N/2^k + k$ bits.

Here $N$ is current input length and $k = \Theta(\sqrt{N})$. Arithmetic is done modulo $2^n+1$, where $n$ is some multiple of $2^k$ which is larger than $2N/2^k + k$; note that $n = \Theta(\sqrt{N})$.
> 5 votes

# Answer
There's an excellent explanation of exactly what's going on, including how the size of the field goes down as you progress, in GMP's documentation: 15.1.6 FFT Multiplication.

A more theoretically in-depth overview starts on page 55 of Modern Computer Arithmetic (pdf) (well... the browser says page 71 but the page itself says 55). It explains the algorithm's correctness and breaks down the complexity analysis.
> 3 votes

---
Tags: algorithm-analysis, time-complexity, multiplication
---


# Question
Title: Efficient algorithm for iterated find/replace
I'm looking for an algorithm for doing iterated find/replace, where the act of finding the replacement list of tokens for a given find is slow.

Specifically: I have a function, `f`, that maps a sequence of tokens to either a shorter list of tokens or None. However, it is slow.

I want to repeatedly try to replace the (first, in the case of ties) shortest unexplored subsequence in the input with the result of applying the function to it, assuming that there is a valid replacement for it. However, the naive way to do this ends up with exponential runtime. Is there a better algorithm for doing this?

(So, for example, if `f` maps `ba` -\> `b`, `aaa` -\> `ab`, and `aba` -\> `bb`, and I apply the algorithm to `aaaaa`, I want to get (`aaaaa`-\>`abaa`-\>`aba`-\>)`ab`, not (`aaaaa`-\>`abaa`-\>`bba`-\>)`bb` or any of the other sequences of replacements possible, if any.)

(Note: this example uses characters for simplicity)

# Answer
This isn't a complete answer, but it provides some context that's far too long to put in a comment. What you've described is an instance of a string rewriting system, also known as a semi-Thue system. Start with a finite alphabet, $\Sigma$, and a binary relation, $R$, on strings over $\Sigma$. For your example, we'll have $R$ defined by

$$ ba\\, R\\, b,\quad aaa\\, R\\, ab,\quad aba\\, R\\, bb $$ We can then define another relation, $\Rightarrow$, on strings by, basically, applying $R$ to substrings. For two strings $x, y$, define $x\Rightarrow y$ if and only if $$ \text{there exist strings }p, q, r, s\text{ such that } x=prq, y=psq,\text{ and }r\\, R\ s $$ In your example, we have, for instance, the chain of rewrites $aaaaa\Rightarrow abaa\Rightarrow aba\Rightarrow bb$, and there we stop, since we cannot reduce $bb$ any further. In a rewriting system, a string like $bb$ which cannot be rewritten is called *irreducible* or sometimes a *normal form*. If there is a chain of rewrites starting from a seed string $x$ that leads to a normal form we denote the result by $x\downarrow$. Again, in your example, the normal forms derivable from $aaaaa$ are $ab, bb, aab, abb$.

Your question in its most general form is

> **Question 1**. In a string rewriting system, is there a computationally efficient way to find a normal form for a given string $x$?

In general, the answer is no, there isn't. The problem comes in part from the fact that some (or all) seed strings might never lead to a normal form. This could arise in a rewriting system that permits chains like $$ x\_1\Rightarrow x\_2\Rightarrow \cdots\Rightarrow x\_i\Rightarrow x\_{i+1}\Rightarrow\cdots\Rightarrow x\_i $$ Fortunately, you've imposed a helpful constraint, namely that whenever $x\\,R\\,y$ then the lengths satisfy $|x|\>|y|$. We'll call such a system *monotone* or *length-reducing*. In a monotone rewriting system we're always going to have a normal form for any seed string, since every rewrite operation strictly decreases the length of the string. A rewriting system for which every string has at least one normal form is called *noetherian*, by the way. Refining the question gives us

> **Question 2**. In a monotone string rewriting system, is there a computationally efficient way to find a normal form for a given string $x$?

The answer to this question is yes, of course: given a seed string $x$, simply apply rewrite rules until you reach a normal form. More systematically, if $|x| = n$ and you have $m$ base rewrite rules $\\{w\_1\\,R\\,z\_1,w\_2\\,R\\,z\_2,\dots w\_m\\,R\\,z\_m\\}$ with $M=\max\\{|w\_i|\\}$, then we'll require $O(nmM)$ character comparisons, even if we don't use efficient string search algorithms.

We haven't quite gotten to your real question, though, since you also stipulate that at each step you will choose to apply your base rewrite rules in order of the lengths of their left-hand sided, |w\_i|, from shortest to longest. It's not clear that this is a useful constraint; in fact, some string search algorithms (Boyer-Moore, in particular) are more efficient when searching for longer substrings than they are for shorter ones. It might be helpful to impose another constraint, though: when searching for a substring to replace, always choose the leftmost substring, regardless of length. This would put you in a situation involving prefixes and there's a fair amount known about this. Choosing rightmost substrings as replacement candidates might also be a useful avenue.

Finally, we come to the most interesting question:

> **Question 3**. In a monotone string rewriting system, is there a computationally efficient way to find a normal form of minimal length?

---

This should help you to find answers. There's good news for your search, namely that there's a *lot* of material out there, both in books (yes, whole books have been written on string rewriting systems) and online. I did a search for "string rewriting systems" and got a million and a half hits. The bad news is that there's a *lot* of material out there, so finding an answer is likely going to take some serious drilling. Frankly, I don't know the answer to Question 3, but my uninformed guess is that the answer is affirmative. If you haven't gotten a definitive answer in a few days, you might want to ask your question, suitably reworded, over at theoretical computer science.
> 2 votes

---
Tags: algorithms, search-algorithms, strings
---


# Question
Title: Find rectangle of minimum area where dimensions are larger than minimum
**Problem**: Given a collection $S$ containing $|S|=n$ rectangles defined by dimensions $(x,y)\in R^2$ (width and height of rectangles are real numbers), find the rectangles with the minimum area ($A\_i = x\_i * y\_i$) where $(x\_i \geq a)$ and $(y\_i \geq b$) for any $(a,b) \in R^2$.

The naive solution $F(S,a,b)$ will solve this with $O(n)$ runtime complexity and $O(1)$ memory complexity: loop through all the rectangles that are larger than the minimum required values $(a,b)$ for $(x,y)$, remember the one with the smallest area $x\*y$ and return that. This requires no preparation or indexing of any kind, just a simple loop (sorting according to area beforehand won't improve the $O(n)$ worst-case runtime complexity).

Can this problem be solved with an algorithm with **faster than $O(n)$ runtime complexity and up to O(n) memory complexity**?

# Answer
> 4 votes
One simple solution uses k-d trees. In preprocessing, prepare a sorted list $L$ of $x\_i y\_i$ as well as a three dimensional k-d tree $T$ storing the points $(x\_i,y\_i,x\_iy\_i)$; this can be done in time $O(n\log n)$ and takes up space $O(n)$. Given $a,b$, we do binary search on $L$ to find the least $c$ such that $T$ contains a point $(x\_i,y\_i,x\_iy\_i)$ with $x\_i \geq a,y\_i \geq b,x\_iy\_i \leq c$; each such query takes time $O(n^{2/3})$, for a total query time of $O(n^{2/3}\log n)$.

It's not clear whether we actually need a three dimensional k-d tree; if a two dimensional one suffices, then the running time could get down to $\tilde{O}(n^{1/2})$.

# Answer
> 2 votes
Similar to another answer, but with range trees (see wikipedia) if you are willing to accept $O(n (\log n)^2)$ space instead of $O(n)$ space. In that case, you perform the same range queries $x \geq a$, $y \geq b$, $xy \leq c$ to perform binary search on $c$ to find the minimal $c$ that produces a query result in your range tree. The advantage over kd-trees is that range queries take only $O((\log n)^2)$ time in a 3-d range tree, for a total complexity of $O((\log n)^3)$. If you are willing to increase storage by a poly-logarithmic factor above $O(n)$, this can be much faster in the worst case.

---
Tags: algorithms, time-complexity, search-algorithms, space-complexity
---


title: Text search by first order formula

text:
# Question
Title: Text search by first order formula
I am searching for substrings that satisfy a given first order formula in a moderately sized text. The formula is made out of usual $\wedge, \neg, \exists$ and predicates `Equals(x, "some string")`, `Before(x, y)` and similar, where variables are pairs indices denoting substrings.

If the text is $n$ symbols long and the formula contains $k$ quantifiers, then the brute search is $O(n^{2k+2})$. This is quite a bit of time. I ask, **is there a way to significantly improve on this?**

Many ranges are 'obviously' not worth iterating over, but I don't see a good way to sufficiently restrict the search space, without enumerating all the possible substrings.

# Answer
The formula's you propose are very reminiscent of the operations of monadic second order logic: position variables, existence letter on position, relative order of positions, boolean operators and position quantification. As you probably know the power of this scheme equals regular languages.

The transformation from MSO to FSA seems to be horrible (negation is complementation, and existential quantification is handled using nondeterminism, hence exponential blow-up for each combination of the two).

Nevertheless, that gives a very different complexity, linear in $n$, but multiplied by a tower of 2-powers of height $k$.
> 1 votes

---
Tags: optimization, search-algorithms
---


# Question
Title: Generating a set of minimal-length strings that, together, invoke every production of a context free language
**Problem** (tl;dr)

Given a context free grammar, $G$, find a set of strings that take $G$ through every production it has at least once.

How and how fast can it be done?

**Background**

I'm working on a compiler whose parser is implemented with a tool similar to Yacc+Antlr. I've written up most of the parser code, and I'd like to generate some code of the object language that invokes every production of the grammar at least once so that I can feed it to the parser and make sure that nothing is wrong.

In the interest of good testing, what I'd really like is one, short test file that has a particular production "under test" -- so, for each production rule, I want to generate a minimal string that takes the parser from the start state, through the production being tested, to a set of terminals.

**Possible solutions**

I imagine there is an elegant solution using graph theory, but I'm not quite sure what it is. I would like to just use Dijkstra's algorithm to find shortest paths through some appropriate structure, but I think that a string is parsed by a context free grammar in a tree structure rather than a path, so I don't know how to make that work.

I think there might be a clever way to pose it as a network flow problem. Something like this: take a graph that has a vertex for every symbol (terminal and nonterminal) and a vertex for every production. If a nonterminal has a production, add a directed edge from the nonterminal to the production. If a production produces a symbol, add a directed edge from the production to the symbol. Add a source with some capacity $c$ and attach it to the vertex corresponding to the start symbol. Add a sink with infinite capacity and attach it to each terminal.

If a nonterminal has an in-arc with a capacity $k$, add an arc from the nonterminal to each of its productions with capacity $k$. If a production has an in-arc with capacity $k$ and it has an out-arc to $n$ nonterminals, add an arc with capacity $\frac k n$ from the production to each nonterminal.

Then run some maximum flow algorithm on the network and let the productions "trickle down" from the start symbol to the terminals. You should end up with a flow $c$ coming out of your source, and you can return all of the terminals you hit with a nonzero flow as your result string. Then you end up with something like $O(n^3)$ time complexity for each run, where $n$ is the sum of the number of terminals and nonterminals in your grammar -- not too bad.

However, I'm still not really sure what this graph looks like: I think that it needs to be infinite and I'm not sure if you can find the maximum flow of an infinite flow network. Past that, I'm not sure how to "remove" a production from consideration so that I'm guaranteed to get a new one for each test run.

I Googled and I couldn't find anything. Is there a nice solution to this problem?

# Answer
# In a nutshell

Not knowing enough the literature, I worked out a solution which is presented in the next section, together with a proof for the hardest part. Once I knew what was needed, I could search the literature for the right ideas. Here is a quick presentation of the algorithm, based on the literature, which is essentially the same I developed.

The first thing to do is to find a size-minimal terminal string $\sigma(U)$ for every non-terminal $U$ of the grammar. This can be done by using Knuth's extension to conc-or graphs (also known as CF grammars) and and-or graphs of Dijkstra's shortest path algorithm. Example B in Knuth's paper does what is needed, almost.

Actually, Knuth computes only the length of these terminal strings, but it is quite easy to modify his algorithm to actually compute one such terminal string $\sigma(U)$ for each non-terminal $U$ (as I do it in my own version below). We also define $\sigma(a)=a$ for every terminal $a$, and we extend $\sigma$ as usual into a string homomorphism.

Then we consider a directed graph where non-terminals are the nodes, and there is an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha V\beta$. If several such rules can produce the same arc $(U,V)$, we keep one such that the length $|\sigma(\alpha\beta)|$ is minimal. The arc is labeled with that rule, and that minimal length $|\sigma(\alpha\beta)|$ becomes the weight of the arc.

Finally, using Dijkstra's shortest path algorithm, we compute the shortest path from the initial non-terminal $S$ to each non-terminal of the grammar. Given the shortest path for a non-terminal $U$, the rule labels on the arcs may be used to get a derivation $S\overset{\*}{\Longrightarrow}\alpha U \beta$. Then, to every rule of the form $U\rightarrow\gamma$ in the grammar, we associate the size-minimal terminal string $\sigma(\alpha\gamma\beta)$ which can be derived using that rule.

To achieve low **complexity**, both Dijkstra's algorithm and Knuth's extension are implemented with heaps, AKA priority queues. This gives for Dijkstra's algorithm a complexity of $O(n\log n +t)$, and for Knuth's algorithm a complexity $O(m \log n +t)$, where there are $m$ grammar rules and $n$ non-terminals, and $t$ is the total length of all rules. The whole is dominated by the complexity of Knuth's algorithm since $m\geq n$.

*What follows is my own work, before I produced the short answer above.*

# Deriving the solution from the useless symbols elimination algorithm.

There are several aspects to this algorithm. For better intuition I chose to present it in three successive versions that introduce progressively more features. The first version does not answer the question, but is a standard algorithm for useless symbols elimination that suggests a solution. The second version answers the question without the minimality constraint, The third version gives an answer to the question, satisfying thye minimality constraint. This third solution is then improved by using an adaptation to and-or graphs of Dijkstra's shortest path algorithm.

The end result is a very simple algorithm, that avoids reconsidering computations already done. But it is less intuitive and does require a proof.

This answer only tries to answer the question as made precise by the OP's comment: "*for each production rule, I want to generate a minimal string that takes the parser from the start state, through the production being tested, to a set of terminals.*" Hence I only try to get a set of strings such that for each rule, there is a string in the set that is one of the size-minimal strings of the language having a derivation using the rule.

It must be however noted that the fact that a string "invokes" a rule, that is has a derivation using that rule, does not necessarily means that the rule will be considered by a parser that work with ambiguous grammars and resolves ambiguities arbitrarily. Handling such a situation would probably require more precise knowledge of the parser, and might well be a more complex question.

## The basic algorithm

To solve this question, one can start with the classical algorithm for useless symbols removal in context-free grammars. It is in section 4.4, pp 88-89, of Hopcroft & Ullman, 1979 edition. But the presentation here may be a bit different.

The algorithm aims precisely at proving the existence of such a covering as requested by the OP, and consists in two parts:

* lemma 4.1 of H&U, page 88: **removal of all unproductive non-terminals**. This is done by trying find for each terminal a terminal string it can derive on. A simple way to explain it is as follow: You create a set $Prod$ od productive symbols, which you initialize with all terminals. Then for each rule, not yet processed, that has all its right-hand-side (RHS) symbols in $Prod$, you add the left-hand-side (LHS) non-terminal to the set $Prod$, and you remove all rules with the same LHS non-terminal from the set of rules to be processed. You iterate the process until there is no rule left with all its RHS symbols in $Prod$. The remaining non-terminals, not in $Prod$ at the end of this process, are non-productive: they cannot be derived into a terminal string, and can thus be removed from the grammar.
* lemma 4.2 of H&U, page 89: **removal of all unreachable symbols**. This is done by the classical node reachability in directed graphs, by considering non-terminals as nodes and having an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha$ such that $V$ occurs in $\alpha$. You create a set $Reach$ of reachable symbols which is initialized with only the initial symbol $S$. Then, for every non-terminal symbol $U$ in $Reach$ or later added to it, and for every rule $U\rightarrow \alpha$, you add to $Reach$ all the symbols in $\alpha$. When all non-terminals in $Reach$ have been thus processed, all symbols (terminal or non-terminals) that are not included in $Reach$ cannot appear in a string derived from the initial symbol, and are therefore useless. Thus they can be removed from the grammar.

These two basic algorithms are useful to simplify the raw results of some grammar construction techniques, such as used for the intersection of a context-free language and a regular set. In particular, this is useful in cleaning up the results of general CF parsers.

Useless non-terminal symbols removal is necessary in the context of solving the question asked, as the rules using them cannot be "invoked" (i.e. used in its derivation) by any string of the language.

## Building a set of string that invoke every rule

(We are not looking yet for minimal strings.)

Now answering specifically the question, one must indeed remove all useless symbols, whether unreachable symbols or unproductive non-terminal symbols, a well as useless rules having such useless non-terminals as LHS. They have no chance of being ever invoked usefully while parsing a terminal string (though some may well waste the processing time of a parser when they are not removed; which ones may waste time depends on the parser technology).

We now consider, for each (useful) rule, the production of a terminal string that invokes it, i.e. that may be generated by using this rule. This is essentially what is done by these two algorithms above, though they do not keep the information, as they are satisfied with proving the existence of these strings to ensure that non-terminals are both reachable and productive.

We modify the first algorithm (lemma 4.1) by keeping with each non-terminal $U$ in the set $Prod$ a terminal string $\sigma(U)$ it derives on: $U\overset{\*}{\Longrightarrow}\sigma(U)$. For every terminal we define the $\sigma$ as the identity mapping. When $U$ is added to the set $Prod$ because a rule $U\rightarrow\gamma$ has all its RHS symbols in $Prod$, then we define $\sigma(U)=\sigma(\gamma)$, extending $\sigma$ as a homomorphism on strings, and we remove all $U$-rules, that is all rules with $U$ as LHS.

We modify the second algorithm (lemma 4.2) by keeping with each non-terminal symbol $U$ added to $Reach$ the path used to reach it from the intial symbol $S$, which gives the successive rules to get a derivation $S\overset{\*}{\Longrightarrow}\alpha U \beta$.

Then, for each rule $U\rightarrow\gamma$ in the grammar, we produce a terminal string that "invokes" this rule as follows. We take from the result of the second algorithm the derivation $S\overset{\*}{\Longrightarrow}\alpha U \beta$. Then we apply the rule to get the string $\alpha \gamma \beta$. A terminal string "invoking" the rule $U\rightarrow\gamma$ is $\sigma(\alpha \gamma \beta)$

## Building a set of minimal strings that "invoke" every rule

We ignore the issue of eliminating useless symbols, which can be a by-product of these modified algorithms.

Building a set of minimal strings relies on first getting a minimal derived string for each non-terminal. This is done by further modifying the first algorithm (lemma 4.1). First we remove from the set of rules to be processed all recursive rules (i.e. with a LHS symbol occurring in the RHS string). It is obvious that none of these rules can derive to a shorter terminal string than the non-recursive rules with the same LHS. And there must be at least one non-recursive rule if the LHS is not a useless non-terminal (because non-productive).

Then we procede as before to build the set $Prod$ of productive symbols, associating with each synbol $U$ a terminal string, which we note $\sigma(U)$. The string $\sigma(U)$ is produced as before by application of the rule $U\rightarrow\gamma$, substituting each non-terminal $V$ occurring in $\gamma$ with $\sigma(V)$. So far, it was necessary to apply this to only one rule with a given non-terminal $U$ as its LHS, the first that would have all its RHS non-terminals in $Prod$, and then ignore the others, because any such derived string would do. But we are now looking for a minimal derived string. Hence, for a non-terminal $U$, this has to be done for all rules with $U$ as LHS. But we keep only one terminal string $\sigma(U)$, replacing the current one by the newly found one, whenever the new one is smaller.

Furthermore, whenever the string $\sigma(U)$ is replaced by a smaller one, all rules with an occurrence of $U$ in the RHS that had been already processed have to be put back in the set of rules to be processed, since change allows deriving their RHS on a shorter string. So doing this will call for more iterations, but will eventually end since none of these strings ever gets much shorter than the empty string.

At the end of this first algorithm, the string $\sigma(U)$ is one of the smallest strings that can be derived from $U$. There may be others.

Now we also have to modify the second algorithm to get, for every non-terminal $U$, (one of) the shortest string containing U as the only non-terminal. To do this, we keep the same directed graph with non-terminals as nodes, and having an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha V \beta$. But now we put weights on the arcs, to compute the minimum length of the terminal context that has to be associated with reachable non-terminals. The weight associated with the arc $(U,V)$ above is the length $|\sigma(\alpha\beta)|$, where the mapping $\sigma$ is extended to terminals as the identity, and then extended again as a string homomorphism. It is the length of (one of) the shortest terminal strings that can be derived from the string $\alpha\beta$. Note that $V$ is removed in this calculation. HOwever, when there are several occurences of $V$ in the RHS, only one must be removed. There may be several possible $(U,V)$ arcs, with different weights, if there are several rules with $U$ as LHS and $V$ in the RHS. In such a case, only (one of) the lighter such arc is kept.

In this graph, we no longer look just for reachability of nodes from $S$, but for the shortest weighted path that reaches every node from the initial symbol $S$. This can be done with Dijkstra's algorithm.

Given the shortest path for a non-terminal $U$, we read it as before as a sequence of rules, from which we get a dérivation $S\overset{\*}{\Longrightarrow}\alpha U \beta$. Then to every rule of the form $U\rightarrow\gamma$ in the grammar, we produce a minimal terminal string that "invokes" this rule as $\sigma(\alpha\gamma\beta)$

**Remark**: The same minimal string may probably be used for several rules. But the fact that one of the strings uses a rule $\rho$ in its derivation does not necessarily mean it is a minimal string for that rule $\rho$, as it may have been found for another rule, while a shorter one can be found for $\rho$. It may be possible to increase the likelyhood that the same minimal string will be found for several rules by using some priority policy whenever there is flexibility. But is it worth the trouble?

## A faster algorithm for minimal terminal string deriving from a non-terminal

Building the function $\sigma$ such that $\sigma(U)$ is a minimal terminal string deriving from $U$ is done above with a rather naive technique that requires iteratively reconsidering work already done when a new smaller derived string is found for some non-terminal. This is wasteful, even if the process will clearly terminate.

We propose here a more efficient algorithm, that is, in essence, an adaptation to the CF grammar graph of an extension of Dijkstra's shortest path algorithm to and-or graphs, with a proper definition of the path-concept for an and-or graph. This variant of the algorithm probably exists in the literature (assuming it is correct), but I have been unable to find it in the resources I can access. Hence I am describing it in more details, together with a proof.

As previously, we first remove from the set of rules to be processed all recursive rules (i.e. rules with a LHS symbol occurring in the RHS string). It is obvious that none of these recursive rules can derive to a shorter terminal string than the non-recursive rules with the same LHS. And, for a LHS $U$ there must be at least one non-recursive $U$-rule if the symbol $U$ is not a useless non-terminal (because non-productive). This is not strictly necessary, but reduces the number of rules to be considered later.

Then we procede as before to build the set $Prod$ of productive symbols, associating with each synbol $X$ a terminal string, which we note $\sigma(X)$, which is a size-minimal terminal string derivable from $X$ (in the previous algorithm, that was true only after termination).The set $Prod$ is initialized with all terminal symbols, and for each terminal symbol $a$, we define $\sigma(a)=a$.

Then we consider every rule $U\rightarrow\gamma$ such that all RHS symbols are in $Prod$, and we choose one such that $\sigma(\gamma)$ is size-minimal. Then we add $U$ to $Prod$, with $\sigma(U)=\sigma(\gamma)$, and remove all $U$-rules. We iterate until all productives terminals have been entered in $Prod$. Any non-terminal $U$, once entered in $Prod$, never has to be considered again to change $\sigma(U)$ for a smaller string.

**Proof**:

The previous algorithms were more or less intuitively obvious. This one is a bit trickier, because of the and-or character of the graph, and a proof seems more necessary. All we need is actually the following lemma, which establishes the correctness of the algorithm when applied to the last iteration.

*Lemma*: After each iteration of the algorithm, $\sigma(X)$ is a size-minimal terminal string derivable from $X$, for all $X$ in $Prod$.

The base step is obvious, since this is true by definition for all terminals in $Prod$ when it is initialized.

Then, assuming it is true after some non-terminals have been added to $Prod$, let $U\rightarrow\gamma$ be the rule chosen to add a new non-terminal to $Prod$. We know that this rule is chosen because $\gamma\in{Prod}^\*$ and $\sigma(\gamma)$ is size-minimal over all RHS of all rules with a RHS in ${Prod}^\*$. Then $U$ is added to $Prod$, and we have only to prove that $\sigma(\gamma)$ is a size-minimal terminal string derivable from $U$.

This is obviously the case for all derivations beginning with the rule $U\rightarrow\gamma$, since by induction hypothesis, application of mapping $\sigma$ is such that all non-terminals in $\sigma$ are substituted with size-minimal terminal strings deriving from them. Hence no other derivation can produce a shorter terminal string.

We thus consider only derivations starting with another $U$-rule $U\rightarrow\beta$, such that $\beta\overset{\*}{\Longrightarrow}w\in\Sigma^\*$, where $\Sigma$ is the set of terminal symbols.

If $\beta\in{Prod}^\*$, then a minimal string it can derive on is $\sigma(\beta)$. But, since we chose the rule $U\rightarrow\gamma$, it must be that $|\sigma(\beta)|\geq|\sigma(\gamma)|$. So the rule $U\rightarrow\beta$ does not derive on a smaller terminal substring.

The last case to consider is when $\beta\notin{Prod}^\*$, and we then consider a derivation $\beta\overset{\*}{\Longrightarrow}w\in\Sigma^\*$. If that derivation involves only non-trminals in $Prod$, then $\beta\in{Prod}^\*$, which is a case we have already seen. Hence we consider only derivations that have steps using a rule with its LHS not in $Prod$. Let $V\rightarrow\alpha$ be such a rule, such that $\alpha\in{Prod}^\*$.There must be at least one such rule since they are partially ordered by derivation order, and $w\in{Prod}^\*$.

Thus we have $U\Longrightarrow\beta\overset{\*}{\Longrightarrow}\mu V\nu$. We know that $\mu$ and $\nu$ derive on a string of size at least 0, and since no $V$-rule with a RHS in ${Prod}^\*$ was chosen, they derive on terminal strings of length at least equal to $|\sigma(\gamma)|$. Hence, with the rule $U\rightarrow\beta$, $U$ derives on a terminal string of length at least equal to $|\sigma(\gamma)|$. $\blacksquare$
> 3 votes

# Answer
## A simple solution

If you don't care too much about the number of strings, there is an easy solution. Basically, for each production, we will generate a string that covers that production.

How do we do that? It's a straightforward worklist algorithm. Suppose we want to cover the production $A ::= BCx$. Basically, we do breadth-first search starting from the start non-terminal $S$ to find a derivation that includes the non-terminal $A$ on the right hand side: initially, all non-terminals are unmarked, and the set of reachable non-terminals is $\\{S\\}$; in each iteration, we pick one unmarked reachable non-terminal, say $X$, and for each production with $X$ on the left-hand side, we add all the non-terminals on the right to the set of reachable terminals, then we mark $X$. Repeat until this process finds that $A$ is reachable. When it does, by backtracing, you obtain a derivation of the form $S \to \cdots A \cdots$. You can extend this to a derivation of the form $S \to \cdots A \cdots \to \cdots BCx \cdots$.

Next, we need to complete the derivation, by picking some way to complete it to be all non-terminals. This is also easy. For each non-terminal, we find the shortest string that is in the language generated by that non-terminals. This can be obtained by a worklist iteration. Let $\ell(A)$ denote the length of the shortest string we've found so far in the language generated by $A$. Initially, we set $\ell(A)=\infty$ for all non-terminals $A$, unless there is a production $A ::= xyz$ where all the symbols on the right-hand side are terminals; in that case, we set $\ell(A)$ accordingly (e.g., $\ell(A)=3$ if the production tells us that $xyz$ is in $L(A)$). Now we iteratively look for a way to find a shorter string. If you have a production like $A ::= xBCy$, you know that $\ell(A) \le 2 + \ell(B) + \ell(C)$; so any time you find a new shorter string in $L(B)$ or $L(C)$ (i.e., any time you update $\ell(B)$ or $\ell(C)$ to be smaller), you can check whether this gives you a new shorter string in $L(A)$, and if so, reduce the value of $\ell(A)$... which may in turn cause other cascading changes. Keep applying all cascading changes until no further changes are triggered. At that point, you have reached a fixed point, and by backtracing, for each non-terminal you know the shortest string (of terminals) that can be derived from that non-terminal.

Now, given your derivation of the form $S \to \cdots BCx \cdots$, find a way to complete the derivation: replace each non-terminal in $\cdots BCx \cdots$ with the shortest string (of terminals) that can be derived from it.

This gives you a string (of terminals) that covers the production $A ::= BCx$. Do this once for each production, until all of them are covered.

The number of strings is equal to the number of productions. The running time is quadratic: the process is linear-time for each production. (You could probably reduce it to be a linear-time algorithm in total, but I suspect this will be good enough in practice.)

## Optimizations

If you want to reduce the number of strings, you might notice that each string will typically cover many productions, so a subset of these strings will probably suffice.

There are many ways you could reduce the number of strings. One simple one is to use the standard greedy approximation algorithm for set cover. Start by generating all of the strings as above, one for each production, and count how many productions each string covers. Keep the string that covers the most productions; that one you definitely want, so add it to your set of keepers. Now some of the productions are covered by this keeper, so we don't need any new strings that cover them again. Thus, you should update your set of counts for each strings: for string $s$, count the number of productions that are covered by $s$ but aren't covered by any keeper. Pick the string that has the largest number, add it to your set of keepers, and update the counts again. Repeat until all productions have been covered. This will likely give you a significantly smaller set of strings that cover all productions in your grammar.
> 2 votes

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


# Question
Title: Prove that an $n$-length string has $2^n$ i18n-style abbreviations
An i18n-style abbreviation is one in which multiple letters are shortened to that number of letters. E.g., "internationalization" -\> "i18n" ("nternationalizatio" is substituted with its length 18). Other abbreviations include "in17n", "i17on", "in16on", etc. I see a pattern in which words with at least 3 characters have $2^{n-2}-1$ different abbreviations. E.g.,

* hat - h1t (1 possible abbreviation)
* code - co1e, c1de, c2e (3 abbreviations)
* words - wor1s, wo1ds, wo2s, w1rds, w1r1s, w2ds, w3s (7 abbreviations)
* active - acti1e, act1ve, act2e, ac1ive, ac1i1e, ac2ve, ac3e, a1tive, a1ti1e, a1t1ve, a1t2e, a2ive, a2i1e, a3ve, a4e (15 abbreviations)

The pattern is apparent, but how do I prove that this is the case?

# Answer
> 2 votes
The proof should be easy once you've modeled the problem sufficiently precisely. Your examples demonstrate some assumptions about possible abbreviations that you don't describe in the accompanying text.

* The first and last letter are always kept unchanged. For example, `hat` can only be abbreviated `h1t` (or left unabbreviated).
* If successive letters are abbreviated, then they must all be included in the same number. An equivalent way to state this is that you cannot have consecutive numbers in an abbreviation. For example, `code` cannot be abbreviated as `c11e`: if both the `o` and the `d` are abbreviated then the number `2` must be used to replace them both together.
* You seem to waver as to whether the original word counts as a (trivial) abbreviation. I'll include it as an abbreviation in my answer.

Under these rules, an abbreviation is uniquely determined by the set of letters to abbreviate. A letter that can be abbreviated is determined by its position, which is an index between $2$ and $n-1$ where $n$ is the number of letters in the word. Therefore, for a word of length $n \ge 2$, the set of possible abbreviations is uniquely determined by the set of indices in the range $\[2,n-1\]$ to abbreviate. In mathematical terms, there is a bijection between abbreviations of a given word of length $n$ and the set of all subsets of $\[2,n-1\]$.

The set of integers $\[2,n-1\]$ has $n-2$ elements. The set of its subsets $\mathscr{P}(\[2,n-1\])$ has $2^{n-2}$ elements. Given the bijection above, the number of abbreviations is also $2^{n-2}$.

---

Follow-up exercise (significantly harder): some of these abbreviations are useless, in that they are no shorter than the original. There is one trivial abbreviation where all the letters are kept, but there are also abbreviations which involve the replacement of a single letter by `1`, such as `h1t` (no shorter than `hat`) or `a2i1e` (no shorter than `a2ive`). How many abbreviations actually shorten the word?

---
Tags: proof-techniques
---


# Question
Title: Set cover problem with constant size subset
Consider a variation of the set cover problem in which the size of the subsets is no larger than a constant $k$. Is this variation still NP-hard?

# Answer
> 4 votes
The problem is NP-hard for $k\ge3$. It has a straightforward reduction from the 3-dimensional matching problem.

---
Tags: algorithms, np-complete, np-hard, set-cover
---


# Question
Title: How does the OS know the physical address of a process' first memory page?
If I have a program, its instructions are stored on the hard drive. When I double-click the executable the pages of memory for this process must get loaded in to RAM. However, for the pages to get loaded in to RAM, the CPU must already have resolved the virtual address to physical address. The latter requires the TLB to have been involved- which requires the L1 cache to have been queried- which cannot have happened as the process instructions haven't even been loaded in to RAM yet?

I am totally confused how the instructions for a process are loaded in to RAM the very first time when the L1 cache doesn't contain any information about the process.

# Answer
> 10 votes
The operating system performs a lot of work before executing the first instruction. The OS must set up at least two data structures, the page table and the *region map*. The region map is called different things in different operating systems. Inside the Linux kernel, for example, it is a linked list of memory-region objects and some kind of index (e.g. a red-black tree) that gives you an efficient way of discovering the region a specific virtual addresses belongs to.

Each memory region has a start address, a length, permissions (can the program read/write/execute from the region), and some information about the "type" of the region, including how the region is supposed to be initialized on first use and how the logical information is supposed to be saved if a mapped page needs to be moved to disk.

The first step is that the operating system creates a new page table with every virtual page marked as "invalid." Next the OS reads the header of the executable file. The header describes the region map and also gives the virtual address of the first instruction to be executed. So the OS creates an in-memory region map to match the structure described in the executable header and then tries to execute the first instruction (it does this by using some kind of "return from interrupt" instruction that sets the root of the page table to the page table for the process we want and then changing the program-counter (instruction-pointer) to the virtual address of the first instruction.

So the processor tries to execute the instruction at the given virtual address. But every page in the page-table is marked invalid, so when the processor performs the translation from virtual to physical address the processor will invoke an "invalid page" fault, bringing control back to the operating system. The operating system will look up the virtual address in the region map. Since this was supposed to be the address of the first instruction, then it should be the case that the virtual address is contained in a region that is marked as being executable, and there should be information about where the instructions are located in the original executable file. The OS reads a page-worth of date from the original executable file into some physical page in memory, and then modifies the page table to reflect the new virtual-to-physical mapping. Finally the OS again tries to return-from-interrupt to the instruction address. This time, although there will be TLB misses and cache misses, the translation will give a mapping from virtual to physical address, the processor will eventually try to fetch the required instruction into the L1 cache and execute it.

In all likelihood the instruction will try to access some not-yet valid data location. There will be another "invalid page" fault for the data's virtual address. The OS will look up the data's virtual address in the region map, allocate a physical page, initialize the page, map the page in the page table and then return-from-interrupt a third time. This time the instruction will get fetched and executed, and after another TLB and cache miss for the data access will actually execute without causing another fault. Then we move to the next instruction and start all over again.

Hopefully we have some spatial and/or temporal locality so this process doesn't happen with every instruction.

---
Tags: operating-systems, memory-management, cpu-cache, process-scheduling
---


# Question
Title: Represent a real number without loss of precision
Current floating point (ANSI C float, double) allow to represent an **approximation** of a real number.
Is there any way to **represent real numbers without errors**?
Here's an idea I had, which is anything but perfect.
For example, 1/3 is 0.33333333...(base 10) or o.01010101...(base 2), but also 0.1(base 3)
Is it a good idea to implement this "structure":

```
base, mantissa, exponent

```

so 1/3 could be 3^-1

```
{[11] = base 3, [1.0] mantissa, [-1] exponent}

```

Any other ideas?

# Answer
It all depends what you want to do.

For example, what you show is a great way of representing rational numbers. But it still can't represent something like $\pi$ or $e$ perfectly.

In fact, many languages such as Haskell and Scheme have built in support for rational numbers, storing them in the form $\frac{a}{b}$ where $a,b$ are integers.

The main reason that these aren't widely used is performance. Floating point numbers are a bit imprecise, but their operations are implemented in hardware. Your proposed system allows for greater precision, but requires several steps to implement, as opposed to a single operation that can be performed in hardware.

It's known that some real numbers are uncomputable, such as the halting numbers. There is no algorithm enumerating its digits, unlike $\pi$, where we can calculate the $n$th digit as long as we wait long enough.

If you want real precision for things irrational or transcendental numbers, you'd likely need to use some sort of system of symbolic algebra, then get a final answer in symbolic form, which you could approximate to any number of digits. However, because of the undecidability problems outlined above, this approach is necessarily limited. It is still good for things like approximating integrals or infinite series.
> 20 votes

# Answer
There is no way to represent all real numbers without errors if each number is to have a finite representation. There are uncountably many real numbers but only countably many finite strings of 1's and 0's that you could use to represent them with.
> 20 votes

# Answer
There are many effective Rational Number implementations but one that has been proposed many times and can even handle **some** irrationals quite well is Continued Fractions.

Quote from Continued Fractions by Darren C. Collins:

> Theorem 5-1. - The continued fraction expression of a real number is finite if and only if the real number is rational.

Quote fromMathworld - Periodic Continued Fractions

> ... a continued fraction is periodic iff it is a root of a quadratic polynomial.

i.e. all roots can be expressed as periodic continued fractions.

There is also an Exact Continued Fraction for π which surprised m e until @AndrejBauer pointed out that it actually isn't.
> 7 votes

# Answer
Your idea does not work because a number represented in base $b$ with mantissa $m$ and exponent $e$ is the rational number $b \cdot m^{-e}$, thus your representation works precisely for rational numbers and no others. You cannot represent $\sqrt{2}$ for instance.

There is a whole branch of computable mathematics which deals with exact real arithmetic. Many data structures for representing **exact** real numbers have been proposed: streams of digits, streams of affine contractions, Cauchy sequences of rationals, Cauchy sequences of dyadic rationals, Dedekind cuts, sequences of shkrinking intervals, etc. There are implementations of exact real arithmetic based on these ideas, for instance:

Of these iRRAM is the most mature and efficient. Marshall in an experimental project, while the third one is a student project, but also the most easily accessible one. It has a very nice introduction explaining the issues regarding real number computation, I highly recommed that you look at it.

Let me make a remark. Someone will object that an infinite object cannot be represented by a computer. In some sense this is true, but in another it is not. We never ever have to represent an *entire* real number, we only need a *finite approximation* at each stage of the computation. Thus, we only need a representation which can represent a real up to any given precision. Of course, once we run out of computer memory we run out of computer memory -- but that is a limitation of the computer, not the representation itself. This situation is no different than many others in programming. For instance, people use integers in Python and they think of them as "arbitrarily large" even though of course they cannot exceed the size of available memory. Sometimes infinity is a useful approximation for a very large finite number.

Furthermore, I often hear the claim that computers can only deal with *computable* real numbers. This misses two important points. First, computers have access to data from the external world, so we would also have to make (the unverifiable) assumption that the external world is computable as well. Second, we need to distinguish between what reals a computer can compute, and what reals it can represent. For instance, if we choose streams of digits as the representation of reals then it is perfectly possible to *represent* a non-computable real: if someone gave it to us we would know how to represent it. But if we choose to represent reals as pieces of source code that compute digits, then we could not represent non-computable reals, obviously.

In any case, this topic is best tackled with some further reading.
> 7 votes

# Answer
There are a number of "exact real" suggestions in the comments (e.g. continued fractions, linear fractional transformations, etc). The typical catch is that while you can compute answers to a formula, equality is often undecidable.

However, if you're just interested in algebraic numbers, then you're in luck: The theory of real closed fields is complete, o-minimal, and decidable. This was proven by Tarski in 1948.

But there's a catch. You don't want to use Tarski's algorithm, since it's in the complexity class NONELEMENTARY, which is as impractical as impractical algorithms can get. There are more recent methods which get the complexity down to DEXP, which is the best we currently know.

Note that the problem is NP-hard because it includes SAT. However, it's not known (or believed) to be in NP.

**EDIT** I'm going to try to explain this a little more.

The framework for understanding all of this is a decision problem known as Satisfiability Modulo Theories, or SMT for short. Basically, we want to solve SAT for a theory built on top of classical logic.

So we start with first order classical logic with an equality test. Which function symbols we want to include and what their axioms are determine whether or not the theory is decidable.

There are lots of interesting theories expressed in the SMT framework. For example, there are theories of data structures (e.g. lists, binary trees, etc) which are used to help prove programs correct, and the theory of Euclidean geometry. But for our purpose, we're looking at theories of different kinds of number.

Presburger arithmetic is the theory of natural numbers with addition. This theory is decidable.

Peano arithmetic is the theory of natural numbers with addition and multiplication. This theory is not decidable, as famously proven by Gödel.

Tarski arithmetic is the theory of the real numbers with all field operations (addition, subtraction, multiplication, and division). Interestingly, this theory is decidable. This was a highly counter-intuitive result at the time. You might assume that because it's a "superset" of the natural numbers it's "harder", but this isn't the case; compare linear programming over the rationals with linear programming over the integers, for example.

It may not seem obvious that satisfiabilty is all you need, but it is. For example, if you want to test whether or not the positive square root of 2 is equal to the real cube root of 3, you can express this as the satisfiability problem:

$$\exists x. x\>0 \wedge x^2 - 2 = 0 \wedge x^3 - 3 = 0$$

So then there's the question as to what other operations you can add to Tarski arithmetic and still keep decidability. The next obvious things to add are elementary transcendental operations like $e^x$, and the trigonometric functions.

It turns out that the theory of reals with $\sin$ is undecidable, because $\\{ \frac{x}{\pi} | \sin x = 0 \\}$ is the integers. Given the reals and $\sin$, you can construct the theory of integers, and the theory of integers is undecidable.

Tarski conjectured that real fields plus $e^x$ is undecidable. I don't know if anyone has proven that it isn't decidable, but I know that nobdody has yet proven that it is decidable. He believed that the reason why this is likely is because of what happens in the complex plane; if you have $e^{ix}$, then you automatically have trigonometry.

---

Alfred Tarski (1948), *A Decision Method for Elementary Algebra and Geometry*.
> 5 votes

# Answer
There is no way to represent a real number since they cannot really be represented in the real world. We can give approximations of them, arbitrary symbols for them like $\pi$, or ways to get them like $\sqrt2$, but there actual value can never be truly represented. You would have to start dealing with them purely symbolically and hope they factor out. However even them, there is no way to account for all of them since as David said, there is not enough strings to give these symbolic representations.
> 1 votes

# Answer
It's possible to represent a very large class of numbers called *algebraic numbers* exactly, by treating them as roots of polynomials.

This article as well as this mathoverflow question have more information, as well as many more resources about this topic. As far as I know, this method still fails to represent transcendental numbers such as $\pi$ or $e$, unless some generalization of it has been discovered. There are many other issues with this method, such as additional solutions to simple addition appearing out of "nowhere" (also known as the complex plane). It's a tradeoff, use your good judgement to tell if it's useful for you.
> 1 votes

# Answer
You cannot represent all real numbers in a computer, but you can represent many. You could use fractions which would represent more numbers than floats. You could also do more sophisticated things like representing numbers as a root of some polynomial with an approximation that under newtons method will converge to the number.
> -1 votes

---
Tags: binary-arithmetic, arithmetic, floating-point, real-numbers, number-formats
---


# Question
Title: What are the meanings of metalanguage and metasyntax and EBNF?
I am trying to understand what BNF, metalanguage, and metasyntax are.

From https://proofwiki.org/wiki/Definition:Metalanguage

> **A metalanguage of a formal language** is a formal language used to **specify** the formal language (make statements about the formal language).
>
> **The object language of a metalanguage** is the language **described** by that metalanguage.

1. From https://proofwiki.org/wiki/Definition:Syntax

> **The syntax of a formal language** is its structure, and is **specified** by a formal grammar of the formal language.

So I wonder if a formal grammar of a formal language is a metalanguage of the formal language?
2. From https://proofwiki.org/wiki/Definition:Metalanguage/Metasyntax

> The syntax of a metalanguage is called **a metasyntax of the object language of that metalanguage**.

From http://en.wikipedia.org/wiki/Extended\_Backus–Naur\_Form

> **Extended Backus–Naur Form (EBNF)** is a family of **metasyntax** notations, any of which can be used to **express** a context-free grammar.

Does it mean that a context-free grammar is a metalanguage of a context-free language, and EBNF is a syntax for the context-free grammar as a metalanguage, and therefore EBNF is a metasyntax for the context-free language as a object language?
3. From http://en.wikipedia.org/wiki/Metasyntax

> A **metasyntax** describes the allowable structure and composition of phrases and sentences of a metalanguage, which is used to describe either a natural language or a computer programming language.
>
> Some of the widely used **formal metalanguages** for computer languages are **Backus–Naur Form (BNF)**, **Extended Backus–Naur Form (EBNF)**, Wirth syntax notation (WSN), and Augmented Backus–Naur Form (ABNF).

Does it mean that EBNF is a metalanguage of a formal language, and this formal language is a context-free grammar?

Thanks and regards!

# Answer
> 4 votes
In general, informally, a metalanguage is a language used to talk about a language, possibly to specify it or to study its properties.

For example, linguists use English to describe the English language. As a consequence English is used as its own metalanguage. To avoid confusion, various quoting system are used to distinguish the two level. For example, when talking about a small animal that barks, we use the word "dog". Here, "dog" represent a word of a language being talked about, not any of the possible meanings of that word in the language it belongs to. It cannot bite.

When a language A is used as metalanguage to talk about a language B, B is called the object language. But, though sometimes used in a formal way, this is very similar to saying that wheather is the object of many conversations.

In computer science, a well known example is the programming language ML. The name ML actually stand for metalanguage. ML was initially conceived by Robin Milner as a metalanguage to develop proofs about a small language called `pplambda` in the LCF theorem prover. Hence, both syntactic and semantic properties of `pplambda` can be expressed in ML.

Another well known example is Lisp, a language that is its own meta language, and has been the first programming language to have that property. Lisp programs can be syntactically represented as a Lisp data structure. The semantics of Lisp is also expressed in Lisp, since the first Lisp interpreter was written in Lisp.

This works so well that the feat has since be often repeated for many other programming languages, and it is very customary to write the first compiler of a language in the language itself, as part of a language bootstrapping process. Hence the language is self compiling. This requires defining both the syntax and the semantics of the language in itself.

So, in effect, most programming languages are, or can be, a metalanguage for themselves, and for other programming languages. That is actually the least one can expect from languages that often claim to have Turing power.

The concept of metalanguage often concerns a conplete object language, whether natural language or programming language, with syntax and semantics. But it can also concern languages in the formal language sense, which are only syntax. A mathematical formalism used to describe (a family of) formal languages (regular sets, context-free, recursively enumerable, ...) is a metalanguage for this formal language.

This is more interesting when the syntax of the metalanguage belongs to the same language family as the formal languages it describes. The best known example is the BNF language (Backus-Naur Form), and its later EBNF variant. It is a language used to write context-free (CF) grammars, thus to define purely syntactic languages. Its own syntax is context-free, hence describable in BNF. Hence BNF can be syntactically its own metalanguage, but not semantically. But then, BNF describes only CF languages and has no claim for Turing power.

It is to be noted that BNF has a CF syntax, but it also has semantics. The semantics of a BNF program is precisely a CF grammar and the formal language it defines, to which the BNF program associates no semantics. A context-free grammar just defines a formal language, and no semantics is associated. Hence it is wrong to consider that BNF is a CF grammar. BNF has a CF grammar which defines its syntax.

**Answering your questions**

Regarding the two preliminary quotes. They are expressed in the context of formal systems, and "formal" means mathematically defined, which may include both syntax and semantics for the language. It does not contradict the above discussion, but rather confirms it.

1. A formal grammar of a formal language is **not** a metalanguage of the formal language. The mathematical formalism used to write the grammar is in this case the metalanguage.

The quote goes into an issue that I did not address here, that of the structure that a syntax definition can attach to the strings of a formal language. It is, as far as I see, quite unrelated to the concept of metalanguage, when we talk of formal languages in the formal language theory sense. Two different syntactic definitions can produce the same language, when considering only the string it defines for the language. But these definitions implicitly associate diffrerent structures with the string (such as parse-trees in the context-free case) and that can be important.

When the formal language is actually the syntax of a complete language that also has semantics, the structure is important as it is usually organizing the definition of the semantics, which is the purpose of many metalanguages.
2. As written above, a context-free grammar cannot be a metalanguage since it has no semantics. The formalism used to write the CF grammar is a metalanguage for the purely syntactic formal language defined by this CF grammar. EBNF is a language with both syntax and semantics. A program (or whatever you want to call it: text, description, grammar, ...) written in EBNF is a text using the syntax of EBNF. This text has a meaning, defined by the semantics of EBNF, which is the CF grammar it describes. EBNF is not a metasyntax, but a meta language for syntax.

This calls for more precision. I consider that the word metasyntax is just shorthand for the expression "syntax of \[a/the\] metalanguage". I do not ses what other meaning it could have.

The first quote is just nonsense to me. The second quote is poorly phrased and should rather be (if I understand the intent):

> Extended Backus-Naur Form (EBNF) is a family of metalanguages for defining syntax, any of which can be used to express a context-free grammar.
3. The quote (out of its context) is in agreement with what I said so far. The expression "formal metalanguage" is not to be understood as formal language in the formal language theory sense, but as a language with a formally, i.e., mathematically, defined syntax and semantics.

This quote alone just say that EBNF is a widely used metalanguage for computer languages, but without being more precise about it. Actually, according to me, EBNF is a metalanguage for (more than one) formal languages in the formal language theory sense, since it can only talk about the syntax, and pure syntax without semantics may be seen as such a formal language. But these formal languages are those described by the grammars expressed in EBNF. A grammar itself is not a language, but it may be part of a language seen as a global object of study, since it can describe its syntax.

I hope this clarifies things.

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


# Question
Title: Why is there readonly (const) in C++, but not writeonly (sink)?
C++ initially had "readonly" and "writeonly" qualifiers, before "readonly" was renamed to "const", and "writeonly" removed. My question is: What are the problems with "writeonly" (or a "sink" qualifier)?

---

There are (non-object oriented) programming languages with "in", "out" and "inout" qualifier for functions arguments. In that context, the meaning of "out" is pretty clear. Writing "result\_p = result\_p+1" is not allowed if "out int& result\_p", and the question whether "result\_p += 1" is allowed doesn't arise, because these languages don't have "+=" and similar constructs.

Now "sink" in C++ would be a type qualifier, not just a function argument qualifier. The meaning of "sink" is clear on a semantic level. Information is only allowed to flow into a "sink" qualified object, but no information is allowed to leave a "sink" qualified object. So writing "result\_p += 1" would be allowed if "sink int& result\_p", but what about "result\_p = result\_p+1"? Its semantic is fine, but there seem to be no general way to check this based on simple syntax or typing rules. But so what, does anything bad happens if "result\_p = result\_p+1" is not allowed?

# Answer
If the question is interpreted in the historical way (as done by Wandering Logic), then the answer can indeed by found in "Bjarne Stroustrup, The Design and Evolution of C++" in section "3.8 Constants". The `readonly` and `writeonly` qualifiers were proposed in January 1981 by Stroustrup as a modification of the C language (not of the C with classes language), long before C++ even existed (but C with classes already existed and was mature). An internal Bell Labs C standards group requested that `readonly` be renamed to `const`, and agreed that it would be introduced into C then (which somehow didn't happen at the time). Stroustrup waited for this to happen, and in the meantime discovered that `const` could also be used to provide symbolic constants (the `parameter` keyword in fortran). The proposal for `writeonly` was not well worked out, didn't provide additional use cases beyond its main purpose in function interfaces, and wasn't accepted by the internal standard group. So `writeonly` wasn't removed by a conscious decision, but just didn't manage to convince enough people of its usefulness. Because Stroustrup still brings up `writeonly` when describing `const`, we can even guess that he's still proud of his initial idea.

> What are the problems with `writeonly` (or a "sink" qualifier)?

* For a language like C with ++ and += operators that return references to the modified object, the question whether this returned reference should be write only is difficult to resolve. The reference returned by the += operator should probably be a `sink`, but some uses of ++ need a non-`sink` returned reference.
* An appropriate formal semantic of a `sink` qualifier is not obvious, and Stroustrup didn't work out a satisfying formal semantic either.
* Even without exceptions, error handling becomes problematic and surprising. As a real world example, I remember me debugging through a "write only" "progress provider", which triggered a GUI update and thereby caused a cancel button to propagate its state to a "cancel provider". If the "progress provider" was replaced by a dummy implementation (when no progress was desired for certain use case), suddenly that "cancel provider" stopped working correctly. An this was even harmless compared to another "progress provider", which just took care of the cancel functionality himself by throwing an exception, thereby crashing the program in many multithreaded and distributed scenarios.
These two examples show some of the real world issues that a `sink` qualifier should address. But this is a much more tricky problem compared to the problems solved by `const`, and it is not clear how a formal semantic resolving these issues can look like.
* ??? (I forgot for the moment, maybe I will remember later)

> But so what, does anything bad happens if "result\_p = result\_p+1" is not allowed?

The answer by Wandering Logic and his reaction to requests for clarification in the comments provide good examples for the bad things that would happen:

* "An append operation for vectors most certainly can not be writeonly, because it must increment the length of the vector (i.e., length = length+1.)"
* "I'm glad Stroustrup didn't invent a language where `x+=1` has different type than `x=x+1`"

Having a half baked language feature would only lead to confusion and frustration, which could never be outweighed by the benefits of the feature. So if one would want such a `sink` feature, then one also needs a formal semantic which closely models the intended (informal) semantic. Some sort of preorder on the accessible references seems required, which determines how information is allowed to flow. But can this preorder always be generated implicitly, or does the programmer sometimes need to also specify details of this preorder? But this all seems to be quite complicated for the limited benefits provided by a `sink` modifier.
> 3 votes

# Answer
I can only hypothesize, so maybe this should only be a comment, but it's too long for the comment box.

In general Stroustrup tries extremely hard to avoid adding new keywords to the language, so if he discovered that there was another way to get whatever "expressivity" `writeonly` might provide he would remove the keyword.

My guess is that he actually couldn't find much use for `writeonly.` Stroustrup came from an Operating Systems background, and (according to \[1\]) a lot of the stuff about `const` and `friend` originally derived from analogies to O.S. access rights. (For `const`, think read/write/execute permissions on files in Unix, and for `friend` think of one program granting access permissions to another program.)

The analogy apparently only goes so far though. The usefulness of a `writeonly` parameter would seem to be that it allows you to return more than one value (but you can return a `pair` or a `struct` in C++, and you can "return" an error code by throwing an exception, and perhaps one return value plus an error code is the common case.) Declaring a non-parameter variable as `writeonly` makes no sense, because then you would need to do a cast in order to do anything with the value. A `writeonly` function is a constructor, and C++ already has those using a different syntax (that doesn't require a new keyword.) An `append` operation for vectors most certainly can not be `writeonly`, because it must increment the length of the vector (i.e., `length = length+1`.)

\[1\] Bjarne Stroustrup, *The Design and Evolution of C++*, Addison-Wesley, 1994.
> 4 votes

---
Tags: concurrency, semantics, access-control
---


title: How "coplanar" is a set of points?

text:
# Question
Title: How "coplanar" is a set of points?
Assume that we have 10 points. If all those points are on the same plane, they all are coplanar. But some of them might be at a different place. That disrupts the structure of the plane if we were to draw the surface that passes from all the points.

I need a metric that tells me how fine the structure of the plane is preserved. Or how planar is the surface.

What I have thought is, take random 3 points among 10 and derive the plane equation in terms of $ax + by + cz = d$. Then, for each remaining point $p(p\_x,p\_y,p\_z)$, calculate the summation $ap\_x + bp\_y + cp\_z$. Store the results and take the standard deviation.

However this method fails for the following reason:
If there are 9 points on the same plane and only 1 point is far away, and if I pick the point who is far away, then the equation I generate is way too different then the plane defined by remaining 9 points.

Plugging the coordinates of remaining points into the equation of the plane, I'll get too many different results. Therefore, even though the surface is almost planar, standard deviation will be so high, depending on the generated equation.

This problem (I think) can be reduced to line cover problem (covering a set of points in 2D with minimum number of lines), hence, NP-Complete.

Or is it really? Is there a polynomial time algorithm that guarantees to find a value for all types of point sets?

I thought about starting not with 3 but with 4 points, then testing the other points. Does that work?

# Answer
Option 1: Use least squares fit to find the closest plane. Then, measure the average squared error (the sum of the squared residuals).

Option 2: Use robust regression instead of least squares. Or, use RANSAC. These will handle outliers better.

All of these run in polynomial time.
> 4 votes

---
Tags: algorithms, np-complete, computational-geometry
---


# Question
Title: Why is there only a polynomial number of provers in multi-prover interactive protocols?
The paper *On The Power of Multi-prover Interactive Protocols* by Fortnow, Rompel, Sipser states the following:

1. There are provers $P\_1, P\_2, \dots, P\_k$ in a multi-prover interactive proof system such that $k$ is polynomial in the size of the input. The value of $k$ cannot exceed a polynomial because this would prevent the verifier in the system from accessing all the provers.
2. In one round a verifier can interact with more than one prover.

Since a verifier can interact with more than one prover in one round, is the real reason that the number of provers must be polynomial due to the fact that the total length of the messages to *all* the provers in one round must be polynomial in the length of the input?

# Answer
Yes. We could have defined MIP to allow an exponential number of provers but that is basically the PCP model which is equivalent to MIP with a polynomial (or just two) provers.
> 2 votes

---
Tags: complexity-theory, interactive-proof-systems
---


# Question
Title: Simulating a sequence of events concurrently subject to a happened-before partial order
I am building a strategy game where multiple units(5 - 20) is fighting each other in the same time.

I have a logic part that calculate those actions for each turn, and than pass it to the game engine to animate. This is the list of action that I currently supporting:

* perform attack
* perform miss
* perform taking damage
* perform dying
* perform moving

If I animate all the actions at once than it look messy:

> Unit A attacks unit B, while unit B is not even there, it went to attack unit C

If I animate all the actions one by one, than it looks lame

> Unit A attacks unit B, the other 18 units is just stand and waiting for the unknown...

## How can I find what actions I can perform in parallel?

For now my best solution, is to wait for unit to finish attacking before attacking it, it cover many scenarios but it still got halls.

> Unit A attacks unit B, unit C waiting for A to finish attacking in order to attack him. Unit D attacks and kill unit C.

## Edit based on D.W answer:

This solution cover most of the cases but, I found a hall in it.

Think about the next scenario

> A attacks B, B attacks C, C attacks D

Because each of those action has a dependency on the prevues one, your algorithm would suggest to break it in to 3 sequences.

* A attacks B
* B attacks C
* C attacks D

How ever I would like to break it in to, two sequences:

* A attacks B, C attack D
* B attacks C

I want to use your algorithm solution iff B kills C.

# Answer
> 4 votes
Try identifying all dependencies between actions, then build a DAG that represents the dependencies: each vertex is an action, each edge is a dependency between two actions. From this you can identify how to perform the maximum number of actions in parallel. Basically, the algorithm is:

1. Find all the sources. Perform all of those actions at once.
2. Delete all of those sources, and the edges going out of them.
3. Go back to step 1.

A *source* is a vertex with in-degree zero, i.e., with no edges entering into it. In your context, it will be an action all of whose dependencies have been satisfied.

For instance, if action 1 must occur before action 2, which must occur before action 4, and action 3 must occur before action 4, the resulting order you get using this algorithm is: first actions 1 + 3 are performed (because they are the two sources); then action 2; then action 4.

---
Tags: concurrency, threads
---