Questions tagged [finite-sets]
The finite-sets tag has no usage guidance.
37
questions
0
votes
0
answers
22
views
Truth table of the next state function of a Moore machine
I'm studying finite state machines and trying to make this table but i don't know where to start. Isn't it necessary to know what happens when for example both inputs A and B from state s1 are active? ...
2
votes
1
answer
721
views
Can we prove that any set of finite strings without substrings is finite?
I want to prove (or disprove) the following conjecture:
Let $\Sigma$ be a finite alphabet, and let $L \subseteq \Sigma^*$
satisfy that there are no $v, w \in L$ such that $v$ is a proper
substring of ...
- 23
4
votes
0
answers
59
views
Finding all sets which are not subsets of other sets
I have a set of sets, for example
{
{1, 2, 3},
{1, 2},
{2},
{2, 4}
}
I want to find all sets which are not subsets of another set. For example, ...
- 141
0
votes
0
answers
69
views
How to find the intersection of two FAs and then check if two FAs are equal?
I am still quite confused on how to properly handle in answering the intersection and equality of two FAs in terms of table form and manipulating its transformation....
- 13
1
vote
0
answers
31
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....
- 21
3
votes
1
answer
58
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 ...
- 83
0
votes
2
answers
46
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 ...
- 185
0
votes
1
answer
53
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 ...
- 1
4
votes
1
answer
119
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$ ...
- 143
1
vote
1
answer
236
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 ...
- 35
6
votes
2
answers
180
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\...
- 353
4
votes
2
answers
226
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
...
D.W.♦
- 154k
1
vote
1
answer
197
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 ...
- 13
0
votes
2
answers
240
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, ...
- 177
2
votes
2
answers
182
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 ...
- 882
3
votes
0
answers
108
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 ...
- 12.8k
5
votes
0
answers
197
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 ...
0
votes
1
answer
1k
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 $...
- 3
1
vote
1
answer
2k
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.:
$$
\...
1
vote
1
answer
7k
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 ...
- 1,637
1
vote
2
answers
128
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 ...
- 12.3k
0
votes
1
answer
132
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 ...
- 101
3
votes
1
answer
166
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 ...
- 133
1
vote
3
answers
708
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 &...
4
votes
1
answer
769
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 ...
- 143
2
votes
1
answer
53
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 ...
- 123
0
votes
2
answers
413
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 ...
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 ...
- 260
1
vote
1
answer
183
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 ...
- 100
4
votes
1
answer
115
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}|\...
- 994
5
votes
2
answers
190
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$ ...
- 622
0
votes
1
answer
86
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 ...
- 429
6
votes
1
answer
1k
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 $\{...
- 63
0
votes
2
answers
721
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 ...
- 101
2
votes
0
answers
65
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$ ...
- 121
3
votes
2
answers
357
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 ...
D.W.♦
- 154k
33
votes
3
answers
13k
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 ...
- 893