Questions tagged [finite-sets]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
24 views

matching vector families that form a group

Is there any research/information on matching vector family sets (the U list or the V list or both) that form a group (under addition)? You can find the definition of MV families here: https://homes....
user avatar
3 votes
1 answer
55 views

Deciding whether a set of relations can be composed to the empty relation

Is there an efficient algorithm to solve the following decision problem? Given a finite set $S$ and a set of relations $\mathcal R$ from $S$ to $S$, determine whether there is any sequence of ...
user avatar
0 votes
2 answers
39 views

Is this the correct answer for the cardinality of this set?

This is a question from a practice quiz at my university. Is the question asking for the cardinality of Σ1 = {a,b} to the power of four? if that's the case, then the set would still have a ...
user avatar
  • 185
0 votes
1 answer
47 views

How to implement conditional probability distribution on set-valued Random Variables

I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing ...
user avatar
  • 1
4 votes
1 answer
86 views

Complexity of a decision problem: system of linear equations over finite field with restricted solutions

I have a system of linear equations over a finite field $\mathbb F_p \cong \mathbb Z_p$, and I'm interested in the decision problem of whether there exists a solution where all of the variables $x_i$ ...
user avatar
1 vote
1 answer
175 views

Union of every language within group of decidable languages is also decidable?

So I was trying to solve following exercise: Let $(L_{i})_{i \in \mathbb{N}}$ be a family of decidable languages - this means that every $L_{i}$ is decidable. Then $\cup_{i \in \mathbb{N}}L_{i} $ is ...
user avatar
  • 35
6 votes
2 answers
173 views

Spanning tree in a graph of intersecting sets

Consider $n$ sets, $X_i$, each having $n$ elements or fewer, drawn among a set of at most $m \gt n$ elements. In other words $$\forall i \in [1 \ldots n],~|X_i| \le n~\wedge~\left|\bigcup_{i=1}^n X_i\...
user avatar
  • 353
4 votes
2 answers
122 views

Regular language as finite union of periodic sets

Is it true that every regular language can be expressed as a finite union of periodic sets? In other words, if $L$ is regular, then do there exist finite sets $A_1,\dots,A_n,B_1,\dots,B_n$ such that ...
user avatar
  • 141k
1 vote
1 answer
54 views

Efficiently finding the intersections of sets that yield a desired set

Given a collection of sets $\{S_1, S_2, \dots, S_n\}$, find all the "reduced" intersections between those sets that yield the desired set $\{x\}$ as the result. A "reduced" intersection is defined as ...
user avatar
0 votes
2 answers
152 views

Efficiently computing minimal elements over partially ordered sets

I have a list of sets that I would like to sort into a partial order based on the subset relation. In fact, I do not require the complete ordering, only the minimal elements. If I am not mistaken, ...
user avatar
2 votes
1 answer
134 views

Quickly obtaining sums of sets of numbers

We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$. We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For ...
user avatar
3 votes
0 answers
67 views

Minimal regular expression from minimal NFA for finite language in polynomial time?

Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language? This question is based on a recent question regarding ...
user avatar
  • 12.6k
5 votes
0 answers
145 views

Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?

I have read that minimizing regular expressions is, in general, PSPACE-complete. Is it known whether minimizing regular expressions without the Kleene closure (star, asterisk) is in P? The language ...
user avatar
0 votes
1 answer
913 views

Find all subsets with a given sum

How to choose from a set of positive numbers all the subsets that sum to some number x? For example if the set $S=[1,1,2,3,4,5,6,7]$ and I'm searching for all the subsets that sum to $7$ I would have $...
user avatar
  • 3
1 vote
1 answer
1k views

What is the most efficient algorithm for creating a list of unique values from a list of pairs of value?

Background I have a list of 50 million $A-A_i$ pairs, where $i>1$, and $A$ and $A_i$ are some text. I need to extract the $A$ values from the list, so I get a new list of unique $A$ values.: $$ \...
user avatar
1 vote
1 answer
6k views

Understanding facts about regular languages, finite sets and subsets of regular languages

I am aware of following two facts related to two concepts: regular languages and finite sets: Regular languages are not closed under subset and proper subset operations. It is decidable ...
user avatar
  • 1,547
1 vote
2 answers
110 views

Get indexes of unique elements in two different arrays in linear time

I have two array of the same set of elements, say for exemple: $a_1 = [x_1, x_2, …, x_n]$ and $a_2 = [y_1, y_2, …, y_n]$ so that $i \neq j \Rightarrow x_i \neq x_j$ Is it possible, in linear time, to ...
user avatar
  • 7,091
0 votes
1 answer
129 views

Is this problem NP-complete?

Let there be a set of cardinality $n\in \mathbb{N}$. Let there also be $n$ subsets of that set. What is the smallest k such that union of some $n-k$ of those subsets is of cardinality at most $k$? The ...
user avatar
3 votes
1 answer
138 views

Compact mapping from an involuted set

Let $S$ be a set (say positive integers $\leq$ N) and $f$ an involution ($f$ is bijective, $f\cdot f=id$, e.g. xor with a constant). $g$ is a idempotent mapping choosing an arbitrary representative ...
user avatar
  • 133
1 vote
3 answers
635 views

What is the space in big-O notation of the minimal DFA accepting the intersection of two finite languages where their minimal DFAs are given

Given two minimal deterministic finite automatons called A and B where A accepts the finite language L(A) and B accepts the finite language L(B) and the alphabet of both languages and automatons are &...
user avatar
4 votes
1 answer
684 views

Finite languages are Turing decidable - contradiction [duplicate]

Let's say that I define the language $L$ over the alphabet $\{0, 1\}$ to be a language containing only one word, $w$, where: $$ w = \begin{cases} 1 & \text{if the continuum hypothesis is ...
user avatar
  • 143
2 votes
1 answer
49 views

Algorithm to get maximal selection set of a collection of sets with a binary relation

I have a finite collection of finite sets $\{A_i\}_{i \in I}$. There is a relation $R$ defined on the elements of those sets (which is not transitive, it is irreflexive, and it is symetric). Suppose ...
user avatar
  • 123
0 votes
2 answers
321 views

Intersection with a finite set

If we have a language $F$ and a regular language $D$ (a finite set) then can we say anything about the intersection of $D$ and $F$? Will the intersection of the languages be finite or regular? This ...
user avatar
10 votes
5 answers
2k views

Is there a known method for constructing a grammar given a finite set of finite strings?

From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around? If given n strings of m length, it should be possible ...
user avatar
1 vote
1 answer
172 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 ...
user avatar
  • 90
4 votes
1 answer
113 views

How many words are in this sets?

I have problems to determine the size of the following sets in dependancy of the parameters $m, n>0$: $$M_{m,n}=\{a^iwa^{m-i}\mid 0\le i \le m,\;w\in\{a,b\}^n\}$$ It is easy to see that $|M_{m,n}|\...
user avatar
  • 994
5 votes
2 answers
187 views

Finding the k-th smallest rational number efficiently

Consider the following set: $S := \left\{\frac{a}{b} \colon a \in \{1,\ldots,A\}, b \in \{1,\ldots,B\} \right\}$ $S$ is the set of all rational numbers that can be represented by two integers $a$ ...
user avatar
0 votes
1 answer
85 views

Lower bound the difference between distinct values of a function over a discrete domain?

I have a function $f: X \to \mathbb{R}$ where the domain $X$ is a (small) discrete set, such as $X = \mathbb{Z}^d \cap [-10,10]^d$ (i.e., the set of $d$-dimensional integer vectors all of whose ...
user avatar
  • 419
6 votes
1 answer
898 views

Computing the complement of a set

Suppose I have a set $A$ of elements in $\{1, \ldots, n\}$, given as an unordered list. I would like to compute the complement of $A$, i.e., I would like to produce an unordered list of entries in $\{...
user avatar
0 votes
1 answer
436 views

If $L^*$ or $L^+$ is empty, can L be an infinite language?

I have to prove or disprove the implications in these two situations $L^* = \emptyset$ $\rightarrow$ $L$ is infinite $L^+ = \emptyset$ $\rightarrow$ $L$ is infinite Here are my thoughts. I would ...
user avatar
2 votes
0 answers
63 views

Approximate target subset by intersecting other subsets

Let $S$ be a finite set of integers (this set contains about 200000 elements). Let $T \subset S$ be a particular subset of $S$ called target. $S$ keeps growing. So does $T$. Each new element of $S$ ...
user avatar
3 votes
2 answers
334 views

Given many partial orders, check them for consistency and report any that are not consistent

Inputs. I am given a finite set $S$ of symbols. I know there should exist some total order $<$ on $S$, but I'm not given this ordering and it could be anything. I am also given a collection of ...
user avatar
  • 141k
28 votes
3 answers
12k views

Pumping lemma for simple finite regular languages

Wikipedia has the following definition of the pumping lemma for regular langauges... Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1 depending only on $L$ such that every ...
user avatar