On shuffle products, acyclic automata and piecewise-testable languages

Simon Halfon; Philippe Schnoebelen

doi:10.1016/j.ipl.2019.01.012

paper

On shuffle products, acyclic automata and piecewise-testable languages

arXiv:1810.02953 · doi:10.1016/j.ipl.2019.01.012

Abstract

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 automata-theoretic characterization of piecewise-testable languages. We also discuss some mild generalizations of the main result, and provide bounds on the piecewise complexity of $L \unicode{x29E2} F$.