On Boolean Combinations forming Piecewise Testable Languages - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2017

On Boolean Combinations forming Piecewise Testable Languages

(1, 2) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
Tcs_bool.pdf (224.18 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01637057 , version 1 (17-11-2017)

Identifiers

  • HAL Id : hal-01637057 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More