I think the crucial bit is that part about union elimination needing to happen in the context. That's a dissymmetry with intersection, which can use a subtyping presentation with the usual rule $\dfrac{x : T \quad T \le T'}{x : T'}$
That question popped into my head suddenly, when I thought intersection types are a classic object of study and union types rarely come up, and why would that be when they should be dual in some way
I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is provided here)?
Input: A directed and finite graph G, with v and u as vertices
Question: Does a p...
There are many ways to define the Kolmogorov-Complexity, and usually, all these definitions they are equivalent up to an additive constant. That is if $K_1$ and $K_2$ are kolmogorov complexity functions (defined via different languages or models), then there exists a constant $c$ such that for ev...
The live refresh feature doesn't take MathJax into account. Here's a screenshot of the Mathematics after clicking on “$n$ questions with new activity”:
I saw the same effect on the CS private beta.
I'm running Chrome 17.0.963.65 (stable) on Linux.
We are now in the third day of private beta with a couple of questions. That is great.
However, most of questions here so far are about CS theory, which already have a full-grown site. The overlap is not a problem per se and is expected. However, if we continue this way, I fear that we could not...
I hereby propose to ban soft-question, as well as should it arise big-picture and any other similar meta-tag.
First, let me reiterate the main generic arguments in the blog post. These tags do not indicate the topic of the question, they indicate its breadth or depth. They cannot work as the sol...
Consider the following protocol:
The Client's "time" is skewed with an unknown constant $u$. Assume message travels from the Client to Server within $C_1$ time, and from Server to Client within $C_2$ time (and these constants don't change with time).
Initially, the Server sends an empty mess...
I am starting a personal bibliographic research on type-checking algorithms and want some tips. What are the most commonly used type-checking algorithms and strategies? Given some strongly static typed languages with complex typing systems like C++, Java 5+ or Scala, what are the type-checking al...
In computer networking and high-performance cluster computer design, network topology refers to the design of the way in which nodes are connected by links to form a communication network. Common network topologies include the mesh, torus, ring, star, tree, etc. These topologies can be studied an...
In database normalization, 1NF (no multivalued attributes), 2NF (all non-PK attributes depending only on PK attributes) and 3NF (all non-PK attributes depending on all of the PK attributes) are widely known. The 4NF (no part of the PK depending on other part of the PK) is less known, but still re...
@RanG only if you think it's wrong. Maybe my proof that it can't be done this way is wrong and it's preventing me from understanding how it can be done. The patent Raphael cites would be subject to the same objection, I think; I haven't yet had time to read it to understand how it claims to do the job.
Someone I know is planning on implementing a text editor in the near future, which prompted me to think about what kind of data structures are fast for a text editor. The most used structures are apparently ropes or gap buffers.
Van Emde Boas trees are just about the fastest priority queues arou...
Consider decision problems stated in some “reasonable” formal language. Let's say formulae in higher-order Peano arithmetic with one free variable as a frame of reference, but I'm equally interested in other models of computation: Diophantine equations, word problems from rewriting rules using Tu...
Which of the following statements is correct?
sufficient and necessary conditions about regularity of a language exist but not discovered yet.
There's no sufficient and necessary condition about regularity of a
language.
Pumping lemma is a necessary condition for non-regularit...
We know from this paper that the minimum number of clues to solve a valid sudoku puzzle is 17. Can all valid sudoku puzzles be specified in 17 clues? If not, what is the minimum number of clues that can completely specify every valid puzzle?
Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$:
$$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$
Which sets of integers can be the length set of a regular language?
Specifying any arbitrary 9x9 grid requires giving the position and value of each square. A naïve encoding for this might give 81 (x, y, value) triplets, requiring 4 bits for each x, y, and value (1-9 = 9 values = 4 bits) for a total of 81x4x3 = 972 bits. By numbering each square, one can reduce t...
Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $T$ and replace all pointers to $T'$ with pointers to $T$.
Give an algorithm that tak...
I get to the point where they've done a round trip in each direction, and then there seems to be a sign error: the text claims $\theta_A = \theta_B$, but if you perform the round trip in different directions, that should be $\theta_A = - \theta_B$, and the equations crumble away. Or am I being dense?
@Gilles sure, I just looked at the bits needed to store n digits, with n=17,18,.. and 5 was not bad I guess it is because log(9^5)/log(2)≈15.85 is close to 16. Sure, you can do it with grouping by 9 digits but it's not fun. (at maybe not a great idea for 17..22 clues)
@Gigili I don't understand what that can mean. Normally you have complete information, the problem is to extract what you want from that pile of information
I'm sure people have studied partial-information settings in a way that resembles decidability theory, but that would have other notions beyond decidable/undecidable
I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is provided here)?
Input: A directed and finite graph G, with v and u as vertices
Question: Does a p...
Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $T$ and replace all pointers to $T'$ with pointers to $T$.
Give an algorithm that tak...
