For question borderline with, or having application to, computer science. Consider also posting http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/ instead of here, if appropriate.

learn more… | top users | synonyms

5
votes
1answer
356 views

Growth zeta-functions of regular languages

Dear All, my following question may be known and ought to be known, so in case it is folklore please could you give me the references. To start, it is obvious that growth of rational languages are ...
7
votes
1answer
586 views

The hardness of computing inverse

Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input. Are ...
2
votes
1answer
296 views

Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the information that the language accepted by this automaton $L(M)$ is a deterministic context-free ...
2
votes
1answer
439 views

Lipschitz constant of Laplace-Beltrami Operator

I already asked this question at stackexchange with no response - so I'll try here. I'm reading a paper on discrete differential geometry: Meyer et.al. They define the Laplace-Beltrami operator at ...
2
votes
2answers
229 views

Correcting bias in samples selected by a prediction

Here is the scenario: I'm trying to find as many golden tickets as I can, so that I can sell them to kids that want to go on a tour of Wonka's chocolate factory. Fortunately, I have a machine that ...
2
votes
1answer
750 views

Official name and complexity of k-way balanced set partitioning? What is the best heuristic?

As a lot of people know, graph partitioning is NP-Complete. In graph partitioning, you try to create k balanced (within some pre-specified epsilon) disjoint subsets of (possibly weighted) vertices ...
2
votes
3answers
2k views

Worst known algorithm in terms of Big-O (more precisely Big-theta)?

Hello, I have been trying to find the worst algorithm in terms of it's Big-O function. By worst I mean n! is worse than n^2, n^n is worse than n!, etc. Essentially the worst algorithm would be the ...
3
votes
2answers
508 views

Partition a square into sub-rectangles with restrictions

Is there an algorithm to generate all partitions of given square by using $n$ vertical and $n$ horizontal lines into sub-rectangles under the following restrictions: 1- No vertical line crosses any ...
0
votes
1answer
163 views

the maximal length of a special dicksonian sequence

First, we define a sequence $t_{1},t_{2},\cdots,t_{k}$ of n-tuples dicksonian, if $\forall 1\leq i < j\leq k,$ there does not exist a non-negative n-tuple t such that $t_{i}+t=t_{j}.$ For example, ...
3
votes
5answers
586 views

Is the following two-dimensional graph likely to be globally rigid?

Consider the two-dimensional non-planar graph $G$, with known topology and edge lengths $(r_1, r_2, ... r_N) \in R$, but unknown vertex coordinates. We further specify that: All vertices within a ...
8
votes
0answers
1k views

Question on randomness extractors

Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$. The adversary doesn't ...
26
votes
3answers
1k views

“Simpler” statements equivalent to Con(PA) or Con(ZFC)?

Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...
0
votes
0answers
96 views

Does there exist an algorithm for computing reachability in dynamic directed forests with fast update?

I'm interested in an algorithm which is able to compute reachability between any two nodes in polylog update (add or remove a valid edge) and query. I know that such an algorithm does exist for all ...
2
votes
0answers
238 views

what is the largest gap between rank and approximate rank

$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} ...
1
vote
2answers
629 views

best deterministic complexity for factoring polynomials over finite field

I would like to know currently what's the best deterministic complexity for factoring polynomials over finite field (without the assumption of GRH)? I have searched on google, there are many source, ...
2
votes
1answer
188 views

Parsing of Stochastic Contex-Free Grammars (SCFGs)

I am interested in parsing of general SCFGs. I am aware of the Earley parser for the general CFGs. The only general algorithm for parsing SCFGs that I am aware of is the Earley-Stolcke parser : ...
1
vote
1answer
559 views

final step(s) for a proof that a function is not primitive recursive

My function is $f:\mathbb{N} \rightarrow \mathbb{N},\ f(n)=2\uparrow ^n 3$ , the Ackermann(-Péter) function, with the second argument fixed to 3 (and "$\uparrow$" the Knuth up-arrow), which I believe ...
15
votes
2answers
627 views

Status of an open problem about semilinear sets

In his book "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg mentioned the following open problem: Find a decision procedure for determining if an arbitrary semilinear set is ...
4
votes
2answers
318 views

Approximate search space on a 5x5x5 cube with 3 different possible classes?

Hey all, I read the meta, and I realize this question might be pretty elementary for this site, but I'm having trouble computing this, and I know it won't take too much insight for someone to give me ...
9
votes
1answer
2k views

All-pairs shortest paths in trees?

This is a reference request, since I'm sure what follows isn't new, but I can't seem to find it. Suppose that we have a finite tree $T$ with non-negative weights on the edges. Naively, computing the ...
4
votes
1answer
362 views

Injections to binary sequences that preserve order

Suppose we have a countable set S with a total order. Can we give an injection from S to the set of finite binary sequences that end in all zeros that preserves the ordering? The order on binary ...
3
votes
2answers
341 views

Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).

Is there an efficient algorithm for finding the solution $x$ of $b = Ax$ that minimizes the Hamming weight of $x$, where $A$ is a nxm-matrix over the field $\mathbb{F}_2$ ("integer matrix modulo ...
6
votes
2answers
500 views

A Query regarding the Halting Problem (Omega): Halting Probability for Given Input Size

I was studying the Halting Problem in context of the Probability and had a few doubts regarding it. Hope someone could help me out. I am aware of the probability of a Random program halting on a ...
5
votes
3answers
530 views

Appropiate models of numerical computation

Hello, in contrast to the more discrete part of computational mathematics (cryptography, combinatorial computation), numerical mathematics seems to ignore typical questions of theoretical computer ...
4
votes
1answer
247 views

Turing Machine which generates order on the set of its states

This question is related to this one Do Turing Machines generates any nontrivial lattice on the set o symbols or states? The Turing machine (TM) is an abstract model for effective implementation of ...
1
vote
1answer
215 views

Do Turing Machines generates any nontrivial lattice on the set o symbols or states?

Second question, probably better: Turing Machine which generates order on the set of its states I would like to ask ( if it is not terribly obviously wrong): Do Turing Machine generates ...
1
vote
2answers
295 views

Positive & Negative Arity

Hi, You can talk about the arity of a function or an operation - something like addition could have an arity of 2, and negation usually has an arity of 1. A paper I am reading is talking about ...
2
votes
2answers
735 views

viewing the second fundamental form as a tensor

Dear all, Thank you for your time reading this post. I am a student in computer science so this viewpoint of the second fundamental form may be interesting to you. I would like to understand the ...
3
votes
2answers
1k views

finding numbers at k hamming distance

Guys, I have N < 2^n randomly generated n-bit numbers stored in a file the lookup for which is expensive. Given a number Y, I have to search for a number in the file that is at most k hamming ...
8
votes
5answers
429 views

Syntactically capturing complexity classes

Primitive recursive functions are syntactically constructible in the sense that from a set of "axioms" we can build every function in the set $PR$. This basicly means that we can build a machine that ...
1
vote
1answer
259 views

Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?

Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}? One case this is possible is when ...
4
votes
1answer
539 views

What fails when using call/cc as realizer of the Peirce formula

Define the axiom constants $p_{A,B}^{((A\rightarrow B)\rightarrow A)\rightarrow A}$ as realizers of the Peirce formula, and $f_A^{\bot\rightarrow A}$ as realizers of the Ex Falso Quodlibet. Then ...
28
votes
17answers
6k views

Computer Science for Mathematicians

This is a big-list community question, so I'm sorry in advance if it is deemed too soft but I haven't seen anything similar yet. I've seen computer scienctists post questions looking to learn things ...
1
vote
2answers
773 views

Verifying a sequence that converges to pi [closed]

A computer program ouputs the digits of $\pi$ by evaluating the recurrence relation $a_{n+1} = a_n + sin \ a_n$ with $a_0 = \frac{6}{5}$ Does the sequence actually converge or is this just ...
5
votes
1answer
425 views

What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?

This question is now also on http://cstheory.stackexchange.com/questions/4081/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k, where a discussion started, and one reference ...
4
votes
2answers
659 views

Coloring edges on a graph s.t. the set of edges for any two vertices have no more than 'k' colors in common

Please imagine the case where one has a planar graph, $G$, with a set of $|V|$ vertices, $(v_1, ..., v_{|V|}) \in V$, and $|E|$ edges, $(e_1, ..., e_{|E|}) \in E$. Now, provided a total of $N$ ...
8
votes
3answers
2k views

n-dimensional voronoi diagram

Hi, I need to compute the voronoi diagram of a set of points in $R^n$. I'm quite unschooled on the topic, could someone point me to the right references so that I can a) understand the theory behind ...
6
votes
1answer
368 views

Are innermost reductions perpetual in untyped $\lambda$-calculus?

Background In the untyped lambda calculus, a term may contain many redexes, and different choices about which one to reduce may produce wildly different results (e.g. $(\lambda x.y)((\lambda ...
2
votes
3answers
320 views

Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?

I'll ask you to consider a situation wherein one has a series of edges for a graph, $(e_1, e_2, ..., e_N) \in E$, each with a specifiable length $(l_1, l_2, ..., l_N) \in L$, and the goal is to insure ...
0
votes
1answer
1k views

How are taps proven to work for LFSRs?

Obviously, you can exhaustively check that it lands on every state except the zero state, but for large linear feedback shift registers (LFSR), this quickly becomes infeasible. Wikipedia states the ...
15
votes
7answers
1k views

Between mu- and primitive recursion

It is well known that primitive recursion is not powerful enough to express all functions, Ackermann function being probably the best known example. Now, in the logic courses (that I have had look ...
5
votes
1answer
336 views

Drawing graphs on circles

Please consider the following problem: Given: a simple graph (without self-loops and without multiple edges) $G$ on $n$ vertices. Task: place equidistantly the vertices of $G$ on a circle of unit ...
6
votes
1answer
3k views

Meaning of \Subset notation

The symbol $\Subset$ (occurring in places where $\subseteq$ could occur syntactically) comes up frequently in a paper I'm reading. The paper lives at the intersection of a few areas of math, and I ...
29
votes
1answer
2k views

An edge partitioning problem on cubic graphs

Hello everyone, I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
6
votes
1answer
451 views

post correspondence problem variant

Is there an algorithm which takes as input two lists of words $v_1,...,v_n$ and $w_1,...,w_n$ over an alphabet $X$ and decides if there is an infinite sequence $(k_i)$ where $1 \leq k_i \leq n$ for ...
4
votes
3answers
1k views

Optimal packing of spheres tangent to a central sphere

Please consider a central, ordinary 2-sphere $S_1$, of some radius $r_1$, and a second ordinary sphere, $S_2$, of radius $r_2$, where $r_2 \leq r_1$. My question concerns optimal values for the ...
0
votes
3answers
298 views

boolean functions and averaging / counting

Hey guys, I have a slightly imprecise question. I would like say something about a whole set of binary strings evaluated by a binary function by just looking at some type of average. The easiest ...
1
vote
2answers
892 views

What is the right citation for the power iteration method to find eigenvalues?

What is the right citation for the power iteration method to find eigenvalues, if I want to cite the method in a paper? I've seen some Google PageRank references in this context. But Brin and Page ...
2
votes
4answers
833 views

Enumerative algorithm through inclusion-exclusion

Hello everybody ! I wondered, without really knowing where to search, whether there was a "smart" way to enumerate/iterate over all the elements of a set which can be counted by inclusion-exclusion. ...
3
votes
1answer
478 views

Approximating an integral representation of the Number Partition Problem

One can write out an integral whose solution gives the number of solutions to the NP-Complete Number Partition Problem and I'm wondering if anyone has an suggestions or ideas on who to solve or ...