The deterministic context-free word problem conjecture for special monoids
The deterministic context-free word problem conjecture for special monoids
Let be a finitely presented special monoid. A monoid has deterministic context-free word problem when its word problem is a deterministic context-free language. Deterministic context-free word problem conjecture. has deterministic context-free word problem if and only if it is isomorphic to a free product of a context-free group and a free monoid . This extends the known structural obstruction provided by the bicyclic monoid. The forward implication is equivalent to the conjecture of Brough, Cain, and Pfeiffer that the bicyclic monoid does not have deterministic context-free word problem; the reverse direction also depends on whether deterministic context-free word problems are closed under free products, which is open.
Sources & referencesView supporting material
Primary source
Carl-Fredrik Nyberg-Brodda, “On the Word Problem for Special Monoids”, arXiv:2011.09466 (2021).
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.