Order-two decomposition conjecture for the ternary Parikh rewriting system

Let P=(Σ,R,{abc})\mathfrak{P}=(\Sigma,R,\{abc\}), where

R={acca}{abwbabawabwΣ}{bcwcbcbwbcwΣ}.R=\{ac\rightarrow ca\}\cup\{abwba\rightarrow bawab\mid w\in\Sigma^*\}\cup\{bcwcb\rightarrow cbwbc\mid w\in\Sigma^*\}.

For words w,wΣw,w'\in\Sigma^*, let d(w,w)d(w,w') denote their distance, and let an irreducible transformation of order at most two mean an irreducible transformation whose order is at most 22. Order-two decomposition conjecture. If wPww\Rightarrow_{\mathfrak{P}}w' and ww and ww' differ in 2d(w,w)2*d(w,w') positions, then there is a sequence of irreducible transformations of order at most 22 that takes ww into ww'. The claim proposes a bounded-order decomposition for transformations satisfying the stated positional-difference condition; the source appends “Why should one be interested in this?” and provides no evidence of resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Wen Chean Teh, “Parikh matrices and Parikh Rewriting Systems”, arXiv:1506.06476 (2015).

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.