# Question
Title: Given a set of LTL formulas, on which states does the Kripke structure hold?
I'm currently learning about LTL and CTL formulas and to get a better understanding I try to manually interpret the formulas over a given Kripke structure. Since I'm not 100% sure if my results are correct I would appreciate if anyone can verify them.

**Task:**

I showed on which states the given LTL formular hold.

**Some LTL notation notes:**

$X$ equals $\bigcirc$

$G$ equals $\Box$

$F$ equals $\diamond$

1. $Fc = \\{\\}$

My interpretation: $Fc$ means that on all paths $c$ holds sometimes the future. Since all paths come along $t4$ it doesn't hold for any state.
2. $G(b \vee c) = \\{\\}$

My interpretation: For all paths holds globally b or c.
3. $G(Fb) = \\{t0, t1, t2, t3, t4, t5, t6\\}$

My interpretation: For all paths holds globally that eventually b will be true.
4. $G(b \Rightarrow (Xa \Rightarrow Xb)) = \\{t0, t1, t2, t3, t4, t5, t6\\}$

My interpretation: Since $Xa \Rightarrow Xb$ is true for every state the implication $b \Rightarrow (Xa \Rightarrow Xb)$ must hold for all states too sinde $? \Rightarrow true$ is always true.
5. $a U (b U c) = \\{t1, t3, t4, t5\\}$

My interpretation: Following paths are valid: aaaaabbbc, bbbbc, c, ccc. Therefore the states $t1, t3, t4, t5$ are valid.

So can anybody confirm my results?

# Answer
A couple of comments:

1. Note that "in the future" is not strict, i.e. $Fb$ is also satisfied whenever $b$ itself holds.
2. Looks fine to me.
3. Also ok, though I'm not sure if your interpretation would be very enlightening in a more complicated Kripke structure.
4. "$Xa\Rightarrow Xb$ is true for every state" is a CTL-ism. What you want to say is that for every state along every path, if $a$ holds in this state and $b$ holds in the next state, then $a$ also holds in the next state.Is this the case?
5. Here you want some finite number (possibly $0$) of $a$s, followed by some finite number (possibly $0$) of $b$s, followed by a $c$. Is this what you see along every path starting in the states you give?
> 1 votes

---
Tags: logic, model-checking, linear-temporal-logic, temporal-logic
---


# Question
Title: Approximating the set of witnesses of a BPP algorithm
Let $\mathcal{A}$ be a randomized algorithm that decides a language $\mathcal{L}$. For each input $x\in\mathcal{L}$, we define the set of witnesses of $x$ as $W(\mathcal{A},x) = \\{r\in\\{0,1\\}^n:\mathcal{A}(x,r) \text{ accepts}\\}$. Suppose that $\mathcal{A}$ is a $\mathsf{BPP}$ algorithm. We wish to show that there exists an algorithm $\mathcal{A}'$ also deciding $\mathcal{L}$ such that $$ |W(\mathcal{A}',x)| \geq \frac{2^n}{4}, \qquad \text{and} \qquad \big|\\{0,1\\}^n - W(\mathcal{A}', x)\big| \geq \frac{2^n}{4} $$ for all input $x\in\mathcal{L}$.

I am sincerely lost for this problem. An idea that was vaguely suggested to me was to flip two fair coins and proceed based on the result: trivially accept if the result is $(1,1)$, trivially reject if it's $(0,0)$ and run the $\mathsf{BPP}$ algorithm for the other two remaining cases. However, I am not sure how exactly that could be of any help, of if another way can be found.

Any help would be appreciated.

# Answer
> 3 votes
The idea suggested to you was helpful. It basically amounts to suggesting a candidate algorithm $\mathcal{A}'$.

Your next step is to try bounding $|W(\mathcal{A}',x)|$ and $|\\{0,1\\}^n - W(\mathcal{A}',x)|$ for that choice of $\mathcal{A}'$. See what you can come up with. See if you can relate $|W(\mathcal{A}',x)|$ to $|W(\mathcal{A},x)|$ etc.

---
Tags: complexity-theory, randomized-algorithms
---


# Question
Title: How can I formalize key value stores with set theory?
I'm currently developing a simple key-value NoSQL store and want to build its formal model. I found article about key value formalisation with category theory, but I'm interested are there some works about formalisation of key-value stores except category theory (I know we can use it for all, but...)? I want to use some more simple and lightweight mathematics for mathematical description of key-value stores. And I feel that set theory will be enough for this, but couldn't find any helpful articles.

# Answer
One simple way to model a key-value store is as a map $f:K \to V$ where $K$ is the set of possible keys and $V$ is the set of possible values.

Often, each value $v \in V$ will itself be a tuple or record. You can represent a tuple as a Cartesian cross-product, e.g., $V = V\_1 \times V\_2 \times \dots \times V\_k$. You can represent a record as either a tuple (if the set of attributes is finite and known in advance), or as a function from attribute names to values.

Modelling languages like Alloy can represent such maps natively. Some modeling languages will use the notation $k.f$ instead of $f(k)$ (i.e., object field access notation instead of function evaluation), but the two are equivalent.

If you don't want to use functions, but want to stick to just sets, that is also feasible. You can model any function $f: K \to V$ as a binary relation, i.e., a set $S \subseteq K \times V$ with the additional property that if $(k\_1,v\_1) \in S$ and $(k\_2,v\_2) \in S$ and $k\_1=k\_2$, then $v\_1=v\_2$. However this may be less natural.

This gives you a way to model the state of the store. You will then need to model the effect of each operation that can be performed on the store, in these mathematical terms.
> 1 votes

---
Tags: sets, database-theory, databases, category-theory, storage
---


# Question
Title: Information Systems (IS) and Data Warehouse
I'm working on a research project about the adoption of DWH systems and doing some literature review I find many documents that refer to Information System. I tried to find the right definition of information system and if a data warehouse can be considered an IS or not, or is just a subset of it. In the wider definition IS comprises also persons and policy and not only the technology (software or hardware). So it become complicated in my opinion to define it. From my personal work experience a DWH is an IS, the hearth of IS. But what about from the academic and computer science point of view? If any *system* with data can be an IS, the extent is that an spreadsheet might be considered as an IS.

# Answer
> 0 votes
Yes, I'd say that a data warehouse is an information system. It stores information, using information technology; it's an information system.

That said, I think focusing too much on trying to obtain a precise definition of "Information System" and "Data Warehouse" is not likely to be super-helpful. Those are just phrases. "Information system" is a broad phrase that doesn't have an especially precise definition -- it gets used in whatever way the author finds helpful. And that's OK. It doesn't need a precise, universally-agreed-upon definition. It's just an aid to communication. Ultimately, it just doesn't matter that much how we classify data warehouses; if I told you they are (or aren't) an information system, that wouldn't really change how you should think about them.

My advice would be not to worry too much about terminology and trying to classify things into some taxonomy. Instead, think about what are the relevant characteristics and properties of the kinds of data warehouse systems you are looking at. Figure out what is your actual goal, and then identify what characteristics are relevant to that goal, and use that to hone in on the aspects of the system that are relevant. Not all information systems are alike -- the range of issues that arise in information systems is incredibly broad.

---
Tags: terminology, databases
---


# Question
Title: Problems in P with provably faster randomized algorithms
Are there any problems in $\mathsf{P}$ that have randomized algorithms beating lower bounds on deterministic algorithms? More concretely, do we know any $k$ for which $\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)$? Here $\mathsf{PTIME}(f(n))$ means the set of languages decidable by a randomized TM with constant-bounded (one or two-sided) error in $f(n)$ steps.

> Does randomness buy us anything inside $\mathsf{P}$?

To be clear, I am looking for something where the difference is asymptotic (preferably polynomial, but I would settle for polylogarithmic), not just a constant.

*I am looking for algorithms asymptotically better in the worst case. Algorithms with better expected complexity are not what I am looking for. I mean randomized algorithms as in RP or BPP not ZPP.*

# Answer
> 17 votes
***Polynomial identity testing*** admits a randomised polynomial time algorithm (see the Schwartz-Zippel lemma), and we currently don't have a deterministic polynomial time or even a sub-exponential time algorithm for it.

***Game tree evaluation*** Consider a complete binary tree with $n$ leaf nodes each storing a 0/1 value. The internal nodes contain OR/AND gates in alternate levels. It can be proved using adversary argument that every deterministic algorithm would have to examine $\Omega{(n)}$ leaf nodes in the worst case. However there is a simple randomised algorithm which takes has *expected* running time of $O(n^{0.793})$ Look at slides 14-27 of the talk.

***Oblivious routing on a hypercube*** Consider a cube in $n$-dimensions containing $N=2^n$ vertices. Each vertex has a packet of data and a destination that it wants to eventually deliver the packet to. The destination of all the packets are different. Even for this, It has been proved that any deterministic routing strategy would take $\Omega{\big(\sqrt{\frac{N}{n}}\big)}$ steps. However, there is a simple randomised strategy which will finish in *expected* $O(n)$ steps *with high probability*.

Note that in randomised algorithms, the expected cost $E(F(n))$ *with high probability* (like for eg. $Pr\[F(n) \> 10 \cdot E(F(n))\] \< \frac{1}{n^2}$) is equivalent to worst case in practice.

# Answer
> 5 votes
Investigating the worst-case is meaningless for randomised algorithms. Not only will the worst-case runtime often be infinite but also they *can not* outperform deterministic algorithms in that metric.

Consider any randomised algorithm $A$. Obtain a deterministic algorithm $B$ by fixing the random tape for $A$ to $0^\infty$. Then, $T\_B(n) \leq T\_A(n)$ for all $n$.

# Answer
> 5 votes
There are many problems where we know of an efficient randomized algorithm, and we don't know of any deterministic algorithm that we can prove is efficient. However, this may reflect shortcomings in our ability to prove things about complexity rather than any fundamental difference.

Based on your comment, it appears you meant to ask whether there exists any problem where there is an efficient randomized algorithm, and we can *prove* there is no deterministic algorithm of comparable efficiency. I don't know of any such problem.

Indeed, there are reasonable grounds to suspect that such problems might be unlikely to exist. Heuristically, the existence of such a problem would likely mean that secure cryptography is impossible. That seems like a rather implausible outcome.

What's the connection, you ask? Well, consider any randomized algorithm $A$ that solves some problem efficiently. It relies upon random coins: random bits obtained from a true-random source. Now suppose we take a cryptographic-quality pseudorandom generator, and replace the true-random source with the output of the pseudorandom generator. Call the resulting algorithm $A'$. Note that $A'$ is a deterministic algorithm and its running time is approximately the same as $A$.

Also, if the cryptographic PRNG is secure, heuristically we should expect $A'$ to be a good algorithm if $A$ is:

* For instance, if $A$ is a Las Vegas algorithm (it always outputs the correct answer, and terminates rapidly with high probability), then $A'$ will be a pretty good deterministic algorithm (always outputs the correct answer, and terminates rapidly for most inputs).
* As another example, if $A'$ is a Monte Carlo algorithm (deterministic running time, and outputs the correct answer with probability at least $1-\varepsilon$), then $A$ will be a pretty good deterministic algorithm (deterministic running time, and outputs the correct answer on a fraction $1-\varepsilon$ of all inputs).

Therefore, if the cryptographic PRNG is secure and there is an efficient randomized algorithm, you get a deterministic algorithm that is pretty good. Now there are many constructions of cryptographic PRNGs that are guaranteed to be secure if certain cryptographic assumptions hold. In practice, those cryptographic assumptions are widely believed: at least, secure commerce and transactions rely upon them being true, so we're apparently willing to bet large sums of money that secure cryptography exists. The only way this transformation can fail is if cryptographic PRNG don't exist, which in turn implies secure cryptography is impossible. While we don't have any proof that this isn't the case, it seems like an unlikely outcome.

Details of the construction: Here's how $A'$ works. On input $x$, it derives a seed for the cryptographic PRNG as a function of $x$ (e.g., by hashing $x$), and then simulates $A(x)$, using the output of the cryptographic PRNG as the coins for $A$. For instance, a specific instantiation would be to set $k=\text{SHA256}(x)$, then use $k$ as the seed for AES256 in counter mode, or some other cryptographic PRNG. We can prove the above statements under the random oracle model.

If you're unhappy with the idea that $A'$ might output incorrect results on some small fraction of inputs, that can be addressed. If you repeat $A'$ multiple times and take a majority vote, the error probability decreases exponentially fast in the number of iterations. So, by iterating a constant number of times, you can get the error probability $\varepsilon$ to be below $1/2^{256}$, which means the chances that you run across an input $x$ where the algorithm outputs the wrong answer are vanishingly small (less than the chances of getting struck by lightning multiple times in a row). Moreover, with the construction I gave above, the chances that an adversary can even *find* an input $x$ where $A'$ gives the wrong answer can be made very small, as that would require breaking the security of the SHA256 hash. (Technically, this requires the random oracle model to justify, so it means that $A$ must be chosen to be "independent" of SHA256 and not hardcode in it calculations that are related to SHA256, but almost all real-world algorithms will satisfy that requirement.)

If you want a stronger theoretical basis, you can iterate $A$ $\Theta(n)$ times, and get the error probability to be below $1/2^n$, where $n$ is the length of the input $x$. Now the fraction of $n$-bit inputs where $A'$ gives an incorrect answer is strictly less than $1/2^n$. But there are only $2^n$ possible $n$-bit inputs, and on each one $A$ is either correct or incorrect, so it follows that there is no input where $A'$ is incorrect: $A'$ is correct on all inputs, and this holds unconditionally. If $A$ runs in time $t(n)$, then $A'$ runs in time $\Theta(n \cdot t(n))$, so $A'$ is a bit slower than $A$ but not too much slower. This is the content of Adleman's proof that BPP is contained in P/poly. For practical purposes this is probably overkill, but if you like clean proofs that avoid cryptographic assumptions or if you approach this from a theoretician's perspective then you might like this version better.

For more details on the latter theoretical considerations and additional problems where we know of an efficient randomized algorithm but we don't know of any deterministic algorithm that we can prove is efficient, see https://cstheory.stackexchange.com/q/31195/5038

In summary: For any problem where we know an efficient randomized algorithm, we also know of a deterministic algorithm that seems likely to be efficient in practice -- but at present we don't know how to *prove* that it is efficient. One possible interpretation is that we're just not very good at proving stuff about algorithms.

---
Tags: algorithms, complexity-theory, randomized-algorithms
---


# Question
Title: Is the question of whether the language of a DFA/CFG is equal to a particular set of string decidable?
Suppose I have a set of strings $S$ that is generated from the alphabet. Suppose I have a DFA $D$ and a CFG $G$, are the questions of

* $\\{D\mid D\text{ is a DFA and }L(D) = S\\}$ and
* $\\{G\mid G\text{ is a CFG and }L(G) = S\\}$

decidable?

I know that the easier question of whether $D$ or $G$ generates a particular string $w$ or whether the language is the empty-language is decidable, but how can I decide on a particular set of strings?

I am thinking for the case of DFA I can do something like set-difference and check if $L(D/S)$ is empty.

For the case of CFG since it is not closed under complement is this question undecideable?

# Answer
Let's assume that $S$ is regular and given in some explicit form (DFA, regular grammar, regular expression, what have you). Given a DFA $D$, we can compute a DFA for $L(D) \triangle S$ (here $\triangle$ is symmetric difference) and check whether it is empty or not. This allows us to decide whether $L(D) = S$ or not.

Given a CFG $G$, we can compute a CFG $G'$ for $G \cap \overline{S}$, and then check whether $L(G') = \emptyset$. This allows us to check whether $L(G) \subseteq S$. However, in general we cannot check the opposite inclusion: determining whether $L(G) = \Sigma^\*$ is undecidable (the universality problem). However, if $S$ is finite, we can check whether $G$ generates each of the strings in $S$, and thereby solve the problem.
> 3 votes

# Answer
If S is finite, then the answer is trivially "yes", for both questions.

If not, we have to know how it is (formally) defined. For instance, if it is defined by a Turing machine, then the answer is "no". In addition, the problem of equivalence of DFAs has a simple solution, but the equivalence of CFGs is undecidable.
> 2 votes

---
Tags: computability, context-free, finite-automata, undecidability
---


# Question
Title: Is there an intuitive proof for the existence of hard functions?
I am referring to the theorem on page 115 of the book by Arora and Barak, which states that, \`\`For every $n\>1$, there exists a function $f:\\{0,1\\}^n \rightarrow \\{0,1\\}$ that cannot be computed by a circuit $C$ of size $\frac{2^n}{10n}$"

* Can someone give a more intuitive proof of this than the one presented there?

For example he proof there at one point claims with little justification that there are at most $2^{0.92^n}$ circuits of size at most $\frac{2^n}{10n}$. Why? I couldn't reproduce this \`\`0.92" thing!

* It seems that one even improve this theorem to higher lower bound of $\frac{2^n}{n}$. Can someone kindly help do that? How much up can one get this?

# Answer
As Pål GD mentions in his comment, the proof is actually very simple: there are $2^{2^n}$ functions, but only $C\_S = S^{O(S)}$ circuits of size at most $S \geq n$. The exact constant in the exponent depends on the exact definition of a circuit. Getting the best exponent requires some rather intricate arguments, together with the assumption $S = \omega(n)$. We then compute the maximal $S$ such that $C\_S \< 2^{2^n}$, and conclude that there must be a function that cannot be computed by a circuit of size at most $S$. The answer is $S = O(2^n/n)$, and we usually really don't care about the hidden constant; we tend to abstract away constants in complexity theory.

The same argument shows, with very small modifications, that a random function has circuit complexity $\Omega(2^n/n)$ in expectation and with high probability.

How about an *explicit* function with complexity $\Omega(2^n/n)$? This is a difficult open problem. The best lower bounds we have for explicit functions are $\Omega(n^3)$ for Andreev's function (see Komargodski–Raz–Tal for the best result in this direction). I am told that obtaining anything better than $\Omega(n^3)$ would be difficult due to the natural proof barrier.
> 9 votes

---
Tags: complexity-theory, lower-bounds, circuits, boolean-algebra
---


# Question
Title: Is there a complexity viewpoint of Galois' theorem?
* Galois's theorem effectively says that one cannot express the roots of a polynomial of degree \>= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a polynomial there is no deterministic algorithm to find the roots?
* Now consider a decision question of the form, "Given a real rooted polynomial $p$ and a number k is the third and the fourth highest root of $p$ at least at a gap of k?"

A proof certificate for this decision question will just be the set of roots of this polynomial and that is short certificate and hence it looks like $NP$ BUT isn't Galois theorem saying that there does not exist any deterministic algorithm to find a certificate for this decision question? (and this property if true rules out any algorithm to decide the answer to this question)

So in what complexity class does this decision question lie in?

---

All NP-complete questions I have seen always have a trivial exponential time algorithm available to solve them. I don't know if this is expected to be a property which should always be true for all NP-complete questions. For this decision question this doesn't seem to be true.

# Answer
> 5 votes
Interesting connection, however Galois theory states that no (consistent) method exists for finding roots of quintic using radicals, instead of saying that the problem has a solution (eg a longest path) which may require super-polynomial time. So i would say it is more related to undecidability rather than complexity.

Specificaly, in Galois theory one progressively builds group extensions of the roots of the equation, in a step-by-step way (adding one root at a time). And all these groups should be solvable, in a sense there should be no ambiguity in the process of constructing these extensions in another order. There is a related question on MO on the complexity of constructing the Galois group of an equation.

Another reference here "COMPUTATIONAL GALOIS THEORY: INVARIANTS AND COMPUTATIONS OVER $\mathbb{Q}$", CLAUS FIEKER JURGEN KLUNERS

Furthermore one can systematicaly represent roots of a polynomial euqation using radicals (when the equation **is solvable** using radicals) based on the construction of the Galois group(s) of the equation. Ref: "Radical Representation of Polynomial Roots", Hirokazu Anai Kazuhiro Yokoyama 2002

The computational complexity of determining if a given monic irreducible polynomial over the integers $\mathbb{Z}$, is soluble by radicals is in $\mathbb{P}$ Ref "Solvability by Radicals Is in Polynomial Time", S. Landau G.L Miller 1984

A survey of recent "Techniques for the Computation of Galois Groups", Alexander Hulpke

Of course if one is looking for good approximation algorithms and their complexity (e.g Newton's method or Sturm's Theorem) this is a slightly different question and the already posted answer provides more infomation in that direction.

# Answer
> 11 votes
I assume you are considering polynomials with *integer* coefficients.

You've taken the wrong starting point for your investigations; your goal is to find *good estimates* for the real roots. Looking for an algebraic formula so that you can evaluate it to enough precision is something you can do, but it's not really the right thing to do here. (unless, of course, "the `k`-th largest real root of a polynomial" is one of your algebraic operations)

A much better starting point is to use *Sturm's theorem* to isolate the roots of the polynomial. You can then produce better estimates by binary search, but if that's too slow, you can use *Newton's method* to quickly produce estimates of high precision.

---

But that's just about *finding* certificates. There's still the question of what certificates can exist.

First off, I will point out that you can directly compute whether or not two of the roots are *exactly* $k$ units apart, e.g. by computing $\gcd(p(x), p(x-k))$. You will also have to decide what you want to do about repeated roots and deal with appropriately. I assume you will deal with these case specially.

If we know the two roots are *not* exactly $k$ units apart, that means that you can produce an estimate of sufficient precision to prove that they are either greater or less than $k$ units apart. e.g. there are two kinds of certificates:

The first kind (proof in the negative) is

* $a$ is not a root of $p$
* $p$ has no roots in $(a-k, a)$
* $p$ has three roots in $(a, \infty)$

The second kind (proof in the positive) is

* $a$ is not a root of $p$
* $p$ has at least two roots in $(a-k,a)$
* $p$ has two roots in $(a, \infty)$

A certificate can be verified by using Sturm's theorem. Now, your question about the size of a certificate boils down to finding how many bits of precision you need to represent $a$.

In other words, what are the bounds on the possible values of $a-b-k$, where $a,b$ are roots of $f$?

I'm not sure of a great approach, but one that should give you something is to observe that all of these values are roots of the polynomial:

$$ g(x) = \mathop{\text{Res}\_y}(f(y), f(x + y + k)) $$

Why? Recall that the resultant of two monic polynomials is the product of all differences of their roots, so

$$ g(x) = c^{d^2} \prod\_{a,b}(b - (a - x - k)) = \prod\_{a,b} (x - (a-b-k))$$

where $c$ is the leading coefficient and $d$ is the degree of $f$. (maybe I've written the formula for $-g(x)$ instead of $g(x)$; I'm never sure on the sign)

So the question is to find estimates for how large the coefficients $g$ can be, and then once you know that, find estimates to how close a root of $g$ can be to zero.

(or, alternatively, find the largest magnitude that a root of the reverse polynomial of $g$ can have; the roots of the reverse polynomial are the inverses of the roots of $g$)

# Answer
> 3 votes
am going to take your questions as mostly open ended. the galois proof now known as the Abel-Ruffini thm shows the impossibility of polynomial solutions to the quintic. (in contrast to eg the quadratic equation). so its not really a result on the *hardness* of a problem per se but rather the *impossibility*. in this sense it is more analogous to eg a proof of undecidability of the halting problem. complexity theory is in general concerned with the "cost" of computing solutions. that is the viewpoint of two leading CS researchers in the introductory section of this following paper (Computability and Complexity / Kleinberg & Papadimitriou), sec 1 The Quest for the Quintic Formula:

> Viewed from the safe distance of a few centuries, the story is clearly one about com- putation, and it contains many of the key ingredients that arise in later efforts to model computation: We take a computational process that we understand intuitively (solving an equation, in this case), formulate a precise model, and from the model derive some highly unexpected consequences about the computational power of the process. It is precisely this approach that we wish to apply to computation in general.

elsewhere a loose/ general analogy might be that a P$\neq$NP proof (or other complexity class separation) is analogous to a computational impossibility result somewhat like the Abel-Ruffini thm. a separation result says roughly that problems of a certain type cannot be solved with "computational resources" of another certain type. a P$\neq$NP theorem would be viewed as a (monumental) computational impossibility result.

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


# Question
Title: Linearizability and Serializability in context of Software Transactional Memory
I've been trying to grasp serializability and linearizability in the context of software transactional memory. However, I think both notions can be applied to transactional memory in general.

At this point, the following is my understanding of both subjects.

# Serializability

> Serializability is a *global* property. It is a correctness property of transactions. Given `k` processes that each execute a transaction `Tk`concurrently, serializability ensures that there is a sequence of transactions that can be executed in sequence (i.e., one after the other) **such that the end result is the same** as the transactions being executed concurrently. So there is a permutation of the list `(T1, T2,..,Tk)` that defines a list of transactions that can be executed sequentially.

This property makes perfect sense to me and I think my definition is correct. I based this definition on the text in "The Art of Multiprocessor programming" by Herlihy and Shavit.

# Linearizability

> Linearizability is a *local* property of concurrent objects (e.g., an instance of a class that is shared amongst threads). Linearizability ensures that when two processes each execute a series op method calls (e.g., `queue` or `dequeue` on a `Queue` instance) on that shared object there is a sequential ordering of these method calls that does *not* necessarily preserve program order (the order in which the programmer wrote them down), but each method call does seem to happen instantly (i.e., invocation and response follow each other directly), whilst maintaining the result of each method call individually and consequently the object its state.

# Question

According to a paper `"On the correctness of TM"` by Guerraoui and Kapalka this is the definition of linearizability in context of TM:

> .. a safety property devised to describe shared objects, is sometimes used as a correctnes criterian for TM. In the TM terminology linearizability means that intuitively, every transaction should appear as if it took place at some single unique point in time during its lifespan.

This definition just seems to resemble serializability to me. But the paper further on defines serializability as follows:

> .. is one of the most commonly required properties of a database transaction. Roughly speaking, a history H of transactions (i.e., the sequence of all operations performed by all transactions in a given execution) is serializable if all committed transactions in H issue the same operations and receive the same responses as in some sequential history S that consists of only the committed transactions in H. (A sequential history is one without concurrency between the transactions).

This definition however seems to imply that one can reorder statements from transactions in such a way that they are interleaved. (I.e. reorder the statements such that not all the statements of a transaction `T` appear in sequence in `H`).

---

I am under the assumption that my personal above definitions are correct. My actual question is how linearizability is defined in the context of transactional memory. It makes no sense to reason about each method call (i.e., read/write operation) in a transaction individually as this would break the semantic of transactional memory. Nor would it make sense to having to reason about two concurrent transactions their interleavings, as this would obviously break serializability. Does linearizability mean that one can reorder individual operations inside a transaction? If linearizability is a stronger form of serializability, it should not matter in which order the operations are executed inside a single transaction.

In short: First of all, is my understanding of serializability and linearizability correct? I am confused after reading a plethora of definitions in different works. And second, what does it mean for a set of transaction to be linearizable?

I have also read the question that was linked inside of the comments. But it did not explain to me my specific question.

# Sources

# Answer
> 6 votes
**About your definitions:**

The basic idea of Serializability ($\textsf{SR}$) is correct. However, it does not have to constrain itself on the your assumption that `each (process) executes a transaction`: Every process can issue as many transactions as they want.

Your understanding of Linearizability ($\textsf{LR}$) is quite wrong. First, for both $\textsf{SR}$ and $\textsf{LR}$, program order between transactions issued by a single process must be preserved. Furthermore, you cannot reorder any operations within a transaction.

**Explaination of $\textsf{SR}$ and $\textsf{LR}$:**

Both $\textsf{SR}$ and $\textsf{LR}$ require all the transactions to behave as if they were executed in some sequential order $H$, meaning that in such a sequential order, all `reads` operations return the same values and the end states of the database is the same as those when the transactions are being executed concurrently.

As mentioned before, for both $\textsf{SR}$ and $\textsf{LR}$, program order between transactions issued by a single process must be preserved.

The above gives the difinition of $\textsf{SR}$. However, $\textsf{LR}$ further requires the sequential order $H$ to obey the so-called real-time (partial) order between transactions: If a transaction $T\_1$ *ends* before another transaction $T\_2$ *starts*, then $T\_1$ must be ordered before $T\_2$ in $H$.

Notice that $\textsf{SR}$ does not enforce the real-time order. That is to say, $\textsf{LR}$ is stronger than $\textsf{SR}$.

**About global property and local property:**

I don't know whether $\textsf{SR}$ is called a global property (please give me some reference if you are sure about this). However, the term "local property" has its special meaning.

> A property $P$ of a concurrent system is said to be *local* if the system as a whole satisfies $P$ whenever each individual object satisfies $P$.

It is known that $\textsf{LR}$ is local \[1\] while $\textsf{SR}$ is not.

**ADDED: About LR and Strict Serializability (SSR)**

As mentioned by @Wandering Logic, LR is originally defined for objects, not for transactions. Quoted from \[1\]；

> Linearizability can be viewed as a special case of strict serializability where transactions are restricted to consist of a single operation applied to a single object.

However, nowadays, many authors have used $\textsf{LR}$ for transactions. For instance, in their seminal paper \[2\], Shavit and Touitou used the term $\textsf{LR}$ for transactions. When used for transactions, $\textsf{LR}$ is the same as $\textsf{SSR}$.

Thanks @Wandering Logic for the discussions.

---

\[1\] Linearizability: A Correctness Condition for Concurrent Objects. By M P. Herlihy and J M. Wing. ACM Transactions on Programming Languages and Systems, Vol. 12, No. 3, July 1990.

\[2\] Software Transactional Memory. By Nir Shavit and Dan Touitou. Distrib. Comput. (1997) 10: 99-116.

# Answer
> 2 votes
Your definition of serializability is correct, and equivalent to the definition of Guerraoui and Kapalka that you quote. Guerraoui and Kapalka's definition, like yours, requires all the instructions inside transaction $T\_k$ to appear to execute and to execute in order. That is: the **end result** is as if you had executed the transactions atomically and in some sequential order. (The *implementation* may be optimized with some crazy concurrent, parallel, out-of-order execution scheme, but the result has to look as if you ran all the transactions in some sequential order and with no interleaving.)

Serializability talks about the behavior of transactions without taking into consideration the processes or threads that issued those transactions. (In your definition you have exactly as many processes as transactions, and each process issues exactly one transaction.)

Linearizability takes into account the fact that each thread will issue multiple transactions, and we expect those transactions to execute and complete in the order we asked them to issue.

> A transactional memory system is *strictly serializable* if the end result of any execution is the same as if the transactions of all the processes were executed atomically in some sequential order, and the transactions issued by each individual process appear in this sequence in the order specified by the program of that process.

(This is the definition of *sequential consistency* from Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", *IEEE T Comp* 28(9):690-691, 1979, but modified to talk about transactions instead of memory operations. Herlihy and Wing call this property *strict serializability*.)

The original paper by Herlihy and Wing that defines linearizability was about operations on objects, not transactions. But, the following connects the two concepts:

> Linearizability can be viewed as a special case of strict serializability where transactions are restricted to consist of a single operation applied to a single object.

(Herlihy, Maurice; Wing, Jeanette: Linearizability: A Correctness Condition for Concurrent Objects. ACM T. Prog. Lang. and Sys. 12(3):463-492, 1990.)

---
Tags: distributed-systems, concurrency, databases
---


# Question
Title: Is relative regularity distinct from regularity?
Let $L$ and $G$ be languages over a finite alphabet $\Sigma$. $L$ is *regular relative to* $G$ if $L \subseteq G$ and there is a finite automaton that accepts every input in $L$, and rejects every input in $G \setminus L$; the behaviour of the automaton on inputs in $\Sigma^{\*}\setminus G$ is not specified. Here are some simple facts about relative regularity.

* If $G$ is regular, then so is any $L$ that is regular relative to $G$.
* If $L$ is regular then it is also regular relative to any $G \subseteq \Sigma^{\*}$ in which it is contained.
* If $L \subseteq G$ and $G \setminus L$ is regular then $L$ is regular relative to $G$.
* It is possible that $L$ is regular and regular relative to $G$, but $G$ is not regular. (Let $\Sigma = \\{0,1\\}$, $L = \emptyset$ and take $G$ to be some non-regular language such as the palindromes.)
* It is possible that $L$ and $G$ are not regular but $L$ is regular relative to $G$. (Just take $G=L$.)
* $L$ is regular relative to $G$ iff $L \subseteq G$ and there is some language $S \subseteq \Sigma^{\*}\setminus G$ such that $L \cup S$ is regular.

> If $L$ is regular relative to some $G \subseteq \Sigma^{\*}$, and $G \setminus L$ is not a regular language, is $L$ always regular?

That last fact suggests that the answer should be no, but I can't think of a counterexample.

If this is a standard exercise or the concept has a name then I would appreciate a pointer.

# Answer
How about $G = \\{ a^n b^n : n \geq 0 \\}$ and $L = \\{ a^{2n} b^{2n} : n \geq 0 \\}$?
> 4 votes

# Answer
Can't you define it as: $L$ is *regular relative* to $G$ iff there is a regular language $R$ such that $L=G\cap R$.

If I am correct, it seems more easily understood, more visual.

The essence of what you are asking is then: when you partition a language by intersection with a regular set, is the regularity of one part related in any way to the regularity of the other part.

The answer is no.

Consider the alphabet $\Sigma$ not containing the symbols $a$ and $b$, and two languages $G\_1, G\_2 \subset \Sigma^\*$. Let $G=aG\_1 \cup bG\_2$ and $L=aG\_1$, so that $G\setminus L=bG\_2$.

The language $L$ is regular relative to $G$, with the discriminating regular language $R=a\Sigma^\*$.

But $G\_1$ and $G\_2$ are whatever you want them to be, and prefixing with $a$ or $b$ usually does not change it much, with regard to most families of languages.

This may also provide examples for some of the other points.
> 2 votes

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


title: Find the minimum range

text:
# Question
Title: Find the minimum range
Given a list of numbers as `L`, how do you find the minimum value `m` such that `L` can be made into a strictly ascending list by adding or subtracting values from `[0,m]` from each element of `L` except the last? (Strictly ascending means the new list can't have any duplicates.)

Example #1:

```
for L = [5, 4, 3, 2, 8] the minimum value for `m` is 3.
5 - 3 = 2 # subtract by 3
4 - 1 = 3 # subtract by 1
3 + 1 = 4 # add by 1
2 + 3 = 5 # add by 3
8 untouched # nothing

result = [2, 3, 4, 5, 8]

```

Example #2:

```
for L = [5, 4, 3, 0, 8], minimum value for `m` is 4

```

**NOTE**: I'm not looking for a complete solution just give me few thoughts and clue.

# Answer
> 3 votes
Below I try to prove that the greedy algorithm ($\mathcal{A}$) given by @norbertpy (and @Bergi) is correct. *Please check it.*

---

**Problem Definition:**

The algorithm $\mathcal{A}$ of @norbertpy is for a variant of the original problem:

> To find the minimum positive number $2m$ such that for each item in the array, **adding** a number from $\[0, 2m\]$ can lead to a strictly ascending array?

The solutions to these two problems can be reduced to each other (by $\pm m$). Note that I have ignored the "except the last" part.

---

**A lemma for the property of the algorithm $\mathcal{A}$:**

Let $L'\[n\]$ be the last element of the resulting strictly ascending list of any feasible solution to $L\[1 \ldots n\]$. We first claim that:

> **Lemma:** $\mathcal{A}$ gives the *smallest* value of $L'\[n\]$ among all the feasible solutions to $L\[1 \ldots n\]$.

This lemma can be proved by mathematical induction on the length $n$ of $L$.

---

**Now we prove that $\mathcal{A}$ always gives the optimal solution.**

**Base case:** $n = 1$ and $n = 2$ are trivial.

**Inductive Hypothesis:** Suppose that for any $L\[1 \cdots n-1\]$ of length $n-1$, the algorithm $\mathcal{A}$ gives us the optimal solution $m$.

**Inductive Step:** Consider the $n$-th iteration of the greedy algorithm $\mathcal{A}$: it compare `a = head + 1 - L[n]` with $m$, and take $M = \max(m,a)$ as the feasible solution to $L\[1 \cdots n\]$.

We aim to prove that

> $M$ is the optimal solution to $L\[1 \cdots n\]$.

Suppose, by contradiction, that there is another feasible solution to $L\[1 \cdots n\]$, denoted by $M' \< M$.

First, $m \< M'$: otherwise, $M'$ is a *smaller* feasible solution to $L\[1 \cdots n-1\]$, which contradicts the assumption.

Thus we have $m \< M' \< M$. Because $M = \max(m,a)$, we obtain $m \< M' \< M = a$.

By the lemma above, $L'\[n-1\]$ in the solution corresponding to $M'$ is not less than that in the solution corresponding to $m$. However, $L'\[n\]$ (for $M'$) is less than that for $M$ (because $M' \< a$). According to the way how $a$ is chosen in $\mathcal{A}$, the resulting array (for $M'$) is not strictly ascending. Thus $M'$ cannot be a solution. Contradication.

# Answer
> 1 votes
Inspired by Bergi's answer, I've written this:

```
import math

a = [5, 4, 3, 2, 8]
b = [5, 4, 3, 0, 8]
c = [5, 4, 110, 0, 8]
d = [5, 4, 3, -16, 8]

def hill(a):
    max_m = 0
    head = a[0]
    for item in a[1:]:
        current_m = math.fabs(head + 1 - item)

        if current_m > max_m:
            max_m = current_m

        # update the head for next iteration
        head = item + current_m

    print math.ceil(max_m / 2)

hill(a) # 3.0
hill(b) # 4.0
hill(c) # 107.0
hill(d) # 12.0

```

The logic is, we set the `max_m` to zero and the `head` to first element of the list. We then start iterating through the `list - first element` and find the minimum value `current_m` such that adding `current_m` to the `item` will be equal to `head + 1`. At each iteration of we find a greater `m`, we just store it in `max_m`.

At the end we divide the `m` by 2 since we just used the addition to find the `m` and not the subtraction.

I hope this helps but I'm still not sure if it's correct for all inputs.

# Answer
> 1 votes
I took three test cases `L1 = [5, 4, 3, 2, 8]`, `L2 = [5, 4, 3, 0, 8]` and `L3 = [4, 6, 1, 2, 5, 7]` and performed the following steps:

1. Take the mean, x of all numbers except the last.

```
x1 = mean(L1') = 3.5
x2 = mean(L2') = 3
x3 = mean(L3') = 3.6
L' is the list excluding last number.

```
2. Perform ceil(x) and duplicate the list L into M

```
x1 = 4, x2 = 3, x3 = 4

```
3. Start from the center, M'\[middle\] do:

```
M[i] = --x if i < middle, else
M[i] = ++x if i > middle.

```

Find the maximum difference, **m**(which is the required answer) between each element of `M[i]` and `L[i]`.

http://ideone.com/SwwXjm

---
Tags: algorithms, integers
---


title: A query about serial data transmission

text:
# Question
Title: A query about serial data transmission
I was studying computer science and I learnt that Serial Data transmission is when one bit is transmitted at a time over one wire/channel. Then what does '8 bit serial' data transmission mean? I was studying about MIDI where it said it uses 8 bit serial data transmission and is asynchronous.

Also, I cannot seem to find an appropriate tag to set to this question.

# Answer
> 3 votes
It was probably a rather unfortunate abbreviation of 8-N-1 serial transmission which is what MIDI uses. The 8 bits are sent serially, one at time, still.

---
Tags: terminology, communication-protocols
---


# Question
Title: Constructing a sphere ($S^2$) in HoTT directly?
(this is a repost of https://stackoverflow.com/questions/29802501/constructing-a-sphere-s2-in-hott-directly, which was voted out of SO)

I understand the construction of $S^2$ as a suspension of $S^1$ in homotopy type theory. I wonder whether one can build $S^2$ in one step as a base point and an open 2-surface. Something like this:

```
data Sphere where
  base : Sphere
  skin : Id (Id Sphere base base) refl refl

```

The above is probably something like a sausage with endpoints identified, though.

So my question is: Can an $S^2$ be built as a HIT from a closed 1-ball whose boundary is identified?

# Answer
> 6 votes
This was asked once on the HoTT-cafe list. The answer is "yes" and I composed a short video which explains exactly how this happens.

---
Tags: homotopy-type-theory
---


# Question
Title: Do linearly dependent features in feature vectors improve the feature vector?
I was reading Wiki on feature vectors, and as far as I can see, it suggests creating new features from already existing features:

> Higher-level features can be obtained from already available features and added to the feature vector, for example for the study of diseases the feature 'Age' is useful and is defined as Age = 'Year of birth' - 'Year of death'. This process is referred to as feature construction.

But assuming that you already have included `'Year of birth'` and `'Year of Death'` as features, will adding `'Age'` (that is, `'Year of birth' - 'Year of death'`) as a feature in the feature vector improve it in any way? I'm thinking not, as the variables are linearly dependent.

If it depends on the machine learning algorithm used, I am mostly interested in SVMs.

# Answer
I believe it can. Consider the following thought experiment: we are attempting to predict if a person lived to be over 100. Knowing year of birth provides *some* predictive power (e.g., if they were born after 1912, we know with certainty they did not live to be 100). Year of death also provides some information (people who died closer to the present day are likely to have had a longer lifespan). However "Age" (defined by year of death - year of birth) will be a perfect predictor.
> 4 votes

# Answer
Though edron's thought experiment is nice, it assumes that you do not already have both of those features. If you did, then adding the third feature cannot help, because, as you say, it is linearly dependent. Assume features x1 = Year of birth, x2 = Year of death and x3 = Age = x2-x1. Then any linear predictor gives:

x1\*w1 + x2\*w2 + x3\*w3 = x1\*(w1+w3) + x2\*(w2-w3)

So, nothing has been gained and we could have learned the same thing with the original features.

A better way to augment the features is to add a nonlinear function of features, such as (x2-x1)^2.
> 12 votes

# Answer
the simple answer/ example is that linear regression alone is considered a basic "learning algorithm" and linear combinations of input variables will have no effect on its performance, ie be redundant. wrt SVM, there are a lot of variants, some basic ones linear. generally with most nontrivial learning algorithms, linear combinations of input vectors are redundant, ie will have no effect on performance of the learning algorithm. also inputs in many cases are typically "conditioned/ smoothed" with a PCA-like step which again would dimensionally reduce any redundant (linear dependent) input vectors.

however, none of this excludes creating *nonlinear* combinations of input vectors, and yes nonlinear combinations of input vectors can in various cases substantially improve the performance of the learning algorithm. each general area of study/ ML application would tend to have some rules-of-thumb for creating nonlinear combinations. also there are a lot of cases of input variables that are roughly correlated, but not totally, and adding them can improve performance of the algorithm. for example in finance, a lot of variables might roughly "trend with the overall market," but not in a strictly correlated way, and the "noncorrelated parts" may actually have useful information the ML algorithm can harness.
> 1 votes

---
Tags: machine-learning
---


title: Instruction level parallelism

text:
# Question
Title: Instruction level parallelism
Can we distinguish instruction level parallelism and SIMD instructions (SSE, 3D now...) ?

Or is SIMD instructions one of the multiple ILP techniques ?

Thank you.

# Answer
> 4 votes
Instruction-level parallelism, data-level parallelism, loop-level parallelism, and task-level parallelism are not well defined terms. The definable concept is *parallelism*. Two operations can run simultaneously (or "in parallel") when the portions of the state they write are non-overlapping, and when the portion of the state written by each operation does not overlap with any of the state read by the other operation.

So two different instructions can run in parallel when the registers and memory they read and write don't overlap. The sub-operations of a SIMD instruction can run in parallel because they are defined to only perform sub-operations that each read or write different portions of a vector register or cache line.

I like to say

> parallelism *is* as parallelism *does*

and what parallelism *does* is run multiple operations simultaneously.

The benefit of SIMD instructions, over just using 4 or 8 or N individual instructions that perform the same sub-operations, is that the fetch, decode, renaming, and scheduling units of the processor don't need to do as much work to exploit the parallelism between the sub-operations.

# Answer
> 0 votes
I would characterize ILP as a stream of instructions going into the CPU and the instructions execute partially overlapped but in a normal serial order (assuming there is nothing but ILP going on).

SIMD is totally different. It's more like just having instructions with really really large registers, like 1024 bits wide, where the instructions operate on the register cut into pieces. For a 1024 bit add that cuts into 32-bit chunks, you can think of a 1024-bit adder that simply doesn't do a carry across boundaries between the 32-bit chunks in the register.

---
Tags: terminology, parallel-computing
---


# Question
Title: Is a subgraph either a spanning subgraph or a full subgraph?
> A graph $G' = (N' ,A')$ is a **spanning subgraph** of a graph $G = (N, A)$ iff $N ' = N$ and $A' \subseteq A$.
>
> A graph $G' = (N',A')$ is a **full subgraph** of a graph $G = (N, A)$ iff $N' \subseteq N$ and $A' = \\{(x,y) \in A \mid x,y \in N '\\}$.

* I have to prove that *"If $G'$ is a subgraph of a graph $G$, then either G' is a spanning subgraph of $G$, or $G'$ is a full subgraph of $G$. If this statement is valid, provide a proof that it is valid, otherwise provide a counterexample"* but isn't a full subgraph actually a spanning subgraph?

I mean that any subgraph of $G$ is a full subgraph in the end, right? Any ideas how I can prove the statement?

* My second question is how to calculate the number of spanning subgraphs of $G$ as a function of the number of nodes in $N$. How can I do this without knowing $A$ or how many edges I have in the graph?

# Answer
On your question "isn't a full subgraph actually a spanning subgraph?". The answer is no, a full subgraph doesn't need to be a spanning subgraph. By your definition, a full subgraph can have lesser number of vertices than in the original graph. However, a spanning subgraph must have exactly the same set of vertices in the original graph.

On your second question "how to calculate the number of spanning subgraphs of $G$ as a function of number of nodes in $N$." Since it is a **fact** that graph $G = (N,A)$ with differing $A$ will have differing number of possible spanning subgraphs, I suspect you might have misunderstood the question. For example, does the question actually only ask for **an upper bound** of the number of possible spanning subgraphs as function of $|N|$?
> 2 votes

---
Tags: graphs
---


# Question
Title: Split-Find: maintaining dynamic graph connectivity information, under edge deletion
Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph?

Let $G$ be an undirected graph. I have two operations I'd like to be able to perform:

* Delete$(u,v)$: delete the edge $(u,v)$ from the graph.
* SameComponent$(u,v)$: returns true or false according to whether $u,v$ are in the same connected component

Is there a data structure that allows me to perform both operations relatively efficiently?

The naive data structure is simply to store the graph in adjacency list representation, and answer SameComponent$(u,v)$ queries by doing a depth-first search from $u$ to see if $v$ is reachable. However, that makes the SameComponent operation take linear time, and it feels like it is re-doing a lot of work, so maybe there is a more efficient algorithm. Is there a data structure where both operations can be done in sub-linear running time?

---

One way to think about it is that I am basically asking for the dual of the Union-Find data structure. The Union-Find data structure offers two operations:

* Union$(u,v)$: add an edge $(u,v)$ to the graph.
* Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).

You could think of this question as asking for a Split-Find data structure, which should support two operations:

* Split$(u,v)$: delete the edge $(u,v)$ from the graph.
* Find$(v)$: return an identifier for the connected component containing $v$ (e.g., a vertex that acts as the representative for the connected component containing $v$).

As we know, there is an efficient Union-Find data structure. The apparent symmetry between Union-Find and Split-Find makes me wonder whether there is also an efficient Split-Find data structure, too.

Of course, if we had an efficient Split-Find data structure, we could answer the original problem: Delete$(u,v)$ would be implemented by calling Split$(u,v)$, and SameComponent$(u,v)$ would be implemented by testing whether Find$(u) = $ Find$(v)$.

So, is there an efficient Split-Find data structure?

# Answer
> 5 votes
It sounds like you're looking for "decremental connectivity". The fastest result I could find was Wulff-Nilson's "Faster deterministic fully-dynamic graph connectivity", which "supports updates (edge insertions/deletions) in $O(\log^2 n/ \log \log n)$ amortized time and connectivity queries in $O(\log n/ \log \log n)$ worst-case time, where $n$ is the number of vertices of the graph."

# Answer
> 0 votes
Here is (the earliest?) ref I know of. It includes data structure motivation and details: https://www.cs.duke.edu/~reif/paper/topdyncon.pdf

---
Tags: graphs, data-structures, union-find
---


# Question
Title: What is happening in this part of the LC3?
This is a diagram of the LC3 Computer

I am trying to understand what is happening in the parts I highlighted. The part I had highlighted had the instruction bit sign extended to 16 bits and then passed on to the SR2 Mux. Does anyone know what instruction is being carried out here or what the role of the mux(SR2) is here?

# Answer
This would appear to be a picture of the LC-3 data path from the book Patt, Yale N; Patel, Sanjay J: *Introduction to Computing Systems*.

The `IR` is the *instruction register*, the register where the actual bits of the instruction are fetched in the beginning cycles of processing the instruction. The `SEXT` unit takes the immediate field out of the instruction. The `SR2MUX` is used by the control unit to control whether the second operand of the instruction comes from a register operand or the immediate operand.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: Are these sets of indices also index sets?
An index set is a set of all indices of some family of computably enumerable sets. It is known that the empty set is an index set and that $K = \\{e \mid e \in W\_e\\}$ is not an index set.

The following was an exam question I didn't manage to answer:

> Which of the following sets are *index sets*?
>
> 1) $\emptyset $
>
> 2) $K= \\{ x \mid x \in W\_x \\}$
>
> 3) $E = \\{2,4,6,8, \dots \\}$
>
> 4) $\\{ x \mid \phi\_x = \phi\_{x^2}\\}$

I think:

It is known $K$ (i.e., the halting set) is not an index set so (2) is ruled out. I read on this on last page problem 4 that the set of even numbers is an index set, so I'm not sure that (1) and (3) is true! But the answer sheet wrote just (1) is true. I don't know what is the definition of $E$ in (3) and not sure about (4).

Can anyone clarify me in order to better understand this challenging question? Why are (3) and (4) not index sets? I'm not familiar with notation (4), any description?

# Answer
We start with a bit of notation:

1. $\phi\_x$ is the partial function computed by program $x$.
2. $W\_x = \operatorname{dom} \phi\_x$, that is, the set of inputs on which program $x$ halts.
3. An *index set* is a set of programs $I$ such that if $\phi\_x = \phi\_y$ then $x \in I \Leftrightarrow y \in I$. (That is, $I$ is a union of equivalence classes of the equivalence relation $x \equiv y \Leftrightarrow \phi\_x = \phi\_y$.)

Rice's theorem immediately shows that if $I$ is a non-trivial index sets (that is, $x \in I$ and $y \notin I$ for some $x,y$) then $I$ is not computable.

We can now go over the four sets in the question:

1. $\emptyset$ is trivially an index set.
2. $K = \\{ e : e \in W\_e \\}$ is not an index set. Indeed, the recursion theorem shows that some $e$ satisfies $W\_e = \\{e\\}$. There are infinitely many programs which halt only on input $e$ and output $\phi\_e(e)$. Pick one of them, $e' \neq e$. Then $e \in K$ and $e' \notin K$ even though $\phi\_e = \phi\_{e'}$. (This proof is taken from S. Barry Cooper, *Computability Theory*, mention by Pål GD in the comments.)
3. $E = \\{2,4,6,8,\ldots\\}$ is computable and so not an index set by Rice's theorem.
4. $\\{ x : \phi\_x = \phi\_{x^2} \\}$ is (probably) not an index set. Indeed, for it to be an index set it must hold that whenever $\phi\_x = \phi\_{x^2} = \phi\_y$ then also $\phi\_y = \phi\_{y^2}$, which sounds unlikely. (The recursion theorem gives us infinitely many $x$ such that $\phi\_x = \phi\_{x^2}$, and for each such $x$, there are infinitely many $y$ such that $\phi\_x = \phi\_y$. It would be a major coincidence if for all $x,y$ we would have $\phi\_y = \phi\_{y^2}$.)

In part 4 there is an argument but not a proof, and this is not a coincidence. Whether $I = \\{ x : \phi\_x = \phi\_{x^2} \\}$ is an index set or not depends on the definition of $\phi$, that is on the universal Turing machine. Every choice corresponds to an admissible numbering, and there are some admissible numberings for which $I$ is an index set (see here), and there are others for which $I$ is not an index set (see here). So the answer for part 4 is really "we don't know" or "it depends". Nevertheless, for any natural admissible numbering, you will find out that $I$ is not an index set; unless you engineer $I$ to be an index set, it won't be an index set.

For convenience, I will repeat the constructions showing that $I$ can be an index set and can be not an index set:

1. $I$ can be an index set: Fix some admissible numbering $\phi\_x$. Let $p\_i$ be the $i$th prime. Define a new admissible numbering $\psi\_x$ by $\psi\_{p\_i^k} = \phi\_i$ for all $k \geq 1$, and $\psi\_x = 0$ whenever $x$ is not a prime power. Thew new admissible numbering satisfies $\psi\_x = \psi\_{x^2}$ for all $x$ and so $I = \mathbb{N}$ is trivially an index set.
2. $I$ can be not an index set: Fix some admissible numbering $\phi\_x$. Define a new admissible numbering $\psi\_x$ by $$ \psi\_x = \begin{cases} 0 & x = 0,1,2,3 \\ 1 & x = 4 \\ \phi\_{x-5} & x \geq 5 \end{cases} $$ In this case $\psi\_1 = \psi\_{1^2} = \psi\_2$ but $\psi\_2 \neq \psi\_{2^2}$, showing that $I$ is not an index set.

I conjecture that under some reasonable interpretation, the fraction of admissible numberings for which $I$ is an index set tends to zero.
> 6 votes

# Answer
Let's review what an index set is.

> Given a Gödel numbering $\phi$ and a set $P \subseteq \mathcal{P}$ of (partially) recursive functions, we call
>
> $\qquad\displaystyle I\_P := \\{ i \mid \phi\_i \in P \\}$
>
> the *index set* of $\mathcal{P}$.

Assuming that we have a Gödel numbering is central; otherwise we can't do much with this notion, for instance Rice's theorem¹ assumes one². In particular, three of the four proofs below need that $\phi$ is a Gödel numbering.

Working from this definition, we can approach the four candidates.

1. Clearly, $\emptyset = I\_{\emptyset}$.
2. I assume that you mean the standard (special) Halting set, i.e.

$\qquad\displaystyle K = \\{ i \mid \phi\_i(i)\\!\uparrow \\}$.

I will now show that there is some $i^{\star} \in K$ for which *all other* indices of $\phi\_{i^{\star}}$ are not in $K$. Note that this is not trivial; $K$ certainly *does* contain all indices of the empty function (the one that loops everywhere), and *none* of any total function.

Let

$\qquad\displaystyle f(i,x) = \begin{cases} 1, &i \neq x;\\ \uparrow, &i = x.\end{cases}$

Clearly, $f \in \mathcal{P}$. By smn theorem, there is totally recursive $g$ so that $\phi\_{g(i)}(x) = f(i,x)$ for all $i$ and $x$. Now, by fixed-point theorem there is $i^{\star}$ with $\phi\_{g(i^{\star})} = \phi\_{i^{\star}}$; that is,

$\qquad\displaystyle \phi\_{i^{\star}}(x) = \begin{cases} 1, &i^{\star} \neq x;\\ \uparrow, &i^{\star} = x.\end{cases}$

Clearly, $i^{\star} \in K$. Now, since $\phi$ is a Gödel numbering there are infininitely many indices for $\phi\_{i^{\star}}$; $\phi\_{j}(j) = \phi\_{i^{\star}}(j) = 1$, so $j \notin K$. Hence, $K$ let $j \neq i^{\star}$ be any one of them. By definition (of $f$), is not an index set.
3. It is another straight-forward application of smn- and fixpoint theorem to show that for each Gödel numbering, there are functions that have (among others) two indices $i$ and $i+1$. It follows directly that $E = 2\mathbb{N}$ is not an index set.

Use $f(i,x) = \lfloor \tfrac{i}{2} \rfloor$. We obtain that $\phi\_{i^\*} = \lfloor \tfrac{i^\*}{2} \rfloor$ for some $i^\*$. Clearly, $\phi\_{i^\*+1} = \phi\_{i^\*}$ if $\phi\_{i^\*} \in 2\mathbb{N}$, and $\phi\_{i^\*-1} = \phi\_{i^\*}$ if $\phi\_{i^\*} \in 2\mathbb{N}+1$.
4. Yes, and no. There are Gödel numberings for which $M\_{\varphi} = \\{ x \mid \varphi\_x = \varphi\_{x^2} \\}$ is an index set, and there are such for which it is not.

Let $\phi$ be an arbitrary Gödel numbering. We will construct new Gödel numberings for each case.

* With $p\_i$ the $i$th prime number, define

    $\qquad\displaystyle h(x) = \begin{cases} i, &\exists i,k \in \mathbb{N}.\ a=p\_i^k;\\ 1, &\text{else}. \end{cases}$

    Now $\psi$ defined by $\psi\_j = \phi\_{h(j)}$ is a Gödel numbering (check the definition; in particular, $h$ is totally recursive). Furthermore, $M\_\psi = \mathbb{N}$ which is clearly an index set (of $\mathcal{P}$); check the two cases $x = p\_i^k$ for some $i$ and $k \geq 1$ (then $x^2 = p\_i^{2k}$, i.e. $\psi\_x = \phi\_i = \psi\_{x^2}$), and $x \neq p\_i^k$ for all $i,k$ (then $x^2$ is not a power of a single prime either and $\psi\_x = \phi\_1 = \psi\_{x^2}$).
    * Define $\nu$ by

    $\qquad\displaystyle \nu\_x = \begin{cases} \phi\_1, &x \leq 2; \\ \phi\_2, &3 \leq x \leq 4; \\ \phi\_{x-4}, &x \geq 5. \end{cases}$

    Check again the definition to see that $\nu$ is a Gödel numbering. Now, by definition $\nu\_1 = \nu\_2$ but $1 \in M\_\nu$ while $2 \notin M\_\nu$, hence $M\_\nu$ is not an index set.

---

1. If you don't like the Wikipedia article, this may help.
2. There seems to be the notion of admissible numberings but I'm not familiar with that one.
> 2 votes

---
Tags: computability
---


# Question
Title: Can any recursion implementation be written as tail-recursion?
Can any method that uses recursion be written as tail-recursion?

# Answer
You can't rewrite all your recursive calls as tail *recursive* calls but you can rewrite your program in *continuation passing style* which is closely related and has the feature that *every* procedure call is a tail call (just not necessarily a tail *recursive* call.)

The way you do this is by recognizing that every time you make a procedure call you are implicitly specifying a return point. Then you split your procedure into multiple procedures, each starting at a return point and ending at the next call point. Continuation-passing style essentially makes the stack explicit. Once the stack is explicit it is easier to apply certain optimization (like tail recursion elimination).

**Example**

```
procedure depth_first(t):
  if not-null(t):
    l = depth_first(t->left)
    r = depth_first(t->right)
    return l + r + 1
  else:
    return 0

```

The first step is to make every procedure take an extra parameter, `k` which is a *continuation procedure* (a procedure which you return to by calling it with the return value as its parameter). Then you turn the procedure "inside out":

```
procedure depth_first(t, k):
  if not-null(t):
    depth_first(t->left,
       lambda(l):
         depth_first(t->right,
           lambda(r):
             k(l + r + 1)
  else:
    k(0)

```

Should you do it? Well, if you're a compiler and you want to perform tail-recursion elimination optimizations, or generate machine code, then yes. Otherwise probably not. One of the joys of high level languages is that they have syntax that makes continuations much easier for humans to read and understand. Let the compiler do what it's best at and concentrate on writing maintainable code.
> 6 votes

# Answer
Good practice, however understood, does have various style implications, and encourages some programming paradigms over others, but I do not know that using tail recursion is part of it. Some people do prefer recursive style for various reasons, and that may result in a lot of tail recursion. That used to be very common in languages like Lisp or Scheme, and their programmers were probably the first to notice the issue below.

Tail recursion was identified originally (afaik) as a situation where compilers could speed up execution by replacing them by a loop, and saving on stack management. It is only what the name says: a tail recursion, i.e. a recursive call that is the last thing done by the function before returning.

It is a property of the source code. Object code does not have recursion (other than possibly for high level virtual machines, not for tangible hardware), only loops and memory management. Thus no implementation of anything is written as recursion of any kind, including tail recursion.

If that sentence was supposed to ask whether a non-tail recursion can be compiled in the same way as a tail recursion is compiled, the answer is no because non-tail recursion requires preserving existing execution environments (so-called activation blocks) on the stack (usually), for whatever code remains to be executed on return. Only tail recursion can avoid that, since it will not have anything to do on return (well, it is the general idea, some details are skipped).

Of course, all recursions can be transformed into loops with some effort. That is precisely what the compiler does, since object code has no recursion. Then the program has no recursions that are not tail recursions, not having any at all (as David Richerby remarked). Furthermore, translating back in a language rich enough, a loop can be replaced by a tail recursion (skipping many details), so that you can have it all with tail recursion. But it does you no good. It is only an intellectual exercise.

I cannot say this reply was not influenced by David Richerby very good comment.
> -1 votes

# Answer
Given the amount of wrong info dispensed in the other answers, I strongly invite you \[collectively\] to read *Specification and Transformation of Programs* by Helmut A. Partsch; it addresses the topic at length in Chapter 6. Transforming programs (say to turn recursion into tail recursion) is alas not a topic commonly covered in other textbooks.

Briefly: You *can* turn any function that uses recursion into one that uses only tail recursion. The result may not be very pretty to read though; it's akin to removing a goto, i.e. you will need to encode control decisions as predicates.

If I have time, I'll expand on these points, but realistically it won't happen this weekend.
> -1 votes

---
Tags: algorithms, recursion, simulation
---


# Question
Title: Discrete solution space in NP-complete problems
While there are many known NP-complete problems, they all seem to be discrete in the solution space. What is the underlying principle for this?

# Answer
It could appear to be the case that "discrete problems" are hard while "continuous problems" are easy. In fact, the exact question has already been asked on TCS.SE here. The answers list some continuous problems that area actually hard to solve.

As usual, computational problems come in all colors, shapes, and sizes. It is *not* a rule that continuous problems are always easy. In this sense, there is no "underlying principle". I think the following comment by Sasho Nikolov puts it well:

> I think the whole discrete vs continuous thing is a red herring. A problem has to have **very special** structure to be efficiently solvable. I think the real difference here is that in the case of easy continuous problems the special structure tends to be convexity, while in the case of easy discrete problems things look more complicated: sometimes the structure is submodularity or matroid intersection, but often it's not. This probably has more to do with the fact that we don't yet understand discrete math very well.
> 5 votes

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


# Question
Title: Intuition behind the max-flow min-cut theorem
What is the intuition behind the *max-flow min-cut theorem*?

I know that the min-cut is the dual of max-flow when formulated as a linear program, but the result seems artificial to me.

# Answer
> 3 votes
So you have a flow thought the network. If you want the maximal flow, your network should not have any bottlenecks. And if you partition the network in two parts, where the source and the sink are in different partitions - you won't be able to push more though the network than this cut - i.e. the sum of edges.

Now the minimum cut will be the worst bottleneck in the network. So it will correspond to maxflow.

---
Tags: graphs, network-flow, intuition
---


# Question
Title: An algorithm to compute a set of states that satisfy a specific CTL formula
Working through a past exam question and I'm unsure where to start or what form they want the answer in:

*Define an algorithm that receives as input a finite transition system TS defined over the set of actions {a, b, c} and computes the set of states of TS that satisfy the CTL formula ∃a U b.*

Would anybody be able to give me a kick-start or a walk-through on how to answer this? Really appreciate any help.

edit: My attempt based on Klaus' answer

```
for all executions in TS
 for all states
  if **b** holds
   add current state to the stack, EXISTS = TRUE
  else if **a** holds
   if current state == next state in execution
    do nothing
   else if next state contains **a** or **b**
    add current state to the stack, EXISTS = TRUE
   else
    do nothing

```

# Answer
> 3 votes
The set of states satisfying $\exists a U b$ is the smallest set $S$ such that

* $S$ contains all states satisfying $b$, and
* $S$ contains all states satisfying $a$ which have a successor in $S$

Note that we specify the "smallest" such set because otherwise you could pick the set of all states, or include arbitrary cycles of $a$-states, etc. Do you see how to get an algorithm from this?

---
Tags: algorithms, model-checking, computation-tree-logic
---


title: Recent Garbage collection survey paper

text:
# Question
Title: Recent Garbage collection survey paper
Many years ago I read a GC survey paper that was updated every few years with advances; I tried to find such a paper today to point a questioner on Stackoverflow at.

However all I can find is very old survey papers that don’t include current thinking on items like hardware assistance.

# Answer
> 1 votes
the area seems to be "mature" in the sense that garbage collection theory/ dynamics is relatively well understood, surveys that come up in searches are years old and many state-of-the-art algorithms are now implemented, and maybe research in the area is far less common or active. also hardware assisted garbage collection seems an uncommon combination theoretically (also/ incl operating system aware/ crosscutting such as algorithms that intentionally mesh well by design with caches, paging, virtualization, etc). speaking as a practitioner in the field, garbage collection algorithms tuned with hardware features or OS mechanisms seems a promising idea that hasnt been explored much.

here is one survey turned up of 3 state of the art algorithms from 2013 and there is a hardware mechanism on the 1st (for reference counting).

---
Tags: reference-request, memory-management, garbage-collection
---


# Question
Title: Correlation between high cpu/ram usage and poor computer performance
I'm researching electromigration and the effects of high cpu/ram usage on a computer.

There are tons of discussions on these topics taking place via forums and message boards, but I am looking for credible sources that are backed by metrics.

# Answer
> 2 votes
There's a general-interest article from the IEEE about transistor aging that's based on the paper "An Array-Based Odometer System for Statistically Significant Circuit Aging Characterization" (2011) by Keane, Zhang, and Kim. They present:

> A system that facilitates efficient statistical aging measurements involving the mechanisms of bias temperature instability (BTI) and hot carrier injection (HCI) stress.

Roberto Lacerda de Orio's dissertation "Electromigration Modeling and Simulation" (2010) has a comprehensive treatment of the physics of electromigration, as well as a numerical model and "several simulation studies of electromigration".

You may find more references in this SuperUser thread.

---
Tags: performance
---


title: Term Rewriting vs Unification

text:
# Question
Title: Term Rewriting vs Unification
How is term rewriting different from unification, and what's the difference between term rewriting languages and logic programming, like Prolog?

# Answer
> 15 votes
Term rewriting is a rewriting formalism. Starting with a term we rewrite the term according to the term rewriting rules until a normal form is found. Unification is finding a solution (substitution with specific properties) to a problem (a pair of terms).

Term rewriting uses a notion called "pattern matching". What you probably meant is: what is the difference between matching and unification?

Let two terms $t\_1$ and $t\_2$ be given.

If we want to unify $t\_1$ and $t\_2$, we search for a substitution $\sigma$ such that $t\_1\sigma = t\_2\sigma$. On the other hand, if we want to match $t\_1$ into $t\_2$, we are looking for a substitution such that $t\_1\sigma = t\_2$. That is, we apply the substitution only on $t\_1$.

Logic programming is a programming paradigm which is based on resolution, which is a proof method for logics. In logic programming unification plays an important role.

---
Tags: terminology, term-rewriting, logic-programming, unification
---


# Question
Title: What is a real-world use-case/need for a left-recursive grammar?
I understand the basics of how left-recursion works, and why some people say it's bad. And I've also ready opinions such as:

> ...like LL and LR parsing, PEGs are often frustrating to use in practise. This is, principally, because they don't support **left recursion**.

http://tratt.net/laurie/blog/entries/parsing\_the\_solved\_problem\_that\_isnt

But this leaves me confused.

I haven't read about an actual real-world use case of why you'd even need left-recursion in the first place, especially if there are techniques to convert left recursion to right recursion. In addition, left-recursion feels less intuitive than right-recursion.

What is a real-world use case or need for a left recursive grammar to help me better understand? By "real world" I'm looking for an example grammar that is more human readable than the typical theoretical examples such as:

$A \to B\alpha \mid C$

$B \to A\beta \mid D$

For example:

$filePath \to pathSegment\*$

$pathSegment \to pathSegment \mid slash$

$slash \to /$

Part of the reason I ask is b/c left-recursion doesn't seem very intuitive; it seems more intuitive to use right-recursion. And also because I wonder if it's even a practical problem to try to solve.

**Update**

This makes sense, but seems to be the only major reason:

> $E \to E - n \mid n$
>
> converted becomes
>
> $E \to nT\*$
>
> $T \to - n$
>
> "10 - 5 - 3" is then parsed:
>
> L-recursive : (((10) - 5) - 3)
>
> R-recusive : (10 (- 5 (- 3)))

http://etymon.blogspot.com/2006/09/why-i-prefer-lalr-parsers.html

Is that all?

# Answer
> 4 votes
There are probably better reasons than this, but one nice thing about left recursion is you get parse trees that naturally represent left associativity. You expect `5 + 3 + 2` to be evaluated as `(5 + 3) + 2`, but when parsed with the right recursive transformation you show, the parse tree would be the opposite.

This doesn't seem to matter until you start thinking about type coercion (Right word?). Consider `1u / 2u / 1.0f` in C. `(1 / 2) / 1.0 = 0 / 1.0 = 0.0` but `1 / (2 / 1.0) = 1 / 2.0 = 0.5`.

---
Tags: formal-grammars, parsers
---


# Question
Title: Need for random bits in final PCP theorem statement
PCP theorem states that $$PCP(O(\log n),O(1))=NP.$$ Could we not run through $O(\log n)$ bits deterministically?

Does PCP theorem statement mean any set of $O(\log n)$ random bits out of $2^{O(\log n)}$ choices of such bits suffice? If so, why cannot I choose all $0$ bits? If not why not?

# Answer
The statement of the PCP theorem is essentially equivalent to the following statement:

> For every problem in NP there is a reduction $f$ to $O(1)$-FUNCTION-SAT such that if $x$ is a YES instance then $f(x)$ is satisfiable, whereas if $x$ is a NO instance then at most half of the clauses of $f(x)$ can be satisfied.

Here an instance of $k$-FUNCTION-SAT consists of a collection of "clauses", each an *arbitrary* function on $k$ inputs.

Where did the parameters $O(\log n),O(1)$ in the PCP theorem disappear? The first parameter is the *logarithm* of the number of clauses, so there are $2^{O(\log n)}$ clauses; the second parameter is the arity of the clauses. Together, these parameters guarantee that the FUNCTION-SAT instance has polynomial size, and so the reduction runs in polynomial time.

PCPs are not always described this way, but the descriptions are equivalent. Proof of the equivalence left to the reader.

You *are* enumerating over all choices of $O(\log n)$ when you are constructing the FUNCTION-SAT instance. But it only allows you to construct the instance, not to tell whether it is satisfiable or not; that is an NP task.
> 7 votes

# Answer
The first parameter is the number of random bits, and the second the number of queries to the oracle string $\Pi$ the verifier may use.

The *length* of $\Pi$ is not bounded; therefore, having only access to $O(1)$ symbols of $\Pi$ (and being allowed only relatively few random bits for choosing which) is a non-trivial restriction.

See here for an example illustrating this.
> 3 votes

# Answer
there are multiple comments stating the question is "uninformed" etc and makes no logical sense and suggesting "read a survey on PCP" but not actually (helpfully) volunteering/ citing any. here is a nice one run across by Ryan O'Donnell an expert on boolean functions. its more of an overview but states the basics, possibly enough to remove some beginner misconceptions, and points to many other papers with more details. consider this something like a "hint" answer.
> 2 votes

---
Tags: complexity-theory, probabilistic-algorithms
---


# Question
Title: Choice of machine learning algorithms frequency of parts of speech
I'm new to machine learning. I have text, and I tag the text according to their parts of speech tag ie walk is tagged as verb, etc. I tag entire sentences, and then convert them into a vector based on their frequency like so:

Dan, walk the dog - \> noun,verb, definite-article, noun -\>\<2,1,1\> (2x nouns, 1 verb, 1x DA).

The sentences each belong to one of two classes. I've performed a Kolmogorov–Smirnov test on each tag and picked the ones with the lowest P-value to use. I've used a couple of the models provided by scikit but each time I'm only getting around 55-56% accuracy. The models I've tried are: Gaussian Naive Bayes, K-Nearest Neighbours, SVM, Decision Tree, Random Forest Classifier, Quadratic Discriminant Analysis...

I'm asking if anyone has any comments or pointers about these methods? Should I be using different machine learning methods? Am I going about this problem completely wrong? I would really appreciate any input.

# Answer
You're trying to classify the sentences' sources, right? I would suggest grouping your training data by their sources (but only up to some fixed size, in which case you would have a duplicate entry for that source). E.g., if you are trying to classify the source of a tweet, you would make each tweet (not sentence, and that means each vector would represent a string of up to 140 characters) a vector and calculate its corresponding features, which should span the contents that the feature vector would relate to. Further if you could get each of the fixed bodies of text into *ARFF* format, where the last value in the vector would represent the source of the fixed body of text and the feature vectors would each have the same number of features (the features of which you would pick, more on this in a bit) then you wouldn't be too far from being able to use the Weka suite of classifiers. As for which classifier you should use, I suggest skimming through the following paper:

Antti Puurula, Sung-Hyon Myaeng. Integrated Instance- and Class-based Generative Modeling for Text Classification. ADCS 2013.

It comes from the same machine learning group that produced the Weka suite of classifiers and should give you some pretty good insight.

For your choice of what features you would like to vectorize the fixed bodies into, it would be good to count classes of tags. For example, you could count the number of adverbs as a feature, and/or count the number of first-person/second-person/third-person pronouns as a feature, and/or count the number of verbs in a certain tense as a feature, etc. The features you choose are more so based on your understanding of the bodies. If your fixed bodies could include multiple sentences then some other features could also be the average length of sentences (with respect to number of tokens), the average length of tokens (omitting punctuation, for example, from this group), and/or even just the number of sentences in the fixed body.

Make sure to pick *enough* features, and make sure to pick features you think would be better at differentiating your classes of sources. For example, if any two of your sources are likely to differ in the formality of their tones, then a useful feature would be the number of slang tokens per fixed body.
> 2 votes

---
Tags: machine-learning, natural-language-processing
---


# Question
Title: Correctness proof for finding weighted maximum independent set for a tree
The maximum weighted independent set for a tree can found out using the following dynamic programming approach.

Min\[u\] = wt(u) + Σ Mout\[v\] where v ∈ children(u) Mout\[u\] = Σ max { Min\[v\], Mout\[v\] } where v ∈ children(u)

where Min\[u\] and Mout\[u\] computes the total weight of the maximum independent set for the sub tree rooted at u by including or excluding u respectively.

I tried to proof the correctness of this algorithm. Suppose the independent set ( say I ) generated from this algorithm is not of maximum weight. Let the maximum weighted independent be I'. Then there must be a vertex V'∈ I' and V' ∉ I. And also there can be 2 cases. Either parent(V')∈ I or parent(V') ∉ I. I tried both the cases to solve furthur but could not proceed. Is this approach correct or there is some alternative way to prove the correctness.

# Answer
> 1 votes
Here is an easier-to-understand dynamic programming approach. I think if you can prove this, then you can prove yours.

Let $\textsf{I}(u)$ be the weight of the weighted largest independent set of subtree rooted at $u$.

The goal is to compute $\textsf{I}(r)$, where $r$ is the root of the tree.

The recurrence relation for dynamic programming is:

$$\textsf{I}(u) = \max \\{ w(u) + \sum\_{v: \text{ grandchild of } u} I(v), \sum\_{v: \text{ child of } u} I(v) \\}$$

Can you prove (or *disprove*) it?

**Hint:** Do a simple case-by-case analysis.

---
Tags: algorithm-analysis, trees
---


title: Variation on Insertion Sort

text:
# Question
Title: Variation on Insertion Sort
I'm writing insertion sort in scheme, but due to the difficulty of writing it recursively within the constraints of list processing of scheme, I made what seems like an insignificant change to the "find lowest" or inner loop.

I'll reproduce the algorithm here in Python (aka the universal psuedocode) to explain. I'll also use iteration so it's easier to understand.

```
def insertion_sort(list):
  for i in range(len(list)):
    for j in range(i + 1, len(list)):
      if list[j] < list[j]:
        list[i], list[j] = list[j], list[i]

```

The difference is that I repeatedly swap the old lowest with new lowest numbers as they're found, and reinsert the old lowest back into the list where the new lowest was.

Can I still (correctly) refer to this as insertion sort and is there a significant effect on efficiency?

Also, just in case there's anyone here who loves scheme:

```
(define lowest-to-front-helper
  (lambda (list lowest)
    (if (eq? (cdr list) '())
        (if (>= (car list) lowest)
            (cons lowest list)
            (cons (car list)
                  (cons lowest '())))
        (if (< (car list) lowest)
            (let ((temp (lowest-to-front-helper (cons lowest (cdr list)) (car list))))
              (cons (car temp)
                    (cdr temp)))
            (let ((temp (lowest-to-front-helper (cdr list) lowest)))
              (cons (car temp)
                    (cons (car list) (cdr temp))))))))

; Permutes list such that the lowest element is moved to the front. (Non-stable.)
(define lowest-to-front
  (lambda (list)
    (lowest-to-front-helper (cdr list) (car list))))

(define insertion-sort
  (lambda (list)
    (if (eq? (cdr list) '())
        list
        (let ((temp (lowest-to-front list)))
          (cons (car temp) (insertion-sort (cdr temp)))))))

```

# Answer
Insertion sort maintains the following loop invariant:

* After iteration $i$, the first $i$ positions in the array are the first $i$ positions of the input, in sorted order

Note that this doesn't mean that they need to be in their final positions for the sort to work at the end. I'd say that this is the defining thing for "insertion sort", but that's not really a formal statement.

Insertion sort is not hard to turn into a recursive procedure. The main routine you want is a helper called `insert-sorted` such that consumes a sorted list and a number, and outputs a new sorted list (one longer) that includes the number. You can write it in a way that is pretty much paradigmatic for Scheme (note, code just typed in, not tried):

```
(define (insert-sorted n l le)
    (if (null? l)
        (list n)
        (if (le n (car l))
            (cons n l)
            (cons (car l) (insert-sorted n (cdr l) le)))))

```

In words, if `n` comes before the first element of `l` or `l` is empty, then `n` goes in first position. Otherwise, the list we want starts with the first element of `l` and ends with `n` in the right place in the tail of `l`.

With the helper, involves repeatedly calling `insert-sorted` to build up the sorted list. If you want to follow the invariant exactly, then an approach like this will work:

```
(define (insertion-sort l le)
    (define (rec s l)
        (if (null? l) s (rec (insert-sorted (car l) s le) (cdr l))))
    (rec '() l))

```

However, this solution explicitly maintains `s`, the partially sorted list. More idiomatic scheme would be to just use the call stack for this:

```
(define (insertion-sort l le)
    (if (null? l)
        '()
         (insert-sorted (car l) (insertion-sort (cdr l) le) le)))

```

I'll leave it to you to work out what the invariant for each implementation is.
> 2 votes

---
Tags: algorithms, sorting
---


# Question
Title: Is it decidable whether a pushdown automaton recognizes a given regular language?
The problem whether two pushdown automaton recognize the same language is undecidable. The problem whether a pushdown automaton recognizes the empty language is decidable, hence it is also decidable whether it recognizes a given finite language. It is undecidable whether the language accepted by a pushdown automaton is regular. But ...

> ... is it decidable whether a pushdown automaton recognizes a *given* regular language?

In case the answer is no, does the problem becomes decidable if the given regular language has star height $1$?

# Answer
> 14 votes
It is undecidable whether a PDA recognizes $\Sigma^\*$, the set of all strings over the input alphabet.

Added. It is undecidable to check that $L(G)=\Sigma^\*$ as a consequence of the fact that "non-valid" computations of a TM can be coded as strings of a CFG. This is Lemma 8.7 of Introduction to Automata Theory by Hopcroft and Ullman. The authors refer for this result to Hartmanis (1967), Context-free languages and Turing machine computations.

A convenient coding of the computations of a Turing machine $M$ is as follows. A configuration of TM $M$ is a string of the form $xpy$ where $uv$ is the contents of the tape, and the state $p$ is indicated at the postion where the head resides. It is important to note that computational steps of a TM are *local* changes: $ucpav \vdash uqcbv$ for the instruction $(p,a,q,b,L)$ where the head moves left, and $ucpav \vdash ucbqv$ for the instruction $(p,a,q,b,R)$ where the head moves right.

A valid computation can be coded as a string $w\_0\\#w\_1^R\\#w\_2\\#w\_3^R\\# \dots$ where $w\_0 = q\_0x$ codes the initial configuration on string $x$, and we have proper steps $w\_i \vdash w\_{i+1}$. The last configuration in the string should be final, i.e., have a halting/final state.

It is now an exercise to verify that the strings that are not valid computations can be generated by a CFG $G\_M$ (or accepted by a PDA). The strings that do not consist of configuration sequences are even regular. Otherwise one non-deterministically guesses a position where *not* $w\_i \vdash w\_{i+1}$. This part of the string is generated by a grammar that is similar to one for $\\{ x\\#y^R \mid x,y\in \\{a,b\\}^\* , x\neq y\\}$.

If the TM $M$ has no accepted strings, it will have no valid computations, and all strings are generated by the grammar $G\_M$.

---
Tags: computability, undecidability, pushdown-automata
---


# Question
Title: Does location transparency imply access transparency?
In distributed systems theory, I have found the definition that a distributed system requires, among others, location and access transparency.

I was wondering if location transparency does not already include access transparency.

Wikipedia defines the two as follows:

> Access transparency – Regardless of how resource access and representation has to be performed on each individual computing entity, the users of a distributed system should always access resources in a single, uniform way.
>
> Location transparency – Users of a distributed system should not have to be aware of where a resource is physically located.

If I am not to become aware of where a resource is physically located, doesn't that automatically imply that I have to be able to access all resources in a uniform way?

If yes, could you leave out access transparency from the definition without changing its meaning?

# Answer
There is certainly a strong dependency between these two properties and many examples will point to this conclusion. Think about an API that needs to use the same operations to access both local and remote files. If you already have a list of files, you are unaware of their physical location (e.g., some URL) since you retrieved these files or how they were retrieved (e.g., ftp?). It should imply that you used the same means to retrieve that list of files. But this is not entirely true. Let's simplify Wikipedia's definition:

*Access transparency* \- enables resources to be accessed **using identical operations**.

*Location transparency* \- enables resources to be accessed **without knowledge of their physical or network location**.

This 2 forms of transparency are necessary since they refer to 2 different architectural layers. The *access transparency* refers to the application layer, whereas *location transparency* refers to the physical layer. Returning to the initial example, you access the list of files using the API, but you are not entirely sure how that list was retrieved or where those files were located before they were retrieved.
> 6 votes

---
Tags: distributed-systems
---


# Question
Title: A clarification on the taxonomy of Evolutionary Algorithms
A rather basic question but I am confused about the characterization of a certain local search method which I want to describe in the framework of EAs. In particular, consider an EA which in every step of the evolution has a neighborhood of size 2; one element in the neighborhood is the current hypothesis (*hypothesis* in the traditional sense of learning theory) and the other element in the neighborhood is another hypothesis that has arisen from the current hypothesis after applying some transformation/mutation.

It is clear that for such algorithms in the neighborhood we can find at most 1 hypothesis that has strictly better fitness compared to our current hypothesis (our current hypothesis is *neutral* compared to our current hypothesis). Thus, my question is, how would one characterize an algorithm of this form that always picks among the beneficial set if the set is non-empty, otherwise it would pick among the neutral set (at random - or with some prescribed probability distribution)? Note that the neutral set is always non-empty as the current hypothesis is always there. So, can this algorithm be described as a $(1+1)$-EA or should it be described as a $(1, 1)$-EA? Is there a difference between a $(1+1)$-EA and a $(1, 1)$-EA?

And since we are here, if anyone would be able to clarify the following I would be indebted. What is the difference between a $(1+k)$-EA and a $(1, k)$-EA for $k \> 1$. As far as I have understood the comma description (i.e. $(1, k)$-EA) refers to the fact that the algorithm picks the *most fit* hypothesis among the $k+1$ elements in the neighborhood. The understanding that I have for $(1+k)$-EAs is that they pick *at random* (however that will be defined) among the hypotheses that have strictly larger fitness values compared to the current hypothesis. Is this understanding correct?

Thank you for your time in advance.

# Answer
I'm not 100% sure I understand your formulation (things like "our current hypothesis is neutral compared to our current hypothesis" are a bit confusing), but if I understand it correctly, it's this:

You have a current solution and at each time step, you generate a new one based on the current one and some random variation operator. If the new one is better than the current one, you accept the new one. Otherwise, you keep the current one.

That's a $(1+1)$-ES.

A $(1,1)$-ES always accepts the new hypothesis/solution, regardless of quality. A $(1,1)$-ES is just a random walk on the graph defined by your variation operator. For a $(\mu$, $\lambda)$-ES, the algorithm generates $\lambda$ hypotheses at each step, and selects the best $\mu$ of them to form the population for the next generation -- the current hypotheses never survive (unless your variation operator produces a copy of one of them). The $(\mu+\lambda)$ strategy takes the best $\mu$ from the union of the current population and the new one.
> 1 votes

---
Tags: machine-learning, genetic-algorithms, learning-theory, evolutionary-computing
---