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

Let FIM1\operatorname{FIM}_1 be the free inverse monoid of rank 11. Write WP(FIM1)\operatorname{WP}(\operatorname{FIM}_1) and ι(FIM1)\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(FIM1)\operatorname{WP}(\operatorname{FIM}_1) nor ι(FIM1)\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.

Sources & referencesView supporting material

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.