The sets tag has no wiki summary.
1
vote
1answer
65 views
If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$
If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$.
Can anyone clarify what does this mean?
6
votes
4answers
184 views
Data Structure for Set Intersection?
Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated?
Init an empty set.
Add an ...
5
votes
1answer
68 views
What is a compact way to represent a partition of a set?
There exist efficient data
structures for representing set
partitions. These data structures have good time complexities for operations
like Union and Find, but they are not particularly ...
6
votes
2answers
84 views
Test if there are two subsets which cover a set
Given a set $S$ of $n$ elements, and a set $\mathcal{X}$ of $m$ subsets of $S$, decide if there exist $U,V \in \mathcal{X}$, s.t. $U \cup V = S$.
Brute force would take time $O(nm^2)$ but is there ...
2
votes
2answers
52 views
Regular language properties
For regular languages $R, S$ and $T$, which of the following are true?
$R \cup S = S \cup R$
$(R \cup S) \cdot T = RT \cup ST $
$R^* \cdot S^* = (R \cup S)^*$
3
votes
2answers
189 views
Finding the minimum subset of intervals covering the whole set
Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers and $a < b$. What is the most efficient algorithm to find the smallest subset $B \subseteq A$ such that, for any ...
2
votes
1answer
53 views
The use of multiset ordering in proving termination
Based on the definition of a multiset and the information in this paper, why do we use multisets in proving the termination of a program?
Is not the well-founded order enough?
3
votes
1answer
88 views
Algorithm for determining minimal set of covering prefixes
I have a set of strings. My goal is to find a minimal set of longest prefixes which will match most of that set.
For instance, if my set is:
...
4
votes
1answer
94 views
Finding containing sets in a set of sets
Suppose I have a set of sets of integers $A$, is there an efficient algorithm/data structure that will allow me to query for all sets of integers that include a given input set? That is, given input ...
0
votes
1answer
53 views
Multisets of a given set
A multiset is an unordered collection of elements where elements may repeat any
number of times. The size of a multiset is the number of elements in it counting
repetitions.
(a) What is the number of ...
10
votes
4answers
123 views
Finding “fingerprint” sets
Let's say we have 10 people, each with a list of favorite books. For a given person X, I would like to find a special subset of X's books liked only by X, i.e. there is no other person that likes all ...
3
votes
1answer
194 views
What is complement of Context-free languages?
I need to know what class of CFL is closed under i.e. what set is complement of CFL.
I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
3
votes
2answers
192 views
Cantor's diagonal method in simple terms?
Could anyone please explain Cantor's diagonalization principle in simple terms?
3
votes
1answer
92 views
Functions between sets?
I recently took a practice exam for the Computer Science GRE and this was one of the questions:
Assume that set $A$ has 5 elements and set $B$ has 4 elements, how many functions exist from set ...
3
votes
1answer
68 views
Computing the rank of a multiset after inserting another element
What is the procedure for computing the rank of a multiset after inserting an element?
For instance, lets say we have a set $S = (0,1)$ containing $n = 2$ distinct elements.
The multiset $M = (1,1)$ ...
7
votes
0answers
120 views
Problems for which algorithms based on partition refinement run faster than in loglinear time
Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement ...
4
votes
1answer
93 views
Data structure for partition of a set
A partition of a set S is a separation of the set into an arbitrary number of non-empty, pairwise disjoint subsets whose union is exactly S. What manner of a data structure should be used to represent ...
