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

9
votes
0answers
255 views

Various definitions of recursion from ordinal machines

Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...
0
votes
1answer
190 views

hypergraph cartesian join operation (over same vertex set)

consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new hypergraph ...
3
votes
2answers
244 views

What categories correspond to the typed lambda calculus with parametric types?

the unadorned typed lambda calculus correspond to the closed cartesian categories, but if we add in dependent or parametric types how are they then characterised?
3
votes
0answers
313 views

Groupoid interpretation of type theory

Hello, I read the paper on groupoid interpretation of type theory by Hofmann and Streicher and I have a question. According to the authors $Tm([[\text{Set}\:[\Gamma]\: ]])$ is the same as ...
0
votes
1answer
249 views

Counterexamples for this algorithm for recognizing lexicographic product of graphs?

Found a possible reduction from recognizing lexicographic product of graphs to 2SAT (since 2SAT is polynomial, the algorithm is polynomial). Can't prove completeness of the algorithm and since it is ...
0
votes
0answers
85 views

Exact Length Problem in a directed graph

I have a directed graph that consist of N^2 vertices (like a square) and each vertex is connected to at most 1 node (not bidirectional) and every connections have length 1. There are no cycles in the ...
4
votes
1answer
486 views

Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows: build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
5
votes
1answer
626 views

How much does a quantum oracle to find a needle in a haystack really cost?

Among the basic algorithms of quantum computations Lov Grover's result on quantum search stands out, both in regards to its intrinsic interest, and for its undisputable elegance. Grover's algorithm ...
9
votes
3answers
1k views

Higher categories as data structures

Still wading through higher category theory. I find the subject a bit intimidating, not so much for technical reasons, but because I lack sufficient intuition as to the motivation(s)/heuristics one ...
6
votes
1answer
416 views

Who introduced the concept of Primitive recursive functions?

I have thought that Gödel introduced the concept of Primitive recursive functions in his seminal paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme" (I hope I ...
6
votes
0answers
147 views

Finding a database of representations as matrices

Sorry if this would be more appropriate as a stackoverflow and not a mathoverflow question, but I think it's more likely to be known in this community. There are plenty of places on the internet or ...
1
vote
2answers
260 views

Satisfiability problem for FOL[<,R]

Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say: < is a strict partial order and R is an irreflexive and ...
4
votes
3answers
285 views

Existential quantification over regular predicates

A regular language over an alphabet $\Sigma$ is a subset of the set of all words over $\Sigma$ that can be accepted by some finite automaton. A regular language identifies a certain property of ...
7
votes
0answers
233 views

Modelling the difficulty of mental calculation. [closed]

Are you aware of any work that tries to model the difficulty of evaluating a formula mentally (for your average, numerate, person, not a trained mental calculator)? For instance, evaluating an ...
0
votes
1answer
278 views

Is there any relationship between a tree(graph theory) and semi-metric?

suppose we have a tree(undirected) with $n$ vertices.The edges are weighted(distances). Is it possible to impose a semi-metric structure on the graph using these distances and adjacency matrix?
20
votes
4answers
1k views

Algorithmically unsolvable problems in topology

This question is inspired by a paper by B. Poonen that appeared on the arxiv some time ago: http://arxiv.org/abs/1204.0299. The paper gives a sample of algorithmically unsolvable problems from various ...
3
votes
2answers
338 views

anyone help me with this inequality

I'm have some difficulties in bounding the following inequality: I want to find a c as small as possible s.t. $$\sum_{i=1}^nx_i^4\sum_{i=1}^nx_i^2 -\sum_{i=1}^nx_i^6 \leq ...
3
votes
2answers
940 views

Is there an algorithm that can “reverse engineer” a Regular Expression?

Given a Regular language (represented as a black box to which one can apply inputs and get 0/1) Is there an algorithm that can find a finite deterministic automaton that produces that language?
5
votes
0answers
193 views

Büchi automata with acceptance strategy

I have already asked this question on cstheory.stackexchange, but without success. Maybe it is too close to an "open problem", although it is not a famous one. Anyway I try here, I can always remove ...
2
votes
1answer
325 views

Algorithm for satisfiability of inequalities.

I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$. In ...
0
votes
0answers
343 views

Examples of Hamiltonian Cycle Problem / Traveling Salesman Problem in general grid graph form

I understand that there is a polynomial algorithm to solve TSPs that are in solid grid graph form (grid graphs without holes). I am particularly interested in the non-solid grid graph form of the ...
3
votes
1answer
188 views

Bezier Curves question

Hi everyone I have a fairly simple question about bezier curves: can you represent n bezier curves that have been continuously joined together by a single bezier curve of degree 3n? My instinct is ...
2
votes
1answer
454 views

#P version of SUBSET SUM

The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...
0
votes
1answer
244 views

Universality of blind graph rewriting

Let us consider $S(M) = \{(f_0, f_1) | f_0, f_1: M \rightarrow M\}$, where $M$ is a finite set. Each element of $S(M)$ is equivalent to a finite directed graph with the set of nodes $M$, which has ...
3
votes
2answers
330 views

Representation of μ-recursive functions

Can every μ-recursive function be defined using a single instance of the μ operator applied to a primitive recursive function? According to Wikipedia, any μ-recursive function can be expressed as the ...
3
votes
1answer
630 views

Algebraic structure generated by primitive graph operations

Let $M$ be a finite set, and $S(M) = \{(f_0, f_1) | f_0, f_1: M → M\}$. Each element of $S(M)$ can be considered as a finite directed graph with the set of nodes $M$, which has exactly two arrows ...
23
votes
11answers
2k views

Interesting conjectures “discovered” by computers and proved by humans?

There are notable examples of computers "proving" results discovered by mathematicians, what about the opposite: Are there interesting conjectures "discovered" by computers and proved by humans? ...
3
votes
2answers
602 views

symmetric difference of languages - both are in NP and coNP

I have this problem, Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like: $L_1 \oplus L_2$ = {x | x is in exactly one of ...
25
votes
0answers
637 views

Computer calculations in A_infinity categories?

Is there a good computer program for doing calculations in A-infinity categories? Explicit calculations in A-infinity categories are an important, useful, yet very tedious task. One has to keep ...
6
votes
2answers
862 views

Busy Beaver - Proof for BB(2) = 4

Hi, I need to prove the above claim. I can show that $BB(2)\ge 4$ by building a turing machine, but how can i show that $BB(2) \le 4$? Searched a lot over the web, and saw that Rado proved it in ...
3
votes
2answers
732 views

Certain type of regular languages

Dear All, there is one type of regular languages, over $\{a,b\}$, which appear naturally in what I am studying, so if anybody could recognise them, or say any sort of their characterisation, that ...
3
votes
2answers
590 views

Kleene's fixed point theorem on recursive subsets of computable functions

I have a question about the possibility to apply/restate the Kleene fixed point theorem on recursive subsets of computable functions. I don't know if this is trivial and/or if related questions have ...
5
votes
1answer
383 views

Arrangement of integers 1..k^2 in k*k grid to minimize energy function

Question arises from considering cache oblivious algorithms. What is the optimal way arrange the numbers $1$ to $k^2$ in a grid, to minimize to average difference between any two neighbouring ...
7
votes
3answers
595 views

Error correcting codes - basic question

Hi, I have a basic question regarding error correcting codes. Suppose I want to encode a finite information $F$ (say a finite string) into a string $x$ of $n$ bits ($n$ can be as large as you want), ...
21
votes
4answers
981 views

A programming language that can only create algorithms with polynomial runtime?

Has someone constructed a programming language that can construct all the algorithms in P, and no others? I'm interested in this restriction coming from the syntax naturally, as opposed to just being ...
2
votes
2answers
536 views

Graph Theory Conjectures [closed]

What are some important conjectures in graph theory that have been checked by computer up to order 11?
6
votes
1answer
319 views

compression of a Turing machine run sequence

consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as ...
2
votes
0answers
106 views

How to argue about state transitions?

Computing differs from math by its dependence on state changes, among other things. A program can be seen as a composition of state transitions, and it would be nice to have an inverse function to ...
2
votes
1answer
466 views

Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...
1
vote
2answers
436 views

Is there constructive proof of the fact that every recursive set $A \ne \varnothing$ is recursively enumerable in non-decreasing order?

Every proof I've read about this fact considers two cases: $A$ - finite and $A$ - infinite but this is undecidable problem. So, is there constructive proof?
8
votes
2answers
306 views

Reduction rules for inductive types

(I'm not sure if I should post this here rather than at Theoretical Computer Science, I've found a lot of type theory related questions on MathOverflow) I'm working in Martin-Löf type theory with ...
0
votes
1answer
150 views

Subset-Free Codes

For each non-negative integer $n$, what antichain(s) in $\{0,1\}^n$ with the pointwise partial order: $\;\;$ 1. $\;$ have the most elements $\;\;$ 2. $\;$ minimize the maximum of its elements' sum ...
6
votes
2answers
1k views

Is there any math foundation for map/reduce?

For a while I was thinking that you just need a map to a monoid, and then reduce would do reduction according to monoid's multiplication. First, this is not exactly how monoids work, and second, this ...
4
votes
2answers
202 views

What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?

The question is mostly in the title. Imagine I have some non-convex polyhedron $P$, and I would like to find the smallest diameter ring that it can pass through in 3-space, undergoing any necessary ...
7
votes
2answers
859 views

Distribution of the computable numbers on the real number line

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...
12
votes
1answer
2k views

Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
3
votes
1answer
627 views

Decomposition of a complete graph into maximal matching subgraphs

Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge? For example, consider $K_4$ with vertices ...
1
vote
1answer
188 views

Recoving an unknown tree graph with knowledge of root node to leaf node distances

Imagine I have an unknown (undirected) tree graph, $G$, with some unknown number of nodes $||V||$. However, I know the edge-length between nodes is of fixed size, $L_{edge} = 1$, and I have access to ...
4
votes
1answer
235 views

Inverse of Kleisli star, or “extension operator”

While thinking about monads in the theory of denotational semantics, I have made an observation about the Kleisli category that I would like to check Suppose $F : \mathcal D \to \mathcal C$, $G : ...
4
votes
1answer
277 views

Hermit H-machines

I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H. Is there a ...