15 problems

Let $m$ be the number of free indices and let $n$ be the size of a binary lambda term, encoded as a binary word of length $n$ according to Tromp's weights. Let…

Berline's conjecture. No graph model has an r.e. theory.

Let derivations be derivations in natural deduction, and let a derivation be reduced to a normal form by the normalization procedures of the system. Prawitz's Normalization Conject…

Let $\mathbb{F}$ be the pseudomonad whose discrete pseudoalgebras are continuous lattices, and let $\mathbf{PsAlg}_{\operatorname{ps}}(\mathbb{F})$ denote its category of pseudoalg…

Openness-linearity conjecture. The notion of openness may be related to linearity.

A planar linear normal $\lambda$-term is a linear normal $\lambda$-term whose syntactic diagram is planar; call it 3-connected when its syntactic diagram is 3-connected. For…

Let $\textsf{ILC}_\mu$ denote the relevant unity-of-logic calculus, and let the dual calculus have call-by-name and call-by-value substructural calculi. Correspondence conjecture.…

The paper studies a call-by-value setting in which execution time is measured by the number of ${\beta_v}$-steps leading to a normal form, if any, using a relational denotational s…

Computational-complexity conjecture. The computational complexity of the $\lambda$-calculus is not enhanced by the introduction of the classical variables and the new rules.

Rooted bridgeless maps are a class of combinatorial maps, and the paper considers a certain natural family of lambda terms associated with the same enumerative setting. Equinumeros…

Three-function conjecture. There are no total recursive functions $f,g:\mathbb{N}\to\mathbb{N}$ such that, for all numeral systems, the functions represented using the system inclu…

Continuous-semantics conjecture. All the effective models living in the continuous semantics have non-r.e. equational theories.

Effective graph-model conjecture. All the effective graph models have non-r.e. equational theories.

Minimum-theory conjecture. The minimum equational graph theory is non-r.e.

Scott-semantics conjecture. No $bb$-model living in Scott's continuous semantics or in one of its refinements has an r.e. equational theory.