# Tagged Questions

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

41 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 ...
22 views

### Split k sets to 2 groups of sets ,is this np hard? [duplicate]

Given k sets ,each contain several elements . I want to split them to two groups , the first group contains m sets ,the second group contain n sets , m + n = k . Let w1 be the sum of the weights of ...
590 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 ...
67 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 ...
36 views

38 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|\}$...
36 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 ...
317 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 ...
98 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 ...
115 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 ...
225 views

297 views

### Application of set theory subjects as ordinals, forcing, generic filters in software engineering

I am going to teach a course in set theory for software engineering students. I am going to talk in this course about: ordinal numbers, partial orders, well ordering, generic filters and maybe some ...
### What is the name of the property where $f(A) \supseteq f(B)$ when $A\supseteq B$?
Suppose I have a function $f$ on sets. What is the property of $f$ called when, for all sets $x$, $y$: $f(x)$ is a superset of $f(y)$ when $x$ is a superset of $y$ i.e. \forall x,y : x\...
What is the complement of $\mathrm{ACFG} = \{ G \mid G \text{ is a CFG and }L(G) = \Sigma^* \}$? I think it is $\mathrm{ECFG} = \{ G \mid G\text{ is a CFG and }L(G) = \emptyset \}$. It makes sense ...