A regular language is  k -piecewise testable ( k   -PT) if it is a Boolean combination of languages of the form   L a 1 a 2 …a n  =Σ ⁎ a 1 Σ ⁎ a 2 Σ ⁎ ⋯Σ ⁎ a n Σ ⁎        L      a    1      a    2    …    a    n      =    Σ    ⁎      a    1      Σ    ⁎      a    2      Σ    ⁎    ⋯    Σ    ⁎      a    n      Σ    ⁎         , where   a i ∈Σ       a    i    ∈  Σ        and   0≤n≤k     0  ≤  n  ≤  k       . Given a finite automaton   A     A       , if the language   L(A)     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        ∼    k          of finite index such that   L(A)     L  (  A  )        is a finite union of   ∼ k        ∼    k         -classes. Every such class is characterized by an intersection of languages of the from   L u        L    u         , for   |u|≤k     |  u  |  ≤  k       , and their complements. To represent the   ∼ k        ∼    k         -classes, we make use of the   ∼ k        ∼    k         -canonical DFA. We identify the states of the   ∼ k        ∼    k         -canonical DFA whose union forms the language   L(A)     L  (  A  )        and use them to construct the required Boolean combination. We study the computational and descriptional complexity of related problems.
['Tomáš Masopust', 'Michaël Thomazo']
On Boolean combinations forming piecewise testable languages