User Daniel Donnelly

9 votes

1 answer

334 views

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

asked Jul 30, 2015 at 22:59

4 votes

0 answers

180 views

How does Earley parsing using an automaton work?

asked Dec 25, 2013 at 17:26

3 votes

1 answer

151 views

Closure of context-sensitive languages under inverse language substitution

asked May 30, 2021 at 18:10

2 votes

1 answer

58 views

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

asked Sep 24, 2021 at 3:49

2 votes

1 answer

493 views

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

asked Apr 21, 2014 at 5:10

2 votes

1 answer

49 views

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

asked Jan 11, 2019 at 7:58

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?

asked Aug 16, 2022 at 14:11

2 votes

1 answer

99 views

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

asked Jul 8 at 7:18

1 vote

2 answers

272 views

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

asked May 12, 2021 at 16:43

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

asked Nov 10, 2022 at 1:14

1 vote

0 answers

40 views

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

asked Aug 1, 2019 at 14:22

1 vote

1 answer

86 views

Complexity of general polynomial map evaluation is polynomial?

asked Apr 19, 2014 at 20:08

1 vote

1 answer

66 views

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

asked Nov 16, 2021 at 21:57

1 vote

1 answer

55 views

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

asked Jan 17, 2022 at 5:10

1 vote

1 answer

63 views

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

asked Jan 30, 2022 at 1:28

0 votes

0 answers

47 views

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

asked Feb 23, 2022 at 12:15

0 votes

1 answer

45 views

k-means clustering with efficient point lookup?

asked Jan 19, 2018 at 19:56

0 votes

1 answer

72 views

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

asked Jul 20, 2018 at 2:10

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

asked Jan 28, 2022 at 5:51

0 votes

1 answer

278 views

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

asked Apr 16, 2014 at 1:23

0 votes

1 answer

161 views

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

asked Oct 6, 2019 at 17:29

0 votes

1 answer

23 views

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

asked Oct 17, 2019 at 16:23

0 votes

1 answer

48 views

What computational model supports arbitrarily sized integers?

asked Jan 21, 2020 at 0:10

0 votes

0 answers

33 views

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

asked Nov 11, 2022 at 17:44

0 votes

0 answers

18 views

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

asked Nov 12, 2022 at 23:27

0 votes

0 answers

27 views

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

asked Oct 22 at 22:54

Stack Exchange Network

26 Questions

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

How does Earley parsing using an automaton work?

Closure of context-sensitive languages under inverse language substitution

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

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

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

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

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

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

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

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

Complexity of general polynomial map evaluation is polynomial?

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

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

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

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

k-means clustering with efficient point lookup?

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

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

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

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

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

What computational model supports arbitrarily sized integers?

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

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

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