Undecidability of regular nice labelings for strongly regular event domains
Undecidability of regular nice labelings for strongly regular event domains
Let 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 , determines whether or not 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.