On $k$-piecewise testability (preliminary report)

Tomáš Masopust, Michaël Thomazo

For a non-negative integer $k$, a language is $k$-piecewise test\-able ($k$-PT) if it is a finite boolean combination of languages of the form ${\Sigma }^{\ast }{a}_1{\Sigma }^{\ast }\cdots {\Sigma }^{\ast }{a}_n{\Sigma }^{\ast }$ for…