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 metadatas

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/hal-01637057
Contributor : Michaël Thomazo <>
Submitted on : Friday, November 17, 2017 - 11:38:01 AM
Last modification on : Friday, June 14, 2019 - 1:58:54 AM
Long-term archiving on : Sunday, February 18, 2018 - 1:55:37 PM

File

Tcs_bool.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01637057, version 1

Collections

Citation

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

Share

Metrics

Record views

166

Files downloads

425