41 problems

Undecidability of containment for finitely defined graph classes
arXiv@arxiv
Undecidability conjecture. The following problem is undecidable:
Conjectureopendecidability graph-classes graph-theory
0
Jones's equivalence conjecture for Diophantine quantifier prefixes
arXiv@arxiv
Consider the prefixes $\exists\forall\exists$ and $\exists\exists$ , with all quantified variables ranging over $\mathbb{N}$ . The prefix $\exists\exists$ is equivalent to the two-va…
Conjectureopendecidability diophantine-equations quantifier-elimination
0
Baker's decidability conjecture for Hilbert's Tenth Problem in two variables
arXiv@arxiv
Let $\mathrm{HTP}(2)$ denote the problem of deciding whether an arbitrary polynomial in $\mathbb{Z}[x,y]$ has a root in $\mathbb{N}^2$ . Its analogue over $\mathbb{Z}^2$ asks whethe…
Conjectureopendecidability diophantine-equations hilberts-tenth-problem
0
Decidability conjecture for the two-variable, one-unary-predicate fragment of QS5
arXiv@arxiv
Let $\mathbf{QS5}$ be the quantified modal logic QS5, and consider its fragment using two individual variables and a single unary predicate letter. Decidability conjecture. The fra…
Conjectureopencomputational-complexity decidability quantified-modal-logic
0
Epperlein's conjecture on undecidability of conjugacy for one-dimensional cellular automata
arXiv@arxiv
A cellular automaton is a shift-commuting endomorphism of a one-dimensional full shift. Two cellular automata are conjugate if there is a shift-commuting homeomorphism intertwining…
Conjectureopencellular-automata decidability symbolic-dynamics
0
Decidability of quantifier-free term modal logic with basic assignments over S5 models
arXiv@arxiv
The paper considers a quantifier-free term modal logic without function symbols, augmented with the basic assignment modalities from dynamic logic. Decidability conjecture. This fr…
Conjectureopendecidability epistemic-logic modal-logic
0
Aiello–van Benthem decidability conjecture for unary expansions of the real affine plane
arXiv@arxiv
Let $(\mathbb{R}^2,\beta)$ be the real affine plane equipped with the ternary betweenness relation $\beta$ , and consider expansions of this structure by arbitrary unary predicates.…
Conjectureopenaffine-geometry decidability model-theory
0
Urquhart's decidability conjecture for semilattice relevant logic
arXiv@arxiv
Let $\mathsf{S}=\mathsf{S}_{\to,\land,\lor}$ be semilattice relevant logic in the signature $\{\to,\land,\lor\}$ . Its decision problem asks whether there is an algorithm deciding,…
Conjectureopendecidability relevant-logic undecidability
0
Decidability conjecture for non-hypothetical logic over Peano Arithmetic
arXiv@arxiv
The language and proof system of non-hypothetical logic are considered over the axioms of Peano Arithmetic, denoted by $\mathsf{PA}$ , in a purely relational language. One may also…
Conjectureopendecidability logic peano-arithmetic
1
Undecidability conjecture for the two-variable, two-unary-predicate fragment of QS5
arXiv@arxiv
Let $\mathbf{QS5}$ be the quantified modal logic QS5, and consider its fragment using two individual variables and two unary predicate letters. Undecidability conjecture. The fragm…
Conjectureopencomputational-complexity decidability quantified-modal-logic
0
Decidability conjecture for selected intuitionistic modal logics
arXiv@arxiv
For each of the intuitionistic modal logics $\mathbf{L}_{\mathbf{bc}}$ , $\mathbf{L}_{\mathbf{dc}}$ , $\mathbf{L}_{\mathbf{bdc}}$ , $\mathbf{L}_{\mathbf{fbdc}}$ ,…
Conjectureopendecidability intuitionistic-logic modal-logic
1
Solvable domino problem for a non-virtually free group
arXiv@arxiv
Let $G$ be a finitely generated group. A group is virtually free if it has a finite-index free subgroup, and its domino problem is the decision problem for finite local colouring c…
Conjecturerefuteddecidability domino-problem group-theory
0
Wqo-based decidability conjecture for the joint embedding property
arXiv@arxiv
Let $(\mathcal{F},\le)$ be a well-quasi-order (wqo), and suppose there are algorithms for basic problems related to $\le$ , including deciding whether $X\le Y$ and, given $X$ , findi…
Conjecturerefuteddecidability joint-embedding-property well-quasi-orders
0
Beauquier–Nivat conjecture on the decidability of 2-polyomino tiling
arXiv@arxiv
Beauquier–Nivat conjecture. The $2$ -polyomino tiling problem is decidable.
Conjectureopendecidability polyominoes tiling-theory
1
Decidability conjecture for the extended multiple von Wright preference logic
arXiv@arxiv
The paper considers an extension of classical propositional calculus in which binary preference relations are defined over propositional formulae. Decidability conjecture. This log…
Conjectureopendecidability preference-logic social-choice-theory
0
The entailment-to-interpolant-existence conjecture
arXiv@arxiv
Entailment-to-interpolant-existence conjecture. The IEP for $L$ is decidable whenever entailment in $L$ is decidable.
Conjectureopendecidability interpolation logic
0
Decidability of Rational Subset Membership in higher Heisenberg groups
arXiv@arxiv
Let $H_{2m+1}(\mathbb Z)$ denote the $(2m+1)$ -dimensional discrete Heisenberg group. Conjecture. Higher $H_{2m+1}(\mathbb Z)$ have decidable Rational Subset Membership. If true, th…
Conjectureopendecidability heisenberg-groups nilpotent-groups
1
Undecidability of testing whether the joint spectral radius is at most one for positive matrices
arXiv@arxiv
Undecidability conjecture. It is undecidable to check whether
Conjectureopendecidability joint-spectral-radius positive-matrices
0
Undecidability of testing whether the joint spectral radius is at least one
arXiv@arxiv
Undecidability conjecture. It is undecidable to check whether $\rho\geq 1$ for the joint spectral radius $\rho$ .
Conjectureopendecidability joint-spectral-radius matrix-products
0
Conjecture that constants can be added to transitive-guarded logics without losing decidability
arXiv@arxiv
The transitive-guarded logics under discussion, including $\text{GF+TG}$ and $\text{TGF+TG}$ , are considered in the absence of constants. Constants and decidability conjecture. Add…
Conjectureopendecidability finite-model-theory guarded-fragment
0
The decidability equivalence for Schreier graphs of contracting self-similar groups
arXiv@arxiv
Decidability equivalence. The following are equivalent:
Conjectureopendecidability schreier-graphs self-similar-groups
0
Undecidability conjecture for the temporal logic of higher-dimensional Minkowski spacetime
arXiv@arxiv
Let Minkowski spacetime have at least three spatial dimensions, with temporal operators ${\bf F}$ for sometime in the future and ${\bf P}$ for access to spacetime points in the pas…
Conjectureopendecidability minkowski-spacetime temporal-logic
0
Conjecture on low-complexity aperiodic SFTs for arbitrary shapes
arXiv@arxiv
Let a two-dimensional configuration have low complexity with respect to a finite shape, without requiring the shape to be rectangular. A subshift of finite type (SFT) is a dynamica…
Conjectureopendecidability symbolic-dynamics tilings
0
Undecidability of regular winning-position languages for strongly terminating games
arXiv@arxiv
The conjecture. Given a strongly terminating game $\mathcal{G}$ , it is undecidable whether the winning positions of $\mathcal{G}$ form a regular language.
Problemopencombinatorial-games decidability formal-languages
0
Undecidability conjecture for three-block Presburger arithmetic with non-quadratic scalar multiplication
arXiv@arxiv
Let $\alpha$ be a non-quadratic scalar. Undecidability conjecture. $\alpha$ -Presburger arithmetic sentences with three alternating blocks of quantifiers are undecidable. The paper…
Conjectureopencomputational-complexity decidability presburger-arithmetic
1