On shuffle products, acyclic automata and piecewise-testable languages

Simon Halfon, Philippe Schnoebelen

We show that the shuffle $L \unicode{x29E2} F$ of a piecewise-testable language $L$ and a finite language $F$ is piecewise-testable. The proof relies on a classic but little-used a…