94
The counting principle that applies here is inclusion-exclusion.
$$ \left|X \cup Y\right| = \left|X\right| + \left|Y\right| - \left|X \cap Y \right|$$
To make the numbers work out, $\left|X \cap Y \right|$ must be 10000.
A Venn diagram may be more convincing to someone who may be intimidated by the notation.
62
Hint: The search x AND y will result in 10 000 hits.
38
The standard algorithm for finding a maximum still works. Start with $a_1$ and go over the elements, if you see a larger value, update the maximum to be that value. The reason this works is that every element you skipped is smaller than at least one element, and can thus not be the maximum.
To be clear, by the "standard algorithm" I mean the following:
max ...
33
To understand the difference between sets and types, ones has to go back to pre-mathematical ideas of "collection" and "construction", and see how sets and types mathematize these.
There is a spectrum of possibilities on what mathematics is about. Two of these are:
We think of mathematics as an activity in which mathematical objects are constructed ...
25
As Ariel notes, the standard maximum-finding algorithm given below:
def find_maximum(a):
m = a[0]
for x in a:
if x > m: m = x
return m
will in fact work without modification as long as:
any pair of elements can be compared, and
the input is guaranteed to contain a maximal element, i.e. an element that is pairwise greater than any ...
14
If each set maintains a record of what other sets exist, and you have a total of $s > 0$ sets, you can easily turn any data structure for a collection (e.g. binary search trees, etc.) into one where you can have retrieval of an element of the intersection of two sets in time $O(\log s)$.
Each set should have a unique identifier from some totally ordered ...
14
Sort T. Then take elements while T[i] >= i+1.
For example sorted(T)=[6,4,3,3,1,1]. Then, T[0] = 6 > 1, T[1] = 4 > 2, T[2] = 3 <= 3 and finally, T[3] = 3 < 4 so we have S = [T[0], T[1], T[2]].
13
This is a common misconception: complexity is not a measure of size. That is, it's not that "bigger" language are harder.
Intuitively, a language becomes harder when it's harder to describe it (TMs being a form of description). For example, as @Yuval Filmus points out in the comments, the language whose description is "everything" is very easy to decide.
...
13
Document 1: The cat is on the table
Document 2: My cat is black
Document 3: The dog is under the table
Document 4: What's the name of your cat?
Document 5: This is a black and white photo
Search for cat: returned documents are 1,2,4 (3 documents returned)
Search for black: returned documents are ...
Search for cat OR black: returned documents are ...
:-D :...
11
In brief, set theory is about membership while category theory is about structure-preserving transformations.
Set theory is only about membership (i.e. being an element) and what can be expressed in terms of that (e.g. being a subset). It does not concern itself with any other properties of elements or sets.
Category theory is a way to talk about how ...
10
Notice that $\mathsf{RE}$ is not closed under complementation. Therefore there exists an $A\in\mathsf{RE}$ such that $B=A^c\notin\mathsf{RE}$, while $A\cap B$ and $A\cup B$ are trivially recursively enumerable.
However, when $A\times B\in\mathsf{RE}$, there is a Turing machine $\mathcal{M}$ accepts $(x,y)$ iff $x\in A$ and $y\in B$. Therefore $\mathcal{M}(x,...
10
In practice, claiming that $x$ being of type $T$ usually is used to describe syntax, while claiming that $x$ is in set $S$ is usually used to indicate a semantic property. I will give some examples to clarify this difference in usage of types and sets. For the difference in what types and sets actually are, I refer to Andrej Bauer's answer.
An example
To ...
10
It's false. The $\lambda$-calculus arose through efforts to understand foundations of mathematics. Nowadays some people mistakenly equate foundations with set theory. The Stanford Encyclopaedia of Philosophy has a very good writeup on the $\lambda$-calculus, as well as its history, I recommend it.
9
If you are willing to store the sets in a specialized data-structure, then you can possibly get some interesting complexities.
Let $I=\mathcal O\left(\min\left(|A|,|B|,|A\Delta B|\right)\right)$
Then you can do set operations $A\cup B, A\cap B,A\setminus B$ and $A\Delta B$, each in $\mathcal O\left(I\cdot\log\frac{|A|+|B|}{I}\right)$ expected time. So ...
9
Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.
Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so ...
9
I see two possible points of confusion in your question, and I will address them separately.
What is meant by the title of your post: ""Regular languages over a common alphabet are closed under union."
"The union of $L_1,L_2$ is $\{x:x∈L_1∨x∈L_2\}$
Does this mean that, for any string $s∈L_1$, we also have $s∈L_2$?"
What is "Closure Under Union"?
Regular ...
9
To start, sets and types aren't even in the same arena. Sets are the objects of a first-order theory, such as ZFC set theory. While types are like overgrown sorts. To put it a different way, a set theory is a first-order theory within first-order logic. A type theory is an extension of logic itself. Martin-Löf Type Theory, for example, is not presented as a ...
8
I think that's called a laminar family.
8
Joe's answer is extremely good, and gives you all the important keywords.
You should be aware that succinct data structure research is still in an early stage, and many of the results are largely theoretical. Many of the proposed data structures are quite complex to implement, but most of the complexity is due to the fact that you need to maintain ...
8
Because regular languages are closed under complement and intersection, $L_2 - L_1$ is regular. Because it's also infinite, it contains words of arbitrarily large lengths.
Therefore, by the pumping lemma, there exist some words $x$, $y$, and $z$ such that the concatenation $x y^k z$ is in $L_2 - L_1$ for all $k \geq 0$.
Now consider the language $L'$ ...
8
From my comment originally: This is closely related to a quantity ubiquitous in academic productivity assessment, the Hirsh index, better known as the $h$-index. In short it is defined as the number of publications $h$ one has such that each of them has at least $h$ citations (the largest such $h$).
The only way your problem differs is that you would be ...
8
For each $i\in \mathbb{N}$, take $S_i = \mathbb{N}\setminus \{i\}$. You can now build any set you want as $X = \bigcap_{i\notin X}S_i$.
Similarly, an easier proof that a union of recursive sets can be anything at all is to let $T_i=\{i\}$ and now any set $X$ is $X = \bigcup_{i\in X}T_i$.
8
No, they're mostly notational variations. There are different connotations to the different notations, and different notations are common in different fields where they can mean quite different things. Also, sometimes they are used in a particular context for different (but usually related) things. You'll, of course, have to see how it has been defined in ...
8
The existential form of the axioms of set theory is convenient for the meta-theoretic explorations of set theory, such as forcing etc., where it is important to have a minimal language to worry about (only $\in$ relation). But even just stating the axioms of set theory without any constants and operation symbols is pretty haunting, see this gist of mine.
If ...
7
The exact meaning of "equivalent" isn't obvious but you have shown something deeper than the normal equivalence under reductions considered for NP-complete problems.
You've demonstrated what's known as a parsimonious reduction between the two problems. Ordinarily, reductions between NP-complete problems are many-one reductions: they only have the property ...
7
You can use the way that the recurrence formula below is derived to find your encoding:
$$ B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k. $$
This is proved by considering how many other elements are in the part containing the element $n+1$. If there are $n-k$ of these, then we have $\binom{n}{n-k} = \binom{n}{k}$ choices for them, and $B_k$ choices for ...
7
This is the Kleene plus. It stands for
$$ L^+ = \bigcup_{i \geq 1} L^i. $$
Here $L^i$ is the set of concatenations of $i$ words from $L$.
In words, $L^+$ consists of all concatenations of one or more words from $L$. A related operator is the Kleene star
$$ L^* = \bigcup_{i \geq 0} L^i, $$
which also allows the empty string ($L^0$).
For example, if $L = \{a\}...
7
Generically, these are sometimes called subset/containment dictionaries. The fact that you had partial matching in your question (but deleted it) is actually not a coincidence, because subset/containment queries and partial matching are equivalent problems for sets.
You probably want to use an UBTree (unlimited branching tree) for this; it's basically a ...
7
My view is that vernacular would consider that S is not empty,
i.e. $\emptyset \neq S\subseteq T$, while mathematical language would
consider that S can be empty, i.e. $\emptyset\subseteq S\subseteq T$.
Lay people do not speak of empty sets, while mathematicians are
aware of their role in their work.
That means that the sentence is not ambiguous, but the ...
7
It's countable. The set $S_\ell$ of strings of length $\ell$ is $\Sigma\times\dots\times\Sigma$, which is a finite product of countable sets, so is countable. Now, the set of all finite strings is $\bigcup_{\ell\geq 0}S_\ell$, which is a countable union of countable sets, which is countable.
Usually, you can only get an uncountable set from ...
Only top voted, non community-wiki answers of a minimum length are eligible
