The EDT0L nonmembership conjecture for rank-one free inverse monoid word problems

About 8 years old · traced to

Let FIM⁡1\operatorname{FIM}_1 be the free inverse monoid of rank 11. Write WP⁡(FIM⁡1)\operatorname{WP}(\operatorname{FIM}_1) and ι(FIM⁡1)\iota(\operatorname{FIM}_1) for its two word problem languages, and let EDT0L denote the class of languages generated by deterministic extended tabled 0L systems. EDT0L nonmembership conjecture. Neither WP⁡(FIM⁡1)\operatorname{WP}(\operatorname{FIM}_1) nor ι(FIM⁡1)\iota(\operatorname{FIM}_1) is EDT0L. These languages are nevertheless known to be ET0L, so the conjecture would separate the ET0L and EDT0L descriptions for these rank-one word problems.

References

Primary source

Tara Brough, “Word Problem Languages for Free Inverse Monoids”, arXiv:1803.08034 (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.