Constructive automata conjecture for Ising-model languages

At least 3 years old · documented by

Let M\mathcal{M} be an Ising model and let LM{\sf L}_{\mathcal{M}} be its language. A constructive PDA decides LM{\sf L}_{\mathcal{M}} by accumulating the unary energy from local contributions and comparing it with the input energy; a constructive LBA accumulates the Hamiltonian energy on a designated tape in binary and accepts exactly when it agrees with the input.

Constructive automata conjecture. For every context free LM{\sf L}_{\mathcal{M}} there exists a constructive PDA that decides it. For every context sensitive LM{\sf L}_{\mathcal{M}} there exists a constructive LBA that decides it.

The claim says that the natural, function-computing condition imposed on the automata is not necessary for restricting the language classes: every language in the relevant class should admit such a constructive recognizer. The source gives no resolution of this conjecture.

References

Primary source

Tobias Reinhart and Gemma De les Coves, “The grammar of the Ising model: A new complexity hierarchy”, arXiv:2208.08301 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.