Questions tagged [finite-sets]
The finite-sets tag has no summary.
39 questions
0
votes
2
answers
135
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
135
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
214
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
93
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
221
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
400
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
433
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
280
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