Skip to Main content Skip to Navigation
Journal articles

On Boolean Combinations forming Piecewise Testable Languages

Tomáš Masopust 1, 2 Michaël Thomazo 3
3 CEDAR - Rich Data Analytics at Cloud Scale
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : A regular language is k-piecewise testable (k-PT) if it is a Boolean combination of languages of the form L a 1 a , 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.
Complete list of metadata

Cited literature [3 references]  Display  Hide  Download
Contributor : Michaël Thomazo <>
Submitted on : Friday, November 17, 2017 - 11:38:01 AM
Last modification on : Friday, April 30, 2021 - 9:58:17 AM
Long-term archiving on: : Sunday, February 18, 2018 - 1:55:37 PM


Files produced by the author(s)


  • HAL Id : hal-01637057, version 1



Tomáš Masopust, Michaël Thomazo. On Boolean Combinations forming Piecewise Testable Languages. Theoretical Computer Science, Elsevier, 2017, 682. ⟨hal-01637057⟩



Record views


Files downloads