Questions tagged [sets]

Questions about finite and infinite sets and multisets, related data structures and concepts.

3
votes
1answer
78 views

Find all items which are subsets of an item

I have a problem that I think should have been studied. I am looking for algorithms for it. Each item is a set of key-value pairs. Let $x$ be an item and $F$ be a set of items. Each key and each ...
7
votes
0answers
148 views

Overlap Maximization problem

Here's the problem: I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
1
vote
1answer
438 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?
17
votes
4answers
7k 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 ...
10
votes
1answer
688 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 space-...
6
votes
2answers
143 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
81 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)^*$
4
votes
2answers
11k 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 ...
3
votes
1answer
318 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?
4
votes
1answer
623 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: ...
5
votes
1answer
172 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 $...
1
vote
1answer
2k 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 ...
11
votes
4answers
231 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 ...
9
votes
3answers
12k 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
1k views

Cantor's diagonal method in simple terms?

Could anyone please explain Cantor's diagonalization principle in simple terms?
3
votes
1answer
145 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 $A$ ...
4
votes
1answer
217 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)$ ...
19
votes
1answer
373 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 ...
15
votes
4answers
6k views

Given a set of sets, find the smallest set(s) containing at least one element from each set

Given a set $\mathbf{S}$ of sets, I’d like to find a set $M$ such that every set $S$ in $\mathbf{S}$ contains at least one element of $M$. I’d also like $M$ to contain as few elements as possible ...
5
votes
1answer
2k 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 ...