Questions tagged [finite-sets]
The finite-sets tag has no summary.
39 questions
0 votes
2 answers
142 views
Why are finite sets decidable?
I am currently trying to understand why some finite sets or problems are always decidable. For example, the halting problem on an empty tape is proven to be undecidable: $$H_0 = \{w \in \{0,1\}^* \mid ...
- 55
1 vote
0 answers
42 views
Intersections of Sets of Strings (Alabama, Alaska, Arizona, Arkansas)
Consider the following four strings of text: Alabama Alaska Arizona Arkansas These strings of text represent four names for four different states within the United States of America. Suppose that we ...
0 votes
0 answers
96 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
777 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
137 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
219 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
55 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
104 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
95 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
1 vote
1 answer
98 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 ...
- 11
4 votes
1 answer
224 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
418 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
293 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
435 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.♦
- 169k
1 vote
1 answer
285 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