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 L a 1 a 2 … a n = Σ ⁎ a 1 Σ ⁎ a 2 Σ ⁎ ⋯ Σ ⁎ a n Σ ⁎, where a i ∈ Σ 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 L u, 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.

Authors

• Tomáš Masopust
• Michaël Thomazo

Keywords

• Automata
• Languages
• k-piecewise testability
• Complexity