Undecidability of regular nice labelings for strongly regular event domains

Let D\mathcal D be a strongly regular event domain. A regular nice labeling is the labeling property used in Thiagarajan's conjecture. Undecidability conjecture. There does not exist an algorithm that, given D\mathcal D, determines whether or not D\mathcal D admits a regular nice labeling. The source describes a proposed connection with aperiodic tilings and Turing-machine halting, but does not establish the conjecture.

Sources & referencesView supporting material

Primary source

Jérémie Chalopin and Victor Chepoi, “A counterexample to Thiagarajan's conjecture on regular event structures”, arXiv:1605.08288 (2018).

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.