All Questions

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 ...

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$ ...

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 ...

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)$ ...

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 ...

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 ...

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 ...

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...

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 \...

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 \...

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 ...

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 ...

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 ...

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 ...

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 ...

(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 ...

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 ...

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 ...

(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 ...

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$ ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 \...

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". ...

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 \...

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=(...

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 ...

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 \}$. ...

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 ...

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 ...

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 ...

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) ...

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 ...

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 ...

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 ...

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 ...

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-...

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 ...

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 ...

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$ ...

The following problem (I'm paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics: Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. ...

We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...

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 ...

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 ...

Suppose we have a System F term $f : \forall \alpha. \alpha\times\alpha\to\alpha$, interpreted in a parametric model which is a bicartesian closed category. I was wondering if in such context it is ...

The problem A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...