On Boolean Combinations forming Piecewise Testable Languages

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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2017, 682
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01637057
Contributeur : Michaël Thomazo <>
Soumis le : vendredi 17 novembre 2017 - 11:38:01
Dernière modification le : mardi 17 avril 2018 - 11:48:04
Document(s) archivé(s) le : dimanche 18 février 2018 - 13:55:37

Fichier

Tcs_bool.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01637057, version 1

Citation

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

Partager

Métriques

Consultations de la notice

77

Téléchargements de fichiers

25