Functional dependencies with the same key? let's consider a table with

carID | hireDate | manufactory | model | custID | custName | outletNo | outletLoc

I want to evaluate all the functional dependencies to bring in first, second and then third normal form.

Functional dependencies

carID,hireDate -> custID

Partial dependencies

carID->manufactory, model, outletNo**

Transitive dependencies

custID->custName
outletNo->outletLoc

Since a car is in a outlet only I have in the partial dependecies this:

carID->manufactory, model, outletNo**

However this leads to anomalies in insertion (imagine adding a car with no outlet), so should not that be like this?

carID->manufactory, model
carID->outletNo

But isn't this still an normalisation anomaly?

I think you're misjudging what an insertion anomaly is. It does make sense for the FD to be

carID -> manufactory, model, outletNo**

since this is just a way to say that the same carID always has the same manufactory, model and outletNo.

Now, if you leave aside for a moment custId and custName, and you decompose the relation this way:

R1(carID, manufactory, model, outletNo), R2(outletNo, location)

you see that this is a fine decomposition that meets 3NF and is free from insertion anomalies: infact you just cannot have, for example, the same carID in two distinct outlets, or the same outletNo with different location.

You're right that adding a car with no outletNo would be no good since outletNo is a foreign key to R2, infact most DBs won't allow you to do such a thing. But this is a different story. Not providing values for mandatory fields is just wrong, and that of course doesn't mean the design of the database is not correct.


Halting problem reduction to Halting for all inputs I was going through my book of revision and I would like someone hints on this.

The Halt for All Input problem (HAI) takes a machine and tell if this machine halts or not for any input
We prove it is unsolvable by proving it reduces to the halting problem

The book says:

Build a $M'$ that does the follwoing
$M'$ erases its input (?)
$M'$ writes I on its tape (did we not just erased this?)
$M'$ simulates $M$

Can someone explain this reduction?

There are a couple of points here. First, you're confusing the direction of the reduction: You're reducing HALT to HAI, not the other direction. Then, your book suggests the transformation $(\langle\,M\,\rangle, x)\rightarrow\langle\,M'\,\rangle$ where $\langle\,M\,\rangle$ is the description of a TM $M$, $x$ is a string, and $\langle\,M'\,\rangle$ is the description of a TM:

M'(y) =
   erase the input y
   write x on the tape  // second point: we're erasing and writing different strings
   simulate M on x

Now if $M$ halts on input $x$, then $M'$ will halt on every input $y$ and so will be an instance of HAI. Conversely, if $M$ fails to halt on $x$, then $M'$ will not halt on any input $y$ and so will not be in HAI.

From here, we can see that HAI is undecidable. If it were, then we could decide whether $M'$ would halt or not, and hence we'd be able to decide whether $M$ halted on $x$. In other words, we'd have a decider for HALT, which we know is impossible.


Why do we need binary trees when we have multi branch trees? Why do we need binary trees when we have multiway trees. Are binary trees even used. Are they used only for teaching the concepts of trees?

Yes, binary trees are used in standard libraries, implementing various data structures. For example, implementation of ordered set in the C++ STL library is typically based on red-black tree, which is a binary search tree of special kind.


Is it possible to do Dependent Types in Typed Racket? Is it possible to use Dependent Types in the existing Typed Racket implementation? (ie do they exist in it?)

Is it reasonably possible to implement a Dependent Types System using Typed Racket?

Dependent Types in Racket are being worked on by Andrew Kent at Indiana University.

There is a set of slides. There is a talk.

Of interest, this potentially also impacts Typed Clojure, which is strongly modeled on Typed Racket.


Is the language $a^{3}b^{+}$ the same as $\{a^{3}b^{n}, n \geq 1\}$ ? and what is the result of pumping this? The regular expression $a^{3}b^{+}$ is indeed regular because we can define an automata $M$. But I see that $\mathcal{L} = \{a^{3}b^{n}, n \geq 1\}$ may generate the same strings, but using the pumping lemma with constant $N$ for a substring $\alpha\beta = a^{3}b^{t},|\alpha\beta| \leq N$, let $\alpha = a$ and $\beta = a^{2}b^{t}$, therefore $\gamma = b^{N-t}$, and when $k = 0$, $\sigma = \alpha \beta^{0} \gamma = \alpha \gamma = ab^{N-t}$, which doesn't belong to $\mathcal{L}$ and the language isn't regular.

So, is really the regex equal to $\mathcal{L}$? or am I pumping wrong?

You are making a classical mistake in applying the pumping lemma. The pumping lemma states that each word $w$ of length at least $N$ in the language (where $N$ is the number of states in the minimal DFA for the language) can be decomposed as $w = xyz$, where $|xy| \leq N$, $|y| \geq 1$, and $xy^i z$ is in the language for all $i$. You don't get to choose this partition! The lemma just states that there is some partition. Taking as an example your word $a^3 b^t$, since $N = 6$ (indeed, the minimal DFA for the language has $6$ states), we can always choose $x = a^3$ and $y = b$, and then $xy^i z = a^3 b^{t+i-1}$ which is always in the language (since $t \geq 3$).

When you use the pumping lemma to prove that a language is not regular, you don't know $N$, and so you have to start by taking $N$ to be arbitrary, and run the proof from there. What you are in effect showing is that for each $N$, there is no DFA accepting the language with at most $N$ states.


Is there any nongeneral CFG parsing algorithm that recognises EPAL? EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar:

$S \rightarrow a a$
$S \rightarrow b b$
$S \rightarrow a S a$
$S \rightarrow b S b$

EPAL is the 'bane' of many parsing algorithms: I have yet to encounter any parsing algorithm for unambiguous CFGs that can parse any grammar describing the language. It is often used to show that there are unambiguous CFGs that cannot be parsed by a particular parser. This inspired my question:

Is there some parsing algorithm accepting only unambiguous CFGs that works on EPAL?

Of course, one can design an ad-hoc two-pass parser for the grammar that parses the language in linear time. I'm interested in parsing methods that have not been designed specifically with EPAL in mind.

Consider the following sketch of a parsing strategy at your own risk.

Instead of reading the input only from one end, we read from both sides and look for matching rules. We can do this in recursive descent style; in a call to $A()$, find prefix $w$ and suffix $v$ to the input such that there is a rule $A \to wBv$, descend to $B()$ on the remaining word. If there is no matching rule, reject the word.

This algorithm parses all linear, unambiguous grammars. It takes linear time if all rule pairs $A \to wBv$ and $A \to w'B'v'$ have $w \not\equiv_p w'$ or $v \not\equiv_s v'$¹. This includes EPAL. Otherwise we need to look ahead so we might take $\Theta(n^2)$ time.

The idea does not work for non-linear grammars at all. Linear but ambiguous grammars can in general not be parsed without backtracking (for negative inputs at least).

$w \not\equiv_p v$ means here that $w \not\sqsubseteq v$ and $v \not\sqsubseteq w$, i.e. neither word is a prefix of the other. $\not\equiv_s$ is similar for suffixes.


Proof of a greedy algorithm concerning “Buy and Resell Problem” "Buy and Resell Problem" can be described in the following way:

There are $n$ cities. For each city, the price of products in this city is given (a positive number). Now a person will travel from city 1 to city $n$, one by one. When reaching a city, he can buy exactly one product with the price in this city, or sell exactly one product if he currectly has at least one product. He can also do nothing and then go on to the next city. The problem is how to plan a strategy so that he can earn maximal money. He has unlimited money initially.

For example, if $n=5$ and the prices are 3,2,5,1,4, then the maximal profit he can earn is $5-2+4-1=6$.

There is a correct greedy algorithm to this problem. When reaching city $i$, consider all $j$ in $1 ... i-1$, and find a $j$ with lowest price such that he doesn't buy a product in city $j$ (he could have sold a product in city $j$). If such $j$ does not exists or the price of city $j$ is higher than city $i$, he simply does nothing in city $i$. Otherwise he buys a product in city $j$ and sells it in city $i$. If he has sold a product in city $j$, it means he does nothing in city $j$ after finishing the $i$th city. The algorithm runs all $i$ in increasing order, and finally gives the best strategy.

The pseudo-code can be written as:

maintain a set s which is empty initially
maintain a boolean array named sell whose items are false initially
profit = 0
for i in 1 to n
  if s is not empty
    select an item j in s with the loweset price
    if price_j is lower than price_i
      profit += price_i - price_j
      if sell_j == true
        sell_j = false
      else
        erase item j from set s
      endif
      sell_i = true
    endif
  endif
  insert i to set s
endfor
output profit

The solution is quite simple and can be easily implemented using a priority_queue, which takes $\Theta(n \log n)$ time in total, but how to prove its correctness?

Summary: It is proposed to label the simple and intriguing algorithm given in the question as Adaptive Greedy. Several characterizations of the best strategy are presented. Also included is a rigorous and nontrivial proof of the algorithm. Some interesting original exercises and topics are attached.

Reformulation in mathematical terms

Let $a..b$ stand for the integers from a to b inclusively.

Let us fix $n\ge 2$ and $p(i)>0$, the price of an item in city $i \in 1..n$ (All items are the same except their prices). Assume all prices are different. This assumption is not necessary in order to establish the arguments, the concepts and conclusions below. However, it does simplify them significantly. For example, the algorithm becomes deterministic, producing the same output given the same input.

A strategy $s$ is a function from $1..n$ to $\{1,0,-1\}$, where $1,0$ and $-1$ mean buying, passing and selling respectively.

Given a strategy $s$,  let $h_s(i)=\sum_{j\in 1..i}s(j)$ be the number of items held right after city $i$ and also let $h_s(0)=0$. A strategy is an admissible strategy if $h_s(i)\ge0$ for all $i$; otherwise it is an inadmissible strategy. We will only consider admissible strategy unless stated otherwise.

The profit made by strategy $s$ is profit$(s)=\sum_{i\in 1..n} -s(i)p(i)$. If strategy $m$ makes the maximal profit, that is, profit$(m)=\max_s($profit$(s))$, then we say $m$ is a best strategy. Since there are finitely many strategies, there must exist at least one best strategy.

The adaptive greedy algorithm that returns the best strategy

Here is the pseudocode in Python style for the adaptive greedy algorithm. It is the same as the pseudocode in the question except that it uses the self-explanatory terms defined above and that it returns the best strategy instead of the maximal profit. We will prove that it returns the unique best strategy shortly.

Input:
  price $p(i)$ for $i\in 1..n$.
Procedure:
  Let s be the all-passing strategy, i.e., s(i)=0 for i in 1..n
  For each city from 1 to n:
    Try finding the previous city where s passes or sells with the \
       lowest prices that is lower than the price at the current city.
    If found, let s sell in the current city and change its action \
       at the city found from pass to buy or from sell to pass.
Output:
    strategy s

The above algorithm, or its equivalent version given in the question, will be referred to as "this algorithm".

Is this algorithm a greedy algorithm and why is it better called adaptive greedy?

At each city, given all admissible pairs of choices of an action in the current city and a change of the action in a previous city, this algorithm selects the pair of choices that can increase the profit the most if it is possible to increase the profit. Otherwise, this algorithm does nothing. That locally optimal selection of admissible choices at each successive city is why we call this algorithm greedy.

Readers might wonder why I explain this algorithm can be classified as greedy, a fact that seems obvious and is assumed by the questioner. That classification is, in fact, not conclusive at all. In fact, the Wikipedia entry on greedy algorithm says the following.

  Greedy choice property
  We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices.

  Optimal substructure
  "A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems."[2]

Note that this algorithm reconsiders all of its choices made so far when it makes every new choices. When this algorithm runs for cities 1, 2, 3, 4, 5 with prices 1, 2, 3, 4, 5 respectively, the unique optimal solution returned by it, buying in city 1 and 2 and selling in city 4 and 5, does not contain any optimal solution to any sub-problem it has considered except for two cities. It is clear this algorithm is not an ordinary greedy algorithm. Nor does it belong to dynamical programming in its usual sense. Readers can also check some answers to does every greedy algorithm have matroid structure.

Considering the definition and explanations in the Wikipedia, I propose to label this algorithm as an adaptive greedy algorithm, a greedy algorithm in the more general sense of "greedy". More precise definitions of adaptive greedy algorithm will be referenced here after they become available elsewhere.

Henceforth, this algorithm will also be referred as "this greedy algorithm" or "this adaptive greedy algorithm".

Why is it not easy to prove this greedy algorithm is correct?

All greedy algorithms other than this algorithm I have seen so far build larger optimal solutions by keeping the smaller optimal solutions intact and adding one more element. Their correctness are often proved by one of the following three strategies, which are not necessarily mutually exclusive.

"Staying Ahead". Show that after each step of $G$, its solution is at least as good as any other algorithm's.
This proof technique applies to Dijkstra's algorithm that finds the shortest path between nodes in a graph and the algorithm that always selects next interval of earliest ending time to find the most compatible interval in activity selction problem (which is also a kind of interval scheduling).
"Unimprovable Solutions". Give any other solution, we can gradually improved it until it becomes unimprovable. Show all unimprovable solutions give the same result or there is only one unimprovable solution. Show that the solution found by greedy algorithm is unimprovable.
This proof technique applies to the usual greedy algorithms for problems such as Interval Scheduling for Minimal Maximum Lateness and others [1] [2] [3] [4] [5].
"Always promising". If $G$ is a weighted matroid or greedoid, its standard greedy algorithm adds one more element to the current result subset in each stage, always promising there is a desired subset with maximal total weight that contains the result subset so far. When the algorithm ends, that promised desired subset will become none other than the result subset. The way to keep the promise is to use exchange of elements.
This proof technique applies to most of problems tagged with "greedy algorithm" including Kruskal’s algorithm or Prim's algorithm for minimal spanning tree.

However, as observed before, the new decision made by this algorithm at each city may, more often than not, modify the decisions for previous cities. In fact, the decision made at the last city may modify the selected action of the first city that has stayed the same for all previous partial solutions. This modification makes it non-trivial to prove the correctness of this simple algorithm. I encourage interested readers to try proving it. Any proof that is easier than the proof below will be a nice surprise.

In fact, there is not a single proof of the correctness of this algorithm as far as I have searched. Many answers, articles or online programming contests may explain clearly the greediness (in its plain sense as in English) of this algorithm or provide vast numerical evidences, which are still, however, far from a rigorous proof of its correctness.

It turns out only the second proof strategy, "unimprovable solutions" can be applied to this adaptive greedy algorithm successfully, as shown in a later section of this answer. There is a new twist, though. The uniqueness of the unimprovable solution can only be established by induction with the help of applying this algorithm. I am stilling searching for ways to show that uniqueness directly without using this algorithm.

The characterization theorem on the best strategy

An increasing integer pair $(i,j)$ is said to be $s$-clearance-separated if $h_s(z)=0$ for some $z\in i..(j-1)$.

A strategy $s$ to be said to improvable at two selected cities if the following conditions hold.

(room to improve) $s$ buy or pass at a lower price in one city but buy or pass at a higher price in the other city. Assume the former city is city $i$ and the other city is city $j$.
(no obstruction to switch) $i>j$ or $i<j$ and $(i,j)$ is not $s$-clearance-separated.

A strategy $s$ is unimprovable if $h_n(s)=0$ and it is not improvable at any two cities.

(The characterization theorem) The following four propositions about a strategy $s$ are equivalent.

(best strategy) $s$ is a best strategy.
(unimprovable strategy) $s$ is unimprovable.
(output of the greedy algorithm) $s$ is the unique strategy produced by this adaptive greedy algorithm.
(anatomy of the best strategy) There are integers $0=i_0\lt i_1\lt i_2\lt\cdots \lt i_t=n$ such that $h_s(i)=0$ if $i=i_j$ for some $j$ and $h_s(i)\gt0$ otherwise. That is, $i_j$'s are all clearance cities where he ends up with no item in his inventory. Call cities $(i_{k-1}+1)..i_k$ of term $k$.

If $s$ buys in a city of some term and sells in a city of the same term or a previous term, the buying price is smaller than the selling price.
If $s$ buys in a city of some term and passes in a city of the same term or a previous term, the buying price is smaller than the passing price.
If $s$ passes in a city of some term and sells in a city of the same term or a previous term, the passing price is smaller than the selling price.
Each passing price happens in a city of a different term.
All passing prices form a decreasing sequence.

Proof of the theorem

"best strategy $\Rightarrow$ unimprovable strategy": Suppose strategy $s$ is not unimprovable.

If $h_s(n)>0$, then we can find city $b$, the last city where $s$ buys. Construct $s'$, the strategy that is the same as  $s$ except $s'$ passes in city $b$. Since $h_{s'}(i)=h_s(i)$ if $i\lt b$ and $h_{s'}(i)=h_s(i)-1\ge h_s(n)-1\ge 0$, $s'$ is an admissible strategy. Since $\text{profit}(s')=\text{profit}(s)+p(b)$, $s'$ makes bigger profit than $s$.

If $h_s(n)=0$, then we can find two integers $i,j\in 1..n$ such that $p(i)<p(j)$ such that one of the following two cases happens.

$s(i)=s(j)=0$ or $s(i)<s(j)$. Furthermore, $i<j$.

Let $s'$ be the strategy that is the same as $s$ except that $s'(i)=s(i)+1$ and $s'(j)=s(j)-1$. Since $h_{s'}(t)\ge h_s(t)$ for all $t$, $s'$ is an admissible strategy. We have,
$$\text{profit}(s')-\text{profit}(s)=-p(i)+p(j)\gt0$$
$s(i)=s(j)=0$ or $s(i)>s(j)$. Furthermore, $i<j$ and $(i,j)$ is not $s$-clearance-separated.

Recall that $h_s(t)\ge0$ for all $t$ and, since $(i,j)$ is not $s$-clearance-separated, $h_s(t)\ge1$ for all $t\in i..(j-1)$. Let $s'$ be the strategy that is the same as $s$ except that $s'(i)=s(i)-1$ and $s'(j)=s(j)+1$. Since $h_{s'}(t)= h_s(t)$ for all $t\not\in i..(j-1)$ and $h_{s'}(t)= h_s(t)-1$ for all $t\in i..(j-1)$, $h_{s'}(t)\ge0$ for all $t$. That is, $s'$ is an admissible strategy. We have,
$$\text{profit}(s')-\text{profit}(s)=p(i)-p(j)\gt0$$

So in all cases, we have found an admissible strategy that makes more profit then $s$.

"unimprovable strategy $\Rightarrow$ output of the greedy algorithm": We will use mathematical induction on $n$.

The base case, $n=2$ is easy. In fact, we can extend the whole exposition to include the case when $n=1$, which becomes the obviously-true base case.

Suppose the implication is true for $n$ cities. Now consider the case of $n+1$ cities. Let $w$ be an unimprovable strategy on $1..(n+1)$ for some price function $q$. Since $w(n+1)=h_w(n+1)-h_w(n)=-h_w(n)\le 0$, there are two cases.

$w(n+1)=0$. That means, $h_w(n)=0$. Let $s$ be the restriction of $w$ to $1..n$. Then $s$ is an unimprovable strategy on $1..n$ for the same prices as $q$. Then $s$ is the uniqued strategy produced by the greedy algorithm running up to city $n$. If we continue to run the greedy algorithm at city $n+1$, it must choose to passes in that last city since $w$ is unimprovable. That is, the greedy algorithm will produce $w$.
$w(n+1)=-1$. That means, $n+1$ is a clearance city where $w$ sells. Treating 0 as an clearance city if necessary, let $c$ be the last clearance city before $n+1$. Let $k$ be the city among $(c+1)..n$ where $w$ passes or buys with the highest price. Let $s$ be the strategy on $1..n$ that is the same as $w$ except that $s(k)=w(k)-1$. Then we can verify that $s$ is an unimprovable strategy on $1..n$ for the same prices as $q$. Then $s$ is the unique strategy produced by the algorithm running up to city $n$. If we continue to run the algorithm at city $n+1$, we can verify that it will select to sell in that city as well as change the action in city $k$ from $s(k)$ to $w(k)$.  That is, the greedy algorithm will produce $w$. (There are quite some details left out in this part of the proof. Interested readers may take a look at Exercise 0.)

So, we have shown the implication is also true for $n+1$.

"output of the greedy algorithm $\Rightarrow$ best strategy" Let $s$ be the unique strategy generated by the greedy algorithm. Let $b$ be a best strategy. Then $b$ must be an unimprovable strategy and, then, must also be the unique strategy generated by the greedy algorithm as we just proved.

"unimprovable strategy $\Leftrightarrow$ anatomy of the best strategy". The latter one is basically a careful refinement of the former one into cases.

Beyond this problem

There are multiple variations and possible generalizations. It should be a nice topic for an undergraduate student or a master student to look further into this phenomenon, since this adaptive greedy algorithm does not fit into the framework of matroid or greedoid.

Please leave a comment if anyone wants to collaborate on this topic. Please leave a comment if anyone encounters some literature that looks like applicable, especially in integer linear programming theory or generalized greedoid or submodular functions.

Some exercises and topics

The answers to all the exercises are known. However, topics are much harder, to which I do not claim to know an answer or verify the answer.

Exercise 0. Fill the missing details in the proof of "unimprovable strategy $\Rightarrow$ output of the greedy algorithm". As a hint, "anatomy of the best strategy" may help you get a better understanding of the cities in the last term. (Thanks to user zbh2047, the questioner, who points out a missing case in a previous more-complex formulation of "unimprovable strategy")

Exercise 1. Suppose the prices in different cities can be the same. Then there might be multiple best strategies. Show that the algorithm, after slight modification, is able to find all best strategies.

Exercise 2. By switching buying and selling, describe a greedy algorithm that starts from city $n$, moving backwards. Prove its correctness.

Exercise 3. Suppose he can only either buy an item or sell one item in each city. That is, he cannot do nothing in any city. Describe a greedy algorithm to find the strategy that makes the most profit or, if no profit can be made, make the least loss. Prove its correctness.

Exercise 4. Describe a greedy algorithm that, in each iteration, tries determining the available city of lowest price to buy an item and the corresponding available city with the highest price that is higher than that lowest price to sell an item, staying away from the inadmissible strategies. If it can find the corresponding city, mark both cities as unavailable; otherwise, mark the first city as unavailable. Prove its correctness.

Exercise 5. Can you find a greedy algorithm and prove its correctness in each of the following situations?
(Part a) Suppose he can short items. That is, the number of items hold by him can be as low as $-n$ but not any lower for some positive integer $n$.
(Part b) Suppose for some positive integer $k$, if the number of items held by him is no more than $k$ in the last city, then the total prices of those items will be added to his profit.
(Part c) Suppose he is required to buy in some specified cities and to sell in some other specified cities.

Exercise 6. Show that the best strategy can be verified in linear time of $n$. The characterization theorem on the best strategy tell us that the best strategy only depends on the relative size of the prices. Show that the minimal number of comparisons needed to determine the best strategy for 2, 3, 4, and n cities are 1, 3, 5 and $\Theta(n\log n)$ respectively.

Topic 1. Suppose he can only buy or pass initially until he holds $k$ items for some positive integer $k$. Then he can buy or sell one item or pass as before. (When) is there a greedy algorithm?

Topic 2. Suppose there is a selling cost $t(i)>0$ associated to sell in city $i$ for each $i\in 1..n$. (When) is there a greedy algorithm?

Topic 3. Let $c(n)$ be the minimal number of comparisons needed to sort any $n$ numbers and $z(n)$ be the minimal number of comparisons needed to find a best strategy for any prices in $n$ cities. We know $z(n) \le c(n)$. Is it true that $c(n)=z(n)$ for all $n$?

All above exercises and topics are created by this author except exercise 4 that comes from an answer at Quora


What is the relationship between minimum sized vertex covers and complete graphs? What is the relationship between the sizes of minimum sized vertex covers and complete graphs?

The size of minimum vertex cover in a complete graph $K_n$ (on $n$ vertices for $n > 1$) is equal to $n-1$.

It is easier to understand using the fact that minimum vertex covers correspond to the complements of maximum independent vertex sets. In a complete graph $K_n$ the maximum independent set is clearly has only one vertex and so the size of a minimum vertex cover is equal to $|V| - \text{ size of maximum independent vertex set} = n-1$.


What mathematical terminology exists for "embellished trees"? I'm looking for some pointers on proper mathematical (FP?, category-theory?) terminology.

My apologies if the below is somewhat imprecise; I suppose the precision is precisely what I'm looking for in the answer.

Say you have a particular Abstract Syntax Tree. Now you also have some editor that allows you to annotate arbitrary nodes in the tree by hand. For example to either highlight nodes, or tie particular textual annotations to nodes ("comments").

The datatypes that allow you to store the information as produced by this editor are somehow "embellished versions" of the original datatype for the AST. E.g. for each node we now have a node that also knows whether it is highlighted or not, and recursively contains such nodes. Values from such datatypes have at least the property that you can throw away the annotations and end up with the original tree.

There is also some notion of "coupling" between the embellished AST's nodes and the "underlying AST"'s nodes, i.e. we can always point at the "source" for any embellished node. This is also to say: if there are two ways of embellishing, we can connect them.

What is the proper framework to (generally) think about this?

A good framework for reasoning about this is research on "ornaments" which were introduced by Conor McBride here: https://personal.cis.strath.ac.uk/conor.mcbride/pub/OAAO/Ornament.pdf .

The idea of ornamentation is that you start with a simple algebraic data type and then you have a separate "ornamented" version of it where the constructors might have more information, which is especially useful in dependently typed programming because a lot of times you want to "adjoin" invariants to a datatype. For more on this, there is another article in the JFP: https://josh-hs-ko.github.io/manuscripts/JFP17.pdf

However, it seems like you are not interested in dependent type theory and have noticed that ornaments arise naturally in everyday programming. For that I would recommend reading about the work on using ornaments in OCaml, specifically this paper (http://pauillac.inria.fr/~remy/ornaments/mlorn-2017-09.pdf) which also has a tutorial for the library here: http://pauillac.inria.fr/~remy/ornaments/ocamlorn/doc/tutorial.html


What's a side-effect free expression in Timed Automata? I'm trying to get myself more familiar with Timed Automata theory. At some point I came across the expression "side-effect free" like in the following:

  A guard is a side-effect free expression that evaluates to a boolean.

But except for the following definition¹ I couldn't find any good source that explains what it actually means or gives examples with respect to Timed Automata:

  We call an expression side effect free if ([![e]!]) is the identity function.

EDIT:

babou pointed me to the global meaning of side-effect which is:

Wikipedia on Side effect (computer science)

  In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world.

However, the trouble I've still got is how to interpret has no effect on states for side-effect free guards. After a guard has been evaluated it will have an effect on states if a transition is taken. In other words, the result of the guard does matter in respect to changing the state or not. But as it seems, the guard itself is called by a higher (side-effect having) instance which makes the state transition (or not).

¹ i.e. searching for the terms side-effect free Timed Automata

Well, I typed side-effect in Google, then I chose anser number 4: Side effect (computer science)

The first sentence states:

  In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world.

From this definition, using elementary logic, I deduce that a "side-effect free expression" is an expression that modifies no state, and has no observable interaction with calling functions or the outside world.

In other words, its evaluation is not supposed to have any observable effect on the program. Then what the program does with the result of the evaluation is another matter and the rest of the program may have an observable behavior that depends on that result. But the effect is the same as if you had been given directly the result rather than evaluating the expression to get it.


L(M)=L where M is a TM that can move right or stay, so L is decidable Suppose that L(M)=L where M is a one tape TM that can move right or stay.

I need to Show that L is decidable.

I thought of reducing a PDA to this TM, since moving to the right is equivalent to popping and pushing some new symbol to the stack. and staying is the same as not touching the automata at all. but im not sure this is correct.

This inherently depends on your exact model of a TM, I'm assuming the following:
A left-bounded tape, the head starts at position 0 and the word to decide is written at the tape. Furthermore, the TM has finitely many states.

Now the TM can only look at the first symbol at a time, can do finite computation (i.e. can have finitely many transitions to different states (*)) and move its head to the right once. Then it can repeat itself (**). In that, this TM is quit limited in what it can do, it can do as much as an DFA (like pointed out in the comments), that is: Look at a symbol, do some state-transitions and look at the next symbol.

(*) What happens, if the TM loops in the inner states without moving its head? Well, since there are only finitely many states, the Universal Turing Machine UTM can simulate the TM and just count how many transitions the TM has made since the last head movement to the right. If this number exceeds the number of states of the TM, the TM will not terminate, so the UTM can answer 'no'.

(**) What happens if the TM just goes to the right indefinitely? Well, at some point it will exceed the word to decide and move its head to a blank cell. An easy argument is to just count from there on the number of transitions (moving right or staying with the head at the current cell). If this number is greater than the number of states of the TM, it is caught in a loop and the UTM can answer 'no'.

To sum it up: The TM in question cannot decide its language, but the UTM can, so it is decidable in the usual sense.


Theoretical machines which are more powerful than Turing machines Are there any theoretical machines which exceed Turing machines capability in at least some areas?

Yes, there are theoretical machines which exceed the Turing machines in computational power, such as Oracle machines and Infinite time Turing machines. The buzzword that you should feed to Google is hypercomputation.


Interesting problem on sorting Given a tube with numbered balls (random). The tube has holes to remove a ball. Consider the following steps for one operation:

You can pick one or more balls from the holes and remember the order in which you picked the balls.
You need to tilt the pipe towards left side so that remaining balls in the pipe shifts towards left and occupy the empty space created by removing the balls.
You are not supposed to change the order in which you picked the numbered balls from the pipe. Now you put them back again in the pipe using the vacant space created by movement of balls.

Steps 1 to 3 is considered as one operation.

Find out the minimum operations required to sort the numbered balls in the ascending order.

For example:
If tube contains: $[1\ 4\ 2\ 3\ 5\ 6]$

Then we can take out $4$ and $5$ and $6$, and if we tilt pipe to the left, we get $[1\ 2\ 3]$, and we insert $(4\ 5\ 6)$ in that order to the end of pipe to get $[1\ 2\ 3\ 4\ 5\ 6]$.

So minimum number of steps required is 1.  I need to find minimum operations to sort the pipe.

Any ideas or hints on how to solve this problem?

Define the run-partition number of a permutation $\pi$, denoted $r(\pi)$, using the following process. Let $k$ be the maximal integer such that the numbers $\min(\pi),\ldots,k$ appear in increasing order in $\pi$. Remove them from $\pi$, and repeat the process. The number of rounds it takes to consume the entire permutation is $r(\pi)$.

For example, let's compute $r(62735814)$. We first set aside $1$, to get $6273584$. Then we set aside $234$, to get $6758$. Then we set aside $5$, to get $678$. Finally, we set aside $678$ to get the empty permutation. This takes four rounds, so $r(62735814) = 4$.

How is this representation useful for sorting $62735814$? Take every second run, i.e. $234,678$, and move these numbers to the right to get $51627384$ (edit: in the order they appear in the permutation, i.e. $627384$). Now there are only two runs, namely $1234,5678$, and we can sort the list by moving $5678$ to the right.

Now let me make the following conjecture: For a permutation $\pi$, let $\Pi$ be the set of all permutations that are reachable from $\pi$ within one move. Then $\min_{\alpha \in \Pi} r(\alpha) = \lceil r(\pi)/2 \rceil$.

Given this conjecture, it is easy to show that the minimal number of moves needed to sort a permutation $\pi$ is $\lceil \log_2 r(\pi) \rceil$, and I have verified this formula for all permutations in $S_n$ for $n \leq 8$.

Edit: Here is a different interpretation of the run-partition number which gives a linear time algorithm for computing it, and allows me to sketch a proof of my conjecture, thus verifying the formula $\lceil \log_2 r(\pi) \rceil$.

Consider the permutation $62735814$ again. The reason that the first run ends in $1$ is that $2$ appears before $1$. Similarly, the second run ends in $4$ since $5$ appears before $4$, and so on. Therefore the run-partition number of a permutation is the number of $i$s such that $i+1$ appears before $i$.

We can state this more succinctly if we look at the inverse of the permutation. Consider again $\pi = 62735814$. Take $\pi^{-1} = 72485136$. This permutation has three descents: $7\mathbf{2}48\mathbf{5}\mathbf{1}36$ (a descent is a position smaller than the preceding one). Each of the descents corresponds to the start of a new run. So $r(\pi)$ is equal to one plus the number of descents in $\pi^{-1}$.

What does the operation look like in terms of $\pi^{-1}$? let $B$ be the set of numbers that we move to the right, and $A$ be the set of numbers that stay to the left. We replace the numbers in $A$ with a permutation on $\{1,\ldots,|A|\}$ representing their relative order, and replace the numbers in $B$ with a permutation on $\{|A|+1,\ldots,|A|+|B|\}$. For example, consider the move $\mathbf{6273}5\mathbf{8}1\mathbf{4} \mapsto 51\mathbf{627384}$. In terms of the inverse permutations, it's $7\mathbf{248}5\mathbf{136} \mapsto 2\mathbf{468}1\mathbf{357}$. So $75$ was mapped to $21$ and $248136$ was mapped to $468357$.

A descent $\ldots xy \ldots$ in $\pi^{-1}$ is lost after the operation only if $x \in A$ and $y \in B$. Conversely, in terms of $\pi^{-1}$, the partition into $A$ and $B$ corresponds to $A$-runs and $B$-runs; every time a $B$-run ends and an $A$-run begins, there is a descent. In order to "kill" a descent, we have to switch from an $A$-run to a $B$-run. If we kill two descents, we will have switched in the middle from a $B$-run to an $A$-run, incurring a descent.

This argument can be formalized to show that if $\alpha$ arises from $\pi$ via an operation, then $d(\alpha^{-1}) \geq \lfloor d(\pi^{-1})/2 \rfloor$, where $d(\cdot)$ is the number of descents. This is equivalent to $r(\alpha) \geq \lceil r(\pi)/2 \rceil$, thus proving one direction of my conjecture. The other direction is easier, and was already outlined above: we simply take every second run and push these runs to the right to get a permutation $\alpha$ satisfying $r(\alpha) = \lceil r(\pi/2) \rceil$.


KD-Tree implementation with lat/lon coordinates I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct results (same nearest neighbor) if I use euclidean distance instead ?

If not, can you give me a concrete example of 3 GPS coordinates (WGS84) where euclidean distance fails to distinguish which coordinate is closer to which ?

Short answer: No, you will not get the same results.

It does not matter what coordinate system or what geographic standard you are using, it is not possible to make projection from sphere into rectangle and save all data (angles and distances) at the same time.
Haversine formula is prepared to operate on circles, 3D distance on sphere, while Euclidean distance will treat them as 2D points, so the result must differ.

Haversine is one of methods to get actual distance on sphere, to use it on Earth, it is only approximation so in such case I would suggest Vincenty formula.

The errors depend on coordinates given and the distance between points.

Take reference point $A =\{40^{\circ}N, 40^{\circ}E\} = \{40, 40\}$, $B =\{42^{\circ}N, 40^{\circ}E\} = \{42, 40\}$, $C =\{40^{\circ}N, 42^{\circ}E\} = \{40, 42\}$, treating them as $X, Y$ tells that they are equidistant - this is how Euclidean distance would see raw coordinates.

According to Haversine formula distance from $A$ to $B$ is ~$222.4 km$ (~$222,108 km$ Vincenty), distance from $A$ to $C$ is ~$170.4 km$ (~$170,784 km$ Vincenty), so it kinda fails.

The idea with ruler on the map, this gets heavy, it will fail as the above, but it depends on map projection (errors change, some projections save angles, some tries to save distances).


Maximal Elements in a Lower Set I have a collection of objects, and a feasibility property for sets of objects which is slow to compute. If a set is feasible then so is any subset. For example, it could be whether the set of things will fit into a certain-sized packing crate.

I want to compute all feasible sets (equivalently - all maximal feasible sets), minimizing the number of evaluations of the feasibility property (worst-case or average). Does anyone know of any theoretical work on this?

Bonus question - what if the cost to compute the property is linear (or superlinear) in the size of the set being evaluated?

Your problem is equivalent to exact learning of monotone DNFs. This task is equivalent to learning all minterms of a monotone function, whereas you are interested in learning all maxterms of a monotone function, but the two problems are equivalent. (Look these terms up if you are not familiar with them.)

If the only queries you allow are membership queries (test whether a given set is feasible or not) then your problem is rather difficult. Theorem 2 in Angluin's Queries and Concept Learning shows that $2^n-1$ queries are required even if there are only $2n$ objects and $n+1$ minterms. See the paper for other models in which your problem can be solved efficiently.


Confused about XORing and addition modulo $2$ It's my understanding that when you XOR something, the result is the sum of the two numbers mod $2$.

Why then does $4 \oplus 2 = 6$ and not $0$? $4+2=6$, $6%2$ doesn't equal $6$. I must be missing something about what "addition modulo 2" means, but what?

  100 // 4

  010 // XOR against 2

  110 = 6 // why not zero if xor = sum mod 2?

The confusion here stems from a missing word. A correct statement is "The result of XORing two bits is the same as that of adding those two bits mod 2."

For example, $(0+1)\bmod 2 = 1\bmod 2 = 1=(0\text{ XOR }1)$

and

$(1+1) \bmod 2= 2\bmod 2 = 0 =(1\text{ XOR }1)$


Solving SAT correctly on all but $poly(m)$ formulas The question is to show that there is no deterministic polynomial time algorithm that solves SAT correctly on all but $poly(m)$ formulas of size $m$, for every $m \geq 0$ unless $P \ne NP$.

I know that if $P = NP$,  a polynomial time algorithm exists that, given a Boolean formula φ, actually produces a satisfying assignment for φ if it is satisfiable. But I can't really understand how a poly time algorithm can solve SAT correctly on only $poly(m)$ formulas, if $P \neq NP$. Am I missing something in understanding the problem or there is a catch?

I'll provide a sketch.

Given any formula $\varphi$ of size $m$, we can rewrite it in an equisatisfiable way as $\varphi \land p$ where $p$ is a fresh propositional variable. In this way, we can generate an infinite amount of equisatisfiable formulas.

Now, exploiting this, it is easy to find a way to generate, in PTIME, $2 poly(m')+1$ formulas $\varphi'$ equisatisfiable wrt $\varphi$, where each such $\varphi'$ is of size $m'$. We can then decide SAT on $\varphi$ by taking what is the result of the majority of $\varphi'$ instances ($poly(m')+1$ instances), and return that. Indeed, among the $2poly(m')+1$ test, at most $poly(m')$ can have a wrong result, so the result of the majority must be the correct one.

This runs a PTIME algorithm a polynomial number of times ($2 poly(m')+1$, where $m'$ is polynomial wrt $m$), so we indeed solve SAT in PTIME.

To generate all the needed $\varphi'$, we note that the "longest" variable name in $\varphi$ can't more than $m$ bit long for obvious size reasons. Hence if we take $p$ to be any variable whose name has size $m+1$ bits it is surely fresh, and this makes $\varphi'$ to have size $m' = m+(m+1)+O(1)$. Further, we have $2^{m+1}$ choices of such $p$, which is (asymptotically) a large enough space to choose $2 poly(m')+1$.


Monadic Second Order Logic for Dummies I am programmer with a grip on automata, but not on logic.

I read in papers that the two are very tightly related.
Deterministic Finite Automata (DFA), Tree Automata and Visibly Pushdown Automata are all related to Monadic Second Order Logic (MSO).
Although, I understand the automata and people (in papers) have tried to explain the relation to MSO to me, they always assume a strong background in logic and an understanding of MSO.

When I look at books and courses on logic, they mostly only handle first order logic, which seems pretty simple and consisting of only a few concepts: variables, or, and, not, implies, for all, exists, etc.

Can someone explain or point me to a resource that can explain:

What is second order logic in contrast to first order logic?
What is monadic vs non monadic logic?
Why is it important for a second order logic to be monadic to be decidable OR why is this the wrong question?
Why is monadic second order logic decidable?
The relation to at least DFAs?

If it is a resource it would be nice if it assumes that I am a programmer and not a logician.
This means that I would like to understand how I would implement it as code, because until then math feels like magic to me ;)

Thank you for any help you can give me.  I would really appreciate it.

What is second order logic in contrast to first order logic?
  What is monadic vs non monadic logic?

Monadic second-order logic is first-order logic plus quantification over sets. So, as well as being able to say that there exists a domain element with some property ($\exists x\dots$), you can also say that there exists a set of domain elements with some property. So, for example, we can define 3-colourability of graphs by saying

\begin{align*}
\exists R\,\exists G\,\exists B\, \big[&\forall x\,\big(x\in R\lor x\in G\lor x\in B\big)\\
&\land \neg\exists x\,\big((x\in R\land x\in G) \lor (x\in G\land x\in B) \lor (x\in B\land x\in R)\big)\\
&\land \forall x\,\forall y\,\big(E(x,y)\rightarrow \neg \big((x\in R\land y\in R)\lor (x\in G\land y\in G)\\
&\qquad\qquad\qquad\qquad\qquad\quad\lor (x\in B\land y\in B)\big)\big)\big]\,.
\end{align*}

In words, there are colours red, green and blue such that

every vertex has a colour
and no vertex has two colours
and, if there's an edge between two vertices, those two vertices don't have the same colour.

General second-order logic allows not just quantification over sets but also over arbitrary relations over the domain.  Recall that a relation is a set of $k$-tuples over the domain, for some $k$.  Sets are just unary relations: $k=1$ and a $1$-tuple is just an element of the domain.

  Why is it important for a second order logic to be monadic to be decidable OR why is this the wrong question?
  Why is monadic second order logic decidable?

Honestly, I don't remember the decidability issues. A key point is that full second-order logic lets you quantify into existence a linear order of the domain

\begin{align*}
    \exists R\,\forall x\,\forall y\,\forall z\,\big[&(R(x,y)\lor R(y,x)\big)\\
    &\big((R(x,y)\land R(y,x))\rightarrow x=y\big)\\
    &\big((R(x,y)\land R(y,z))\rightarrow R(x,z)\big)\big]\,.
\end{align*}

That is, there exists a binary relation that is total, antisymmetric and transitive, i.e., is a linear order on the domain $D$. That implicitly gives you a linear order on $D^n$ for any $n$, and you can use relations on $D^n$ for large enough $n$ to simulate a Turing machine tape.  But, with monadic SO, you can't do any of these things.

(I guess that, if your domain is infinite, you probably need to specify in addition that the linear order is discrete and has a minimal element; then you know that it has an initial segment that's isomorphic to the natural numbers, and that should be enough.)

On finite inputs, the existential fragment of SO – formulas of the form $\exists R_1\dots \exists R_k\,\varphi$, where the $R_i$ are relation symbols and $\varphi$ is first-order – defines exactly NP. Full second-order logic defines exactly the polynomial hierarchy.  This is exactly because of the ability to encode Turing machines and the fact that quantifying a fixed collection of relations gives you a polynomial amount of stuff to play with.

  The relation to at least DFAs?

We can represent strings over some finite alphabet $\Sigma$ by relational structures.  The vocabulary has a binary relation symbol $\leq$ that will be interpreted as a linear order, and a unany relation symbol $R_a$ for each character $a\in\Sigma$.  Each element of the domain is a character in the string, the linear order tells you what order the characters appear in and the relations $R_a$ tell you what character appears in each position.

Now, suppose we have a DFA with $k$ states and let's assume we're dealing with finite strings, for now.  We can write a formula that's broadly similar to the three-colourability formula above that says that our DFA accepts the string coded by its input.  It says that there are sets (of domain elements, i.e., positions in the string) $Q_1, \dots, Q_k$, such that $Q_i$ will be the set of positions in the string at which the automaton is in state $i$.  So assert that:

each position $j$ is in exactly one of $Q_1, \dots, Q_k$;
the first position is in $Q_1$ (assuming this is the start state);
if the $j$th position is in $Q_i$ then the $(j+1)$th position is in whatever state the automaton's transition function says it should be;
the final position is in an accepting state.

If this formula is true, the automaton must accept the string; if it's false, the automaton must reject.  For NFAs, we just say that each position is in at least one state and the final state is in at least one accepting state. For infinite inputs, we can code, e.g., the Büchi condition by saying "for all positions $j$ in the input, if $j$ is in an accepting state, there's some $j'>j$ such that $j'$ is also in an accepting state.

Right now, I don't recall the proof of the converse (that everything definable in MSO can be recognized by an appropriate automaton).  If I have time, I'll look that up and post a sketch.

Conversely, we can represent the meaning of MSO formulas by finite state automata inductively, following the construction of the automata. To do this we augment the alphabet of the automaton, by adding components that indicate the value of the free position variables $i$ and set variables $X$. If we read a string along the automaton we find exactly a single $1$ to indicate a certain postion $i$, and the positions in a set $X$ are marked likewise.

The basic formulas are $R_a(i)$ for "position $i$ has symbol $a$", $i\in X$ for "$i$ is an element of $X$" and $i<j$ for "position $i$ is before position $j$".
These formulas can be represented by the following simple finite state automata (over the augmented alphabet suited for the formula):

More complicated formulas are constructed using the Boolean connectives $\lor, \lnot$ and the existential quantifiers $\exists i, \exists X$. The intended meaning of these operators are easily translated to languages as the language operators union $\cup$, complement ${}^c$ and projection, which is the operation that removes the corresponding component from the augmented alphabet. For union we have to pay some attention to the augmented alphabets in case the two parts of the formula do not agree on the set of free variables. Projection is simple, but it will change a deterministic automaton into a nondeterministic one.


Consensus number of memory-to-memory swap I think that consensus number of mem-to-mem-swap(a,b) operation which atomically swaps the values between shared locations a and b (shared R/W memory) is infinite , but I'm having trouble proving it.
I thought about implementing CAS with mem-to-mem-swap but comparing atomically is problematic, I think there is straightforward consensus protocol but I can't think about one.

See Theorem 10 (Figure 13) of the paper "Wait-Free Synchronization
" by Herlihy, 1991.

  Theorem 10: An array of registers with memory-to-meory swap has infinite
  consensus number.

  Proof: The protocol is shown in Figure 13. The processes share an array of
  registers $a[1 \ldots n]$ whose elements are initialized to $0$ and a single register $r$, initialized to $1$. The first process to swap $1$ into $a$ wins.

Footnote 4 of this paper remarks that:

  The memory-to-memory swap should not be confused with the read-modify-write swap; the former exchanges the values of two public registers, while the latter exchanges the value of a public register with a processor’s private register.


Searching a hierarchy for progressive node criteria In our organization we have various business units that organize their data in different ways. The folder structure can vary, but they abide by business unit practices when making backups etc.

I am to make a scraper that locates backups and copies them. I have found a general way to describe the business unit specific way of making backups. I do not wish to search the whole directory structure because it may be massive.

/X
  A
   a
  B
   a
  C
   a

Here for instance, in order to locate all the lower case "a", I can say that the criteria is a list of strings

"*","*","a"

The X will satisfy the first asterisk. The A/B/C subfolders will satisfy the second asterisk and the lower case a's will satisfy the lower case a criteria. Already, we see a potential for the two "" to be represented as "" and a multiplier modifier.

All well and good.
In C#, this is easy. The DirectoryInfo class has the GetDirectories method which performs a scan with a searchpattern.

However, what if the structure is staggered? What if I would like to list the criteria as follows?

Pattern="*" MaxRepetitions=3 MinRepetitions=1
Pattern="a" MaxRepetitions=1 MinRepetitions=1

The code becomes messy quick. For instance "a" will also be satisfied by "*" criteria, so the engine may not be "sure" which criteria is being exhausted and therefore must test multiple criteria on next pass. I assume regex has solved this problem because it runs so fast on large strings and still manages to return without duplicates.

Are there any pointers? Is there any theory behind how to preserve a context (visitor state), assuming this is the visitor pattern.

These things are generally done through backtracking. Which in your case would look somewhat like this:

Go down 3 levels and look for 'a'
If you find some -> perform your magic
If you find none (or if you do, depending on the implementation) -> go up 1 level repeat steps 1-3

Really this is no better than simply searching all directories in the worst case, but there is no way you can guarantee having found all a's without searching every directory anyway (assuming no prior knowledge). However this solution will have a much better average case performance if the a's are always at the maximum level than simply starting to search at level 1, then level 2 etc.

edit: also, regexes are fast because the average CPU performs billions of operations per second. If you're copying files then the copying will be the part slowing it own drastically anyway so you probably should not be too concerned with the performance of your searching algorithm


How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton? In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which are productions annotated with a position and a lookahead character.

It's known that given a state in an LR(1) automaton, the configurating set formed by dropping the lookahead tokens from each LR(1) item yields a configurating set corresponding to some state in the LR(0) automaton. In that sense, the main difference between an LR(1) automaton and an LR(0) automaton is that the LR(1) automaton has more copies of the states in the LR(0) automaton, each of which is annotated with lookahead information. For this reason, LR(1) automata for a given CFG are typically larger than the corresponding LR(0) parser for that CFG.

My question is how much larger the LR(1) automaton can be. If there are $n$ distinct terminal symbols in the alphabet of the grammar, then in principle we might need to replicate each state in the LR(0) automaton at least once per subset of those $n$ distinct terminal symbols, potentially leading to an LR(1) automaton that's $2^n$ times larger than the original LR(0) automaton. Given that each individual item in the LR(0) automaton consists of a set of different LR(0) items, we may get an even larger blowup.

That said, I can't seem to find a way to construct a family of grammars for which the LR(1) automaton is significantly larger than the corresponding LR(0) automaton. Everything I've tried has led to a modest increase in size (usually around 2-4x), but I can't seem to find a pattern that leads to a large blowup.

Are there known families of context-free grammars whose LR(1) automata are exponentially larger than the corresponding LR(0) automata? Or is it known that in the worst case, you can't actually get an exponential blowup?

Thanks!

The grammar

$$\begin{array}{l}
S \rightarrow T_0 \\
T_n \rightarrow a \; T_{n+1} \\
T_n \rightarrow b \; T_{n+1} \\
T_n \rightarrow b \; T_{n+1} \; t_n \\
T_N \rightarrow t_N
\end{array}
$$

has the LR(0) state
$$T_N \rightarrow t_N \dot \\$$
expanded to $2^N$ variants in the LR(1) automata as all the partitions of $\{t_0 \dots t_{N-1}\}$ are possible look-head which appear in different contexts.  The number of states in the LR(0) automaton on the other hand is linear in term of $N$.  Thus an expansion factor of the order of $2^N/N$ is possible.

Edit: I'll have to check later when I've more time, I think adding $T_N \rightarrow T_0$ would give the exponential factor on nearly all the LR(0) states. That result in a shift-reduce conflict.


Select the n closest nodes from a starting node in a weighted directed graph I need to select a given number of nodes from a weighted directed graph such that the nodes selected are the closest to a given starting node.  This seems like a common problem to need to solve, but I haven't found much material on it.  Does anyone know if this particular problem has a name, or any published material (formal or informal) related to it?

Note, I am not asking for a solution to the problem itself.  I am interested in finding material related to the problem.  For very large graphs, the canonical Dijkstra algorithm will not work because you must enqueue every node first.  I believe a modified version of the Uniform Cost Search will do what I want, since it does not enqueue all the nodes first.  Things get more interesting in this case, because you don't have full knowledge of all shortest paths.  I'm interested in things like how do you know when you've found all the shortest paths for the closest nodes, without traversing the entire graph in the process.  I think this is possible using an admissible heuristic as in the A* search.  These are the kinds of details I want to be able to read up on.

Question 1. For very large graphs, the canonical Dijkstra algorithm will not work because you must enqueue every node first.

Yes, you are right about the disadvantage of canonical Dijkstra's algorithm. However, it can be easily adapted (wiki):

  The algorithm can start with a priority queue that contains only one item, and insert new items as they are discovered (instead of doing a decrease-key, check whether the key is in the queue; if it is, decrease its key, otherwise insert it).

See the paper for details (including experiments) on implementing Dijkstra's algorithm with such a modified priority queue.

  Question 2. I'm interested in things like how do you know when you've found all the shortest paths for the closest nodes, without traversing the entire graph in the process.

The Dijkstra's algorithm finds the shorted paths from a starting node in the order of increasing costs. So, the first $n$ vertices removed (delete-min) from the priority queue are the $n$ closest nodes from a starting node you are looking for.


For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes in my notes I have one fact:
in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at most $\frac{2n}{3}$.

Does it work for every binary tree or only when $n$ is divisible by three?
How can I quickly prove the fact in my note? A simple idea?

$\DeclareMathOperator\s{size}\def\f#1{\lfloor#1\rfloor}\def\c#1{\lceil#1\rceil}$As already pointed out by gnasher729, the statement is not literally true when $n\equiv1\pmod3$: if $n=3k+1$, there are binary trees of size $n$ whose all subtrees have size either $\le k<n/3$ or $\ge2k+1>2n/3$.
A version suitable for all $n$ can be proved as follows. Let $\s(u)$ denote the size of the subtree rooted at $u$.

Lemma 1: If $1\le s\le n$, then every binary tree of size $n$ has a node $u$ such that $s\le\s(u)\le2s-1$.

Proof: Let $u$ be a node with $\s(u)\ge s$ such that $\s(u)$ is minimal possible. By minimality, the child subtrees of $u$ have size $\le s-1$ each, hence $\s(u)\le2(s-1)+1=2s-1$. QED
Balancing $\s(u)$ and its complement, we obtain the following.

Corollary 2: In every binary tree of size $n>1$,

there is a node $u$ such that $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}$, and

there is a node $u$ such that $\c{n/3}\le\s(u)\le\f{(2n+1)/3}$.

Proof: Using Lemma 1 with $s=\f{(n+1)/3}$, we have $2s-1\le\f{(2n+2)/3}-1=\f{(2n-1)/3}$. Likewise, $2\c{n/3}-1=2\f{(n+2)/3}-1\le\f{(2n+4)/3}-1=\f{(2n+1)/3}$. QED
We can also reformulate it as follows:

Corollary 3: Every binary tree of size $n>1$ has a subtree such that both the subtree and its complement have sizes between $\f{(n+1)/3}$ and $\f{(2n+1)/3}$.

Proof: Taking $u$ with $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}$ by Corollary 2, the complement of the subtree rooted at $u$ has size between $n-\f{(2n-1)/3}=\c{(n+1)/3}=\f{n/3}+1$ and $n-\f{(n+1)/3}=\c{(2n-1)/3}=\f{(2n+1)/3}$. QED
Using Corollary 2, the simple bound $n/3\le\s(u)<2n/3$ works if $n\equiv0,2\pmod3$. It also works for all $n$ if the tree is full:

Corollary 4: Every binary tree of size $n>1$ such that all nodes have $0$ or $2$ children has a node $u$ such that $n/3\le\s(u)<2n/3$.

Proof: In this case, the size of every subtree (including $n$ itself) is odd. By Corollary 2, there is $u$ with $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}<2n/3$. If $\f{(n+1)/3}\ge n/3$, we are done. The remaining case is that $\f{(n+1)/3}=(n-1)/3$. But here $n-1$ is even, hence $(n-1)/3$ is also even, while $\s(u)$ is odd. Thus $\s(u)\ge1+(n-1)/3>n/3$. QED


If $m \leq a \log m + b$, why does $m = O(\max\{a \log a, b\})$? I'm found this claim in something I was reading and I'm having trouble working out the logic. Can someone help me out?

$m \leq a \log m + b$ has no asymptotic behavior. This is because regardless of constants $a, b$, the left hand side grows faster than the right side, leaving only a finite range where $m$ is valid.

It is likely what was meant is $m \leq a \log a + b$. In this case we have that $m$ is bounded by something, so $m = O(a \log a + b)$. If you have that $O(x + y) = O(\max(x, y))$, then the question is solved.

But why is $O(x + y) = O(\max(x, y))$ true? With big-$O$ notation we are interested in the asymptotically fastest growing part. We ignore constant factors. Now check three cases (in the limit):

$$x < y \rightarrow O(x + y) = O(y)$$
$$x > y \rightarrow O(x + y) = O(x)$$
$$x = y \rightarrow O(x + y) = O(x + x) = O(2x) = O(x)$$

Since our choice for $x = y$ doesn't matter, we can see that choosing the minimum gives us the right asymptotic behavior.


Class of the language only containing the empty string? $L = \left \{ \epsilon  \right \}$
Clearly this language is finite so this must be a regular language.
Now since every regular language is Context Sensitive, $L$ is a CSL.
We can define the grammar for $L$ as :
$S\rightarrow \epsilon$
Now since $L$ is a CSL, this grammar must be a Context Sensitive Grammar.
But from the definition of a Context Sensitive Grammar:

  A Context sensitive grammar is any grammar in which the left side of
  each production is not longer than the right side.

But here
$\left | S \right | > \left | \epsilon  \right |$
This is contradictory.
I am unable to figure out what's wrong here.

This issue is covered in wikipedia's article on noncontracting grammars. Such grammars do not allow deriving the empty string, which is no problem when one considers languages $L\subseteq A^+$. When one wants to allow the empty string, a special case is made and the rule $S\to\lambda$ is allowed with ugly side conditions ($S$ cannot appear in a right-hand side).

So the situation is that there are several available, mostly equivalent, definitions, that offer different tradeoffs between elegance, generality, ease of use, etc. This is a typical situation in mathematics. When you scratch the surface, the different definitions are there and they come with extra terminology, like "essentially noncontracting".

This may look confusing for newcomers but the good side is that it separates the important from the not-so-important details.

BTW your reasoning has a flaw. You say that the language is CSL (correct) and $S\to\lambda$ is a grammar for it (correct), thus that grammar is CS. That implication is incorrect. You can only deduce that there exists a CS grammar for it. But you are right in thinking that any such grammar must have a contracting rule.


How to find the vertices on simple path between two given vertices in a directed graph Given a directed graph and two distinct vertices S and T, is there a polynomial-time algorithm which finds every vertex which is on at least one simple path from S to T?

It is not difficult to find all vertices that are both successors of S and predecessors of T but this is only a superset of the set above. For example, consider the following graph:
S -> a; a -> b; b -> c; b-> T; c -> a

While a, b and c are all successors of S and predecessors of T, there is no simple path from S to T going through c (because every path from S to T going through c contains twice a and b).

A closely related problem is the following:
Given a directed graph and three distinct vertices S and T and I, is there a polynomial-time algorithm to decide if there exist a simple path from S to T going through I.

A polynomial-time algorithm to this latter problem can be use to build a polynomial algorithm to the former since we can apply it succesively by replacing I by every node in the graph (or more efficiently to every node that is both a succesor of S and a predecessor of T).

Thanks for your answers.
As master foo pointed out, the second problem -- given a directed graph and three distinct vertices $s, t$ and $i$, decide if there exist a simple path from $s$ to $t$ going through $i$ -- is indeed NP-complete.

From the paper The Directed Subgraph Homeomorphism Problem by Steven Fortune, John E. Hopcroft and James Wyllie, it is clear that the pattern graph $s \to i \to t$ is one for which the fixed directed subgraph homeomorphism problem is NP-complete since it is a tree of depth two.

Here are few definitions from this paper:

  The subgraph homeomorphism problem is to determine: if a pattern graph p is
  homeomorphic to a subgraph of an input graph G. The homeomorphism maps nodes
  of P to nodes of G and arcs of P to simple paths in G. The graphs P and G are either both directed or both undirected. The paths in G corresponding to arcs in P must be pairwise node-disjoint. The mapping of nodes in P to nodes in G may be specified or left arbitrary. This problem can be viewed as a generalized path-finding problem. For example, if the pattern graph consists of two disjoint arcs and the node mapping is given, then the problem is equivalent to finding a disjoint pair of paths between specified vertices in
  the input graph.

Basically, only the pattern graphs that are trees of depth one and their reverse graphs (with possibly loops arcs on the root) can be solved in polynomial time.

  Let C be the collection of all directed graphs with a distinguished node called the root possessing the property that either the root is the head of every arc or the root is the tail of every arc. Note that the root may be both the head and tail of some arcs and thus loops at the root are allowed. Equivalently, a graph is in C if, when all loops at the root are deleted and multiple arcs between pairs of nodes are merged into single arcs, the resulting graph is a tree of height at most one.

  [...]

  Next we show that for each pattern P not in C the fixed subgraph homeomorphism
  problem with pattern P is NP-complete.

I have not read the proof yet so I'll stop here.

There is also a close connection from the problem I have just mentionned and the two disjoint paths problem as pointed out by one of my collegue. The two dijsoint paths problem is:

  Given a directed graph and four distinct vertices $s_1, t_1, s_2, t_2$, decide if there exist two pairwise node disjoints simple paths from $s_1$ to $t_2$ and from $s_2$ to $t_2$.

This problem for directed graphs is well known to be NP-complete.
However, there is a simple transformation from the two disjoint paths problem to the $s \to i \to t$ problem. In order to do that, we need to add one extra node $i$ and the two extra edges $t_1 \to i$ and $i \to s_2$.

If there was a polynomial algorithm to solve the $s \to i \to t$ problem, we could use it to solve the two disjoint paths problem in polynomial time with the simple transformation above and thereby solving the $s \to i \to t$ problem.


How to minimize this DFA using given algorithm? I am trying to use Myhill-Nerode theorem to minimize the DFA appearing below.

The algorithm repeatedly runs the following step:

  If there is an unmarked pair $(Q_i, Q_j)$, mark it if the pair $\{δ (Q_i, A), δ (Q_j, A)\}$ is marked for some input letter.

Initially only $\{0,3\},\{1,3\},\{2,3\}$ are marked.
However, $\{0,1\}$ or $\{0,2\}$ won't be marked since the don't have common edges,
$\{1,3\},\{1,2\}$ or $\{2,3\}$ only goes to state 3 with edge 3, but there is no such pair $\{3,3\}$. Then it seems no minimization can be done.

The minimized DFA, however, should merge states 1 and 2.

The difficulty with the problem is, as Dean Gurvitz hinted and as you have experienced, not all transitions are specified explicitly. For example, given input 3 at state 0, what is the transition? According to the definition of DFA, every transition for any input symbol at any state must be specified.

You will ask then, why do I see such a graph for a DFA? What you see is a DFA specified as an incomplete DFA.

  some authors use deterministic finite automaton for a slightly different notion: an automaton that defines at most one transition for each state and each input symbol; the transition function is allowed to be partial. When no transition is defined, such an automaton halts.

To apply your procedure to minimize a DFA, you have to convert an incomplete DFA to a (complete) DFA. Add another state $R$, the rejected state. Whenever a transition from some state given some symbol is not specified, add a transition from that state given that symbol that goes to $R$. In particular, all transitions that start from $R$ go to $R$. Now that a (complete) DFA if formed, you can compute merrily with your procedure, treating $R$ just as any other non-final state. Once you are done with your procedure, you will have a (complete) DFA with minimal states. If preferred or necessary, you can convert the minimal (complete) DFA to an incomplete DFA by removing the (new) rejected state, i.e., the state that comes from $R$, and all transitions from or to that state.


How to select a subset of columns in a given matrix to satisfy a condition? Let $a_{kn}$ be positive real numbers for all $k\in\{1,\dots,K\}$ and $n\in\{1,\dots,N\}$ and let $t>0$. I need to find a subset $S$ of $\{1,\dots,N\}$ of minimum size
 such that:

if $|S|=1$ then $a_{ki}\geq t$ for all $k\in\{1,\dots,K\}$ and $i\in S$.
if $|S|>1$ then for all $k\in\{1,\dots,K\}$, there must exist some $i\in S$ such that  $a_{ki}/a_{kj}\geq t$ for all $j\in S\backslash\{i\}$.

I need to find a good heuristic for this problem (an optimal if possible).

Example:

let $t=2$; and
the matrix $A$ given as:

$$A=\begin{pmatrix} 50 & 1 & 1\\ 1 & 70 & 1\\ 1 & 1 & 40\end{pmatrix}.$$

The set $S$ should be $\{1,2,3\}$.

To solve the problem, I need to enumerate all possible subsets of $\{1,\ldots,N\}$. Do you see any particular characteristic of the problem that I can use to solve it?

The feasibility version of your problem is NP-complete, for any fixed $t > 1$, by reduction from SAT.

Suppose we are given a formula over the variables $x_1,\ldots,x_a$, having clauses $C_1,\ldots,C_b$. We will have $2a$ columns, one column per literal.

For each variable $x_i$ we will have the following row:

Positions $x_i,\lnot x_i$ have value $1$, and all other columns have the value $1/t$.

This row forces the solution $S$ not to be a singleton, and forces it to contain exactly one of $\{x_i,\lnot x_i\}$.

For each clause $C_j = \ell_1 \lor \cdots \lor \ell_c$ we will have the following row:

Positions $\ell_1,\ldots,\ell_c$ have values $1,1/t,\ldots,1/t^{c-1}$, and all other positions have value $1/t^c$.

This row forces the solution to contain at least one of the literals $\ell_1,\ldots,\ell_c$.

Conversely, any satisfying assignment corresponds to a set $S$, as can be easily checked. Hence a set $S$ exists iff the original formula is satisfiable.


What do Arora and Barak mean by $x|_S$ in their definition of certificate complexity? I am having much trouble understanding the following definition (of certificate complexity - for decision trees) from Arora and Barak's book Computational Complexity: A Modern Approach. Perhaps there is a typo in it:

  Definition 12.3 (page 262). Let $f : \{0,1\}^n \to \{0, 1\}$, and $x \in \{0,1\}^n$. A 0-certificate for $x$ is a subset $S \subseteq \{0,1\}^n$, such that $f(x') = 0$ for every $x'$ such that $x'|_S = x|_S$ (where $x|_S$ denotes the substring of $x$ in the coordinates in $S$$)\ldots$

So, given that $S$ is a subset of $\{0,1\}^n$, what on earth does $x|_S$ mean? (Their parenthetical remark is not clear to me.)

  Is there in fact a typo in what $S$ is?

I've looked online at a few other authors' definitions of certificate complexity, and it seems to me that $S$ should actually be a subset of $[n] = \{1,2,\ldots,n\}$. Is this correct? If so, then $x|_S$ would make sense.

Finally, I'll note that I have looked online for an errata list, but I could not find anything very comprehensive.

It is a typo. $S$ indeed should be a subset of $[n] = \{1,2,\ldots,n\}$. On page 263, in the second sentence of their proof of Theorem 12.5, they list a 0-certificate (or 1-certificate) as a subset of $[n]$.

Because $S \subseteq [n]$, it is easy to understand $x|_S$ (as is stated in the question). This is just the usual notation for the restriction of a function on a subset of its domain. Note that an $x \in \{0,1\}^n$ can be thought of as a function from $[n]$ to $\{0,1\}$.


If a parser can parse a non-deterministic grammar, is the parser non-deterministic? I've written a recursive-descent parser generator, and I'm trying to classify it (call me a cowboy coder if you must). According to wikipedia, S → 0S0 | 1S1 | ε, which checks for an even-length palindrome, is a non-deterministic grammar. My parser generator can handle this grammar. Does that mean my parser is non-deterministic?

To be honest, I'm not even sure that it's proper to try to classify it like this. It doesn't really match the description of a pushdown automata, since it passes data up and down through the stack (parameters, passed by reference, which may be modified). If anyone would be interested in taking a closer look at it, I'd be most grateful. It handles left recursion and ambiguous grammars in (I believe) polynomial time and space. https://github.com/coder0xff/parlex

No, it doesn't mean that.  A non-deterministic algorithm is one that uses non-determinism.  You're not using non-determinism; your algorithm is completely deterministic.

Here's what's tripped you up.  You can recognize a non-deterministic grammar using a deterministic algorithm.  Similarly, you can recognize whether a word is accepted by a non-deterministic finite automaton (NFA) using a deterministic algorithm (e.g., simply convert the NFA to a DFA, then check whether the DFA accepts the word).  So, no, just because the grammar is non-deterministic does not mean that we should call your parsing algorithm non-deterministic.


Why does the effectiveness of my reinforcement based neural network recede after a while? I have a reinforcement based neural network training on the OpenAI gym CartPole-v1 environment. For the structure and training algorithm, assume it is the same as the one in this article.

Typically, it averages becoming more effective, eventually perfectly solving the environment (500/500 reward for several hundred games in a row) but then starts to regress. Typically somewhere in the range of 100~150/500 total reward. This seems to happen regardless of learning rate, but I haven't tested with very low learning rates (less than 0.01) because of the amount of time it takes to train.

Can anyone tell me why this happens? I can't seem to find any literature on it, but perhaps I just don't know the name.

There seems to be some kind of overfitting happening.It happens when noise and fluctuation in data is learned as concept by your Neural Network Model.

https://en.wikipedia.org/wiki/Overfitting


Analog of PP for computability rather than complexity? The complexity class PP can be defined in many ways, one of which involves randomness - a language $L$ is in PP if there is a polynomial-time, randomized TM $M$ such that $w \in L$ if and only if the probability that $M$ accepts $w$ is greater than 1/2.

I'm curious whether there is a name for the complexity class that can be obtained by relaxing the definition so that the randomized TM doesn't necessarily have to run in polynomial time. Specifically, consider the class of languages $L$ such that there is a TM $M$ where $w \in L$ if and only if the probability that $M$ accepts $w$ is greater than 1/2. There is no requirement that this TM halt on all inputs.

Where does this class of problems lie? This class contains RE because any recognizer accepts a string $w \in L$ with probability 1 and accepts any string $w \notin L$ with probability 0. I doubt that it's equal to RE, though, since I can't see how you could convert this "majority recognizer" for $L$ into an actual recognizer for $L$. I tried placing it somewhere in the arithmetical hierarchy, but I don't see how to encode the concept "more than half of the computation branches accept" into some first-order formula involving alternating quantifiers.

Does this class of problems already exist and have a name? If so, what is it?

Thanks!

The ideas in this answer come directly from Ricky Demer. I wanted to write a more long-form answer that fills in a few of the details and justifies why this new complexity class is equal to RE.

First, let's introduce some notation. Let's call the complexity class described in this problem PRE for "probabilistic RE." We'll say that a language $L$ is in PRE if and only if there is a randomized TM $M$ such that

$$w \in L \leftrightarrow Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$$

The question now is how RE and PRE relate to one another. The goal will be to prove this theorem:

  Theorem: PRE = RE

To prove this, we'll show that each set is a subset of the other. One direction here happens to be relatively easy:

  Theorem: RE $\subseteq$ PRE.

  Proof: Consider an arbitrary $L \in$ RE. Since $L$ is in RE, there must be a TM $M$ that recognizes $L$. Specifically, for any string $w$, if $w \in L$, then $M$ accepts $w$, and if $w \notin L$, then $M$ does not accept $w$. Now, we can construct a randomized TM $M'$ that's basically the same as $M$; it doesn't actually use any randomness. As a result, if $w \in L$, then $Pr[M \mbox{ accepts } w] = 1$ and if $w \notin L$, then $Pr[M \mbox{ accepts } w] = 0$. Consequently, $L \in $ PRE.

The other direction of implication is the harder one. We're going to show that if you start with an arbitrary PRE language, you can prove that it's also an RE language. Equivalently, we'll show how to start with a randomized TM $M$ meeting the criteria of PRE and then show how to construct a recognizer for it.

Let $$M$$ be any randomized TM. Our goal will be to prove the following key lemma:

  Lemma: $Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$ if and only if there is some $n \in \mathbb{N}$ where $Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}] \gt \frac{1}{2}$

For now, let's assume the lemma is true. This gives rise to an elegant way to build a recognizer for any PRE language. Counting up from $n=1$, exhaustively list all computation paths through $M$ whose length is at most $n$ and explicitly compute the probability that $M$ accepts within $n$ steps. If at any point we find that this probability is greater than 1/2, by the lemma we know that the overall probability that $M$ accepts is greater than 1/2, so the input string $w$ must belong to $L$.

On the other hand, suppose that we never find an $n$ for which the acceptance probability within $n$ steps is greater than 1/2. That means that the acceptance probability for each computation length is at most 1/2. Since

$$Pr[M \mbox{ accepts } w] = \lim_{n \rightarrow \infty} Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}]$$

we would conclude that $Pr[M \mbox{ accepts } w] \le \frac{1}{2}$, meaning that $w \notin L$. In other words, the TM that just brute-force checks the acceptance probability for each computation length would be a recognizer for $L$, and so we'd see that PRE $\subseteq$ RE.

Everything hinges on this key lemma, so let's see how we might go about proving it. One direction is easier. Let's argue that if $Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$, then there must be some $n$ such that $Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{steps}] \gt 1/2$. As mentioned above, we know that

$$Pr[M \mbox{ accepts } w] = \lim_{n \rightarrow \infty} Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}]$$

Therefore, if we assume that $Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$, we know that

$$\lim_{n \rightarrow \infty} Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}] \gt \frac{1}{2}$$

We can use the formal definition of a limit to conclude from this that there must be at least one $n \in \mathbb{N}$ such that $Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}] \gt \frac{1}{2}$.

For the other direction, we need this additional result: if $m \le n$, then

$$Pr[M \mbox{ accepts } w \mbox{ within } m \mbox{ steps}] \le Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}]$$

Intuitively, this says that the acceptance probability as a function of the length of the computations considered is nondecreasing. Why is this? If you run a computation for $m$ steps and then continue to run it for one more step, all of the branches that were already accepting are still accepting. If none of the new branches exposed by running the TM for one more step are accepting, then the new acceptance probability is the same as the old acceptance probability. If any of the new branches exposed are accepting, the acceptance probability goes up.

Given this, we can say that if the acceptance probability after some number of steps $n$ ever exceeds $\frac{1}{2}$, then the acceptance probability for all larger numbers of steps also exceeds $\frac{1}{2}$, so the limit of the acceptance probability is also greater than $\frac{1}{2}$.

To summarize:

RE $\subseteq$ PRE since any recognizer fulfills the conditions of a randomized TM for a PRE language.
If we have a randomized TM meeting the requirements for a PRE language, then that TM accepts a string with probability greater than one half if and only if after some finite number of steps the acceptance probability exceeds one half. We can then build a recognizer for the language by simulating branches of the randomized TM and checking, at each point, whether the acceptance probability is at least one half.

Hope this helps!


Number of hardware page tables and page directories kept in the MMU How many hardware page tables (physical) and page directories are kept in the memory management unit?
If a cpu has a 32 bit virtual address, the upper 10 bits are used for the page directory, the middle 10 bits for the page table, and 12 bits for the 4K page frame. Does that mean 1 page directory containing 1042, 32 bit pointers, and 1042 page tables containing 1042, 32 bit pointers are needed?
What is the role of the page directory cr3 pointer control register in intel cpu?

The page tables are not kept in the MMU. In the MMU is a cache called the TLB which holds translated addresses. The TLB holds virtual addresses to physical addresses translations. For example, the TLB on intel core i5 has 64 entries for pages of 4KB.
Since the 10 upper bits are used as the offset in the page directory on 32 bits architecture, there are 2^10 = 1024 possible entries. The page directory has 1024 entries which hold the addresses of the page tables. Each page table has again 1024 entries holding the actual addresses of the page frames.
The CR3 register is used to locate the bottom of the page directory by the MMU. It holds a physical address (doesn't need to be translated).


general question amortized cost and worst case lets say a data structure has operations called insert and delete both of which take O(log(n)) worst case. Suppose the amortized cost of insert is O(log(n)) and the amortized cost of delete is O(1).

Now if a sequence that has n delete operations performed on this data structure  that has n elements currently, then what is the worst case? If delete takes O(1) amortized cost does this mean the worst case (not amortized) is O(n) for n delete's ?

I think no because it doesn't seem right but I'm not sure how to explain it

The answer hinges on the definition of amortized cost. Since you haven't given such a definition, let me assume that you are using the common definition.

Consider a data structure supporting operations $O_1,\ldots,O_m$. These operations have amortized cost $T_i$ (where $T_i$ could depend on parameters) if the total cost of a sequence of operations run immediately after initializing the data structure consisting of $c_i$ many operations of type $O_i$ is at most
$$ c_1 O_1 + \cdots + c_m O_m. $$
This bound only works if we consider all operations done on the data structure since initialization.

In your case, you are only considering one part of the operations performed on the data structure, and so amortized cost doesn't apply.


Undecidable among these for turing machine Below are two questions I found in Theory of Computation book but couldn't find its correct answers, can anyone please give correct answers with explanation?

It is undecidable, whether

an arbitrary Turing machine(TM) has 15 states
an arbitrary TM halts after 10 steps
an arbitrary TM ever prints a specific letter
an arbitrary TM accepts a string w in 5 steps

Which one of the following is not decidable?

given a TM M, a string s and an integer k, M accepts s with k steps
equivalence of two given TMs
language accepted by a given DFSA(Deterministic finite state automata) is nonempty
language accepted by a CFG(Context free grammar) is nonempty

Update: In first question I think 1.2 is right because halting is undecidable for Turing machine but not sure whether remaining options are decidable or not.
In second question I think 2 is right, but not sure about the decidability of non emptiness of CFG and DFSA.

(1.1) Is it undecidable whether an arbitrary Turing machine(TM) has 15 states?

No, this is a decidable problem. Given a TM in a suitable encoding, it is fairly straightforward to determine how many states the TM has. Consider any common encoding, or define a reasonable one yourself, and then describe an algorithm that answers the question using the encoding. Hint: you can make your algorithm really simple if you define the encoding such that the first part of the encoding is an encoded list of states that are part of the TM.

(1.2) Is it undecidable whether an arbitrary TM halts after 10 steps?

I assume what you mean by this is the following: is it undecidable whether an arbitrary TM halts after exactly 10 steps for some input? The answer is that, no, this is also decidable. Consider all $\Sigma^{10}$ configurations of the first $10$ cells of the tape. For each of these, configurations, execute 10 steps according to the TM's transition table (for nondeterministic TMs, this includes all possible paths of length 10). If one of the paths halts after exactly 10 steps, output yes; otherwise, output no.

(1.3) Is it undecidable whether an arbitrary TM ever prints a specific letter?

This one is actually undecidable. Suppose it weren't undecidable. Take an arbitrary TM. Construct a new TM with a new alphabet symbol not in the alphabet of the original TM. Replace all transitions in the original TM which cause the machine to halt with transitions which cause the machine to halt and which write this new symbol to the tape. By the assumption, the problem of whether the new TM prints this specific symbol is decidable; however, solving this problem would give us a way to solve the halting problem for the original TM (since the new one printing the symbol would only occur if the original one halted). Since the halting problem is undecidable, we have a contradiction, hence, this problem is undecidable.

(1.4) Is it undecidable whether an arbitrary TM accepts a string w in 5 steps?

This is clearly decidable. Given a TM and a string, write the string on the tape and execute five steps of the TM according to its transition table.

Which one of the following is not decidable?

given a TM M, a string s and an integer k, M accepts s with k steps
equivalence of two given TMs
language accepted by a given DFSA(Deterministic finite state automata) is nonempty
language accepted by a CFG(Context free grammar) is nonempty

(2.1.) is definitely decidable as per the argument in (1.4).
(2.2.) is ambiguous; if we mean syntactically equivalent, then this should be decidable given a suitable encoding. If it means semantically equivalent, i.e., they decide/accept the same language, then this is definitely undecidable.
(2.3.) is definitely decidable, since you can always minimize the DFA and see whether it's a single state with no accepting states.
(2.4.) is definitely decidable. Begin marking symbols (terminal/nonterminal) if they lead to a string of only terminal symbols. First, mark all terminal symbols. Next, mark nonterminals which lead to a string of only nonterminals. Iteratively, mark unmarked nonterminals which lead to strings of terminals or already-marked nonterminals. Continue until you complete an iteration without marking any new nonterminals. If the start symbol is marked, then it leads to a string of terminals, which is a string generated by the grammar, so its language is non-empty. Otherwise, the start symbol doesn't lead to a string of all terminals, so its language is empty.

By process of elimination, the answer to question (2) must be (2.2) and the interpretation given to "equivalent" must be "decides/accepts the same language."


Existence of NP problems with complexity intermediate between P and NP-hard Assuming P!=NP, there is a result that there are decision problems intermediate between P and NP-complete. That is, the class NP cannot be a union of two disjoint subsets: P and NP-complete.

I could never quite understand the proof of the above result. The proof I saw in a textbook was starting with the assumption that one can enumerate all P and NP-hard problems, and then proceeding with a construction of a function that didn't fit in either. However, this construction seemed a bit fishy to me; in particular, the assumption that one can start with enumerated set of problems in a particular class, the NP.

Could you refer me to a clear self-contained proof of the statement in the 1st paragraph? More generally, what would be a good reference for proofs of such results?

The result you're describing is called 'Ladner's Theorem.'  The Wikipedia article on 'NP-Intermediate' is probably a good place to start - you can find references to Ladner's original paper there.

There's also an extensive list of such problems on the cstheory Stackexchange.

For a couple of proofs of Ladner's Theorem, check out this note adapted from Downy & Fortnow's paper 'Uniformly Hard Languages'.


Why does universe level restriction behave differently between inductive family and parameterized inductive type without axiom K in agda An observation when defining List in agda with --without-K enabled:
The following parameterized inductive definition is accepted:
data List (A : Set) : Set where
    [] : List A
    _::_ : A → List A → List A

but not the equivalent inductive family definition:
data List' : Set → Set where
    []'  : {A : Set} → List' A
    _::'_ : {A : Set} → A → List' A → List' A

The error message is Set₁ is not less or equal than Set, so I have to change the type from List' : Set → Set to List' : Set → Set₁ in order for it to type-check. If I disable --without-K, then agda also correctly type-checks.
I tried to look up why this is the case, e.g., on the page https://agda.readthedocs.io/en/latest/language/without-k.html it says "When --without-K is enabled, some indexed datatypes must be defined in a higher universe level. In particular, the types of all indices should fit in the sort of the datatype." But it doesn't say the reason for such difference between inductive family (indexed datatypes) definition and the parameterized inductive definition. I guess it has something to do with the homotopy model interpretation of the underlying type theory. However I want to know what sort of "bad" thing will happen if the inductive family lives in a smaller universe (syntax and semantics). And how would parameterized inductive definition avoids such issue?

Normally, Agda does an analysis to determine that your indexed type is equivalent to a parameterized type. Essentially, since A occurs in the result type, knowing that l : List A tells you what type A is 'stored' in the value l. The value is known, which means that tricks that involve embedding a universe into a small type within said universe to cause a paradox will not work.
However, the above reasoning basically presumes K for the universe. Really all we can say is that knowing the type List A lets us know that the stored type is equal to A, but without K, we don't know that there are no non-trivial equalities between types. I'm not sure if there is an example of how this extra degree of freedom would allow a paradox to be written, but even if no example is known, it is safer to require the larger size than to assume that the small size is consistent.


Hard computational problem on special class of bipartite graphs I am interested in the properties of a class of bipartite graphs $G(X \cup Y, E)$ where all nodes in $X$ are 3-regular, all nodes in $Y$ are 2-regular, and $|X|=|2Y/3|$. First, Is this a well known class of graphs? Secondly,

  Is there an example of intractable computational problem restricted to this class of bipartite graphs?

Given a 3-regular graph $G = \{V,E\}$ you can build a bipartite graph $G'$ with the required properties picking $X = V$ and $Y = E$ and for every edge $e_k = (u_i,u_j) \in E$ add edges $(u_i, e_k), (e_k, u_j)$. So I think that you can find some hard problems starting from hard problems on 3-regular graphs.

For example SUBGRAPH ISOMORPHISM is NP-hard for your class of graphs.

The reduction is from Hamiltonian cycle on 3-regular graphs: given a 3-regular graph $G$, build the corresponding $G' = \{X \cup Y, E'\}$ and check for a subgraph $H'$ which is a closed simple cycle of length $2|V|$. $G'$ has a subgraph isomorphic to $H'$ if and only if $G$ has an Hamiltonian cycle.


Bellman-Ford - is number of interations greater than diameter? Diameter of a connected, undirected graph is the smallest natural
  number d, so that between any two vertices of the graph exist path
  of length at most d.

  Prove or disprove: in Bellman-Ford is the number of iterations always
  equal or lower than d.

I'm trying to solve this issue. What I tried was sketching a lot of graphs, however I have failed to find a single graph where the number of iterations would be higher than the diameter.

The only graph where the number of iterations wouldn't be <= than diameter would be a graph with negative edges, however I found out that in undirected graph there can't be any negative edges, otherwhere there would be a negative cycle.

So, AFAIK the statement is correct. However, how would I prove such a statement? I don't even know how to start. Thanks for any help

In the Bellman–Ford algorithm, after $t$ iterations the array contains, for any two nodes, the minimal walk of length at most $t$ connecting them. Assuming your graph doesn't have negative weights, the shortest walk between any two vertices will be a path, and so its length would be at most the diameter. Therefore there is no need to run the algorithm beyond $d$ iterations.