The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
1answer
60 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 ...
4
votes
1answer
97 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 ...
5
votes
2answers
87 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$ ...
0
votes
1answer
59 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 ...
4
votes
1answer
122 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 ...
0
votes
1answer
107 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 ...
2
votes
0answers
45 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$ ...
3
votes
2answers
183 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 ...