MaiaVictor's user avatar
MaiaVictor's user avatar
MaiaVictor's user avatar
MaiaVictor
  • Member for 10 years, 7 months
  • Last seen more than a month ago
4 votes
1 answer
154 views

Is the church-style affine calculus of constructions with unrestricted recursion consistent?

4 votes
1 answer
298 views

What, in simple terms, are the restrictions imposed by Elementary Affine Logic?

4 votes
1 answer
159 views

Is it possible to create an algorithm-aware optimizer?

3 votes
1 answer
109 views

Is it possible to determine if a reduction is correct?

3 votes
0 answers
403 views

Is there any system where function equality (extensionality) is decidable?

3 votes
0 answers
176 views

How useful is program search in the field of programming-language theory?

3 votes
2 answers
932 views

Is there a space efficient way to represent numbers on the lambda calculus?

3 votes
1 answer
184 views

What is the simplest universal unidimensional interaction net system?

3 votes
1 answer
165 views

Is there a pair of different lambda terms in the normal form that behave identically when applied to any input?

3 votes
3 answers
246 views

Is it reasonable to allow the type of a λ/∀-bound variable to refer to itself?

3 votes
0 answers
135 views

Would it be possible to derive `transp` natively from Path, Interval and typecase?

3 votes
0 answers
387 views

Is it possible to check equality of equi-recursive types, or recursive λ-terms?

3 votes
1 answer
184 views

Is there an efficient algorithm to check for duplicator-invariant equivalence on symmetric interaction combinators?

2 votes
1 answer
205 views

Can interaction combinators implement any interaction net efficiently?

2 votes
1 answer
733 views

Wouldn't the calculus of constructions with linear types be a simple functional core that is consistent and expressive?

2 votes
3 answers
351 views

Is there any programming language in which any equivalent program has a unique, decidable normal representation?

2 votes
3 answers
298 views

Is there any language for which a perfect optimization is decidable?

2 votes
2 answers
235 views

Would it be possible for a compiler to convert a recursive sum into the average formula?

2 votes
1 answer
180 views

Would a proof that the traveling salesman algorithm can't be encoded on LAL also prove P!=NP?

1 vote
3 answers
633 views

Is there an array structure that allows for O(1) complexity for reverse, zip, slice etc operations?

1 vote
0 answers
71 views

Efficient compilation of interaction combinators with infinite cell types to usual interaction combinators?

1 vote
1 answer
169 views

What is an efficient algorithm to check for equivalence on symmetric interaction combinators?

1 vote
1 answer
101 views

Extending EAL with recursion makes it incompatible with the abstract algorithm?

1 vote
1 answer
170 views

How could one define a language based on the Calculus of Constructions, but with fixed points and EAL-style duplication restrictions?

1 vote
0 answers
49 views

Is it possible to use arbitrary fixpoint values on EAL without losing strong normalization?

0 votes
0 answers
295 views

Can $f^{2^N}(x)$ be computed in polynomial time when $f$ is linear?

0 votes
0 answers
168 views

What is wrong with the "obvious" approach to function extensionality by providing context-aware rewrites?

0 votes
0 answers
173 views

Is there an algorithm to find whether 2 combinators form a Turing-complete system?

-2 votes
1 answer
436 views

What is the simplest known solver for a np-complete problem?

1
2