Deciding Piecewise Testable Separability for Regular Tree Languages

Jean Goubault-Larrecq 1 Sylvain Schmitz 1, 2
2 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : The piecewise testable separability problem asks, given two input languages, whether there exists a piecewise testable language that contains the first input language and is disjoint from the second. We prove a general characterisation of piecewise testable separability on languages in a well-quasi-order, in terms of ideals of the ordering. This subsumes the known characterisations in the case of finite words. In the case of finite ranked trees ordered by homeomorphic embedding, we show using effective representations for tree ideals that it entails the decidability of piecewise testable separability when the input languages are regular. A final byproduct is a new proof of the decidability of whether an input regular language of ranked trees is piecewise testable, which was first shown in the ranked case for a coarser ordering by Place [CSL 2008], and in the unranked case for the homeomorphic embedding relation by Bojańczyk, Segoufin, and Straubing [Log. Meth. in Comput. Sci., 8(3:26), 2012].
Type de document :
Communication dans un congrès
Ioannis Chatzigiannakis; Michael Mitzenmacher; Yuval Rabani; Davide Sangiorgi. ICALP 2016, Jul 2016, Rome, Italy. 55, pp.97:1--97:15, 2016, Leibniz International Proceedings in Informatics. 〈10.4230/LIPIcs.ICALP.2016.97〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01276119
Contributeur : Sylvain Schmitz <>
Soumis le : mardi 11 octobre 2016 - 12:22:43
Dernière modification le : samedi 18 février 2017 - 01:14:32
Document(s) archivé(s) le : samedi 4 février 2017 - 18:57:16

Fichier

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Jean Goubault-Larrecq, Sylvain Schmitz. Deciding Piecewise Testable Separability for Regular Tree Languages. Ioannis Chatzigiannakis; Michael Mitzenmacher; Yuval Rabani; Davide Sangiorgi. ICALP 2016, Jul 2016, Rome, Italy. 55, pp.97:1--97:15, 2016, Leibniz International Proceedings in Informatics. 〈10.4230/LIPIcs.ICALP.2016.97〉. 〈hal-01276119v4〉

Partager

Métriques

Consultations de la notice

161

Téléchargements de fichiers

50