Strictly Piecewise Languages

Strictly Piecewise Language is a subclass of Subregular Languages. It is defined by a set of forbidden subsequences.

We can map the monoid of words to the monoid of sets of subsequences of length up to k.

$\begin{CD} \Sigma^*\times \Sigma^* @>\circ>> \Sigma^* \\ @Vf \times fVV @VVfV \\ \mathbb{P}(\Sigma^{\leq k})\times \mathbb{P}(\Sigma^{\leq k}) @>\oplus>>\mathbb{P}(\Sigma^{\leq k}) \end{CD}$

$ \begin{CD} (w_1,w_2) @>\circ>> w_1 \circ w_2 \\ @VP_{\leq k} \times P_{\leq k}VV @VVP_{\leq k}V \\ (P_{\leq k}(w_1),P_{\leq k}(w_2)) @>\oplus>>P_{\leq k}(w_1 \circ w_2) \end{CD}\\$

$S_1 \oplus S_2=\cup(P_{\leq k}(S_1 \circ S_2))$

$P_{\leq k}(w_1 \circ w_2)=P_{\leq k}(w_1) \oplus P_{\leq k}(w_2) = \cup(P_{\leq k}(P_{\leq k}(w_1) \circ P_{\leq k}(w_2)))$








Back