Order-two decomposition conjecture for the ternary Parikh rewriting system

About 11 years old · traced to

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

R={ac→ca}∪{abwba→bawab∣w∈Σ∗}∪{bcwcb→cbwbc∣w∈Σ∗}.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 w⇒Pw′w\Rightarrow_{\mathfrak{P}}w' and ww and w′w' differ in 2∗d(w,w′)2*d(w,w') positions, then there is a sequence of irreducible transformations of order at most 22 that takes ww into w′w'. 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.

References

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.