Weak bisimulation up-to $\approx$ Given this definition of weak bisimilarity:

A configuration relation $\mathcal{R}$ is a weak bisimulation
  provided that whenever $P\ \mathcal{R}\ Q$ and $\alpha$ is $\mu$ or $\tau$ action then:

$P \to^\alpha P'$ then $Q \Rightarrow^\widehat{\alpha} Q'$ for some $Q'$ s.t. $P'\ \mathcal{R}\ Q'$
$Q \to^\alpha Q'$ then $P \Rightarrow^\widehat{\alpha} P'$ for some $P'$ s.t.
  $P'\ \mathcal{R}\ Q'$

P and Q are weakly bisimilar, written $P \ \approx \ Q$, if $P \ \mathcal{R} \ Q$
  for some configuration relation $\mathcal{R}$.

My questions are:

For the relation $\mathcal{R} = \{(\tau.a, 0)\}$, $\mathcal{R} \nsubseteq \approx$ but $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$. Why is $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$?
According to Sangiorgi's book, P uses $\tau$ and ends up with $a \approx \tau.a$ and Q has $0$ and ignores the move. I am wondering, how is it that you can ignore the move? I thought that one is forced to do a move...
Could you please provide an detailed explanation of why weak bisimilarity up-to $\approx$ is unsound? (You can use the example above but I would appreciate a detailed explanation

Thanks.

(partial answer)

  For the relation $\mathcal{R} = \{(\tau.a, 0)\}$, $\mathcal{R} \nsubseteq \approx$ but $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$. Why is $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$?

Actually, the inclusion $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$ holds for any relation $\mathcal{R}$, and not just the one mentioned. Indeed, if we have $P \mathcal{R} Q$, then we also have $P \approx P \mathcal{R} Q \approx Q$, by reflexivity of weak bisimulation.

  According to Sangiorgi's book, P uses $\tau$ and ends up with $a \approx \tau.a$ and Q has $0$ and ignores the move. I am wondering, how is it that you can ignore the move? I thought that one is forced to do a move...

You have to check that $0\xrightarrow{{\hat\tau}} 0$, which (if I remember correctly) is defined as $0\xrightarrow{{\tau}}^* 0$ which holds since the Kleene's star includes "zero steps".

I seem to remember that the "$\hat\alpha$" move definition made a special case for $\hat\tau$, specifically to allow for zero steps.


Does a subcubic algorithm exist for the following problem? Given a symmetric real $n \times n$ matrix $A=(a_{ij})$, is there an algorithm which computes the sum $$\sum_{i,j,k}\max(a_{ij},a_{ik},a_{jk})$$ over all $1\leq i<j<k\leq n$ with time-complexity better than $O(n^3)$?

There exists a quite practical approach that works in $O(n^3 / w)$ time, where $w$ is the number
of bits in the processor word. The main idea is that you iterate over
the elements of the matrix one by one in the increasing order (break ties arbitrarily)
and "switch them on". Consider the moment when the largest element of
some triple $a_{ij}, a_{ik}, a_{jk}$ is switched on. For simplicity, let's assume
that the said element is $a_{ij}$. It is natural to add the value of the triple
to the answer now, when the last element is switched on. So we have to count
the number of possible $k$'s such that $a_{ik}$ and $a_{jk}$ are already switched on (that would be the number of triples, here $a_{ij}$ is the largest element, so they were completely switched on just now). Here we can speed up the naive $O(n)$ implementation by using bit optimisation.

For details you can refer to the following implementation in C++11 that
should work for $n \leqslant 5000$, $|a_{ij}| \leqslant 10^9$
(it is not very optimized; however,
it still beats naive summation for $n = 5000$ by large margin at least on my machine).

// code is not very elegant,
// but should be understandable
// here the matrix a has dimensions n x n
// a has to be symmetric!
int64_t solve (int n, const vector<vector<int32_t>> &a)
{
        std::vector<boost::dynamic_bitset<int64_t>> mat
        (n, boost::dynamic_bitset<int64_t>(n));

        vector<pair<int, int>> order;
        for (int j = 1; j < n; j++)
        for (int i = 0; i < j; i++)
            order.emplace_back(i, j);
        sort(order.begin(), order.end(),
            [&] (const pair<int, int> &l, const pair<int, int> &r)
            {return a[l.first][l.second] < a[r.first][r.second];});

        int64_t ans = 0;
        for (const auto &position : order)
        {
            int i, j;
            tie (i, j) = position;
            mat[i][j] = mat[j][i] = 1;
            // here it is important that conditions
            // mat[i][i] = 0 and mat[j][j] = 0 always hold
            ans += (mat[i] & mat[j]).count() * int64_t(a[i][j]);
        }

        return ans;
}

If you consider using bit optimisations cheating,
you can use four russians method to the same result here,
yielding a $O(n^3 / \log n)$ algorithm, which should be less practical
(because $w$ is pretty large on most modern hardware)
but is theoretically better.
Indeed, let's choose $b \approx \log_2 n$ and keep each
row of the matrix as an array of $\lceil \frac{n}{b} \rceil$ integers
from $0$ to $2^b - 1$, where the $i$-th number in the array
corresponds to the bits of
the row ranging from $ib$ inclusive to $\min(n, (i + 1)b)$ exclusive
in $0$-indexation. We can precalculate the scalar products of every two
such blocks in $O(2^{2b} b)$ time. Updating a position in the matrix
is fast because we are changing only one integer. To find the scalar product
of rows $i$ and $j$ just iterate over arrays corresponding to that rows,
look up scalar products of the corresponding blocks in the table and sum up the
obtained products.

The above paragraph assumes that operations with integers $\leqslant n$ take $O(1)$ time. It is quite common assumption, because it usually
does not actually change the comparative speed of the algorithms (for example,
if we don't use that assumption, brute force method actually works in
$O(n^3 \log n)$ time (here we measure time in bit operations) if $a_{ij}$ take integer values with absolute values at least up to $n^{\varepsilon}$ for some constant $\varepsilon > 0$
(and otherwise we can solve the problem with $O(n^{\varepsilon})$ matrix multiplications anyway); however the four russians method suggested
above uses $O(n^3 / \log n)$ operations with numbers of size $O(\log n)$ in that
case; so it makes $O(n^3)$ bit operations, which is still better than brute force despite the change of the model).

The question about existence of $O(n^{3 - \varepsilon})$ approach is still interesting, though.

Techniques (bit optimisations and four russians method) presented in this answer are by no means original and are presented here for completeness of the exposition. However, finding a way to apply them was not trivial.


Is there a name for graphs which contain oriented and non-oriented edges? Is there a name for graphs which contain oriented and non-oriented edges?

I couldn't find on the internet if there exist a specific name for such graphs.


What is the difference between luma and luminance? I understand the following (correct me if I'm wrong):

Statements

Luma as the weighted sum of RGB gamma corrected components, but luminance is the weighted sum of RGB linear components.
The gamma correction has two forms: gamma compression and expansion. When we want to encode luminance into imaging systems, we turn it into luma using gamma compression (so $\gamma <1$ when we raise the RGB components to a higher power).

So in short, Luma is the stuff in the "computer world" and Luminance is exists in the "physical world", is this correct? Because Luminance is roughly equivalent to the $Y$ value in CIE-XYZ colour space.

Questions

When I have my images, are the pixel values already in linear RGB components or are they gamma corrected RGB components? That is, how is luma represented internally in imaging systems?
When we want to emit the colour in the screen, we perform gamma expansion, is this right? If so, will the light that comes out of the screen be considered as luminance?
When light waves travel, what physical property does luminance represent? Is it the amplitude of light waves?
In the CIE-XYZ colour space, is Y the only one that has physical meaning? Meaning to say X and Z are rather arbitrary factors dependent on the human visual system and nothing to do with physics itself,is this correct?

There are actually three related terms:

Luminance is a physical measure which represents the luminous intensity per unit area of light travelling in some direction. The units are candela per square metre. This is, if you like, an objective measure of how "intense" light is.
Relative luminance is a measure how "intense" light appears to a human; since humans can't see X-rays or infra-red, that doesn't register. The CIE standard defines a "standard observer" (more on this later) under various conditions. This is normalised into a range from 0 to 1 or 0 to 100, where the higher value is a reference white.
Luma is defined as the relative luminance calculation performed on a gamma-compressed video signal.

So if you take a real-world light source, and point an image sensor at it, the image sensor will output $R'G'B'$ values, where the prime denotes gamma compression.

If you were to uncompress those signals (i.e. convert the gamma-compressed $R'$ into its corresponding linear-space $R$, then:

$Y = 0.2126 R + 0.7152 G + 0.0722 B$ is the relative luminance
$Y' = 0.2126 R' + 0.7152 G' + 0.0722 B'$ is the luma

Relative luminance is exactly Y in CIE-XYZ. Y is calculated by calculating the inner product of the power spectral density of a light source with the luminosity function which represents the "standard observer".

(Note that CIE standard actually defines more than one luminosity function, because the human eye behaves differently in low-light condition; Y is defined in terms of the photopic luminosity function.)

The only reason why we define luma is for signal processing and compression reasons. It's easier to compress based on the luma signal than the relative luminance because the transformation is simpler; in fact, it's achievable using relatively cheap 1960s-era analog electronics. And since there's a more-or-less monotonic relationship between the two, luma key is close enough to keying on relative luminance.

OK, now to your questions:

When I have my images, are the pixel values already in linear RGB components or are they gamma corrected RGB components? That is, how is luma represented internally in imaging systems?

High-quality image formats tell you. Along with an array of triplets of numbers (which are just numbers), there should be information about what colour space the image is in.

Unless you have been told otherwise, it's safe to assume that any standard dynamic range still image pulled off the Internet is in sRGB. This is gamma-compressed, although the gamma is not constant.

For video, there are lots of colour spaces in use. Broadcast television follows the ITU-R recommendations (e.g. Rec 601 is standard definition, Rec 709 is high-definition, etc), and film tends to use Cineon.

But each camera manufacturer typically defines its own colour space too, which represents the best approximation of the sensors in the camera. ARRI cameras, for example, output their own colour space known as ARRI Log C.

It's something of a mess.

When we want to emit the colour in the screen, we perform gamma expansion, is this right? If so, will the light that comes out of the screen be considered as luminance?

"Gamma" is a confusing concept because it refers to two distinct things. Strictly speaking, "gamma" should refer to the nonlinearity of a hardware device, such as a sensor or display. All image data should be linear, intermediate work should be in a linear space, and gamma should only be applied when data is acquired or displayed.

"Gamma compression" refers to a technique for compressing linear data in a file format, so that fewer bits per sample are required.

It just so happens that a lot of modern display vendors and file format designers have agreed on the same standard, sRGB. So if you have data compressed in sRGB format and a display which works in sRGB, the operation of decompressing the file format and the operation of preparing the data for display cancel each other out. In general, that need not be the case.

For a properly calibrated display, yes, Y is relative luminance.

When light waves travel, what physical property does luminance represent? Is it the amplitude of light waves?

Answered above. Luminance is the physical measure of the intensity of light, and relative luminance is the perceived intensity of light (for a standardised human observer).

In the CIE-XYZ colour space, is Y the only one that has physical meaning? Meaning to say X and Z are rather arbitrary factors dependent on the human visual system and nothing to do with physics itself,is this correct?

What I hope you can now see is that Y, relative luminance, is also defined on the human visual system.


Running an application that needs 6 threads on dual core processor If a dual core processor have 4 threads, then what will happen if i run an application which uses more than 4 threads?
And just to make sure i'm understanding what are threads in a cpu, when an application uses more than one "task" on its main process a single core will switch back and forth between the threads to give the illusion that it is running them in parallel, is that right?

If there are $2$ cores and $4$ threads, two threads will be assigned to each core. Similarly, if there are $6$ threads, three threads will be assigned to each core. For example, suppose $6$ threads are $T_1,T_2,T_3,T_4,T_5,T_6$. Then, say $T_1,T_2,T_3$ are assigned to core $1$ and $T_4,T_5,T_6$ are assigned to core $2$.
As you are saying, $T_1,T_2,T_3$ will switch back and forth on core $1$ to give an illusion of parallel. However, note that $T_1$ and $T_4$ are indeed running in parallel on different cores.


How to prevent the optimization algorithm from just shrinking the image? I'm trying to optimize a set of patterns in an image, but unfortunately they only way I have of evaluating the images results in smaller versions of the pattern scoring much better than larger versions.

As a result, the optimization methods I've tried all just end up shrinking the pattern down until they run into aliasing issues, and start becoming erratic.

I've tried normalizing the images by resizing the patterns to all be the same size at each step, but the optimization algorithm quickly just adds 'decoy' pixels to the corners, defeating the normalization.

I've considered trying to do the optimization with a vectorized form, but evaluating a pattern requires it to be rasterized to a particular size anyway.
Vectorizing the pattern also doesn't solve the problem with normalization and adding decoy geometry.

How can I prevent the optimization process from just scaling down the image?

I doubt your question can be answered in any detail without knowing more about what you're trying to achieve with these patterns.  The general answer to "my scoring function rewards something I don't want" is either to fix the scoring function or to add a penalty to counteract it, but I'm sure you were already aware of that.

Depending the optimization method you're using, you could possibly also try biasing your sample generation method away from local optima in the unwanted part of the parameter space, but that's generally only effective if there's some other, better local optimum available elsewhere for the process to converge to instead.  If the unwanted local optimum is actually the global optimum for your scoring function, then any decent optimizer will sooner or later find its way there.  If that's the case, you really do just need to find a way to fix your scoring.

Anyway, since you say in the comments that smaller patterns are objectively better in some sense, I assume they must also have some property that makes them objectively worse in some other way. You might want to think about what exactly that property is, and try to penalize that.


classify location of the expiry date on drug label and lot number Is it possible that using the Machine Learning classification model we can classify/predict the LOCATION/ORIENTATION of the lot number and expiration date on different vials label?

If yes, possible approaches.

Update: So far what I have observed is with EAST model
https://arxiv.org/abs/1704.03155

one can locate text in the scene and then use OCR s/w like Textract to read those locations. Now, the real challenge is when you have lots of text available in the image vertical and horizontal and when you don't know where the particular text would appear in the image like expiry date - Is it possible to train a system to give just one or two locations which will be expiry date and lot number?

The challenge here I feel is the location but what features we would take to train as it's just text. I feel it's a classification problem with supervised learning but I may be wrong. Comment?

Thanks

It seems plausible that it might be doable, using methods in the research literature on object detection and localization (Yolo, Faster R-CNN, etc.).  The only way to tell for sure is to acquire a large dataset of such images and try it out and see how well it works on your data.


Reductions to and from PRIME I think PRIME (is the given number a prime number?) is a good example a decision problem.  Therefore, when I'm trying to explain reduction, I'd like to give an example of a problem that is related to PRIME.

What are decision problems that can be reduced to PRIME, and how do these reductions look like?

What are decision problems that PRIME can reduce to, and how do these reductions look like?

Assuming you're talking about polynomial-time reductions, since PRIME is in $P$, you can reduce it to any non-trivial decision problem (for which there is at least one instance with answer YES and at least one instance with answer NO). Moreover, any problem in $P$ can be reduced to PRIME.

To reduce an instance $I$ of PRIME to an instance $I_Q$ of non trivial decision problem $Q$, let $Y_Q$ and $N_Q$ be a YES and a NO instance for $Q$, respectively. The reduction is as follows: solve $I$ using a polynomial-time algorithm for PRIME. Then, let

$$I_Q = \begin{cases}Y_Q & \mbox{if $I$ is a YES instance}, \\ N_Q & \mbox{if $I$ is a NO instance}.\end{cases}$$

To reduce an instance $I_Q$ of a problem $Q \in P$ to an instance $I$ of PRIME, solve $I_Q$ using a polynomial-time algorithm for $Q$ and define

$$I = \begin{cases}2 & \mbox{if $I_Q$ is a YES instance}, \\ 1 & \mbox{if $I_Q$ is a NO instance.}\end{cases}$$


Why is the target function minimized at (0,0) if I can get to a negative number? I just started learning LP and I saw this Q in my textbook:

$$
min  : -x -y \\
S.T. : x + 2y \le 3, 2x +y \le 3, x \ge 0, y \ge 0
$$

It is easy to see that the polygon created from these constraints can't have a negative coordinate. In my textbook it says the answer is $(0,0)$ since $-0 -0 = 0$ and this is the minimum value of the target function (i.e. $f(x,y) = -x -y$).

Why is that the minimum? If I choose any other values (S.T. the constraints are satisfied) I can get, for example, $(1,1)$ which will result in $-1 -1 = -2 < 0$!

Another thing that I don't understand - would there be a difference if my function was different? If the min is $(0,0)$ - wouldn't it be the case for any other $f(x,y) = a*x + b*y$ for any other $a,b$?

Is easy to prove that $(0,0)$ is the maximum of your suggested target function, so it may be an errata of your text.

Your second question is way more interesting, the answer is no, if you change your target function to another linear function the maximum or minimum may change, suppose you change your target function to $x+y$, the minimum now is $(0,0)$, previously it was $(1,1)$.

However, as you suggested in the comments, if you only change your function by a positive scaling factor $a$, the maximum/minimum remain the same. This is easy to prove as
$$\alpha\leq \beta\iff a\alpha\leq a\beta$$
holds (I leave the details to you).

In general, there are branches of linear programming called "postoptimization" and "sensitivity analysis" in which your second question is studied in detail, for example, describing algorithms to obtain an optimal solution of the same problem for various target functions in almost the same running time of solving just one problem.


Is there any other computation theory besides the one in automata theory? I'm a bit confused at a fundamental level.

In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, security, or automata theory for example). Of course, there are also calculus and nonlinear mathematics in Computer Science, but it seems to me that that doesn't matter in the subject Theory of Computation.

Theory of Computation is supposedly for machines. In Theory of Computation, the object of interest is languages and one-dimensional strings/sequences of symbols.

But why is it that it's only for linear, one-dimensional sequences of symbols? The natural phenomenon is also more to analog than digital (take a look at physics, waves for example). Does it mean that Theory of Computation or Theory of Automata is restricted only to machines/computation that is using one-dimensional strings/sequences of symbols?

In general, not only in Computer Science, is there any other object of interest for computation, other than languages and strings? Since languages and strings of symbols are discrete. What about nonlinear mathematics, dynamical system, and wave for example? They are not strings of symbols, right? So, what about their Computation Theory? Is it still restricted to automata, grammars, Turing machine, or are they totally something different?

Are all things can be represented with languages/ strings of symbols? Are languages/string of symbols enough to represent any thing/phenomenon?

What is computation theory exactly for things other than languages/ strings of symbols (if any)?

Sorry that I don't know how to phrase all these better. Can somebody please enlighten me, or provide any keywords that I can search for? Thank you very much!

There is indeed computability-theory for non-discrete settings. This area is called computable analysis. A decent tutorial to computable analysis is here (if you have an institutional subscription, or can get it from a library):

https://link.springer.com/chapter/10.1007%2F978-0-387-68546-5_18

The tutorial focuses quite a bit on the case where we are computing with real numbers, or at least elements of metric spaces. Computable analysis can handle much more situations though. Roughly speaking, we probably have reasonable computability-notions for any kind of space appearing in ordinary mathematics.

It turns out that many concepts from the classical, discrete computability theory still apply, but topological aspects also become very relevant.


Why use logic gates in this situation? (XOR gates) I came across this circuit that swaps logical signals:

However I don't understand why would you need to use logic gates. Would it be possible to just connect the A on the left to the B on the right and the same with the B on the left (maybe add a diode to prevent current from going back?).

And one last question; would an "Enable" signal make this circuit more useful (only swaping when Enable is high)?

Maybe I'm missing something. Thank you.

One reason for using such a circuit is to avoid wire crossing. Integrated circuits are laid out on several planar layers, and inside each layer, wires are not allowed to cross (for obvious reasons). Hence if you want to switch two wires, you either need to reach out to a different layer, or to use a gadget such as the one shown. I have no idea whether this kind of gadget is actually used in practice.

It should be noted that same idea can be used to swap two values without using any additional memory:

$A \gets A \oplus B$
$B \gets B \oplus A$
$A \gets A \oplus B$

In a C-like language, this would be A ^= B; B ^= A; A ^= B. This code corresponds to an execution of your circuit in topological order.


What is the difference between exactness and optimality of an algorithm? I'm studying some papers related to graph partitioning (GP). It is well-known that the GP problem is NP-Complete. Based on my understanding, it means that there is no polynomial time solution to solve this problem, or there is no optimal solution for that.
The following paper mentioned this fact in its introduction:
"An exact algorithm for graph partitioning"

However, they provided an exact solution for GP using branch-and-bound algorithm. Isn't it a paradox?, I mean I assume that if a problem is NP-Complete, there is also no exact solution for that, right?

Every NP-complete problem can be solved in exponential time. Assuming that P differs from NP, it cannot be solved in polynomial time. It follows that the branch-and-bound algorithm probably doesn't run in polynomial time (in the worst case).

To give a concrete example, consider the problem of MAX-CLIQUE: given a graph, the task is to find a clique of maximum size. The decision version of this problem (given a graph and a number $k$, decide whether the maximum clique has size at least $k$) is NP-complete. This means that (unless P equals NP), no polynomial time algorithm can solve MAX-CLIQUE exactly on all inputs. However, there is a simple exponential time algorithm that does solve MAX-CLIQUE exactly: it just tries all potential cliques and checks which of them are present in the graph.

Finally, you mention that if a problem is NP-complete then the reason might be that there is no optimal solution. This is just wrong, and I suggest ignoring the source which led you to believe this statement.


Large-scale string clustering I've more than 10 million strings of length 1-100 characters. This number will be even bigger in the future. I'm interested in clustering this data, but I'm not quite sure what would be effective at this scale.

These are the clustering algorithms I've been looking into:

Affinity propagation:: seems like a good solution, but the memory usage seems way too high, since the data is dense.
DBSCAN: could also be an option, but I want all nodes/strings to belong to a cluster and not be considered "noise.
K-medoids: seems like a good option in terms of memory usage, but the computation time seems worrying. It would also be highly preferred if the number of clusters was not determined before running the algorithm as in affinity propagation.

Do you have any ideas on how this problem can be solved? The computation time is not extremely important, as long as the result is satisfiable and it can be done within a couple of days.

Thank you in advance!

There are many possible approaches.  One approach that I would suggest investigating is finding all pairs of similar strings, and then applying a standard algorithm for clustering of sparse graphs.  There are multiple possible approaches for finding similar strings, depending on how you plan to measure similarity.

One approach is to measure similarity using the Levenshtein edit distance.  If you have $N$ strings, the naive way is to loop over all $N^2/2$ pairs, compute the edit distance for each, and save the pairs where the edit distance is below some threshold.  However, this doesn't scale when $N$ gets large.  Another alternative is to use fancier data structures and algorithms to find only the pairs of strings that are similar, e.g., BK-trees, ternary search trees, metric trees, Levenshtein automata, shingling, or other methods.  See, e.g., How fast can we identifiy almost-duplicates in a list of strings?, How to speed up process of finding duplicates/similar items in a large amount of strings?, Find all pairs of strings in a set with Levenshtein distance < d, Efficient map data structure supporting approximate lookup, Efficient data structures for building a fast spell checker, and https://cstheory.stackexchange.com/q/4165/5038 for some references.  Credits to Pseudonym for part of this suggestion.

Alternatively, if you want to measure similarity using the number of characters the differ (i.e., like the edit distance but with only the "replace" operation and without the "insert" or "delete" operations), you could look at locality sensitive hashing as a way to find all pairs of similar strings.


Is it possible to form a PDA for this language? $$L=\left \{ a^nb^m|n\leq m\leq 2n \right \}$$
Is this even context free?
I am asking because by looking at the condition, for an expression that holds:$n< m<2n$ can be written as : $a^nb^nb^c (c<n)$.
Following this term(taken from geeks for geeks https://www.geeksforgeeks.org/check-if-the-language-is-context-free-or-not/) :"An expression that involves counting and comparison of three or more variables independently is not context free language, as stack allows comparison of only two variables at a time."
So here I need to make sure that number of first b's is the same as a's and the second b's are less than n$(c<n)$, which makes me think that L might not be context free(although it specified clearly to build PDA for this).

Yes, the language is context-free.  I recommend that you ignore that article on geeks for geeks; its so-called "analysis" is stated in a way that is highly ambiguous, and appears to be faulty in some cases.
Hint: The language has the form $L = \{a^j a^k b^k b^{2j}\}$.  Build a PDA that non-deterministically guesses $j$.  (I assume you know how to build a PDA for $\{a^n b^n\}$ and $\{a^n b^{2n}\}$.)


Lexicographic Order of Expression [Automata Theory] what will be kleene star "expansion" of expression $a^*b^*$ in lexicographic order?
I'm confused and I really want to clear my concepts so I can proceed further

The lexicographic order is defined on words, not on regular expressions. An interesting exercise is to describe the restriction of the lexicographic order to the language $a^*b^*$, assuming that $a < b$. Note for instance that
$1 < a < a^2 < \dotsm < a^n < \dotsm$, but $\dotsm <a^nb <\dotsm <a^2b < ab < b$.


How to move spheres in 3d without collision Is there an algorithm that gets as an input 2 arrays (arr_origin, arr_dest) that represent spheres with a set radius (R) in a 3d space, (x,y,z) points. And finds a route for the spheres from origin to dest without collisions, in the fastest way given each sphere can move at a speed from 0 to V?

Here's how I would do it:
Create an oriented bounding box around the path of each sphere, with dimensions equal to the sphere's diameter. Now perform collision detection on all of those bounding boxes. For the ones which do not collide, their correlating sphere's can travel at max velocity.
For the bounding boxes that DO collide, do they collide at a point equidistant to the spheres' starting points (+/-  radii)? If not then they are free to move at max velocity.
If they DO collide at an equidistant point(+/- radii), then you must slow one sphere down so that it will not collide.

Hope this helps.
Good luck!


Recovering the transition function of a Turing machine with a known number of states Suppose we have a Turing Machine and know how many states it has as well as bound on its running time, but do not initially know its transition function.  Is it possible to determine its transition function (up to a relabeling of its states and disregard for inaccessible states) by noting its behavior on only finitely many strings?  (By behavior I mean  a record of its computation histories leaving out the information of which state it is in at any particular step.)

On the one hand, there are only finitely many Turing machines with a set number of states, so we could definitely run them on all of the finitely many given strings to determine if a given transition function is not a candidate.  However, I realize that Rice's Theorem might prevent us from determining the behavior on all inputs given only its behavior on inputs up to a given length.  Even if it is not possible for Turing machines to recover its transition function, is it possible for simpler computation models like DFA's and PDA's?  Thanks for your help.

Yes, this is possible.  This is not really a question about Turing machines so much as a question about learning DFAs given membership queries (you provide an input to the DFA and learn whether it accepts or not, and in the case of a finite-state transducer, the output it produces).  Therefore, decidability doesn't really enter into it.

If you know the number of states in the FSM of the Turing machine, yes, observing its behavior on finitely many strings is enough.  You can use Biermann's algorithm to infer a FSM that is consistent with the observed behavior.

You can think of Biermann's algorithm as basically just using SAT, where for each string $u$, you have a variable $s_u$ to represent the state the FSM is in after reading string $u$.  If the FSM has $n$ states, then each $s_u$ must be one of $n$ possible values.  You can use the outputs to deduce some relationships on these variables: e.g., the FSM's behavior on input sequence $u$ differs from its behavior on input sequence $v$, then we obtain the constraint $s_u \ne s_v$.  Also, you get some additional relationships due to the fact that this is a FSM: $s_u = s_v \implies s_{uw} = s_{vw}$ for all $u,v,w$.

Biermann's algorithm yields an (exponential-time) algorithm for finding a FSM that is consistent with all of the observations, if one exists.  Learning a FSM given just membership queries is NP-hard, so you can't expect a more efficient solution in this model.

Biermann's algorithm only promises to give you a FSM that is consistent with all of the observations.  How do we know whether this will match the FSM of the Turing machine?  In general, we don't, but in this case we can use our knowledge of the number of states of the FSM to solve this.  In particular, suppose we know there are $n$ states in the FSA of the Turing machine (after it has been minimized).  We apply Biermann's algorithm to check whether there exists a FSM that's consistent with all the observations and uses $n$ states, and use Biermann's algorithm to check whether there exists a FSM that's consistent with all the observations and uses $n-1$ states.  If the answers are yes and no, respectively, we are done.  If the answers are yes and yes, then we generate more observations until we're done (this can be done systematically in a way that will terminate, by using knowledge of the candidate FSM with $n-1$ states).

I am assuming by "observe its behavior" you mean "observe each step of the execution of the Turing machine on some input".  This lets you treat the FSM as a finite-state transducer and observe the output of the FSM for any desired sequence of inputs, by providing an appropriate input to the Turing machine.

If you don't know the number of states in the FSM, it's easy to prove that you can never know when you have the full thing (this is an easy adversary argument).


Algorithm to estimate the probability that a "0 and 1 matrix" fills up following the bootstrap percolation rules Presentation of the model: we consider the regular lattice created from $\mathbb{Z}^2$ (It's no more, no less a square lattice).

At $t=0$, each site is said "active" independently with a probability $p$, "inactive" otherwise.
At $t$, if a site is inactive, it becomes active if at least $2$ of its neighbours are active.

We call neighbour of $x$ each element of $V(x)=\{y\in\mathbb{Z}^2, ||x-y||=1\}$ (or, if I have a matrix M in python, a neighbour of $M[i][j]$ is $M[i\pm1][j]$ or $M[i][j\pm 1]$).

My problem: I consider a $n\times n$ matrix filled with 0s and 1s, (0 = inactive ; 1 = active), and I want to estimate the probability $p_c$ that a matrix, following the rules above, fills up (at $t\rightarrow \infty$, but this happen really fast in reality). The probability $p_c$ depend on $n$. I want to test it for $n=2$ to $n=100$ at least.

What I already have: I have a program, matrix_creation(n,p) that creates a $n\times n$  matrix with the probability $p$ for each coefficient to be 1, and another, test(M), to test if "M" fills up.

Here is a reasonably fast approach to estimate $p_c$. We will perform $N$ different trials, count the number of successes $M$, and estimate the result as $M/N \pm 1/\sqrt{N}$ (better estimates are possible if $p_c$ is close to 0 or to 1).

For each trial, you initialize an $N \times N$ matrix with the initial filling. You then go over the array, calculating the number of active neighbors of each non-filled point in the matrix, and whenever that number reaches 2, you put it in a stack. You then repeatedly pop elements from the stack, updating the matrix of active neighbors, and whenever that number reaches 2 for some non-filled point, you add it to the stack. When the stack is empty, the process is complete, and you can check whether all points have been activated.

There are many optimizations possible: for example, you can use an $(N+2)\times(N+2)$ matrix to help deal with border cases, you can keep track of the number of active points, and so on.

Using this naive approach, I managed to perform $10^6$ trials for $n = 100$, $p = 0.0535$ in about two minutes on my PC. The answer was $M/N \approx 0.5008$, so the critical probability is pretty close to $0.0535$.


Restricting capabilities of admin role in database schema Suppose I have to design database for learning management system. Which will going to have user having roles such as admin, teacher, tutor, student etc. In a system student can submit solution for an assignment in a course and teacher or tutor can provide the grade for it.

Now while implementing is it good idea to not allow admin of a database to not to change the grade of students for an assignment? I got this suggestion that as admin is superuser (user with all capabilities) he should be able to change the grade. So what should I do?  and why?

Generally, you cannot prevent administrators from making any change they want to the database.  Many administrator actions require privileges that give them a lot of control over the database.  For instance, if they can restore from backups (something that administrators often need to do), they can overwrite everything in the database.

Designing systems that will remain secure even when the system administrator is not trusted is very challenging, and for a learning management system, is probably more expensive than is worth it.

Therefore, there's probably no point in trying to restrict admin.  Don't forbid what you can't prevent.


how to express an intertemporal implication constraint in integer linear programming (ILP)? I want to express the following locigal expression in an IP:

$$x_{di} \wedge x_{d'j} \Rightarrow \sum_{\substack{d'' \in D\\ i < k <j}} x_{d''k} = \sum_{i<k<j} a_{k} \ \forall \ d, d' \in D, i,j \in T, i<j$$

where $x_{dt}$ is a binary decision variable ($x_{dt} \in \{0,1\}$) and $a_{k}$ is a binary parameter.

The meaning should be as follows: $T$ represents a set of timeslots. Whenever something happens at timeslots $i$ and $j$ (i.e. $x_{di} = 1$ for some $d$, $x_{d'j} = 1$ for some $d'$, $i<j$), then there should also something be happening at all timeslots inbetween $i$ and $j$, but only if at timeslot $t$ something can actually happen ($a_t = 1$, otherwise $a_t$ is $0$).

Can anyone tell me how to do this? Thanks in advance!

Base yourself on the fact that $x_{d,i} \land x_{d',j} $ happens iff $ x_{d,i} + x_{d',j} =2  $.

$\forall (d,d') \in D^2, \forall (i,j) \in T^2, i<j, \sum\limits_{d'' \in D \\ i<j<k} x_{d'',k} \leq \sum\limits_{i<j<k} a_k + (j-i)(2-x_{d,i} - x_{d',j}) $

$\forall (d,d') \in D^2, \forall (i,j) \in T^2, i<j, \sum\limits_{d'' \in D \\ i<j<k} x_{d'',k} \geq \sum\limits_{i<j<k} a_k + (j-i)(x_{d,i} + x_{d',j} - 2) $

Check these equations in two cases : $ x_{d,i} + x_{d',j} =2 $ and $ x_{d,i} + x_{d',j} < 2  $

Depending on your $a_k$ and problem, you may get a better multiplicative constant than $(j-i)$. If you can, do it, otherwise the continuous relaxation is going to suck.


Number of spanning arborescences with a specific root in a directed graph I am wondering how to calculate the number of spanning arborescences in a directed graph when a root is specified. For example:

where there are 5 spanning arborescences. Note that there is an edge from b2 to b3 and one from b3 to b2.
Angela Pretorius mentioned a method in Number of Spanning Arborescences, Mathematics, but there is no euclidean circuit in this example. It seems that he/she is referring to BEST theorem.

It seems that Kirchhoff's theorem can be used:

Kirchhoff's theorem can be modified to count the number of oriented spanning trees in directed multigraphs. The matrix Q is constructed as follows:
The entry i, j for distinct i and j equals −m, where m is the number of edges from i to j;
The entry i, i equals the indegree of i minus the number of loops at i.
The number of oriented spanning trees rooted at a vertex i is the determinant of the matrix gotten by removing the i-th row and column of Q.


How Types avoids Russel's Paradox? I gone through the Russel's paradox.

From Wikipedia :

  According to naive set theory, any definable collection is a set. Let R be the set of all sets that are not members of themselves. If R is not a member of itself, then its definition dictates that it must contain itself, and if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves.

Next Russell's and Alonzo Church developed type theory to avoid this paradox. Can someone explain clearly how these types (type theory) avoids this paradox. Thanks

There is a second solution to the conundrum, which is Quine's NF (New Foundations) set theory.

NF is a set theory that avoid the paradox, but a set of all sets does exist. NF avoids Russell's paradox by putting constraints on the what formulae are allowed in comprehension. In other words the predicate $\phi$ in

$$
   \{x\ |\ \phi(x)\}
$$

does not range over all predicates, but only over predicates that are "well-stratified". In particular, $true$ is well-stratified, so the universe

$$
   U = \{x\ |\ true\}
$$

is a set in NF. A first-order logic formula $\phi$ in the language of set-theory (i.e. $\in$ is the sole non-equality predicate) is well-stratified, provided there is a function

$$level : Vars \rightarrow \mathbb{N}$$

(Here $Vars$ is the set of all variables) such that the following holds.

For all sub-formulae $x \in y$ in $\phi$: $level(x) + 1 = level(y)$.
For all sub-formulae $x = y$ in $\phi$: $level(x)  = level(y)$.

In summary, while ZF(C) set-theory avoids Russell's paradox by prohibiting sets that are too big, NF avoids Russell's paradox by prohibiting sets that are too ugly.


Graph theory: BFS (Breadth First Search) - why is current processed first? I am referencing some code I found on GeeksForGeeks.com: Why is the current node printed (and processed) first before its children are processed? Wouldn't "breadth first" mean "Process children first, then process parent"? or, is that only for Trees? I can't be the only one to not understand this, so instead of flaming me, somebody please simply post the answer?

void Graph::DFSUtil(int v, bool visited[])
{
    visited[v] = true; <-- why is this printed FIRST?
    cout << v << " ";

    // Recur for all the vertices adjacent
    // to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}

// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function
    // to print DFS traversal
    DFSUtil(v, visited);
}

1) In answer to the semantic question "Wouldn't 'breadth first' mean 'Process children first, then process parent'?"

This question is a duplicate of the following: What is the meaning of 'breadth' in breadth first search?

2) In answer to the technical question "Why is the current node printed (and processed) first before its children are processed?":

BFS processes nodes in the following order: the starting vertex, then all the vertices at distance 1, then all the vertices at distance 2, etc. As pointed out by @user111398, you need to mark a node as visited before processing it or you will go on an infinite loop if the graph is cyclic. If you mark the parent but don't process it before (marking and) processing its children then you are processing the nodes in the following order: all the nodes at max distance, then all the nodes at max depth minus one, etc. This is reverse-BFS, not BFS.


Why every point is in exactly one pair in Well Separated Pair Decomposition(WSPD) In the Geometric Spanner Networks book by Giri Narasimhan and Michiel Smid Page 153 says

  Definition 9.1.3 (Well-Separated Pair Decomposition). Let $S$ be a set of $n$ points in $\mathbb R^d$, and let $s > 0$ be a real number. A well-separated pair decomposition (WSPD) for $S$, with respect to $s$, is a sequence

  $\{A_1, B_1\},\{A_2, B_2\}, \cdots , \{A_m, B_m\}$

  of pairs of nonempty subsets of $S$, for some integer $m$, such that

  for each $i$ with $1 \leq i \leq m, A_i$ and $B_i$ are well-separated with respect to $s$, and
  for any two distinct points $p$ and $q$ of $S$, there is exactly one index $i$ with $1 \leq i \leq m$, such that

  $p \in A_i$ and $q \in B_i$ or
  $p \in B_i$ and $q \in A_i$

Look at the following image

The points $x_1, x_2, x_3$ are given in the plane and the split tree is drawn. Suppose for some $s$ the WSPD is built as shown. In this way the well separated pairs are going to be

$
A_1 = \{x_1, x_2\}, B_1 = \{x_3 \}
$

$
A_2 = \{x_1\}, B_2 = \{x_2 \}
$

The $x_1,x_2$ together are well separated to $x_3$ and $x_1$ is well separated to $x_2$. As you see $x_1 \in A_1$ and $x_1 \in A_2$, so it is in more than one pair which contradicts the definition.

I would like to know what is the problem with my example and why every point is in exactly one pair in Well Separated Pair Decomposition?

Thanks in advance.

OK, I found it. The definition says

  for any two distinct points ...

It means I must consider two points, not a one solitary. $x_1$ is well separated with $x_3$, and it is well separated with $x_2$ as well, But there is exactly one pair that separates $x_3$ from $x_1$ and also there is exactly one pair that separates $x_2$ from $x_1$


How are programming languages and foundations of mathematics related? Basically I am aware of three foundations for math

Set theory
Type theory
Category theory

So in what ways are programming languages and foundations of mathematics related?

EDIT

The original question was "Programming languages based on foundations of math"

with the added paragarph of

And implementations of theory
1. Type theory in Coq
2. Set theory in SETL
3. Category theory in Haskell

Based on a suggestion this was changed to "How are programming languages and foundations of mathematics related"

Since this is one of those questions were I did not know enough about what I was asking but wanted to learn something, I am modifing the question to make it more valuable for learning and others, yet leaving the details in so as not to make the current answer by Andrej Bauer seem off topic.

Thanks for all the comments and the answer so far, I am learning from them.

[Note: this paragraphs is now outdated.] The title of your question contains an unwarranted assumption, namely that programming languages are "based on foundations of mathematics". This is generally not the case, although the two areas do have important relationships. A more accurate statement would be that (some) programming languages were designed using foundational techniques. A better question to ask would be "how are programming languages and foundations of mathematics related?"

The most general connection is embodied in the slogan proofs-as-programs, which can be made to work in several ways. The Curry-Howard correspondence is the most obvious one. With it we relate at once type theory, logic, and programming. But it should be emphasize that the Curry-Howard correspondence does not work very well in the presence of general recursion (because every type becomes inhabited), which every general-purpose programming language supports.

A subtler way of making the slogan proofs-as-programs work is to use realizability. Here too we relate proofs and programs, but now the direction goes from proofs to programs: every proof gives a program, but not every program is necessarily a proof.

The main example of a programming language based on a foundation is Agda, which simply is an implementation of dependent type theory. However, Agda is not a general-purpose programming language because it does not support general recursion. Every function in Agda is total, and there are computable functions which cannot be implemented in Agda. In practice programmers won't notice this, but they will notice that Agda does not allow undefined values, for example infinite loops.

Coq is not a programming language but rather a proof assistant. However, it too has extraction capabilities which give programs from proofs. Proof assistants and programming languages should not be confused with each other.

We should not forget that prolog and other logic programming languages take their inspiration from the idea that computation is proof search. This of course relates them closely to logic.

Haskell is a general-purpose programming language which is based on domain theory. That is to say, its semantics is domain-theoretic because it has to account for partial functions and recursion. The Haskell community has developed a number of techniques inspired by category theory, of which monads are best known but should not be confused with monads. More generally, advanced programming features are usually treated with a combination of domain theory and category theory, but this is not something that the Haskell programmer in the street is adept at. The so-called "syntactic category" of Haskell types is a lay man's view of how Haskell and category theory correspond to each other.

Set theory (classical or constructive) seems to inspire ideas in programming language to a lesser extent. Of course, constructive set theory has its connection to programming through constructive logic. One important application of intuitionistic set theory to programming languages was given by Alex Simpson who used it to make synthetic domain theory work. But this is quite advanced stuff, maybe see these slides. Jean-Louis Krivine has developed a very interesting brand of realizability for classical set theory. This seems a good way to relate classical set theory and programming.

In summary, the theory of programming languages uses foundational techniques. This is not surprising, as we consider computation to be a fundamental concept. But it is too naive to say that programming languages are "based" on a certain foundations. In fact, the trichotomy of foundations "set theory -- type theory -- category theory" is again just a useful high-level observation that can be made mathematically precise in various ways, but there is nothing necessary about it. It is a historic accident.


How do I find the max and min value of an array in 3n/2−2 comparisons? So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers or a single number.

What I'm trying to do now is the same thing but I'm trying to come up with a method that will always use 3n/2−2 comparisons. The method above doesn't use 3n/2−2 comparisons each time. So I just want to visualize how this is done on an array before I start to programming the method.

Imagine having a tournament made of the array elements. Group the array elements into pairs, then compare each pair. Put the larger numbers into one group and the smallers number into another group. The maximum value of the original array must be the max of the larger group and the minimum value of the original array must be the min of the smaller group. Initially, you do n/2 comparisons to make the split, and from there you need to find the max and min of two groups of n/2 elements each, which can be done with a total of n/2 - 1 comparisons per group. Overall, this is 3n / 2 - 2 compares.

... assuming, of course, you have an even total number of elements. Think about what happens if that isn't the case.


If a problem is "not semi-decidable" and "not decidable" can we say it is "undecidable"? I was under impression that when a Language (or problem) is not semi-decidable and not decidable then we can say it's undecidable and I think it makes sense also based on diagram.

However, in my assignment the TA struck out "undecidable" and wrote "not semi-decidable". Why is "undecidable" wrong if it's both not semi-decidable and not decidable?

Undecidable isn't wrong: "undecidable" means exactly the same thing as "not decidable". However, your TA is saying that you can make the strictly stronger statement that the set is not even semi-decidable.  This implies that it's undecidable, but isn't implied by "it is undecidable".

Suppose you were, instead in a biology class. You wrote "This is not a lizard" and your TA crossed it out and wrote "This is not any kind of reptile." You're both right, but your TA's version has more information in it.


Why hasn't functional programming researched dynamic trees? Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging dictionaries ("A Simple Mergeable Dictionary" by Adam Karczmarz),

By dynamic trees I refer to the definition stated in Sleator & Tarjan's paper "A data structure for dynamic trees" in 1983. Few efforts have been published within the functional programming research area since.

Edward Kmett implemented a version of the ST trees mostly as a translation of the C++ counterpart, see Link-cut trees.
Chris Okasaki wrote a limited implementation of the Splay trees in his renowned book "Purely functional data structures".
Ralf Hinze and Ross Paterson introduced a functional data structure called 2-3 finger trees but with somewhat different aim from that of original definition of dynamic trees.

Implementation (and perhaps performance) of dynamic trees are divided according to three approaches:

Linearization, where ET trees (Euler tour) play a great role. Not found a purely functional study.
Path-decomposition, where ST trees are the flagship, just found the Kmett's version.
Tree contraction, where Top trees, topology trees and RC trees are the players. Not found a purely functional study.

Purely functional analysis and implementation can be found on Splay, AVL, red-black tree, but those are NOT dynamic trees. The former are considered the shadow (also called virtual or auxiliary) data structure of the latter.

So, my question is:

What are the reasons (drawbacks, weaknesses) for the Functional Programming research community not to take part into the dynamic trees data structure?

"In computer science, functional programming is a programming paradigm.  A style of building the structure and elements of computer programs that treats computation as the evaluation of mathematical functions and avoids changing state and mutable data." - Wikipedia

"changing state and mutable data"  in other words "dynamic".

So your question is a bit like asking why left isn't right.


Is Semantic Preservation Soundness (or Correctness) or Completeness When transforming terms from one language to another, the intuitively desired property is the preservation of semantics (as used e.g. here for a CPS transformatation):

$$ s \Downarrow v \implies c(s) \Downarrow c(v) $$

I am a little troubled, however, by reconciling this with the classical terms correctness (or soundness) and completeness of logic systems. Usually, I would consider the above statement the completeness property of $c$ (and the converse the definition of correctness).

Intuitively, however, a compiler should be correct rather than complete (as e.g. type-checking often rules out correct programs). The converse of the statement above is only true if $c$ is injective:
If the source language contains for instance booleans and operations on them and the compilation replaces them via Church-encoding, the target language can evaluate boolean operations on terms compiled from boolean literals and lambda-abstractions, which the source language cannot evaluate.

Am I right to assume, that the above statement is the completeness property of $c$ (so the intuitive requirement actually has a counter-intuitive name)?
Am I also right in my conclusion that a non-injective compiler then is usually not correct?

This is really a question about the notion of operational correspondence.

The paper Towards a Unified Approach to Encodability and
Separation Results for Process Calculi by Daniele Gorla (http://wwwusers.di.uniroma1.it/~gorla/papers/G-CONCUR08.pdf) is concerned with correctness criteria for translations between process calculi.

In his work, Gorla introduces a notion of behavioural equivalence; I will leave it out here in order not to complicate the explanation overly.

Let $[ \! [ \; ] \! ]$ be an encoding, let $\rightarrow_1$ be the transition relation defined for the source language and let $\rightarrow_2$ be the transition relation defined for the target language. If we have that

If $S \rightarrow_1 S'$ then $[ \! [ S ] \! ] \rightarrow^*_2 [ \! [ S' ] \! ]$, we say that the encoding is complete
If $[ \! [ S ] \! ] \rightarrow^*_2 T$, then there exists a $S'$ such that $S \rightarrow^*_1 S'$ and $T \rightarrow^*_2 [ \! [ S' ] \! ]$, we say that the encoding is sound.

So yes, the notion mentioned in the questions is indeed that of completeness. The notion of soundness is shaped by the fact that the target language will often be richer than the target language or contain syntactic constructs whose behaviour does not correspond to anything in the source language. This explains why we speak of the intermediate configuration $T$ in the definition instead of requiring injectivity.


Pumping lemma problem - Choosing the right string to pump I have a problem finding the right string to pump for the following language:

$$L_1 = \{a^{p+q}b^rc^sd^{q+r}e^s \mid p, q, r, s \ge 0\}$$

Which string should I choose to pump? The problem is that I don't know how to handle the fact that I have $p+q$ and $q+r$?

Can I choose:
$$Z = a^{2n}b^nc^nd^{2n}e^s$$

Thanks in advance.

If $k$ is the pump length from the regular pumping lemma choose $w=c^ke^k$. Clearly, $w\in L_1$, but if you pump you have to change the number of $c$'s while leaving the $e$'s unaltered. Hence after pumping the word is no longer a member of $L_1$.


Why does left recursion have to be eliminated? For example,

Let the Grammar be:

S->Sa|B

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

What's wrong with this?

Why is right recursion a solution to the problem?

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

I am assuming that you are talking about context free grammars.

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

What do you mean by a problem?

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


Self-balancing binary search tree optimized for insertion I've written a "quiz" that prompts the user for comparisons between two items of subjective value, and once the position of all of the items is determined, displays an ordered list from most valuable to least.  The number of items is fixed.  The current implementation can be seen at https://dfdx.us/core-values-quiz/.

What matters most is minimizing the number of comparisons the user needs to input, or, more accurately, minimizing the amount of time the user requires to make each comparison times the number of comparisons.

Currently I offer two sorting methods: Quicksort and insertion into a binary tree.  Compared to a self-balancing BST, Quicksort will always require more comparisons, but because each consecutive comparison is against a single item (the partition item), the brain doesn't need to make much of a context switch and can answer the questions quicker.  The binary search tree will present fewer questions that take longer.  I let the user decide which method they want to use, given the pros and cons of each.

Since the comparisons required to rebalance the tree are handled by the computer, and not the user, those comparisons don't need to be optimized at all, only the number of comparisons required to determine the relative position within the current tree.  I believe this optimization is equivalent to, between each item's insertion, balancing the tree as perfectly as possible.  That is, requiring the strictest balancing constraint.

The best algorithm I've tested is the AVL tree.  While the AVL tree is pretty terrible for insertion/deletion times for most applications, it has a decent balancing constraint which results in great look-up speeds.  The rebalancing between each insertion/deletion is what makes it unperformant, but since, compared to human input, those comparisons are negligible, it is very good for my situation.

My situation requires one more constraint: the user must never be presented with the same comparison twice.  For the AVL tree, rebalancing breaks this constraint, so I've just memoized all of the user's answers in a dictionary.  I can't imagine a situation in which this case couldn't be handled with that memoziation, but I figured I'd mention it nonetheless.

I really have two questions:

Am I right with my assertion that balancing the tree as perfectly as possible guarantees the fewest number of prompts to the user?
Is there a better balancing algorithm than an AVL tree?

Given that before the quiz begins, the items' order is randomized, even using a non-auto-balancing BST should result in a roughly balanced tree.  I could see an argument being made that perfectly rebalancing after every insertion could actually produce a greater number of prompts, since each one will have as close to lg(n) prompts as possible; a slightly less balanced tree could potentially have a few "lucky" insertions that require a few less than lg(n), and a few "unlucky" insertions that require more, but that the lucky ones will, on average, outweigh the unlucky ones.  (I hope that made sense.)

I realized, considering that memory and processing constraints are negligible in my situation, that it is trivial to produce a new, perfectly balanced tree from an in-order traversal of the unbalanced tree, where perfectly balanced means that the max depth of a leaf node is at most one more than the minimum depth of a leaf node.

For that matter, a tree isn't even necessary.  Using a binary search over an ordered array to determine where to insert each new element is more efficient than using a binary search tree at all.  Given that my input set is a fixed 58 items, using JavaScript's Array.prototype.splice() function is more than performant enough, and makes the code trivial, as well.


Comparison using only bitwise operators (and return -1 or 0) I have to use only bitwise operators to compare two numbers (represented in two's complement), and return $-1$ (represented by all $1$'s) if the numbers aren't equal or return $0$ (represented by all $0$'s) otherwise.

Say $a$ and $b$ are $W$ bits long ($W$ is not necessarily $2^n$). I find it easy to find out if both numbers are equal using $\mathsf{XOR}$: just do it like $a\ \mathsf{XOR} \ b$ and I will obtain $0$ (all $0$'s) if the two are the same. However I stuck at trying to get $-1$ when the two numbers differ, since the result of $\mathsf{XOR}$ just says which position of the two numbers differ and I have no idea how I should turn a non-zero number into $-1$.

How can I convert a non-zero number into $-1$ in two's complement representation (all bits set to $1$), while keeping it $0$ when it's not non-zero, which is a step further for the simple $\mathsf{XOR}$ comparison?

Edit: In the situation this question was originated from, subtraction was not a native operator which could be directly used. The 5-operation solution from @Evil and the answer from @D.W. should also be perfectly right when an extended collection of operators, like the subtraction, were implemented.

The first step is to take $c = a \text{ XOR } b$, this will return $0$ if the numbers were equal or some bits set to $1$ otherwise. Now to calculate the result the $c$ variable should be ORed with its circular shifts, to propagate $1$ on the whole variable.

$c = c \text{ OR }  (c \text{ ROL } 1)$
$c = c \text{ OR } (c \text{ ROL } 2)$
$c = c \text{ OR } (c \text{ ROL } 4)$
$\dots$
$c = c \text{ OR } (c \text{ ROL }(W / 2))$.

Using consecutive powers of two gives exactly $\log_2 n$ ROLs needed (credit for Extrarius, it works when you store the partial results back to $c$).


Does interpreter for language L1 have to be written in lower level language L0? While reading A.S. Tanenbaum's book "Structured Computer Organization", I had come to this paragraph. The text is about how interpretation of a program works.

  The other technique is to write a program in L0 that takes programs in L1 as input data and carries them out by examining each instruction in turn and executing the equivalent sequence of L0 instructions directly. This technique does not require first generating a new program in L0. It is called interpretation and the program that carries it out is called an interpreter.ote

My question is; does this program have to be written in L0 Language, by means of lower level language?
Can this program(interpreter) be written in L1 language and have its output to be L0 language?

I think the implication of your Tanenbaum quote is that there is no compiler for L1.  In which case yes, the interpreter does have to be written in another language (how else would you run the interpreter?).[1]  It doesn't have to be lower-level; you could write an interpreter for Haskell in ML, say, or vice-versa.  You usually want to use a lower-level language, though, since interpretation is going to impose an order of magnitude speed (and size) overhead you need to win back in the speed of your interpreter for the language to be competitive.

In general, no.  You can write an interpreter for any language L1 in L1, provided you also write a compiler for L1.  Lisps are traditionally bootstrapped by: write an interpreter (a) for Lisp in some other language, then write a compiler (b) for Lisp in Lisp, executed by (a), then write an interpreter (c) for Lisp in Lisp, compiled by (b).  Now you have a Lisp interpreter written in Lisp.

Having said that, a program that takes a program in L1 and produces a program in L0 is a compiler; it compiles to L0.  All compilers compile to some other language[2] which in turn may be compiled some number of additional times, and then is interpreted either by hardware or by another program.

[1] Again, there are techniques for bootstrapping interpreters interpreted by themselves, but they all involve hand-written code in another language (or in the same language but compiled) and are a bit beyond this level.

[2] This is an over-simplification; optimization passes can be written as 'compilers' that compile to their source language and there are other uses for compilers that compile to the same language as the input.  But for your purposes, think of a compiler as compiling to a different language than the source.


Absorption rule in Boolean algebra I am confused regarding the absorption rule which states: A OR (A AND B) = A.

I do not completely understand how the expression simplifies to A and while i have seen proofs for this question, i still feel that i don't completely grasp it.

I will outline my working out below:

if expression = A OR (A AND B) then, according to the commutative rule we can rewrite this as (A OR A) AND B. (A OR A) simplifies to A. This means we should be left with A AND B. However, the expression simplifies to A which i don't understand.
Why is this the case?

One way to grasp it would be with concrete examples.

So an expression like:

"is a man" OR "is a man with a sister" (i.e. A = is a man and B = has a sister)

In this expression, if you're a man, it doesn't really matter whether you have a sister or not, you are to be counted.

or perhaps closer to a program, in an answer to "which words should we select?":

"words that start with W" OR "words that start with W and end with S"

You can see that the second condition identifies at most a subset of the first and is therefore redundant (and can safely be lopped off).

In code, you would simplify an expression like:

if s.startswith("W") or (s.startswith("W") and s.endswith("S"))

to

if s.startswith("W")

This might be why it's handy to know as a computer scientist. Conditional expressions have a tendency to become complex (and therefore difficult to reason about). Being able to simplify them safely is often a good refactoring move.

Another way to grasp it would be visually, with a Venn diagram with A and B overlapping circles. In that case, A AND B would be their intersection (the overlapping part) and the expression A OR (A AND B) would mean all points inside A or inside the intersection. Since the intersection is by definition all within A, specifying the (A AND B) intersection as an alternative is redundant.


Undecidability in the context of modern programming languages Imagine a program, executed by an interpreter to be a Turing Machine. Consider this code:

x = read_input
print x

Does undecidability mean that there may possibly be an input to this program such that the program may never halt?

Short answer: No.

Undecidability is a property of problems, not of programs. What is undecidable is however to check if some given program ever halts on any input. This problem has the program as input.

If you fix a program, then it may be decidable to check if the program halts for some input. This problem has the program input as input. In particular, for programs such as yours that always terminate, the termination problem is decidable, meaning there exists an algorithm for it: it just outputs "yes".

Note that the term "undecidability" only has a meaning in environments that allow arbitrary memory size and arbitrary input size. The Python language may fit to this definition, but the interpreter your are using certainly doesn't.


Is the runtime of binary search big omega of logarithm of n? My question is that can we say that runtime of the binary search is $\Omega(\log n)$?

I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst case. And for this reason the time complexity of binary search is $\Theta(\log n)$.

However, I still cannot interpret if it is also $\Omega(\log n)$ even if I think (and know that) it is. So, I just need some scientific explanation.

First, you can analyze the time complexity of binary search in whatever case you wish, say "best case" and "worst case". In the best case, you use $f(n)$ time, while in the worst case you use $g(n)$ time. These are two functions of $n$, describing two different scenarios you have defined. Now, you can make statements such as $f(n) = O(1)$ or $g(n) = \Theta(\log n)$. However, the Big Oh of a function has nothing to do with time complexity, it is merely something applied to a function that could just as well be representing the number of apples you get for $n$ euros.

In particular, thinking along the lines of "$O$ is always for best case, $\Omega$ is for the worst case" (or whatever), is wrong and dangerous.

To you specific question: if a function $g(n) = \Omega(\log n)$ and $g(n) = O(\log n)$, then $g(n) = \Theta(\log n)$. The function $g(n)$ might be representing the time complexity of binary search or the number of apples, it doesn't matter. And as always, look at the definitions and you can stop guessing.


What is the fastest to find just smallest prime number to a given number N where N can be as large as 10^18? During a programming contest I was asked to find just smallest prime number to given number N.
As Sieve cannot be used and brute force also doesn't work.

So, I was wondering is there any other faster implementation.

Here N -> (2, 10^18).

By fast primary testing you can test whether a given number is probably prime or not, actually methods like Miller Rabin are very fast and because we know the gap of size $O(\log n)$, between two consecutive primes, you can expect that when you start from $N$, you should visit few numbers by fast primarily testing, also, in most cases, fast primarily testing algorithms for the range you mentioned are correct.

In your case, because your numbers are bounded just few composite numbers can pass the miller rabin test which are:

2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321

You can see them in this list, So you just need to check the number that passed the Miller Rabin test, is in above list or not, and by using this code, is possible to do it in less than a second.


What does a square mean in a Boolean formula I am reading the paper Measuring the hardness of SAT instances by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF) and I would like to know what the square symbol in the following means

  Lemma 3 The space satisfies the following three properties:

  $s(\Gamma \cup \{\Box\})$ = 0
  For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
  For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\{x\}\to\{0,1\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.

  The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3

  $$s(\Gamma) = \min_{x, \overline{x}\in\Gamma, b\in\{0,1\}} \big\{
\max\{s([x\mapsto b](\Gamma))+1, s([x\mapsto\overline{b}](\Gamma))\}\;\big\}$$
  when $\Box\notin\Gamma$, and $s(\Gamma\cup\{\Box\}) = 0$.

  3 Note that, since $\Gamma$ is unsatisfiable, it either contains $\Box$ or it contains a variable with both signs.

Ran's comment is correct. This isn't standard notation in proof complexity (the relevant area of TCS), though it might be standard in SAT solving (the relevant applied area). It stands for the empty disjunction.

Semantically, the empty disjunction is the same as contradiction, but the former is a clause whereas the latter is a formula (or sometimes a constant). The usual symbol for contradiction is $\bot$, read bottom.


Flexible Team Orienteering Problem In Team Orienteering Problem (TOP) we have a graph $G=(V,E)$ and $K$ participants, We are supposed to find $K$ paths with total edge cost less than a threshold while maximising total vertex rewards. The constraint on reward collecting is once a reward has been collected by some participant the it can not be collected again by another participant. e.g. each vertex have only one piece of reward.

But given a graph like this, and two participants, where $s,t$ are the start and terminating points. I want to have two pieces of reward in $d$ but only one piece of reward in $b$ and $c$.

Does this problem has a name ? Is that proven to be NP-Complete ?

I don't know if it has a name but it's NP-hard. Just take $K=1$, give every edge and vertex weight $1$ and ask if there's a solution with vertex reward $|V|$ and edge cost at most $|V|-1$. This happens if, and only if, there's an $s$–$t$ Hamiltonian path.  The decision version "Can I get reward at least $R$ with cost at most $C$" is NP-complete.


Is undecidable(complement of R) a subset of NP-hard? Is there an undecidable problem which is not NP-hard?

If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$\neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.

We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.

The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s \in SAT$ iff $f_i(s) \notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s \in A$ iff $|s| \in K$.

By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n \in K$ (for $n \geq 2$) by taking a majority of three strings of length $n$.


Sequential numbers to unique-looking numbers I'm not sure how to word this because I'm not familiar with this, but I'm sure a process like this is rather common.

Basically, I've got members signing up for our website, and each one is assigned a normal sequential ID (a MySQL auto_increment ID), i.e. 1, 2, 3, ....

The client wants these users to have a "member number" -- something around 8 digits long. It doesn't matter if the algorithm is predictable, I just want to generate an 8-digit number that I know won't repeat and isn't totally obvious that it's sequential, e.g. I don't want to use 10000001, 10000002, 10000003....

Is there a simple algorithm for generating "member numbers" in a case like this? Like I said, I don't care if it's reverse-engineerable, just as long as I know it will always be unique.

For instance, I considered just taking a hash and truncating it, e.g. md5(1), md5(2), md5(3)` in base 10 and taking the first 8 characters -- but there's always a chance of conflict, where two IDs produce a similar hash.

Any thoughts?

Not sure what you mean by "totally obvious". Technically, every permutation of $\{1,\dots,10^8\}$ would work here.
You can randomly generate such a permutation, store it in an array, and use this array as an index.
If you want a specific example, which may look at first glance non-sequential, take some big number $p$ such that $\gcd(p,10^8)=1$ (e.g. $p= 19683$), then the id of user $i$ will be $i \cdot p \pmod{10^8}$. This is guaranteed to be unique for each user (up to $10^8$ users).
It may look random only at a glance, but anyone who takes enough time can figure out this is not random.


Communication allowed in the NC^i model? I want to verify if I am correct in my interpretation of the $\mathrm{NC}^i$ model.

In this model the input is given to at most $O(n^k)$ processors and each processor takes at most $O(\log^i n)$ time to arrive at a solution.

Can the processors communicate on any intermediate data?

How is the result whether accept or reject announced?

A fine grained problem

So the output of the algorithm can depend on partial results computed on previous processors?

There are $O(n^k)$ processors. So even if each processor computes $1$ bit of intermediate data that is useful for all processors then reading the intermediate results will itself take $\Omega(n^k)$ time then there is no way processors can finish in $O(\log^in)$ time.

So what limitations are there in the length and dependency on intermediate results?

The model of parallel computing used in the definition of Nick's class is PRAM (see this wiki page, note: particular policy for handling read/write conflicts is irrelevant for Nick's class). In this model, the processors share memory and a common clock, but are otherwise independent. Therefore, any communication that happens between processors uses memory as the channel. The result of the computation can be announced in some pre specified register.

Edit:

Note there are a couple ambiguities in your statements: to show that a problem belongs to $\mathrm{NC}^i$ you can choose $k$ (the power in your polynomial number of processors) depending on the particular problem, while $i$ is fixed. Also, all the quantities should only be specified up to a constant, e.g. $O(\log^i n)$ time and $O(n^k)$ processors.


Halting (on empty input tape) for an infinite subset of all Turing machines As is well known, there is no single procedure for deciding whether any given Turing machine halts on an empty input tape. This is easily shown, e. g., by applying Rice's theorem.
But what if, instead of considering the entire set of Turing machines, we only focus on a subset thereof? Clearly, if the subset is finite, the problem is decidable. But if the subset is infinite, is there an easy way to prove its undecidability?
Take, e.g., the following decision problem (let's call it EVEN):
EVEN = determine whether any given Turing machine with an even index halts on an empty input tape.
(Just to be clear about quantifiers, I mean: does there exist a procedure that is able, for any given Turing machine with an even index, to decide whether that machine halts on an empty input tape?)
In this case, the considered set of Turing machines is infinite, but Rice's theorem is no longer applicable (a.f.a.i.k.) and even a diagonalization argument does not seem to be conclusive, since you may end up with a function with an odd index, so self-reference is lost.
So my questions are:

is EVEN undecidable? How can you prove its undecidability?
what about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? would this problem still be undecidable or does that depend on the subset?

Regarding question 2, one could take the set of TMs that compute, say, f(x) = x, which certainly always halt; however, the set of indices of those TMs is not a recursive set, so the question seems ill-formulated.

is EVEN undecidable? How can you prove its undecidability?

It depends entirely on the enumeration that you use. E.g. one could make an enumeration that maps all Turing machines that halt with 1000 steps to an even index and all others to odd indices. Then EVEN is still an infinite set but decidable.
However a simple way to prove EVEN undecidable (assuming your enumeration is anything sane) is to show that for every Turing machine T there exists a machine T' that has an even index but identical behavior. You can do this by adding unreachable states, or useless extra transitions, etc, as long as it switches the parity of the enumeration.

What about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? Would this problem still be undecidable or does that depend on the subset?

Entirely depends on the subset. See the example above, "the set of all Turing machines that halt within 1000 steps" is infinite, and trivially decidable. Other examples could include any mapping from infinite families of functions that you know that halt to Turing machines. All you need is an injective mapping - you don't need to decide behavioral equivalence.


What is and amplification factor in pseudo-random generators? I can't seem to find an answer to this. For instance, I have this question:
Show that, if $P=NP$, there aren't any pseudo-random generators (even with amplification factor $n+1$).
My gut tells me this is because, in a world where $P=NP$, pretty much any process can be efficiently inverted so there aren't one-way functions (which pseudo-random generators rely on).

Amplification is equivalent to "stretch", the number of (seemingly) random bits that your algorithm generates given the truly random seed.
Let $G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a PRG that maps strings of length $n$ to strings of length $l(n)$, then $l(n)$ is said to be the stretch function of $G$. If $l(n)>n$ and $l$ is injective, then you have $\forall n :|Im(G)\cap\{0,1\}^n|\le 2^{n-1}$.  You can use this to construct a language $L\in NP$, such that $L\in P$ allows you to break $G$ (construct a distinguisher with success probability $\ge\frac{1}{2})$. Note that you can relax the injectivity requirement by ignoring some of the output (i.e. given a PRG with stretch $l(n)>n$, you can construct a PRG with stretch $l'(n)=n+1$).


A relational algebra extended to model the full DML ("CRUD") domain There are multiple references about the relational algebra for modeling queries (SELECT) but I have found very very little on the expanded algebra that would include concepts in all of DML such as INSERT, UPDATE, DELETE and maybe even MERGE, DECLARE, SET (as defined by MS SQL Server, whenever I must choose).  I'm looking for information about such an expanded algebra to help me reason about DML operations.

I assume that MS SQL Server, for example, must have some meta-domain model and/or type system that helps it validate SQL Scripts.  Here are a few of SQL SERVER 2008's SYS.MESSAGES (issued for scripted DML operations) that suggest to me violations of a type or domain-rule nature, not syntactic:

286 - The logical tables INSERTED and DELETED cannot be updated.
417 - TOP is not allowed in an UPDATE or DELETE statement against a partitioned view.
10729 - A nested INSERT, UPDATE, DELETE, or MERGE statement is not allowed in a SELECT statement that is not the immediate source of rows for an INSERT statement.
354 - The target '%.*ls' of the INSERT statement cannot be a view or common table expression when the FROM clause contains a nested INSERT, UPDATE, DELETE, or MERGE statement.
4005 - Cannot update columns from more than one underlying table in a single update call.

The database engine is compiling and analyzing the scripted commands it is given and emitting these messages in response to violations against its domain.

An engine executing this following statement isn't merely tacking on something trivial to the join of Table1 and Table2.  Beyond what it needed to SELECT, for the UPDATE it has to track more information throughout the statement such as the actual tables that ColB and ColC in the resulting join came from so that 1) it knows that they are from the same table (Error #4005) and 2) so it can actually write the results to somewhere permanent (not just a local transformation of the join):

UPDATE Table2
SET
    ColB = Table2.ColB + Table1.ColB,
    ColC = 3
FROM Table2
INNER JOIN Table1 ON Table2.ColA = Table1.ColA
WHERE Table1.ColX < 100

I've never used jOOQ, but the documentation suggests to me an uncommon level of sophistication/understanding compared to software with similar goals.  It apparently includes a fluent-style API for DML, and assuming that some of the library's value is in its ability to detect certain errors at compile-time, this suggests to me a decent domain model of DML.  Are jOOQ developers breaking ground with new and proprietary ways of understanding DML operations or is there published research into DML/CRUD types that they're implementing?  I'm so far overwhelmed trying to reverse-engineer the domain models from an implementation but I cannot find such a pure reference.

What is the domain model that is behind DML engines like SQL Server's script execution engine or softwares like the jOOQ library enabling them to understand/analyze DML scripts? For sql statements, relational algebra gives mathematical concepts of views, selections, projections, various joins, aggreggations, windowing, grouping, pivoting and each concept has type calculus that it dictates.  (Perhaps that a selection over a view yields a view of the same type with equal or fewer elements, that join takes two views and a join condition and yields a view of tupled elements, etc).  There are several implementations including Linq-To-SQL, Entity Framework which support (to varying degrees of competency) an alternate encoding and code translation of queries.  I assume that those softwares are grounded in the domain model of relational algebra.  But what would be the same basis for a library that supports full DML reasoning?

Thanks!

Excellent question, and since you referred to us ("jOOQ developers", which I am - working for the company behind jOOQ), I feel qualified to give a partial answer.

A bit of historic context first

Since the very beginning of software, there had been:

Theory (which is what "Computer Science", i.e. this Stack Exchange subsite is about)
Practice (more like Stack Overflow, i.e. "how can I get the compiler to stop barking at me")

The origins of set theory, relational algebra, and relational calculus were clearly on the theoretical side. Up to this day, popular RDBMS implementations have only managed to approximate this theory, mostly through SQL.

Although there had been competing languages before SQL was standardised mainly by Oracle and IBM, the power of SQL lay in the fact that it was a very practical language, which worked sufficiently well both for computer programs (e.g. written in COBOL, which was an equally practical language), software engineers, and most importantly: "other people", including analysts, project managers, and also managers. Everyone can quickly write up a SELECT * FROM person WHERE first_name = 'John' query. More theoretical languages like QUEL, which would have been closer to relational calculus, lacked the business vision that Oracle had.

Since then, SQL has emancipated from the outdated relational model and embraced a lot of alternative models, including procedural extensions (stored procedures), OLAP features, XML, JSON, etc. Not all of these enhancements were very well executed. To this day, the XML integration, for instance, is rather weak, poorly standardised and hard to grasp. I'm just speculating that the ANSI/ISO/IEC SQL standards committee and the w3c didn't work together closely enough to truly embed XQuery into SQL at the time. Unfortunately for w3c, as hardly anyone is using XQuery today, while everyone still uses SQL.

The historic irony here is that a lot of innovation came from academia, and I'd like to specifically mention Michael Stonebraker (Quel, Ingres, the original Postgres, Vertica, H-Store, and much more) who was recently awarded with the well-deserved turing award. Stonebraker has always been innovating into new areas. Most of the recent in-memory column store "hype" (also often referred to as "NewSQL") evolved around him. Stonebraker is a good example of the difference between academia and business. We've blogged about this some time ago here:

http://blog.jooq.org/2013/08/24/mit-prof-michael-stonebraker-the-traditional-rdbms-wisdom-is-all-wrong (very interesting talk by Stonebraker)
http://blog.jooq.org/2013/08/27/column-stores-teaching-an-old-elephant-new-tricks

When you hear the excellent talks by Oracle's Andrew Mendelsohn for instance, or other influencers from companies like Microsoft, SAP, IBM, you will notice that business has always embraced SQL for very good reasons, which were often not at all academic.

Context for your question

You have to differentiate between around four levels of abstraction:

Relational calculus
The SQL standard
The SQL Server specification
The SQL Server implementation

Your example is a particularly interesting one, because UPDATE .. SET .. FROM is not part of the latest SQL:2011 standard. To our knowledge, the UPDATE .. FROM clause is supported in at least:

SAP HANA
Ingres
Postgres
SQL Server
Sybase

Other databases allow for updating views, e.g.

UPDATE t1 JOIN t2 ON ... SET ...
UPDATE (SELECT * FROM t1 JOIN t2 ON ...) SET ...

In terms of Codd's Rules, the following two would apply:

  Rule 6: The view updating rule:

  All views that are theoretically updatable must be updatable by the system.

  Rule 7: High-level insert, update, and delete:

  The system must support set-at-a-time insert, update, and delete operators. This means that data can be retrieved from a relational database in sets constructed of data from multiple rows and/or multiple tables. This rule states that insert, update, and delete operations should be supported for any retrievable set rather than just for a single row in a single table.

So, Codd demands that an RDBMS can update views using sets, but he wouldn't want to specify how to actually do that (e.g. syntax-wise).

In fact, the concrete rules which apply to these kinds of statement are rather different from database to database. This has nothing to do with the SQL language, or with relational calculus per se, but simply with the individual implementations of each database - often also because of how the locking / concurrency model is implemented - something that is left open to implementations by both Codd's Rules as well as to some extent by the SQL standard. For instance, the standard does not explicitly refer to MVCC.

In the particular case of UPDATE .. FROM, think of it this way (assumptions only):

Some customer probably wanted to be able to write UPDATE statements that take into account more than one table
Some database vendor then implemented a "reasonable" syntax that fits into the general feeling of writing SQL
Some other database vendor then copied this syntax in order to provide migration paths, but "improved" on syntax and/or semantics
Yet another database vendor (probably IBM or Oracle) came up with yet another, much more powerful syntax for such use-cases, namely MERGE
As that database vendor has closer ties to the ANSI/ISO/IEC standards committee, and as this syntax was clearly more useful, MERGE now became a standard, and is now implemented in more and more RDBMS. To our knowledge in at least:

CUBRID
DB2
Firebird (upcoming 3.0 only)
HSQLDB
Informix
Oracle
SQL Server
Sybase SQL Anywhere

Answer to your questions

  Are jOOQ developers breaking ground with new and proprietary ways of understanding DML operations [...]?

We're not really breaking ground here. Before jOOQ, there had been many many SQL parsers and translators / migrators that allowed for standardising some vendor-specific SQL features. One example is Gudu Software's SQL Parser - the use case being migrating off DB2 towards Oracle, for instance.

What's new in jOOQ is that we introduced another "SQL dialect" implemented directly in Java, which mimicks a bit of the SQL standard and a bit of popular vendor-specific SQL dialects. Since jOOQ users explicitly create an Abstract Syntax Tree in their Java programs by using jOOQ API, jOOQ can easily perform a lot of SQL transformation internally in order to standardise the generated SQL output for all currently supported ~20 RDBMS, without the need to previously parse SQL statements (which is extremely hard). This extends to DML statements only to a certain degree, of course, as the underlying database implementation still needs to be able to process the semantics of a given statement.

What's also new (or at least different) in jOOQ is that unlike HQL, JPQL, LINQ, and many other abstractions, jOOQ is sticking to SQL instead of embedding also other concepts / domains like objects (ORMs) or XML/Collections (LINQ)

  Or is there published work on this?

jOOQ is not academic work. It evolved from real user needs over the past 6 years. We're following SQL here as we want to follow real business needs. We're not aware of third-party publications about jOOQ, although there had been a lot of similar papers about other, similar APIs in the past:

The World According to LINQ (and many other publications) by Erik Meijer
Embedded Typesafe Domain Specific Languages for Java by Jevgeni Kabanov and Rein Raudjärv
Database Queries in Java by Christopher Ming-Yee Iu (see also our article)

Embedding an external language like SQL in Java is rather easy, though. The basic technique is published in our article

The Java Fluent API Designer Crash Course

  I'm so far overwhelmed trying to reverse-engineer the domain models from an implementation.

So are we :-)

As you can see, SQL is a very real-world, pragmatic, sometimes (often) a bit ugly, vendor-specific (although well standardised), huge thing. The SQL:2011 standard's main document has almost 1500 pages, including DML (you can find some publicly available draft document versions here, for free). This doesn't even include extensions like XML, the INFORMATION_SCHEMA or other extensions.

Most people I've talked with in the past would agree that we really need something better than SQL. But the ugly truth is, there is nothing better than SQL right now, and even if there were, it would have to be backwards-compatible. There is no way that our whole industry will stop using the excellent and huge tool-chain that has been built around SQL. If "NoSQL" databases want to be successful these days, they build SQL-esque langauges (e.g. Cassandra with CQL, Couchbase with N1QL, Neo4j with Cypher). Oracle shows that SQL-on-Hadoop (BigDataSQL) is possible, and SAP's HANA completely bypassed NoSQL and implemented their number-crunching in-memory database directly on top of SQL.

The flip-side of this focus on practicality is that the academic quality of something like UPDATE .. FROM deteriorates to a point where you simply shrug and accept that this is merely a useful, perhaps a bit weird SQL statement.

TL;DR

If you want to understand the individual error messages that your SQL Server instance displays to you, then you're probably best off learning about SQL Server first. These concrete, real-world problems are so far away from the original theory ("Codd's Rules", "Tutorial D") that you'll be much better off bypassing the theory for these cases.


Determining the number of iterations needed to find the number of bits in an integer I'm trying to understand the complexity/number of iterations needed to determine the number of bits in an integer.
4 = 100  =  3 bits
3 = 011  =  2 bits
8 = 1000 =  4 bits

I skimmed through this article and it says: A positive integer n has b bits when 2^b-1 ≤ n ≤ 2^b – 1
But when you do the math for an integer 4, you get 2.32 ~= 2. What am I doing wrong?

The number of bits is always an integer, so you have to solve for that equation over the integers.  Thus, use $\lceil \lg (n+1) \rceil$.