Polynomial operations and hierarchies of concatenation (Q1183588): Difference between revisions

Given a class of languages \(A^*{\mathcal C}\) on the alphabet \(A\), \(\text{Pol}(A^*{\mathcal C})\) denotes its closure under union and the operations \((L,L')\mapsto LaL'\) (\(a\in A\)). The main result is that if \(A^*{\mathcal C}\) is closed under the operations \(L\mapsto a^{- 1}L=\{w\mid\;aw\in L\}\) and \(L\mapsto La^{-1}\), and if \(A^*{\mathcal C}\) is a boolean algebra, then \(\text{Pol}(A^*{\mathcal C})\) is closed under intersection. Applications of these methods is a refinement of the Straubing hierarchy, to the intermediate levels \(n+{1 \over 2}\), and the decidability of levels \(1 \over 2\) and \(3 \over 2\).