Unanswered Questions
16
votes
0answers
138 views
Asymptotics of the number of words in a regular language of given length
For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
15
votes
1answer
447 views
Is Logical Min-Cut NP-Complete?
Logical Min Cut (LMC) problem definition
Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...
14
votes
0answers
433 views
Is there a 'string stack' data structure that supports these string operations?
I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing ...
10
votes
0answers
204 views
Is this strange language context free?
Is the following language context free: $L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^*\text \{ \epsilon \} \ ,\ \mid u \mid = \mid v \mid \ , \ u \not= v \ , \ \mid x \mid = \mid y \mid \ , \ x \not= y \ ...
10
votes
0answers
124 views
How does the runtime of the Ukkonen's algorithm depend on the alphabet size?
I am concerned with the question of the asymptotic running time of the Ukkonen's algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time.
Here is a citation ...
10
votes
0answers
111 views
Knapsack problem with many divisibility conditions
Let $S$ be a set of natural numbers. We consider $S$ under the divisibility relation, i.e. $s_1 \leq_d s_2 \iff s_1 \mid s_2$. Let
$\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, ...
10
votes
0answers
266 views
Proving the (in)tractability of this Nth prime recurrence
As follows from my previous question, I've been playing with the Riemann hypothesis as a matter of recreational mathematics. In the process, I've come to a rather interesting recurrence, and I'm ...
10
votes
2answers
416 views
Measuring one way network latency
This is a puzzle about measuring network latency that I created. I believe the solution is that it's impossible, but friends disagree. I'm looking for convincing explanations either way. (Though it is ...
9
votes
0answers
120 views
Towers of Hanoi but with arbitrary initial and final configuration
Recently, I came across this problem, a variation of towers of hanoi.
Problem statement:
Consider the folowing variation of the well know problem Towers of
Hanoi:
We are given $n$ towers ...
9
votes
0answers
170 views
Complexity of deciding whether there is a winning strategy in the following game
The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 ...
9
votes
0answers
166 views
How to pack polygons inside another polygon?
I have ordered a few leather sheets from which I would like to build juggling balls by sewing edges together. I'm using the Platonic solids for the shape of the balls.
I can scan the leather sheets ...
9
votes
0answers
160 views
Approximate minimum-weighted tree decomposition on complete graphs
Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
9
votes
0answers
188 views
distributed alpha beta pruning
I am looking for an efficient algorithm that lets me process the minimax search tree for chess with alpha-beta pruning on a distributed architecture. The algorithms I have found (PVS, YBWC, DTS see ...
7
votes
0answers
78 views
Solving divide & conquer reccurences if the split-ratio depends on $n$
Is there a general method to solve the recurrence of the form:
$T(n) = T(n-n^c) + T(n^c) + f(n)$
for $c < 1$, or more generally
$T(n) = T(n-g(n)) + T(r(n)) + f(n)$
where $g(n),r(n)$ are some ...
7
votes
0answers
93 views
Universal Turing Machine simulation with bounded time overhead
Is it possible to design a Universal Turing Machine in which the simulation time of a given Turing Machine $M$ is bounded by a factor of $\mathcal{O}(\log|\Gamma|+\log|Q|)$ of the original ...
