Deciding Piecewise Testable Separability for Regular Tree Languages - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Deciding Piecewise Testable Separability for Regular Tree Languages

Résumé

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].
Fichier principal
Vignette du fichier
lipics.pdf (601.69 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01276119 , version 1 (18-02-2016)
hal-01276119 , version 2 (19-05-2016)
hal-01276119 , version 3 (09-08-2016)
hal-01276119 , version 4 (11-10-2016)

Licence

Paternité

Identifiants

Citer

Jean Goubault-Larrecq, Sylvain Schmitz. Deciding Piecewise Testable Separability for Regular Tree Languages. ICALP 2016, Jul 2016, Rome, Italy. pp.97:1--97:15, ⟨10.4230/LIPIcs.ICALP.2016.97⟩. ⟨hal-01276119v4⟩
487 Consultations
277 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More