Skip to main content
SeekingAMathGeekGirlfriend's user avatar
SeekingAMathGeekGirlfriend's user avatar
SeekingAMathGeekGirlfriend's user avatar
SeekingAMathGeekGirlfriend
  • Member for 10 years, 6 months
  • Last seen more than a week ago
9 votes
1 answer
339 views

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

4 votes
0 answers
186 views

How does Earley parsing using an automaton work?

3 votes
1 answer
161 views

Closure of context-sensitive languages under inverse language substitution

2 votes
1 answer
62 views

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

2 votes
1 answer
97 views

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

2 votes
1 answer
500 views

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

2 votes
1 answer
54 views

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

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
106 views

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

1 vote
2 answers
277 views

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

1 vote
0 answers
26 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|$?

1 vote
0 answers
40 views

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

1 vote
1 answer
86 views

Complexity of general polynomial map evaluation is polynomial?

1 vote
1 answer
55 views

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

1 vote
1 answer
104 views

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

0 votes
0 answers
56 views

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

0 votes
1 answer
46 views

k-means clustering with efficient point lookup?

0 votes
1 answer
75 views

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

0 votes
1 answer
26 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
279 views

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

0 votes
1 answer
175 views

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

0 votes
1 answer
23 views

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

0 votes
1 answer
56 views

What computational model supports arbitrarily sized integers?

0 votes
0 answers
35 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
21 views

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

0 votes
0 answers
34 views

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