On commutative context-free languages (Q1092674): Difference between revisions

Let \(\Sigma =\{a_ 1,a_ 2,...,a_ n\}\) be an alphabet and let \(L\subset \Sigma^*\) be the commutative image of \(FP^*\) where F and P are finite subsets of \(\Sigma^*\). If, for any permutation \(\sigma\) of \(\{\) 1,2,...,n\(\}\), \(L\cap a^*_{\sigma (1)}...a^*_{\sigma (n)}\) is context-free, then L is context-free. This theorem provides a solution to the Fliess conjecture in a restricted case. If the result could be extended to finite unions of the \(FP^*\) above, the Fliess conjecture could be solved.