# Questions tagged [sets]

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

285 questions
Filter by
Sorted by
Tagged with
247 views

### Set notation of the set of all strings

How do I present the complement using set notation? I guess it has to be shows with universal set - {aa,bb} but I do not know how to represent the universal set in ...
84 views

### What is an efficient way to calculate the biggest system of disjunct sets?

Let $I$ be a finite set of items and $\mathcal{M} = \{M | M \subseteq I\}$ be a set of subsets of $I$. The task is to find the biggest subset $\tilde{\mathcal{M}} \subseteq \mathcal{M}$ so that all ...
80 views

67 views

### The meaning of “set” in NP-complete problem

Garey and Johnson describe in their book many NP-complete problems which are based on sets, for example Hitting Set, Minimum Test Set, Set Packing, Set Splitting, and many more. The traditional ...
626 views

### Finding a fixed-size set whose members are contained by the largest number of other sets

I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to ...
88 views

### What kinds of problems are modeled by a recursive definition of a set of strings?

Given this definition: The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by: BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string) RECURSIVE ...
63 views

138 views

### Vertex-independent paths [duplicate]

Let $s$ and $t$ be 2 vertices (not adjacent) in graph $G$. Let $p_l(s,t;G)$ be the $maximum$ number of vertex-independent paths from $s$ to $t$ in graph $G$, of length $\le$ $l$ ($l \in \{1,...,|G|\}$...
96 views

### Regular language subsets [duplicate]

If $L_{1} \subseteq L_{2}$ and $L_{2}$ is regular, does it follow that $L_{1}$ is necessarily regular? I don't understand this question, is there any proof to show this or is there an assumption we ...
944 views

### Alternative to Bloom filter for extreme parameters

A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below). I am interested in a ...
4k views

### How to prove a set has infinite cardinality?

Set S is a set consisting of all string of one or more a or b such as "a, b, ab, ba, abb, bba..." and how to prove set S is a infinity set. I have tried proving set S as one to one corresponding to ...
793 views

### Algorithm for generating coprime number sequences?

Does anyone know of an algorithm to generate a set of numbers of size $N$ which are all co-prime to eachother? Ideally I'm looking for something that has random access abilities so i could ask for ...