On Boolean combinations forming piecewise testable languages

A regular language is k-piecewise testable (k-PT) if it is a Boolean combination of languages of the form La1a2…an=Σ⁎a1Σ⁎a2Σ⁎⋯Σ⁎anΣ⁎, where ai∈Σ and 0≤n≤k. Given a finite automaton A, if the language L(A) is piecewise testable, we want to express it as a Boolean combination of languages of the above form. The idea is as follows. If the language is k-PT, then there exists a congruence ∼k of finite index such that L(A) is a finite union of ∼k-classes. Every such class is characterized by an intersection of languages of the from Lu, for |u|≤k, and their complements. To represent the ∼k-classes, we make use of the ∼k-canonical DFA. We identify the states of the ∼k-canonical DFA whose union forms the language L(A) and use them to construct the required Boolean combination. We study the computational and descriptional complexity of related problems.