Daniel Donnelly's user avatar
Daniel Donnelly's user avatar
Daniel Donnelly's user avatar
Daniel Donnelly
  • Member for 10 years, 2 months
  • Last seen more than a month ago
2 votes
1 answer
1k views

Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?

2 votes
1 answer
495 views

Do you know of a brute-force algorithm for optimizing polynomial expressions? [closed]

9 votes
1 answer
334 views

Can an Earley Parser be made into a fuzzy parser similar to the Levenshtein Automata Algo for DFA?

0 votes
1 answer
278 views

Is there a model of computation, that tries to be realistic? [closed]

1 vote
2 answers
274 views

Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?

4 votes
0 answers
182 views

How does Earley parsing using an automaton work?

0 votes
1 answer
165 views

Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists?

3 votes
1 answer
154 views

Closure of context-sensitive languages under inverse language substitution

2 votes
1 answer
104 views

What is the closest theory to "The theory of code refactoring"?

1 vote
1 answer
86 views

Complexity of general polynomial map evaluation is polynomial?

1 vote
1 answer
80 views

Encoding Turing machine-like behavior using families of sequences of vector spaces and modules. P=NP related

0 votes
1 answer
72 views

Can you automatically generate a parser for a type using type theory some how?

1 vote
1 answer
69 views

Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

2 votes
1 answer
61 views

Do graphs with a bounded number of incident edges have a polynomial-time subgraph-isomorphism algorithm?

1 vote
1 answer
55 views

Efficient comparison, using only sum, product, difference, and conditional jump if zero

2 votes
1 answer
53 views

If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

0 votes
1 answer
51 views

What computational model supports arbitrarily sized integers?

0 votes
0 answers
50 views

What is the standard definition of recursive automata (or state machines)?

0 votes
1 answer
45 views

k-means clustering with efficient point lookup?

1 vote
0 answers
40 views

How do you solve a general linear diophantine equation in polynomial time (with minimization constraint)?

0 votes
0 answers
34 views

An ingenious exact smallest grammar algorithm for strings over a single letter, $s \in \{a\}^*$. First enumerate the start rules up to commutation

0 votes
0 answers
33 views

What is the minimum length word accepted by the product of these simple loop automata?

1 vote
0 answers
24 views

Determine whether we can pack $(r_1, \dots, r_k)$ copies of the variables $(A_1, \dots, A_k)$ into a string $s$, in time polynomial in $|s|$?

0 votes
1 answer
24 views

Can we simply consider a pseudo random number generator to be a function $f: \Bbb{Z}_n \to \Bbb{Z}_n$ for ever-increasing $n$?

0 votes
1 answer
23 views

How do we formally regard a function that takes a lookup set as a parameter?

0 votes
0 answers
18 views

The maximal choice smallest grammar algorithm. Is this an exact algorithm or an approximation?