All Questions

9,053 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
41
votes
0answers
2k views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
37
votes
0answers
548 views

Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it: Given a planar graph $G$, and two vertices $s$ and $t$, find an $s$-$t$ path $P$ ...
37
votes
1answer
2k views

Is it NP-hard to fill up bins with minimum moves?

There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$. You start with $b_j$ balls of type $j$. Each ball of ...
26
votes
0answers
654 views

Largest set of cocircular points

Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior). This can be done in $O(n^3)$ ...
23
votes
0answers
808 views

Can a calculus have incremental copying and closed scopes?

A few days ago, I proposed the Abstract Calculus, a minimal untyped language that is very similar to the Lambda Calculus, except for the main difference that substitutions are ...
23
votes
1answer
1k views

Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
22
votes
0answers
500 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 ...
22
votes
5answers
2k views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
20
votes
0answers
601 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 \...
19
votes
1answer
897 views

Why hasn't functional programming researched dynamic trees?

Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging ...
19
votes
1answer
1k views

Could min cut be easier than network flow?

Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
18
votes
0answers
415 views

Is finding a weight-balanced tree NP-hard?

In the following, we consider binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves. Let $T.l$ and $T.r$ be the left child and ...
16
votes
2answers
596 views

Steps that guarantee exiting a maze

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
15
votes
0answers
299 views

Is the two-color leapfrog problem in P?

My question is whether a specific decision problem is in P or not. It's straightforwardly in NP. The decision problem is a specific case of the general $k$-color leapfrog problem. I can already show ...
15
votes
1answer
565 views

Is the language of words that are unbalanced in the first half context-free?

(Practice exam question in computational models) Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s. Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
15
votes
0answers
245 views

Using logic to prove non-regularity of a language

A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik ...
14
votes
0answers
140 views

What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?

In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ...
13
votes
2answers
704 views

Flow graph that requires pushing back flow in Ford Fulkerson

Does there exist a flow graph that always requires flow to be pushed back no matter what ordering of augmenting paths is chosen in Ford Fulkerson? Let's assume we use the standard procedure of ...
13
votes
0answers
202 views

Why do we have to forbid non-conforming lower and upper type bounds?

(it's a repost of my unanswered question from scala-user@googlegroups.com about Scala) In the Scala Language Specification, §4.4 Type Parameters, there is a requirement: The most general form of a ...
13
votes
0answers
394 views

Choosing a subset of binary variables to maximize the sum of the highest $K$

Consider the following problem: Input: integers $n > m > k$; $n$ numbers $0 \leq p_1, \ldots, p_n \leq 1$; $n$ numbers $r_1, \ldots, r_n$ where ($r_i \geq 0$). Let $X_1,\dots,X_n$ be $n$ ...
13
votes
0answers
628 views

Test whether two languages are equal, when give in algebraic form

This sub-problem is motivated by Algorithm to test whether a language is regular. Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
12
votes
0answers
224 views

Is extensionality for coinductive datatypes consistent with Coq's logic?

Given a coinductive datatype, one can usually (always?) define a bisimulation as the largest equivalence relation over it. I would like to add an axiom stating that if two members of the type are ...
12
votes
1answer
577 views

The difference between dynamic logic and temporal logic

To find the difference, I'd just encountered with assertions below about temporal logic in Wikipedia: another variant of modal logic sharing many common features with dynamic logic, differs from ...
12
votes
0answers
760 views

Optimal meeting point in directed graph

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$. I need ...
12
votes
0answers
777 views

Fast algorithm for max-convolution with concave functions?

I'm interested in a discrete max-convolution problem, which is to compute $$r(c) = \max_{x | x \ge 0, \sum_k x_k = c} \left[ \sum_{k=1} f_k(x_k) \right] $$ for all values $c=0, \ldots, C$, where $x=(...
11
votes
0answers
106 views

Min-eigenvalue bound for a random d-regular graph

I need help proving the following fact: Let $G$ be a random $d$-regular graph with adjacency matrix $A$. The smallest eigenvalue $\lambda_n$ of $A$ should satisfy $|\lambda_n| = o_d(d)$. (In ...
11
votes
0answers
163 views

Covering a complete graph with n copies of an arbitrary graph: NP-complete?

Given a complete graph $G$, an arbitrary graph $H$, and a positive integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that their union is $G$, and each of them ...
11
votes
0answers
136 views

Denotational semantics of object-oriented languages

I am interested in denotational semantics of object oriented languages. Namely, what are the common/typical denotations of objects used in the literature? Is this an interesting topic these days? The ...
11
votes
0answers
1k views

Alternative to Bloom filter for extreme parameters

A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below). I am interested in a ...
11
votes
0answers
344 views

Change in the distances in a graph after removal of a node

Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that, $$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G \...
11
votes
0answers
358 views

Proof of PCP theorem

I am reading the proof of PCP theorem in Proof Verication and Hardness of Approximation Problems. The following paragraph appears in section 3 (page 4), "Outline of the Proof of the Main Theorem". ...
11
votes
0answers
2k views

Alternatives to SVD for rank factorization

I have rank-deficient matrix $M \in \mathbb{R}^{n\times m}$ with $\text{rank}(M) = k$ and I want to find a rank factorization $M = PQ$ with $P \in \mathbb{R}^{n \times k}$ and $Q \in \mathbb{R}^{k \...
10
votes
0answers
117 views

Regularity profiles

A standard exercise in formal language theory uses Lagrange's four-square theorem to construct a language $L$ such that $L$ isn't regular but $L^2$ is regular. (Let $A = \{ a^{n^2} : n \geq 0 \}$. ...
10
votes
0answers
106 views

Can we say McCarthy and Hoare had the same objective in the 60s regarding a mathematical theory of computation?

I don't think there's any way to ask a very precise question here, so this might be considered opinion based. Nevertheless, it seems the question is clear enough because I'm asking whether these two ...
10
votes
0answers
183 views

Constructing a connected graph with given degree sequence

I am interested in constructing simple connected graphs where each vertex has a fixed number of edges (degree) ahead of time. I had originally assume I could use some modification of the Havel-Hakimi ...
10
votes
0answers
560 views

Advantages of algorithm W over algorithm J for type inference in Hindley-Milner type system

According to A modern eye on ML type inference Furthermore, for some unknown reason, W appears to have become more popular than J, even though the latter is viewed—with reason!—by Milner as ...
10
votes
0answers
358 views

Is Agda sound as a proof system?

I was browsing Agda's stdlib source code, since I was trying to get into it seriously and therefore wanted to know more. I was amazed at that Agda is way more developed than I thought and it's ...
10
votes
0answers
161 views

When can you "invert" an equation in the lambda calculus

Suppose that $M$ is a full model of the simply typed lambda calculus. Suppose each base type is infinite. Now suppose that $f$ and $g$ are two functions in $M$ (not necessarily in the same domain) ...
10
votes
0answers
222 views

Minimum edge deletion partitioning of a planar graph

I'm interested in the time complexity of the following problem: Given an undirected planar graph $G=(V,E)$ and a weight function $w:E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color ...
10
votes
0answers
144 views

Complexity class for probabilistic approximation algorithms with bounded error

What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ...
10
votes
0answers
1k views

Does Automatic Differentiation handle conditional branches, if yes how?

I'm trying to understand how Automatic Differentiation (AD) works. For simple algebraic operation, I get the chain rule thing. But, when the code contains conditional statement like ...
10
votes
0answers
171 views

(Slightly) faster simulation of quantum Fourier transform

Suppose I want to write a classical software simulator of a quantum circuit with $N$ qubits. When it comes time to simulate the quantum Fourier transform I can evaluate all $2^N$ states to determine ...
10
votes
1answer
392 views

Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
10
votes
0answers
906 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 running-...
10
votes
0answers
207 views

"Essential" problem for MA

I am trying to understand different interactive proof systems, in particular AM and MA. Is there a typical problem for the complexity class MA as Graph-NonIsomorphism problem is for AM? Is there ...
10
votes
0answers
128 views

Applying the graph mining algorithm Leap Search in an unlabeled setting

I am reading Mining Significant Graph Patterns by Leap Search (Yan et al., 2008), and I am unclear on how their technique translates to the unlabeled setting, since $p$ and $q$ (the frequency ...
10
votes
1answer
4k views

Finding the longest repeating subsequence

Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
9
votes
0answers
279 views

Are there consequences for P ≠ NP that are unintuitive?

It's often regarded that the most intuitive answer to the question of $P$ vs $NP$ is that $P ≠ NP$. This is often illustrated with some consequences that would follow if $P = NP$ were true. Things ...
9
votes
0answers
183 views

Can you multiply complex 2x2 matrices in fewer than 21 real multiplies?

It is well known that 2x2 matrices can be multiplied using just 7 (instead of the obvious 8) multiplications in the ground field (Strassen-Winograd, etc.). It is also well known that complex numbers ...
9
votes
0answers
679 views

How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?

I'm stuck on problem 9.4 from The Nature of Computation which reads: Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this ...

15 30 50 per page
1
2 3 4 5
182