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

learn more… | top users | synonyms

0
votes
1answer
17 views

Datalog - Single Step Operator

I am currently taking a class called Logic for Computer Scientist. During the first four weeks or so now we have been studying a concept Datalog with subsections Syntax and Formal Semantics and ...
0
votes
1answer
18 views

Partitioning a set to the maximum number of subsets summing to zero

Given a multiset of numbers $X = \{x_1, \dots, x_n\}$, such that $\sum X = 0$, how can $X$ be partitioned to the maximum number of subsets so that each subset sums to zero? I have searched around a ...
1
vote
1answer
62 views

Logic formula for exactly n unique objects (no more, no less)

I have a question in Logic: If I am asked to construct a formula, using the '=' predicate, that shows that there are exactly n objects, I need to show that there are no n+1 objects, right? For ...
3
votes
1answer
20 views

Why use minhash instead of directly computing Jaccard coefficient?

Minhash is said to estimate the Jaccard coefficient - supposedly because it's faster to compute. Given two sets $A$ and $B$, minhash (with k hash functions) takes $O(k*(|A|+|B|))$ time to compute. ...
4
votes
3answers
74 views

Data structure to store sphere points (latitude,longitude) and retrieve all points within a distance

I have a set of thousands~millions of points on a sphere's surface, each with latitude, longitude. I want to quickly get all points within a distance d of a ...
0
votes
2answers
188 views

Number of finite strings over a countably infinite alphabet

If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite?
4
votes
0answers
57 views

How to find a basic elements of a set?

I have a set of propositions, for example $\{a_1,a_2,\dots,a_n\}$. Some propositions depend on others (for example, $a_1,a_2\Rightarrow a_3$, means if $a_1,a_2$ are true, then $a_3$ is true). I want ...
3
votes
2answers
24 views

How do set partitions get mapped by restricted growth functions

I am reading Skiena but do not have a formal background in Computer Science. On page 457 he discusses generating set partitions via restricted growth functions. Here's specifically what he says: ...
2
votes
1answer
65 views

Find a regular language that is “infinitely between” two other regular languages

Suppose I have two regular languages $L_{1}$ and $L_{2}$ such that $L_{1} \subseteq L_{2}$ and $L_{2} - L_{1}$ is infinite. I want to find another regular language $L_{3}$ such that $L_{1} \subseteq ...
0
votes
0answers
36 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 ...
-2
votes
1answer
31 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 ...
5
votes
0answers
227 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 ...
2
votes
5answers
65 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 ...
1
vote
1answer
52 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 ...
3
votes
2answers
191 views

Efficiently finding $k$ smallest elements of Cartesian product

Given lists $A_1, A_2, \dots, A_n$ of non-negative numbers, I want to find the $k$ smallest elements of the Cartesian product $A_1 \times A_2 \times \dots \times A_n$ ordered by the value $x_1 + x_2 + ...
3
votes
3answers
92 views

Algorithm that finds concise representations of sets of pairs using Cartesian products

I feel like there should be a known algorithm to the following problem, but I am short of ideas how to construct or search for it. Suppose as an input you have a list of two-dimensional data points ...
3
votes
1answer
47 views

Data structure for optimal deduplication of common subsets

Consider a database with the following properties: It stores symbols (represented as 64-bit integers) and sets of symbols Sets may contain thousands of symbols, and there may be thousands of sets ...
1
vote
1answer
63 views

How can a set offer better search performance than an array

While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer ...
3
votes
1answer
76 views

Data structure for ordered counted set

Is there a name for a counted set (multiset) that is ordered? For example lets say this data structure represents a shopping cart (or basket if you're British). The shopping cart shows the order the ...
0
votes
1answer
53 views

Understanding the definition of endless sets

In a course on theoretical computer science we have to prove if sets are endless. I have two problems with the exercise: I don't understand exactly, what an endless set is (I find it very hard to ...
-1
votes
1answer
32 views

$k$-Multiset intersection efficient algorithm

Given a collection of sets $C= \{S_1,S_2,\cdots,S_n\}$ such that each set $S_i \in C$ is sorted and has at least $k$ elements. What is the most efficient algorithm for finding the intersection of ...
0
votes
0answers
136 views

What happens if the associativity level is greater than the cache size?

I am working on a computer organization caching problem The Problem: What happens if the associativity level is greater than the cache size? I know that associativity level is how many blocks are ...
0
votes
2answers
59 views

set complement and superset

If 'S is a set complement of S, then a set complement of a superset of S' is a subset of S. Just want to verify that above is true just based on the definition of ...
1
vote
1answer
49 views

Is the union of finite and infinite sequences over alphabet of length 1 countable?

Is the union of finite and countably infinite sequence over alphabet $\Sigma=\{1\}$, countably infinite as well? I understand this is similar a question to the one of finite and countably infinite ...
1
vote
0answers
101 views

Given an amount of sets with numbers, find a set of numbers not including any of the given

Given an amount of sets with numbers (0-20 e.g) , we are asked to find the maximum set of numbers from 0-20 that doesn't include any of the given sets(it can include numbers from a set,but not the ...
0
votes
1answer
38 views

How can I formalize key value stores with set theory?

I'm currently developing a simple key-value NoSQL store and want to build its formal model. I found article about key value formalisation with category theory, but I'm interested are there some works ...
2
votes
2answers
137 views

Does “contains only” imply “contains”?

Written in English, does "the set S contains only members of set T" imply that S does contain some member of set T? How would this relationship be written formally?
1
vote
1answer
64 views

Minimal Number of Fixed Size Sets to contain all Sets

My problem is very similar to the one posted here. Instead of finding one set covering the maximum of subsets, I need to find the minimal number of sets to cover all subsets. I have $U = \{1, 2, ..., ...
5
votes
2answers
244 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 ...
3
votes
1answer
251 views

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 : ...
1
vote
1answer
59 views

What is the complement of ACFG

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 ...
0
votes
2answers
17 views

Assistance with Notation in the Paper Entitled: “Search Through Systematic Set Enumeration”

So I'm reading "Search Through Systematic Set Enumeration" by Ron Rymon (currently available online for free. I'm having a problem with the notation in the following definition presented bellow: ...
4
votes
1answer
139 views

Data structure for a static set of sets

I have collection $U$ of sets, where each set is of size at most 95 (corresponding to each printable ASCII character). For example, $\{h,r,l,a\}$ is one set, and $U = \{\{h,r,l,a\}, \{l,e,d\}, ...
0
votes
1answer
57 views

If $A \cap B$ or $A \cup B$ or $A \times B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

Sets $A$ and $B$ are given but we don't know what kind of sets they are. If we know that $A \cap B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable? what ...
0
votes
1answer
58 views

Set Intersection with asymmetric set sizes

I'm looking for an algorithm to perform set intersection where set $N_1$ is very small and set $N_2$ is very large. Due to the constraints of the problem I am solving, I cannot rely on an algorithm ...
0
votes
1answer
42 views

Language intersections (set theory) - Understanding better

I've joined computer science classes at high school because I have a wide knowledge and a few years of experience in programming in multiple of languages, however I didn't fit in the requirements of ...
3
votes
1answer
68 views

Finding set of disjoint sets with additional value optimization

I've got a set $Q$ of pairs $[S, v]$ where $S$ is a nonempty set and $v$ is a value ($v \in \mathbb{N}_{+}$). I need to find a subset $R$ of $Q$ with following properties: Sum of all $v$'s is ...
1
vote
0answers
99 views

Show that every infinite recursive set has both a nonrecursive r.e. subset and a non-r.e. subset

My attempt to solve this: If $\mathcal{A}$ is an arbitrary infinite recursive set then the members of $\mathcal{A}$ can be ordered in ascending order. We can do bijection between $\mathcal{N}$ and ...
1
vote
0answers
29 views

How to find the accuracy of a set partitioning?

Suppose that there are $k$ sets $S_1, S_2, S_3, \dots, S_k$. The numbers $N = \{1, 2, \dots,n\}$ are distributed into these sets equally. Say that we partition $N$ into $m$ sets $P_1, P_2, \dots, ...
2
votes
1answer
122 views

Count-Min sketch: dyadic ranges

Can anyone give me a proof as to why Any range over a unviverse {1...n} can be reduced to at most $2log_2n$ disjoint dyadic ranges? Where a dyadic range is a range of the form ...
1
vote
0answers
47 views

Tradoff between space and false positive rate when using bloom filters

Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is ...
0
votes
2answers
75 views

find the optimal combination [closed]

Suppose I have these values with weights -- $$ x_1 = 2\\ x_2 = 4\\ x_3 = 5\\ $$ There is no negative or $0$ value. I need to find $2$ element subset with maximum value computed from a function ...
2
votes
1answer
43 views

How to apply “verification” and “decision” for the SUBSET SUM problem?

The SUBSET SUM problem states that: Given finite set S of integers, is there a subset whose sum is exactly t? Can someone show me why verification is simpler ...
1
vote
1answer
386 views

Minimize sum of squared error

I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to ...
3
votes
1answer
81 views

Count all possible unions in a collection of sets

Say we have a collections of sets $\mathcal X = \{X_1, \dots, X_n\}$ (not necessarily disjoint), and we want to count the number of possible unions of sets in $\mathcal X$, i.e. the size of ...
3
votes
1answer
93 views

Does any one know what this problem is called?

We are given finite sets $A$ and $B$ and a set $S\subseteq \mathcal{P}(A)$. The members of $\mathcal{S}$ may have arbitrary intersections with one another and their union is not necessarily $A$. ...
2
votes
0answers
123 views

Message protocol to probabilistically infer missing object from Union of two subsets of a larger set

This was a challenge problem I read some time ago and just remembered it: Say you have two people, $A$ and $B$, collect objects distinctly labeled $1,...,n$. They will each separately collect ...
1
vote
1answer
38 views

Find a collection of sets where each number from a given list is contained in a different set

I have a set of numbers S of cardinality N, and a collection of sets each containing some subset of S. The cardinality of each of these sets can be anywhere from 1 to N. The number of sets is ...
2
votes
1answer
449 views

compressing a set of binary strings with fixed length

I'm looking for a data structure / algorithm to store an unordered set S of binary strings of a fixed length n (i.e. all ...
3
votes
1answer
62 views

How can finite sets be represented as a type?

Manually self-migrated from stack overflow. A set of objects of a type T is often represented using its indicator function (set T = ...